SDGs 대응을 위한 국내 신·재생에너지 정책분석

임혜숙(Hyesook Lim),허은녕(Eunnyeong Heo) 한국신재생에너지학회 2015 한국신재생에너지학회 학술대회논문집 Vol.2015 No.11

인생 사용법

임혜숙(Hyesook LIM) 한국물리학회 2023 물리학과 첨단기술 Vol.32 No.4

삭제허용 블룸필터의 삭제확률 오류 정정

임혜숙(Hyesook Lim),이정원(Jungwon Lee),임창훈(Changhoon Lim) 대한전자공학회 2017 대한전자공학회 학술대회 Vol.2017 No.11

IP 주소 검색을 위한 가중 이진 프리픽스 트리

임창훈,임혜숙,이보미,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.

블룸 필터와 리프-푸슁을 이용한 길이에 대한 이진 검색 알고리즘

이정원(Jung Won Lee),임혜숙(Hyesook Lim) 한국통신학회 2012 한국통신학회 학술대회논문집 Vol.2012 No.6

영역 분할 사분 트라이에 블룸 필터 선 검색을 사용한 패킷 분류 알고리즘

변하영(Hayoung Byun),임혜숙(Hyesook Lim) Korean Institute of Information Scientists and Eng 2015 정보과학회논문지 Vol.42 No.8

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.

함수 블룸필터와 해싱 기반 데이터 구조의 성능비교

변하영(Hayoung Byun),임혜숙(Hyesook Lim) 대한전자공학회 2017 대한전자공학회 학술대회 Vol.2017 No.6

Key-value data structures, which return a value corresponding to an input key, are commonly used in many applications. Hashing is a representative key-value data structure. However, as the load factor of the hash table increases, the number of collisions increases, and unsaved elements cause false results. In this paper, we propose to use a functional Bloom filter instead of the hash table. While the hash table should store the signature of each input key in addition to the return value, the functional Bloom filter stores values only. Simulation results show that the functional Bloom filter is more efficient than hashing-based data structures such as hashing with a linked list, cuckoo hashing, and d-left hashing. Especially when the load factor is close to 1, while the number of incorrect results increases in hashing-based data structures because of collisions, the functional Bloom filter provides more accurate results using the same amount of memory.

패킷 분류를 위한 하드웨어 가속기 설계

이하나(Hana Lee),임혜숙(Hyesook Lim) 대한전자공학회 2017 대한전자공학회 학술대회 Vol.2017 No.6

Packet classification is a key functionality essentially required to provide the quality of service for real-time network applications such as multimedia streaming and voice-of-IP. To classify a large number of data packets at line-speed, a hardware based packet classification engine is required. In this paper, we present a hardware accelerator for packet classification. We selected a well-known packet classification algorithm, tuple pruning using Bloom filters, and implemented it using an FPGA. Implementation results show that our architecture just requires 100KB to store a packet classification table with about 1000 rules and the average number of cycles to perform the packet classification of an input is 343 cycles.

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.