Research On Compact Routing Schemes Based On Scale-Free Network

Routing is the basic function of Internet. Now,the routing table size expands rapidly as the Internet size increases,which brings severe challenge to the scalability of the traditional shortest path routing.While,compact routing algorithm guarantees the routing scalability well by increasing the path length appropriately and reducing the routing table size greatly.There are universal compact routing and specialized compact routing. It can be applied to any network for universal compact routing,while specialized compact routing makes full use of the topological characteristics and gets a better performance in these network.As we all know,the Internet topology is a scale-free network with power-law,small world and other characteristics.So,the paper mainly researches the specialized compact routing based scale-free network and the main contents are shown as follows:1. Research the effect to the Thorup-Zwick (TZ) compact routing algorithm arised by the landmark coverage in scale-free network.We analysis the relationships between landmark coverage and the average stretch,the average routing table size systematically and propose a compact routing algorithm based the coverage of landmark by setting an threshold to limit the landmark coverage in scale-free network.Also,we simulate it in the snapshots of Internet AS graph. The results show that:The average stretch decreases firstly and then increases gradually,the average routing table size decreases firstly and then keep invariant; How secleting the threshold is determined by the real network.when choosing an approximate threshold, the compact routing algorithm based the coverage of landmark shows lower average stretch,lower average routing table size compared to the TZ algorithm.2. Research the name-independent compact routing algorithm based the scale-free network. Analysis the name-independent heghest-degree compact routing (NIHDLR) algorithm deeply based the TZ and Carmi-Cohen (CC) schemes,and compare the difference about the two algorithms systematically in the snapshots of the Internet AS graph spanning a10year period. The concrete results show that: Both algorithms are almost shown to offer consistently same performance,and the NIHDLR algorithm based CC scheme acieves a little smaller average stretch,but gets a littlle larger routing table size. For handshaking mechanism which can optimize the routing performance,the experimental results show that,with no handshaking mechanism, the average stretch for both algorithm is1.5with slight fluctuation and both increases slowly as the AS graph has grown;with the handshaking mechanism, the average stretch for both algorithm is1.08with slight fluctuation and both decreases slowly as the AS graph has grown.