The Network as a Storage Device: Dynamic Routing with Bounded Buffers |
| |
Authors: | Stanislav Angelov Sanjeev Khanna Keshav Kunal |
| |
Affiliation: | (1) Department of Computer and Information Science, School of Engineering and Applied Sciences, University of Pennsylvania, Philadelphia, PA 19104, USA |
| |
Abstract: | We study dynamic routing in store-and-forward packet networks where each network link has bounded buffer capacity for receiving
incoming packets and is capable of transmitting a fixed number of packets per unit of time. At any moment in time, packets
are injected at various network nodes with each packet specifying its destination node. The goal is to maximize the throughput, defined as the number of packets delivered to their destinations.
In this paper, we make some progress on throughput maximization in various network topologies. Let n and m denote the number of nodes and links in the network, respectively. For line networks, we show that Nearest-to-Go (NTG), a
natural distributed greedy algorithm, is
-competitive, essentially matching a known
lower bound on the performance of any greedy algorithm. We also show that if we allow the online routing algorithm to make centralized decisions, there is a randomized
polylog(n)-competitive algorithm for line networks as well as for rooted tree networks, where each packet is destined for the root
of the tree. For grid graphs, we show that NTG has a competitive ratio of
while no greedy algorithm can achieve a ratio better than
. Finally, for arbitrary network topologies, we show that NTG is
-competitive, improving upon an earlier bound of O(mn).
An extended abstract appeared in the Proceedings of the 8th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, Berkeley, CA, USA, pp. 1–13, Lecture Notes in Computer Science, vol. 1741, Springer, Berlin.
S. Angelov is supported in part by NSF Career Award CCR-0093117, NSF Award ITR 0205456 and NIGMS Award 1-P20-GM-6912-1.
S. Khanna is supported in part by an NSF Career Award CCR-0093117, NSF Award CCF-0429836, and a US-Israel Binational Science
Foundation Grant.
K. Kunal is supported in part by an NSF Career Award CCR-0093117 and NSF Award CCF-0429836. |
| |
Keywords: | Network routing Troughput maximization Online algorithms |
本文献已被 SpringerLink 等数据库收录! |
|