On the Hot-Potato Permutation Routing Algorithm of

Borodin, Rabani and Schieber

Richard Thomas Plunkett Antonis Symvonis

Basser Department of Computer Science

University of Sydney

Sydney, N.S.W. 2006

Australia

frichard,[email protected]

Technical Report 500
August 1995
Updated: November 1995

Abstract

Borodin, Rabani and Schieber [3] presented an O(npn)-step algorithm for hot-potato routing of permutations on n ? n meshes. They conjectured that their algorithm completes the routing of a permutation in O(n) steps. In this paper, we present worst-case partial permutations which force their algorithm to use ?(npn) routing steps.

Keywords Packet routing, hot-potato routing, permutation routing, routing algorithm.

1 Introduction

Message routing has been abstracted in several ways. In packet routing it is assumed that a message can be transmitted between two adjacent processors (vertices of the undirected graph) in a single step as a packet. We concentrate on the routing model known as deflection (or hot-potato) routing in which packets continuously move between processors from the time they are injected into the network until the time they are consumed at their destination.

The advantage of deflection routing is obvious. No queueing area is required at the processors. However, the fact that packets always move implies that at any step each processor must transmit the packets it received during the previous step (unless they were destined for it). As a result, several packets might be derouted away from their destination. This makes the analysis extremely difficult.

The work of Feige and Raghavan [4] which provided analysis for deflection routing algorithms for the torus and the hypercube, renewed the interest in deflection routing. As a result, several papers ap-

Proceedings of CATS'96 (Computing: The Australasian Theory Symposium), Melbourne, Australia, January 29{January 30 1996.

peared with deflection routing as their main theme. Kaklamanis, Krizanc and Rao [5] considered batch and permutation routing on torii and meshes. BarNoy et al [1] gave a nearly optimal deterministic algorithm for routing permutations on the n?n mesh and torus. Based on sorting algorithms, Newman and Schuster [7] derived asymptotically optimal algorithms for routing permutations on the mesh and the torus networks and a near optimal algorithm for the hypercube. Kaufmann et al [6] fine tuned their results for the case of meshes and managed to reduce the constant hidden in the asymptotic analysis.

Ben-Aroya and Schuster [2] considered the general situation where a mesh is loaded with k packets that have to be routed to their destinations in a hot-potato manner. Through clever analysis of their greedy algorithm they showed that routing will terminate within dist + 2(k ? 1) steps where dist is the initial maximum distance a packet has to travel. Independently, Borodin et al [3] formalized the notion of the deflection sequence, a nice way to charge each deflection of an individual packet to distinct packets travelling on the network. By using their method, they show that routing k packets in a hot-potato manner can be completed within dist + 2(k ? 1) steps for trees, butterflies and multidimensional meshes.

For permutation routing on two-dimensional meshes, the algorithm of Borodin et al [3] completes the routing in O(npn) steps. It was conjectured that the actual performance of the algorithm is O(n). In this paper, we disprove the conjecture of Borodin et al [3] regarding the performance of their algorithm for permutation routing on twodimensional meshes by demonstrating worst case input permutations that require ?(npn) for their routing. The paper is organised as follows: In the next section, we describe the algorithm of Bar-Noy