본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

최장 길이 우선 검색에 기초한 프리픽스 길이에 따른 이진 IP 검색 구조
Longest First Binary Search on Prefix Length for IP Address Lookup

추하늘   (이화여자대학교 정보통신공학과UU0001056  ); 임혜숙   (이화여자대학교 정보통신공학과 SoC설계연구실UU0001056  );
  • 초록

    라우터는 입력된 패킷의 목적지 주소에 따라 IP 주소검색을 통해 패킷의 최종 목적지로 갈 수 있는 다음 흡으로 패킷을 전달하는 역할을 한다. 인터넷에 접속된 단일 호스트 네트워크 수의 증가로 인해 라우팅 테이블의 크기가 급격히 증가하고 있으며, 통신 링크의 속도 또한 기하급수적으로 빠르게 증가하고 있다. 라우터에 입력된 패킷은 선속도(wire-speed)로 처리되어야 하므로, 링크 속도의 증가는 라우터에서의 패킷 처리시간이 감소됨을 의미한다. 그러므로 차세대 라우터는 더 효율적이고 빠른 IP 주소검색 기술을 필요로 한다. 기존에 연구되어온 대부분의 검색 구조들에서는 짧은 길이의 프리픽스로부터 긴 길이의 프리픽스로 검색 영역을 확장하였다. 이 때문에 일치하는 가장 긴 프리픽스를 찾을 때까지 현재까지 일치된 가장 긴 프리픽스를 기억하면서 검색을 진행하였다. 본 논문에서는 긴 프리픽스를 먼저 검색하는 프리픽스 길이에 따른 이진 IP 주소 검색 구조를 제안한다. 제안하는 구조는 트라이의 리프에 존재하는 프리픽스들만으로 이루어진 독립적인 여러 개의 트라이를 구성하고, 길이에 따르는 이진 검색을 통해 긴 길이의 프리픽스와의 일치 여부를 먼저 확인함으로써 보다 빠른 검색속도를 제공한다. 또한, 이 구조는 기존의 프리픽스 길이에 따른 이진검색 구조가 선처리(pre-processing)가 많아 프리픽스의 부가적 추가가 힘들었던 것과는 다르게 선처리가 없이 프리픽스의 부가적 추가가 가능한 장점을 갖는다. 본 논문에서는 제안하는 구조의 성능을 실험한 후, 기존에 연구되어온 다른 IP 주소 검색 구조와 성능을 비교하였다.$ 와 혼합된 rubrene에 의한 낮은 전하주 입장벽, 높은 전류밀도에서 나타나는 발광감쇄현상의 감소, 그리고 발광층의 DLD구조에 의한 전하의 trap & confinement 에 따른 발광 exciton의 형성확률이 증가한데서 나타났다고 생각된다. 차이가 없었으나 고급알코올함량을 비교하였을 때 Sacch. cerevisiae Wine 3이 와인제조에 가장 적합한 것으로 평가되었다.장 낮은 값을 나타내었으며, 홍국의 함유량이 증가할수록 유의적으로 증가하였다. b값은 CSB가 가장 낮은 값을 나타내었으며, 홍국의 함유량이 증가할수록 유의적으로 증가하였다. 물성측정 결과 경도와 응집성은 각 시료들 간의 유의적인 차이가 나타나지 않았다. 탄력성과 부서짐성은 CSB가 가장 낮았으며, 홍국의 함유량이 증가할수록 증가하였다. 점착성은 SDB1이 가장 낮았으며, 홍국의 함유량이 증가할수록 증가하였다. 관능검사 결과 기공의 균일성은 SDB1이 가장 균일한 것으로 나타났으며, 색은 홍국의 함유량이 증가할수록 높게 나타났다. 경도, 탄력성, 단맛 및 신맛 등은 홍국 함유량이 증가할수록 증가하는 것으로 나타났다. 이취는 SDB1이 가장 적게 나는 것으로 나타났으며, 전반적인 기호도는 SDB1이 가장 높았다. 따라서 홍국을 10% 첨가한 sourdough starter를 3일 동안 발효한 후 반죽에 첨가하여 sourdough bread를 제조할 때 품질이 가장 우수한 제품을 얻을 수 있었다.생수와 여러 물질의 혼합용액의 온도가 장에 끼치는 자극에 차이가 있지 않나 추측되며 이에 관한 추후 연구가 요망된다. 총대장통과시간의


    Based on the destination IP address of incoming packets, the Internet routers determine next hops and forward packets toward final destinations through If address lookup. The bandwidth of communication links increases exponentially fast as well as the routing table size grows significant as the number of single host networks attached to the Internet increases. Since packets should be processed at wire-speed, the increased link speed reduces the processing time of a packet in routers, and hence more efficient and fast IP address lookup algorithms and architectures are required in the next generation routers. Most of the previous IP lookup schemes compare routing prefixes of shorter length first with a given input IP address. Since IP address lookup needs to find the most specific route of the given input, search continues until the longest matched prefix is found while it keeps remembering the current test matching prefix. In this paper, based on binary search on prefix length, we proposed a new IP address lookup algorithm which compares longer prefixes first. The proposed scheme is consisted of multiple tries with prefixes on leaves only. The trie composed of the longest prefixes is primarily searched whether there is a match with the given input. This processing is repeated for the trio of the next longer prefixes until there finds a match. Hence the proposed algorithm provides the fast search speed. The proposed algorithm also provides the incremental update of prefixes while the previous binary search on length scheme does not provide the incremental update because of pre-processing requirement. In this paper, we performed extensive simulations and showed the performance comparisons with related works.


  • 주제어

    IP address lookup .   Longest first search .   Prefix grouping .   Binary trie .   Binary search on length.  

  • 참고문헌 (10)

    1. M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, 'Scalable high speed IP routing lookups,' in Proc. ACM SIGCOMM Conf., Cannes, France, pp.25-35, 1997 
    2. Changhoon Yim, Bomi Lee, and Hyesook Lim, 'Efficient Binary Search for IP Address Lookup,' IEEE Communications Letters, Vol.9, No.7, pp.652-654, Jul. 2005 
    3. B. Lampson, V. Srinivasan, and G. Varghese, 'IP Lookups Using Multiway and Multicolumn Search,' IEEF/ACM Transaction on Networking, Vol.7, No.3, pp.324-334, Jun. 1999 
    4. Ju Hyoung Mun, Hyesook Lim, and Changhoon Yim, 'Binary Search on Prefix Lengths for IP Address Lookup,' IEEE Communications Letters, Vol.10, No.6, pp.492-494, June. 2006 
    5. G. Varghese, 'Network Algorithmics,' Morgan Kaufmann, 2005 
    6. M.A. Ruiz-Sanchex, E.W. Biersack, and W. Dabbous, 'Survey and Taxonomy of IP Address Lookup Algorithms,' IEEE Network, pp.8-23, March/April 2001 
    7. N. Yazdani and P. S. Min, 'Fast and Scalable Schemes for the IP Address Lookup Problem,' Proc. IEEE HPSR2000, pp.83-92, 2000 
    8. H. Jonathan Chao, 'Next Generation Routers,' Proceeding of the IEEE, vol.90, no.9, September 2002 
    9. http://www.potaroo.net 
    10. Hyesook Lim, Wonjung Kim, and Bomi Lee, 'Binary Search in a Balanced Tree for IP Address Lookup,' Proc. IEEE HPSR2005, May 2005 
  • 이 논문을 인용한 문헌 (1)

    1. Mun, Ju-Hyoung ; Lim, Hye-Sook 2007. "Packet Classification Using Two-Dimensional Binary Search on Length" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스, 32(b9): 577~588     

 저자의 다른 논문

  • 추하늘 (1)

    1. 2007 "하드웨어 기반 모바일 IPv6의 구현" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스 32 (b1): 40~52    
  • 임혜숙 (21)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기