✦ LIBER ✦

Greedy Dynamic Routing on Arrays

✍ Scribed by Nabil Kahale; Tom Leighton

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 212 KB
Volume: 29
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0958

No coin nor oath required. For personal study only.

✦ Synopsis

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 q . log Trlog 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.

📜 SIMILAR VOLUMES

Optimally Scaling Permutation Routing on

Optimally Scaling Permutation Routing on Reconfigurable Linear Arrays with Optical Buses

✍ Jerry L. Trahan; Anu G. Bourgeois; Yi Pan; Ramachandran Vaidyanathan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We present an optimal and scalable permutation routing algorithm for three reconfigurable models based on linear arrays that allow pipelining of information through an optical bus. Specifically, for any P N, our algorithm routes any permutation of N elements on a P-processor model optimally in O( N

Arrays of dynamic circular loads moving

Arrays of dynamic circular loads moving on an infinite plate

✍ Lu Sun; Feiquan Luo 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 1015 KB

On the reliability evaluation of dynamic

On the reliability evaluation of dynamic networks with m-level hierarchical routing

✍ J.M. Kontoleon; D. Mandaltsis 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 336 KB

Molecular dynamics of rigid polyatomic m

Molecular dynamics of rigid polyatomic molecules on transputer arrays

✍ C.J. Craven; G.S. Pawley 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 934 KB

Molecular dynamics simulations (MDS) require massive amounts of computation, and the inherent parallelism of the method makes it highly suitable for the use of both SIMD and MIMD parallel computers. An implementation of an MDS program for transputer arrays is presented, for the simulation of rigid p

Dynamic evacuation routes for personnel

Dynamic evacuation routes for personnel on a naval ship

✍ Francisco Pérez-Villalonga; Javier Salmerón; Kevin Wood 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

Concurrent molecular dynamics simulation

Concurrent molecular dynamics simulation of spinodal phase transition on transputer arrays

✍ F. Brugè; S.L. Fornili 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 739 KB

We describe a concurrent implementation on cost-effective transputer arrays of a molecular dynamics program to efficiently simulate physical systems consisting of thousands of mobile particles with an interaction range much shorter than the system dimensions. This program, which uses a geometric dec