Abstract
We study oblivious routing in which the packet paths are constructed independently of each other. We give a simple oblivious routing algorithm for geometric networks in which the nodes are embedded in the Euclidean plane. In our algorithm, a packet path is constructed by first choosing a random intermediate node in the space between the source and destination, and then the packet is sent to its destination through the intermediate node. We analyze the performance of the algorithm in terms of the stretch and congestion of the resulting paths. We show that the stretch is constant, and the congestion is near optimal when the network paths can be chosen to be close to the geodesic lines that connect the end points of the paths. We give applications of our general result to the mesh topology and uniformly distributed disc graphs. Previous oblivious routing algorithms with near optimal congestion use many intermediate nodes and do not control the stretch.
Original language | English (US) |
---|---|
Pages | 316-324 |
Number of pages | 9 |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
Event | Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States Duration: Jul 18 2005 → Jul 20 2005 |
Conference
Conference | Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|---|
Country/Territory | United States |
City | Las Vegas, NV |
Period | 7/18/05 → 7/20/05 |
Keywords
- Congestion
- Disc Graphs
- Geometric Networks
- Oblivious Routing
- Stretch
ASJC Scopus subject areas
- General Engineering