Research On ICN-oriented Scalable Name-based Routing Mechanisms

Distributing and accessing content has become the main usage of the Internet today,but the architecture of the Internet is still a host-centric end-to-end design.To solve the contradiction between the usage pattern and the architecture design,a new network architecture,Information-Centric Networking(ICN),is proposed.ICN treats contents as first class citizens and aims at providing efficient content distribution and retrieval,and it has become the hot topic of future Internet research.As the key component of ICN,namebased routing directly accesses contents via content names rather than host addresses.However,due to massive content names and location-independent naming,name-based routing faces the serious scalability issues with scale and performance.Based on the theory of scalable routing,this thesis aims to explore scalable name-based routing via geometric routing from the perspective of name resolution and studies the scalable design of name-based routing and the scalable optimization based on geometric routing.First,most name-based resolution routing schemes adopt overlay designs,but they have two problems: the underlying routing adopts the traditional IP routing that still faces scalability issues;the inconsistence between the overlay topology and the underlying topology may cause long routing paths.To solve above problems,a geometric namebased routing scheme based on overlay networks is proposed.For underlying routing,a universal geometric routing framework is proposed.All geometric routing schemes can be used for name registration and resolution.For long routing paths,a name resolution system based on a bi-level grouping strategy is proposed.Each name resolution needs at most two hops.By combining the name resolution system and the geometric routing framework,a resolution node near to the requester can always be found.This routing scheme achieves a scalable trade-off between scale and performance.Second,by analyzing the properties of the metric space of geometric routing and the key space of DHT,we solve the scalable problem of name-based routing from another perspective.A geometric name-based routing scheme based on underlay networks is proposed.Both a geometric routing scheme and a DHT-based name resolution system are implemented in the same metric space.We first propose a tree-based metric space inspired by the hierarchical division of symbol space.Then,we propose a greedy embedding scheme and a name mapping scheme in this metric space.A content name is directly mapped to a coordinate in the metric space,and then it is resolved or registered according to its coordinate via greedy forwarding.The path stretch and the size of routing table are effectively decreased.Meanwhile,to solve the unbalanced distribution of resolution entries,we propose two strategies: coding with unequal probabilities and registration forwarding.These two strategies can improve the balance of resolution load dramatically.Third,dynamical topologies may cause the scalability issues of routing updates.For geometric routing,when some nodes join or leave,numerous nodes or the whole topology should be re-embedded,which causes a great number of coordinate updates.For underlay geometric name-based routing,the coordinate update and the topology change may cause a great number of resolution updates.To solve above problems,a geometric routing scheme and an underlay geometric name-based routing scheme for dynamic topologies are proposed.Firstly,by analyzing the dynamical problem of geometric routing,we propose a dimensional expanding strategy and corresponding bit-string based prefix embedding scheme for dynamic geometric routing.This scheme can effectively avoid the node re-embedding,as well as the resolution updates caused by coordinate updates.Then,a name mapping scheme is proposed for dynamic geometric name-based routing.A trade-off between topology independence and resolution load balancing is achieved by using coarse-grained topology information,which provides a reasonable load balancing and decreases the number of resolution updates caused by the topology change.Finally,although the routing table of geometric routing only stores neighbors' coordinates,it faces the scalability challenge of long coordinates,i.e.,succinct greedy embedding.The long coordinate makes the packet header too large,which causes a waste of network resources.To solve the above problem,a practical succinct bit-string based prefix embedding scheme is proposed.Firstly,a heavy path decomposition method and a thick path decomposition method are proposed.These two methods can find some key paths in the spanning tree of the topology from bottom to top.Then,a compressed embedding scheme is proposed.The spanning tree is embedded in a top-down manner,and the node coordinates on the key path are compressed.Our scheme satisfies the greediness and succinctness.For arbitrary topologies,the upper bound of coordinate length is polylogarithmic number of bits.