Greedy Dynamic Routing on Arrays

Author： Kahale N.   Leighton T.  

Publisher： Academic Press

ISSN： 0196-6774

Source： Journal of Algorithms, Vol.29, Iss.2, 1998-11, pp. : 390-410

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We study the problem of dynamic routing on arrays. We prove that a large class of greedy algorithms perform very well on average. In the dynamic case, when the arrival rate of packets in an N × N array is at most 99% of network capacity, we establish an exponential bound on the tail of the delay distribution. Moreover, we show that in any window of T steps, the maximum queue-size is O(1 + log T/log N) with high probability. We extend these results to the case of bit-serial routing, and to the static case. We also calculate the exact value of the ergodic expected delay and queue-sizes under the farthest first protocol for the one-dimensional array, and for the ring when the arrivals are Poisson.

Related content

Ant Colony System for a Dynamic Vehicle Routing Problem

By Montemanni R.   Gambardella L.   Rizzoli A.   Donati A.  

Journal of Combinatorial Optimization, Vol. 10, Iss. 4, 2005-12 ,pp. : 327-343 (17)

Springer Publishing Company

Access to resources Recommend Favorite

Dynamic light trail routing in WDM optical networks

By Zhang Weiyi   Kandah Farah   Wang Chonggang   Li Hongxiang  

Photonic Network Communications, Vol. 21, Iss. 1, 2011-02 ,pp. : 78-89 (12)

Springer Publishing Company

Access to resources Recommend Favorite

Dynamic Routing and Wavelength Assignment in Optical Networks by Means of Genetic Algorithms

By Bisbal David   Miguel Ignacio de   González Fernando   Blas Juan   Aguado Juan Carlos   Fernández Patricia   Durán Javier   Durán Ramón   Lorenzo Rubén M.   Abril Evaristo J.   López Miguel  

Photonic Network Communications, Vol. 7, Iss. 1, 2004-01 ,pp. : 43-58 (16)

Springer Publishing Company

Access to resources Recommend Favorite

Dynamic Deflection Routing with Virtual Wavelength Assignment in Optical Burst-Switched Networks

By Lee SuKyoung   Kim LaeYoung   Song JooSeok   Griffith David   Sriram Kotikalapudi  

Photonic Network Communications, Vol. 9, Iss. 3, 2005-05 ,pp. : 347-356 (10)

Springer Publishing Company

Access to resources Recommend Favorite

Routing Algorithms in WDM Networks under Mixed Static and Dynamic Lambda-Traffic

By Maier Guido   Pattavina Achille   Barbato Luigi   Cecini Francesca   Martinelli Mario  

Photonic Network Communications, Vol. 8, Iss. 1, 2004-06 ,pp. : 69-87 (19)

Springer Publishing Company

Access to resources Recommend Favorite