룰레오 알고리즘

Luleå algorithm

Degermark et al.(1997)에 의해 설계된 컴퓨터 과학의 Lulea 알고리즘은 인터넷 라우팅 테이블을 효율적으로 저장하고 검색하는 기술입니다.이 기술의 이름은 이 기술의 저자들의 본고장/대학인 룰레오 공과대학교의 이름을 따서 지어졌다.알고리즘의 이름은 이 알고리즘을 설명하는 원본 문서에는 나타나지 않지만,[1] Craig Partridge에서 발행 전에 해당 논문을 설명하는 Internet Engineering Task Force에 보낸 메시지에 사용되었습니다.

인터넷 라우팅에서 실행하는 중요한 작업은 특정 IPv4 주소(32비트 시퀀스로 표시됨)를 라우팅 정보를 사용할 수 있는 주소의 가장 긴 프레픽스에 일치시키는 것입니다.이 프리픽스 매칭 문제는 트라이에 의해 해결될 수 있지만 트라이 구조에서는 상당한 양의 공간(각 주소의 각 비트에 대한 노드)이 사용됩니다.이러한 노드들을 검색하려면 주소의 비트 수에 비례하는 길이를 가진 일련의 노드를 통과해야 합니다.Lulea 알고리즘은 trie 전체를 저장하는 것이 아니라 trie 구조의 3가지 레벨에 노드만 저장함으로써 이 프로세스를 단축합니다.

Lulea trie를 구축하기 전에 라우팅 테이블엔트리를 전처리해야 합니다.작은 프레픽스와 겹치는 큰 프레픽스는 작은 프레픽스로 반복적으로 분할해야 하며 작은 프레픽스와 겹치지 않는 분할 프레픽스만 유지됩니다.또한 프리픽스 트리가 완전해야 합니다.주소 공간 전체에 라우팅 테이블엔트리가 없는 경우 더미 엔트리를 추가하여 완성해야 합니다.더미 엔트리는 해당 범위에 루트가 존재하지 않는다는 정보만 전달합니다.이것에 의해, Lulea trie(Sundström 2007)로 간단하게 검색할 수 있습니다.

라우팅 태스크에 대한 Lulea 알고리즘의 주요 장점은 대용량 라우팅 테이블의 경우 엔트리당 평균 4~5바이트로 매우 적은 메모리를 사용한다는 것입니다.메모리 용량이 작기 때문에 데이터 구조 전체가 라우팅 프로세서의 캐시에 들어가 운용이 고속화되는 경우가 많습니다.단, 라우팅 테이블을 조금만 변경하면 데이터 구조의 대부분 또는 전부를 재구축해야 하는 경우가 있다는 단점이 있습니다.최신 가정용 컴퓨터(PC)는 알고리즘을 실행하기에 충분한 하드웨어/메모리를 갖추고 있습니다.

제1레벨

데이터 구조의 첫 번째 레벨은 다음과 같이 구성됩니다.

  • 2 = 65,536비트로 구성된16 비트 벡터. IPv4 주소의 16비트 프리픽스마다 1개의 엔트리가 있습니다.이 테이블의 비트는 해당 프리픽스에 관련된 라우팅 정보 또는 해당 프리픽스로 시작하는 긴 시퀀스를 가진 라우팅 정보가 있는 경우 또는 지정된 프리픽스가 상위 레벨의 라우팅 정보와 관련된 첫 번째 프리픽스일 경우 0으로 설정됩니다.
  • 비트 벡터의 0이 아닌 각 비트에 대한 16비트 워드 배열.각 데이텀은 대응하는 프레픽스의 제2레벨 데이터 구조 오브젝트를 가리키는 인덱스를 제공하거나 해당 프레픽스의 라우팅 정보를 직접 제공합니다.
  • 비트 벡터의 64비트의 연속된 각 후속 비트에 대해 하나씩, 그 후속 비트와 관련된 첫 번째 기준점을 가리키는 "기본 인덱스" 배열.
  • 비트 벡터에서 16비트의 연속된 각 후속에 대해 하나씩의 "코드 워드" 배열입니다.각 코드 워드는 16비트이며 10비트 "값"과 6비트 "오프셋"으로 구성됩니다.오프셋과 연관된 기본 인덱스의 합계는 지정된 16비트 후속 비트에서 0이 아닌 비트와 연관된 첫 번째 기준점에 대한 포인터를 제공합니다.10비트 값은 적절한 기준의 정확한 위치를 찾을 수 있는 "맵 테이블"에 인덱스를 제공합니다.
  • 지도 테이블.프리픽스 트리는 완전해야 하므로 비트 벡터 678에 존재할 수 있는 16비트비트 마스크 값은 한정되어 있습니다.맵 테이블 행은 이러한 678 16비트 조합에 대응하며, 컬럼에 대응하는 비트 위치에 있는 비트마스크 내의 설정 비트 수에서 1을 뺀 값을 입력합니다.따라서 비트마스크 101010101010의 열6에는 2의 값이 있습니다.맵 테이블은 라우팅 테이블의 내용에 대해 일정합니다.

데이터 구조의 첫 번째 레벨에서 특정 주소 x의 데이텀을 검색하기 위해 Luleö 알고리즘은 다음 세 가지 값을 계산합니다.

  1. x의 처음 10비트에 의해 색인화된 기본 지수 배열의 위치에서의 기본 지수
  2. x의 처음 12비트에 의해 색인화된 코드워드 배열 위치에서의 오프셋
  3. maptable[y][z]의 값. 여기서 y는 코드 워드 배열의 맵 테이블 색인이고 z는 x의 비트 13~16입니다.

이 세 값의 합계는 항목 배열에서 x에 사용할 인덱스를 제공합니다.

제2레벨과 제3레벨

데이터 구조의 두 번째 레벨과 세 번째 레벨은 서로 동일하게 구조화되어 있습니다.이들 레벨 각각에서 Lulea 알고리즘은 8비트 양(각각 주소의 비트17~24 및 25~32)에 대해 프리픽스 매칭을 실행할 필요가 있습니다.데이터 구조는 "chunks"로 구성되며, 각각은 주소 공간의 후속 부분에서 이 접두사 일치 태스크를 수행할 수 있습니다. 첫 번째 수준의 데이터 구조에서 데이터 항목은 이러한 청크를 가리킵니다.

청크와 관련된 라우팅 정보가 충분히 다를 경우 청크는 이러한 경로의 목록을 저장하고 바이너리 검색과 순차 검색의 단일 단계를 통해 이들 경로를 검색합니다.그 이외의 경우에는 제1레벨과 유사한 인덱싱 기술이 적용된다.

메모들

  1. ^ "IETFers를 위한 두 번째 유럽 여행..." 크레이그 파트리지 IETF, 1997년 5월 1일

레퍼런스

  • 를 클릭합니다Degermark, Mikael; Brodnik, Andrej; Carlsson, Svante; Pink, Stephen (1997), "Small forwarding tables for fast routing lookups", Proceedings of the ACM SIGCOMM '97 conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 3–14, doi:10.1145/263105.263133, S2CID 17232414.
  • US 6266706, Degermark, Mikael; Brodnik, Andrej & Carlsson, Svante 등, 「IP 데이터그램의 라우팅처를 결정하기 위한 라우팅 테이블내의 완전한 프리픽스 트리, 비트 벡터, 포인터를 사용한 고속 라우팅 룩업 시스템」, 2001년 발행.
  • 를 클릭합니다Medhi, Deepankar; Ramasamy, Karthikeyan (2007), Network Routing: Algorithms, Protocols, and Architectures, Elsevier, pp. 510–513, ISBN 978-0-12-088588-6.
  • 를 클릭합니다Sundström, Mikael (2007), "Time and Space Efficient Algorithms for Packet Classification and Forwarding", Doctoral Thesis, ISSN 1402-1544.