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.

Abstract

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:4004-11
Keywords:scalable, geographic, coordinate, routing, Internet, embedding
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record