Call Number | SEM-212 |
Collection Type | Indeks Artikel prosiding/Sem |
Title | Bounds on the Greedy Routing Algorithm for Array Networks |
Author | Michael Mitzenmacher; |
Publisher | 6th Annual ACM Symposium on Parallel Algorithms and Architecture |
Subject | |
Location |
Nomor Panggil | ID Koleksi | Status |
---|---|---|
SEM-212 | TERSEDIA |
We extend previous work on greedy routing for array net- works by providing bounds on the average delay and the average number of packets in the system. We analyze the dynamic routing problem, where packets are generated at each node according to a Poisson process. Each packet is sent to a destination chosen uniformly at random. Packets are routed greedily, first moving to the correct column and then to the correct row. Packets require unit time to travel across a directed edge between nodes; only a single packet can cross an edge at any given time, and packets waiting for an edge are buffered. Our bounds are based on comparisons with computationally more simple queueing networks, and the methods used are generally applicable to other network systems. A primary contribution of the paper is a new lower bound technique that also improves on the previous lower bounds by Stamoulis and Tsitsiklis for heavily loaded hy- percube networks. [11] On heavily loaded array networks, our lower and upper bounds differ by only a small constant factor. We further examine extensions of the problem where our methods prove useful. For example, we consider variations where edges can have different transmission rates or the des- tination distribution is non-uniform. In particular, we study to what extent optimally configured array networks outper- form the standard array network.