Greedy Routing in the Internet: Is it a Solution?

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The current protocol for interdomain routing (BGP) faces several problems which may compromise its future. Being scalability and convergence the biggest cause of concern, forms of scalable routing are a relevant contribution for this discussion.
This papers presents greedy routing, a form of scalable routing with remarkable properties, e.g., the complexity in each node is O(#neighbours) as opposed to O(#nodes). The applicability of greedy routing is supported by studies concerning large-scale networks on which the traditional routing schemes do not scale. Being the Internet AS graph one of those networks [1], the application of a greedy routing scheme for interdomain routing could solve its scalability and convergence problems.
Index Terms—Routing, Internet Topology, Scale-free Net- works, Greedy Routing
Original languageUnknown
Title of host publicationCRC
Pages19 - 24
Publication statusPublished - 1 Jan 2010
EventConferência de Redes de Computadores (CRC) -
Duration: 1 Jan 2010 → …


ConferenceConferência de Redes de Computadores (CRC)
Period1/01/10 → …

Cite this