loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
34th Annual Symposium on Foundations of Computer Science (FOCS 1993)
Palo Alto, CA, USA
November 03-November 05
ISBN: 0-8186-4370-6
B. Awerbuch, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to completion and no reroutings are allowed. The "no rerouting" restriction appears in all the proposals for future high-speed networks and stems from current hardware limitations, in particular the fact that the bandwidth-delay product of the newly developed optical communication links far exceeds the buffer capacity of the network. In case the goal is to maximize the throughput, our framework yields an on-line O(log nT)-competitive strategy, where n is the number of nodes in the network and T is the maximum call duration. In other words, our strategy results in throughput that is within O(log nT) factor of the highest possible throughput achievable by an omniscient algorithm that knows all of the requests in advance. Moreover, we show that no on-line strategy can achieve a better competitive ratio. Our framework leads to competitive strategies applicable in several more general settings. Extensions include assigning each connection an associated "profit" that represents the importance of this connection, and addressing the issue of call-establishment costs.
Index Terms:
maximum call duration, throughput-competitive on-line routing, admission control, high-speed networks, bandwidth-delay product, optical communication links
Citation:
B. Awerbuch, Y. Azar, S. Plotkin, "Throughput-competitive on-line routing," focs, pp.32-40, 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), 1993
Usage of this product signifies your acceptance of the Terms of Use.