UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

RSR: Reduced-State Routing in the Internet

Gummadi, R; Kothari, N; Kim, Y-J; Govindan, R; Karp, B; Shenker, S; (2004) RSR: Reduced-State Routing in the Internet. In: (Proceedings) Proceedings of the Third ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets 2004). ACM: San Diego, CA, USA.

Full text not available from this repository.


November 2004. In today's Internet core, routers store forwarding state proportional to the number of edge networks. As the Internet grows and core line rates increase, routers require memories that are increasingly fast and large--and are correspondingly increasingly expensive and difficult to engineer. In this paper, we present Reduced-State Routing (RSR), in which core routers require state only concerning the network topology within a two-hop radius, and thus of a size independent of the total number of Internet edge networks. RSR achieves this feat by routing geographically using two sets of node addresses: virtual coordinates, that are assigned to reflect the link costs within an autonomous system; and geographic coordinates, that correspond to nodes' physical locations. RSR routes greedily on virtual coordinates, and falls back to face routing on geographic coordinates when greedy progress is impossible on virtual coordinates. Unlike previous geographic routing schemes, RSR works on Internet-like graphs (rather than only on wireless-like graphs), and supports policy routing. By simulating RSR on real tier-1 ISP topologies, we demonstrate that RSR achieves low path stretch, comparable to that caused by policy routing in today's Internet.

Type: Proceedings paper
Title: RSR: Reduced-State Routing in the Internet
Event: Proceedings of the Third ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets 2004)
Dates: November 4004
Keywords: scalable, geographic, coordinate, routing, Internet, embedding
UCL classification: UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Engineering Science
URI: http://discovery.ucl.ac.uk/id/eprint/74382
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item