Author ： Hyesook Lim, Changhoon Yim, and Earl E. Swartzlander, Jr., Fellow Publisher ： IEEE TRANSACTIONS ON COMPUTERS, VOL. 59, NO. 6, JUNE 2010 Presenter.

Presentation on theme: "Author ： Hyesook Lim, Changhoon Yim, and Earl E. Swartzlander, Jr., Fellow Publisher ： IEEE TRANSACTIONS ON COMPUTERS, VOL. 59, NO. 6, JUNE 2010 Presenter."— Presentation transcript:

1 Author ： Hyesook Lim, Changhoon Yim, and Earl E. Swartzlander, Jr., Fellow Publisher ： IEEE TRANSACTIONS ON COMPUTERS, VOL. 59, NO. 6, JUNE 2010 Presenter ： Yu-To Chen Date ： 2011/09/21

2 INTRODUCTION THE PROPOSED ALGORITHM range representation of prefixes priority tries PERFORMACE ANALYSIS AND SIMULATION 2

3 In this range representation, prefixes are represented as ranges on a number line between 0 and 1 without expanding to the maximum length The priority trie is based on the trie structure, with empty internal nodes in the trie replaced by the priority prefix which is the longest among those in the subtrie rooted by the empty nodes. 3

4 4

5 5

6 6 Insert 規則 1. 先將 prefix 排序由長 到短排序 ( 等長度隨機 ) 2. 從 root 開始放, 最長 的放 root( 第 0 層 ), 之後 的由第一個位元開始 依照 0 或 1 往左右走, 遇 到空的點或是該點為 priority nood( 白點 ) 且 prefix 被自己包含即放 入, 並設為 priority nood 3. 若是層級剛好等於 prefix 長度, 則設為 ordinary nood ( 黑點 ) 並佔據那一格

7 7

8 8 Insert prefix : 1001101*

9 9 Delete node : 10011*

10 10

11 The entry width of the routing table can be designed with 39 bits (1 bit for the node identity, i.e., priority node or ordinary node, 25 bits for the prefix considering that the shortest prefix length is 8 bits, 5 bits for the prefix length, and 8 bits for routing information) plus two fields for child pointers. The number of bits for the child pointers depends on the size of routing data set. 11

12 12