Compact routing for the future internet

QA75 Electronic computers. Computer science

Strowes, Stephen D. ; Perkins, Colin

University:University of Glasgow

Department:School of Computing Science

关键词: internet routing scalability algorithms networks bgp;   

Others  :  http://theses.gla.ac.uk/3202/1/2012strowesphd.pdf

来源: University of Glasgow

【 摘 要 】

The Internet relies on its inter-domain routing system to allow datatransfer between any two endpoints regardless of where they arelocated. This routing system currently uses a shortest path routing algorithm(modified by local policy constraints) called the Border GatewayProtocol. The massive growth of the Internet has led to large routingtables that will continue to grow. This will present a seriousengineering challenge for router designers in the long-term,rendering state (routing table) growth at this pace unsustainable.There are various short-term engineering solutions that may slow thegrowth of the inter-domain routing tables, at the expense of increasingthe complexity of the network. In addition, some of these require manual configuration, orintroduce additional points of failure within the network. These solutions maygive an incremental, constant factor, improvement. However,we know from previous work that all shortest path routing algorithmsrequire forwarding state that grows linearly with the size of thenetwork in the worst case.Rather than attempt to sustain inter-domain routing through a shortest path routing algorithm, compact routing algorithms exist thatguarantee worst-case sub-linear state requirements at all nodes byallowing an upper-bound on path length relative to the theoreticalshortest path, known as path stretch. Previous work has shownthe promise of these algorithms when applied to synthetic graphswith similar properties to the known Internetgraph, but they haven't been studied in-depth on Internet topologiesderived from real data.In this dissertation, I demonstrate the consistently strongperformance of these compact routing algorithms for inter-domain routing by performinga longitudinal study of two compact routing algorithms on the InternetAutonomous System (AS) graph over time.I then show, using the k-cores graph decomposition algorithm, thatthe structurally important nodes in the AS graph are highly stableover time. This property makes these nodes suitable for use as the"landmark" nodes used by the most stable of the compact routingalgorithms evaluated, and the use of these nodes shows similar strongrouting performance.Finally, I present a decentralised compact routing algorithm fordynamic graphs, and present state requirements and message overheadson AS graphs using realistic simulation inputs.To allow the continued long-term growth of Internet routing state, analternative routing architecture may be required. The use of thecompact routing algorithms presented in this dissertation offerpromise for a scalable future Internet routing system.