http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
임규희(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.