Posts Tagged ‘routing scalability’
Recently, there have been a lot of talks around LISP – location and Identity Separation Protocol. This is a “new” technology aiming to resolve some of the Internet scalability issues and which has been implemented in IOS 15.x. In this blog publication we are going to give a general overview of LISP, pointing out benefits as well as drawbacks of the technology.
Hierarchical Routing and its Problems
Ever since ARPANet has been launched, routing in packet switched networks (PSNs) has been based on hierarchical network addressing to achieve scalability. The groundbreaking work by Kleinrock and Kamoun named “Hierarchical Routing for Large Networks, Performance Evaluation and Optimization” ([KLEIN]) clearly outlined all ideas of hierarchical routing. The main result of this work is that for a network of arbitrary connected N nodes it is possible to devise a hierarchical clustering scheme where nodes inside a single cluster only have to know routes to the nodes in the same cluster and other clusters, provided that addresses are assigned to the nodes following the hierarchical structure. The routing is assumed to be classic shortest-path selection process. Under optimal partitioning scheme, the size of routing table on every router would be of order O(log(N)).