Evaluating Compact Routing Algorithms on Real-World Networks
Graham Mooney · 2010
Compact routing has shown promise for reducing the forwarding state in Internetlike graphs, without badly impacting traffic flows. This dissertation compares two such compact routing algorithms on real Internet snapshots from router data across 12 years. The results indicate that these algorithms behave consistently over time, and exhibit extremely small forwarding tables with very low path inflation. Acknowledgements Colin Perkins and Stephen Strowes for their support, feedback, discussions, helpful pointers, field trips, anecdotes, and, of course, the initial idea for this project. The departmental support staff for their help through out the year with machine upkeep, and allowing access to copious amounts of server space, hard drives, and docks; their assistance was invaluable. The Embedded, Networked and Distributed Systems group for their help and support through out. The Algorithms group for sanity checking any graph theory and algorithms I produced. My fellow MSci and MRes students for their company, help, and generally making this year bearable. Finally, the Level 4 and 3 students for their patience while I stole their CPU cycles, RAM modules, and hard drive space. ii 5.2.3 Routing............................. 29 5.3 Summary................................ 29 6 Brady-Cowen (BC) compact routing 30