자료 주워주신 코카스 님께 감사를 드리며 ㅎㅎ
저번에 처음 딱 받아서 봤을 때는 일단 데이터 스트럭처부터 무슨 소린지 잘 이해가 안 갔다. 그림을 좀 더 잘 그려놨으면 이해하기 쉬웠을텐데, 안 되는 말로 꼬아서 써놨으니 대체 뭐가 어디에 붙어있다는건지 ㅡㅡ;; 아직 깔끔하게 설명할 정도는 아닌데 감은 대략 잡힌다.
일단 기존 연구의 한계를 먼저 보자. 하드웨어 기반 연구나 프로토콜 기반 연구 따위는 볼 필요 없고, 소프트웨어 기반 연구만 보면 된다. NetBSD 1.2에서 썼다는 페트리샤 트라이는 한 번에 한 비트씩 비교해 나가니까 백본에서 5만개쯤 경로가 있다고 하면 최악의 경우 22회 정도 메모리 접근을 해야 되고 이걸로는 기가급 속도를 낼 수가 없다. 0이나 1을 압축해서 표현하기도 하고 보통 16비트가 많으니 16비트만 해시테이블로 해서 섞어 쓰기도 하고, prefix 길이별로 최적화도 해보고, LC-trie 기법으로 트라이 레벨을 압축하기도 하고, postfix trie를 만들기도 하고, 뭐 여러가지 방법이 있었다. 자세한건 레퍼런스 부분 참조해서 쫓아가보자.
여기서는 Bitmap Trie를 쓰는데.. 기존 Trie에서 노드에 비트 하나씩 박아넣었다면, 이번엔 비트맵을 박아넣은 것이다. 원래 비트 하나씩 박아넣은 trie라면 leaf node가 2의 32승 개가 나오게 될텐데, 깊이도 깊이려니와 갯수도 무진장 많다. 이거 그대로 쓸 수 없으니까, 적당히 8비트씩 (그러니까 aaa.bbb.ccc.ddd를 . 단위로 쪼갠 것으로 생각해도 된다.) 비트맵의 Trie로 바꿔놓았다. 그러면 총 4레벨이 나오는데 최상위 레벨에 길이가 256인 비트맵에서 일단 aaa 인덱스를 바로 찾아본다. 최장 일치를 해야되니까 1로 마크되어 있어도 바로 그걸로 할 수는 없고, 하위에 더 봐야될 노드가 있는지 없는지 판정하는데 쓸 비트맵이 필요하다. 이게 논문에서 말하는 CBM이다.
그럼 라우팅 엔트리는 어떻게 찾아가냐. 1로 표시되어 있는 prefix node 하나마다 대응되는 경로가 라우팅 테이블에 한 줄씩 있을 것이다. 비트 하나씩 박아넣은 Trie에서 prefix node가 1로 표시되어 있다고 상상해봤을 때 in-order traverse로 1을 누적한 값이 인덱스로 쓰인다고 생각하면 된다. 검색할 때 이렇게 한다는 것은 아니고 개념적으로 그렇다. 이러면 경로 인덱스가 전부 유일하면서 전체 경로 갯수에 딱 맞는 라우팅 테이블 크기만 유지할 수 있다는거다.
어.. 나중에 다시 정리.. 너무 늦었다. -_-; 인덱스 결정이 아직 잘 감이 안 잡히고 확장된 검색은 안 봤다.
저번에 처음 딱 받아서 봤을 때는 일단 데이터 스트럭처부터 무슨 소린지 잘 이해가 안 갔다. 그림을 좀 더 잘 그려놨으면 이해하기 쉬웠을텐데, 안 되는 말로 꼬아서 써놨으니 대체 뭐가 어디에 붙어있다는건지 ㅡㅡ;; 아직 깔끔하게 설명할 정도는 아닌데 감은 대략 잡힌다.
일단 기존 연구의 한계를 먼저 보자. 하드웨어 기반 연구나 프로토콜 기반 연구 따위는 볼 필요 없고, 소프트웨어 기반 연구만 보면 된다. NetBSD 1.2에서 썼다는 페트리샤 트라이는 한 번에 한 비트씩 비교해 나가니까 백본에서 5만개쯤 경로가 있다고 하면 최악의 경우 22회 정도 메모리 접근을 해야 되고 이걸로는 기가급 속도를 낼 수가 없다. 0이나 1을 압축해서 표현하기도 하고 보통 16비트가 많으니 16비트만 해시테이블로 해서 섞어 쓰기도 하고, prefix 길이별로 최적화도 해보고, LC-trie 기법으로 트라이 레벨을 압축하기도 하고, postfix trie를 만들기도 하고, 뭐 여러가지 방법이 있었다. 자세한건 레퍼런스 부분 참조해서 쫓아가보자.
여기서는 Bitmap Trie를 쓰는데.. 기존 Trie에서 노드에 비트 하나씩 박아넣었다면, 이번엔 비트맵을 박아넣은 것이다. 원래 비트 하나씩 박아넣은 trie라면 leaf node가 2의 32승 개가 나오게 될텐데, 깊이도 깊이려니와 갯수도 무진장 많다. 이거 그대로 쓸 수 없으니까, 적당히 8비트씩 (그러니까 aaa.bbb.ccc.ddd를 . 단위로 쪼갠 것으로 생각해도 된다.) 비트맵의 Trie로 바꿔놓았다. 그러면 총 4레벨이 나오는데 최상위 레벨에 길이가 256인 비트맵에서 일단 aaa 인덱스를 바로 찾아본다. 최장 일치를 해야되니까 1로 마크되어 있어도 바로 그걸로 할 수는 없고, 하위에 더 봐야될 노드가 있는지 없는지 판정하는데 쓸 비트맵이 필요하다. 이게 논문에서 말하는 CBM이다.
그럼 라우팅 엔트리는 어떻게 찾아가냐. 1로 표시되어 있는 prefix node 하나마다 대응되는 경로가 라우팅 테이블에 한 줄씩 있을 것이다. 비트 하나씩 박아넣은 Trie에서 prefix node가 1로 표시되어 있다고 상상해봤을 때 in-order traverse로 1을 누적한 값이 인덱스로 쓰인다고 생각하면 된다. 검색할 때 이렇게 한다는 것은 아니고 개념적으로 그렇다. 이러면 경로 인덱스가 전부 유일하면서 전체 경로 갯수에 딱 맞는 라우팅 테이블 크기만 유지할 수 있다는거다.
어.. 나중에 다시 정리.. 너무 늦었다. -_-; 인덱스 결정이 아직 잘 감이 안 잡히고 확장된 검색은 안 봤다.
덧글