×

Greedy hot-potato routing on the two-dimensional mesh. (English) Zbl 1448.68073

Summary: We propose hot-potato (or, deflection) packet routing algorithms on the two-dimensional mesh. The algorithms are strongly greedy in the sense that they attempt to send packets in good directions whenever possible. Furthermore, the routing operations are simple and independent of the time that has elapsed. The first algorithm gives the best evacuation time known for delivering all the packets to their destinations. A batch of \(k\) packets with maximal source-to-destination distance \(d_{\max}\) is delivered in \(2(k-1)+d_{\max}\). The second algorithm improves this bound to \(k+d_{\max}\) when all packets are destined to the same node. This also implies a new bound for the multitarget case, which is the first to take into account the number of in-edges of a node. The third algorithm is designed for routing permutations with source-to-destination distance at most three, in which case the algorithm terminates in at most seven steps. We also show a lower bound of five steps for this problem.

MSC:

68M14 Distributed systems
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Acampora AS, Shah SIA: Multihop lightwave networks: a comparison of store-and-forward and hot-potato routing. IEEE INFOCOM, pp 10-19 (1991)
[2] Badr HG, Podar S: An optimal shortest-path routing policy for network computers with regular mesh-connected topologies. IEEE Trans Comput 38 (10): 1362-1371 (1989) · Zbl 1395.68023
[3] Bar-Noy A, Raghavan P, Schieber B, Tamaki H: Fast deflection routing for packets and worms. In: Proc 12th ACM Symposium on Principles of Distributed Computing, 1993 · Zbl 1373.68035
[4] Baran P: On distributed communications networks. IEEE Trans Commun 12: 1-9 (1964)
[5] Ben-Aroya I, Newman I, Schuster A: Randomized single target hot potato routing. In: Proc 3rd Israeli Symposium on the Theory of Computing and Systems, pp 20-29, January 1995 (Also Technion/LPCR TR#9406, June 1994) · Zbl 0866.68041
[6] Ben-Aroya I, Schuster A: A CLT-type lower bound for hot-potato permutation routing. TR LPCR #9405, CS Dept Technion, May 1994
[7] Ben-Aroya I, Schuster A: Greedy hot-potato routing on the two-dimensional mesh. In: 2nd European Symposium on Algorithms, Utrecht, September 1994 (Also Technion/LPCR TR #9320, November 1993)
[8] Ben-Dor A, Halevi S, Schuster A: Potential function analysis of greedy hot-potato routing. In: Proc of 13th ACM Symposium on Principles of Distributed Computing, Los Angeles, August 1994 · Zbl 1373.68036
[9] Borodin A, Hopcroft JE: Routing, merging, and sorting on parallel models of computation. J Comput Syst Sci 30: 130-145 (1985) · Zbl 0603.68065
[10] Borodin A, Rabani Y, Schieber B: Deterministic many-to-many hot potato routing, 1994
[11] Brassil JT, Cruz RL: Bounds on maximum delay in networks with deflection routing. In: 29th Annual Allerton Conference on Communication, Control and Computing, pp 571-580, 1991 (To appear IEEE TPDS)
[12] Feige U: Observations on hot potato routing. In: Proc 3rd Israeli Symposium on the Theory of Computing and Systems, pp 30-39, January 1995
[13] Feige U, Raghavan P: Exact analysis of hot-potato routing. In: Proc IEEE Symposium on Foundations of Computer Science, November 1992 · Zbl 0977.68544
[14] Greenberg AG, Goodman J: Sharp approximate models of adaptive routing in mesh networks. In: Boxma OJ, Cohen JW, Tijms HC (eds) Teletraffic Analysis and Computer Performance Evaluation. Elsevier, Amsterdam 1986, pp 255-270 (Revised 1988)
[15] Greenberg AG, Hajek B: Deflection routing in hypercube net-works. IEEE Trans Commun June 1992 · Zbl 0825.94034
[16] Hajek B: Bounds on evacuation time for deflection routing. Distrib Comput 5: 1-6 (1991) · Zbl 0723.68015
[17] Hillis WD: The Connection Machine. MIT Press 1985
[18] Kaklamanis C, Krizanc D, Rao S: Hot-potato routing on processor arrays. In: Symposium of Parallel Algorithms and Architectures, 1993
[19] Lawrie DH, Padua DA: Analysis of message switching with shuffle-exchanges in multi-processors. In: Proc Workshop on Interconnection Networks for Parallel and Distributed Computing, pp 116-123, 1980
[20] Leighton FT: Introduction to parallel algorithms and architectures. Morgan Kaufmann 1992. · Zbl 0743.68007
[21] Maxemchuk NF: Comparison of deflection and store and forward techniques in the manhattan street and shuffle exchange networks. IEEE INFOCOM, pp 800-809 (1989)
[22] Newman I, Schuster A: Hot-potato algorithms for permutation routing. TR PCL Report #9201, CS Dept Technion, November 1992
[23] Ngai JY, Seitz CL: A framework for adaptive routing in multicomputer networks. In: Proc 1st Annual Symposium on Parallel Algorithms and Architectures, pp 1-9. ACM, 1989
[24] Prager R: An algorithm for routing in hypercube networks. Master’s thesis, 1986
[25] Seitz CL, Boden N, Seizovic J, Su W: The design of the Caltech Mosaic C multicomputer. In: Proc Symposium on Integrated Systems, pp 1-22, 1993
[26] Smith B: Architecture and applications of the HEP multiprocessor computer system. In: Proc (SPIE) Real Time Signal Processing IV, pp 241-248, 1981
[27] Szymanski T: An analysis of hot potato routing in a fiber optic packet switched hypercube. In: IEEE INFOCOM, pp 918-926 (1990)
[28] Zhang Z,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.