http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 임혜숙 ( Hyesook Lim ) (검색결과 59 건)
- 무료
- 기관 내 무료
- 유료
-
-
-
-
임창훈,임혜숙,이보미,Yim Changhoon,Lim Hyesook,Lee Bomi 한국통신학회 2004 韓國通信學會論文誌 Vol.29 No.11B
IP 주소 검색은 인터넷 라우터의 필수적인 기능의 하나로서, 라우터 전체의 성능을 결정하는 중요한 요소이다. 소프트웨어에 기반한 IP 주소 검색 방식의 성능 평가 기준 중 가장 중요한 것은 라우터의 처리 속도를 보장해 주는 의미를 갖는 최대 메모리 접근 횟수이다. 이진 프리픽스 트리 방식(BPT)은 최대 메모리 접근 횟수에 있어서 기존의 다른 소프트웨어에 기반한 방식 중 우수한 방식이지만, 트리의 구조가 불균형적이 되는 단점이 있다. 본 논문에서는 기존의 BPT 방식의 트리 생성 과정에 가중치 개념을 추가하여, 완전 균형 트리에 매우 근접하는 트리를 생성하는 가중 이진 프리픽스 트리 (WBPT) 방식을 제안한다. 제안하는 WBPT 방식은 기존의 소프트웨어에 근거한 방식들에 비교하여 최대 메모리 접근 횟수에 있어서 가장 적은 성능을 보인다. 또한 3만 개 정도의 프리픽스에 대해서 L2 캐쉬에 저장이 가능한 정도의 작은 메모리 크기를 요구하구 프리픽스의 추가, 삭제가 용이하므로 실제적인 라우터의 IP 검색을 위하여 사용될 수 있는 방식이다. IP address lookup is one of the essential functions on internet routers, and it determines overall router performance. The most important evaluation factor for software-based IP address lookup is the number of the worst case memory accesses. Binary prefix tree (BPT) scheme gives small number of worst case memory accesses among previous software-based schemes. However the tree structure of BPT is normally unbalanced. In this paper, we propose weighted binary prefix tree (WBP) scheme which generates nearly balanced tree, through combining the concept of weight to the BPT generation process. The proposed WBPT gives very small number of worst case memory accesses compared to the previous software-based schemes. Moreover the WBPT requires comparably small size of memory which can be fit within L2 cache for about 30,000 prefixes, and it is rather simple for prefix addition and deletion. Hence the proposed WBPT can be used for software-based If address lookup in practical routers.
-
임규희(Kyuhee Lim),이나라(Nara Lee),임혜숙(Hyesook Lim) 한국정보과학회 2012 정보과학회논문지 : 정보통신 Vol.39 No.1
인터넷 라우터에서 패킷 분류는 IP 주소 검색과 달리 입력된 패킷 헤더의 여러 필드와 일치하는 최우선 룰을 찾아내야 하는 어려움이 있다. 이 논문에서는 패킷 분류 알고리즘 중 튜플 프루닝 알고리즘에 적용되어 검색 성능을 향상시킬 수 있는 튜플 블룸 필터를 사용한 튜플 프루닝 구조를 제안한다. 튜플 프루닝 알고리즘은 검색하여야 할 튜플의 수를 줄이기 위하여, 필드 별 검색을 통하여 해당 인풋 헤더와 일치하는 길이를 찾은 후, 일치하는 길이들의 조합에 의해 생성된 튜플들로 검색 공간을 제한하는 알고리즘이다. 이러한 방식의 튜플 프루닝은 검색하여야 할 튜플의 수를 줄임에 있어 매우 효율적인 방법이나, 길이의 조합만을 사용하고 값의 정보를 사용하지 않는 단점이 있다. 본 논문에서 제안하는 구조는 기존의 튜플 프루닝 알고리즘에 튜플 블룸 필터를 추가한 구조로서, 튜플 블룸 필터를 통해 일치하는 값의 조합에 의하여 다시 한번 필터링 하기 때문에, 검색하여야 할 튜플의 수를 더욱 줄인다. 패킷 분류의 성능평가를 위해 많이 사용되는 각 6000개의 룰을 갖는 ACL, FW, IPC 룰 데이터 베이스를 사용하여 성능을 실험한 결과, 약 2~4Kbyte의 메모리를 갖는 튜플 블룸 필터를 추가하여 평균 30%의 외부 메모리 접근 횟수가 감소되어 검색 성능이 향상됨을 확인하였다. Packet classification in Internet routers is a more challenging task than IP address lookup since it has to find out the best matching rule that matches the multiple header fields of incoming packets. This paper proposes a refined tuple pruning architecture using a tuple Bloom filter, which improves the search performance of tuple pruning algorithm. To reduce the number of tuples included in the search space of a given input, the existing tuple pruning algorithm firstly finds out matching lengths in each field by performing individual field lookup and determines tuples of the search space by combining the results. The tuple pruning approach is efficient in reducing the search space, but it has an issue, in that it only uses the information of matching lengths and does not use the information of matching values. By inserting a tuple Bloom filter to the tuple pruning algorithm, the proposed architecture of this paper uses the combination of matching values in filtering out unnecessary tuples from the search space so that the number of tuples in the search space is more reduced. Simulation results using ACL, FW, and IP rule sets with about 6000 rules show that the refined tuple pruning architecture reduces about 30% of external memory accesses in average using a tuple Bloom filter with 2~4 Kbytes.
-
-
IP Address Lookup Algorithm Using a Vectored Bloom Filter
Hayoung Byun(변하영),Hyesook Lim(임혜숙) 대한전기학회 2016 전기학회논문지 Vol.65 No.12
A Bloom filter is a space-efficient data structure popularly applied in many network algorithms. This paper proposes a vectored Bloom filter to provide a high-speed Internet protocol (IP) address lookup. While each hash index for a Bloom filter indicates one bit, which is used to identify the membership of the input, each index of the proposed vectored Bloom filter indicates a vector which is used to represent the membership and the output port for the input. Hence the proposed Bloom filter can complete the IP address lookup without accessing an off-chip hash table for most cases. Simulation results show that with a reasonable sized Bloom filter that can be stored using an on-chip memory, an IP address lookup can be performed with less than 0.0003 off-chip accesses on average in our proposed architecture.
-
-
-
영역 분할 사분 트라이에 블룸 필터 선 검색을 사용한 패킷 분류 알고리즘
변하영(Hayoung Byun),임혜숙(Hyesook Lim) 한국정보과학회 2015 정보과학회논문지 Vol.42 No.8
영역분할을 이용한 패킷분류의 대표적인 알고리즘인 영역분할 사분 트라이(area-based quadtrie, AQT)는 검색 시 룰 노드를 만나도 더 높은 우선순위의 룰이 있을 수 있어 트라이의 끝까지 검색해야 하는 문제가 있다. 리프-푸싱(leaf-pushing) AQT는 모든 검색 경로에 룰 노드를 하나만 위치시켜 검색 성능을 높인 알고리즘이다. 본 논문에서는 리프-푸싱 AQT를 해시 테이블 기반으로 구현하고 블룸필터를 적용해 검색 성능을 더욱 향상시킨 알고리즘을 제안한다. 제안하는 알고리즘에서는 온-칩(on-chip) 블룸필터를 연쇄적으로 우선 검색하여 룰 노드의 레벨을 알아낸 후, 오프-칩(off-chip)에 저장된 룰 노드에 접근한다. 실험을 통해 적절한 크기의 블룸필터를 사용하여 평균 한 번의 해시테이블 접근만으로 패킷분류를 수행할 수 있음을 보았으며, 메모리 사용량 및 검색 성능에 있어 기존의 알고리즘과 제안하는 구조의 성능을 비교하였다. As a representative area-decomposed algorithm, an area-based quad-trie (AQT) has an issue of search performance. The search procedure must continue to follow the path to its end, due to the possibility of the higher priority-matching rule, even though a matching rule is encountered in a node. A leaf-pushing AQT improves the search performance of the AQT by making a single rule node exist in each search path. This paper proposes a new algorithm to further improve the search performance of the leaf-pushing AQT. The proposed algorithm implements a leaf-pushing AQT using a hash table and an on-chip Bloom filter. In the proposed algorithm, by sequentially querying the Bloom filter, the level of the rule node in the leaf-pushing AQT is identified first. After this procedure, the rule database, which is usually stored in an off-chip memory, is accessed. Simulation results show that packet classification can be performed through a single hash table access using a reasonable sized Bloom filter. The proposed algorithm is compared with existing algorithms in terms of the memory requirement and the search performance.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
