Greedy Routing in the Internet: Is it a Solution?

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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