FAST, MINIMAL, AND OBLIVIOUS ROUTING ALGORITHMS ON THE MESH WITH BOUNDED QUEUES
Ami Litman, Shiri Moran-Schein · Journal of Interconnection Networks · 2001
This paper studies fast, deterministic permutation routing algorithms with bounded queues on the n×n mesh. Our main result is an O(n)-step, strongly-dimensional (and thus also source-oblivious and minimal) permutation routing algorithm. This algorithm works under a relaxed model in which nodes can freely send data to their neighbors. In a more prevalent model, the standard model, data may be sent only when accompanied by a packet. Under this model we present the following two algorithms: an O(n log n)-step strongly-dimensional algorithm and an O(n)-step oblivious and weakly-dimensional (and thus also minimal) algorithm. As said, all these algorithms store only O(1) packets in a node. Moreover, they use only O( log n) state bits in a node and transfer only O( log n) data bits on an edge in a step. All our routing algorithms are based on the following new technique of open-loop flow control. An algorithm is composed of two stages: setup and transportation. The setup stage computes certain values and stores them in the network. In particular, it computes a rational number α(e) for certain critical edges e. The transportation stage moves the packets to their destinations. It uses the computed values to slow the packets so that the traffic on each critical edge e is bounded byα(e); that is, at most ⌈α(e) · l⌉ packets traverse e during any l consecutive steps. This bounded on the burstiness of the traffic enables the algorithm to avoid hot spots and maintain bounded queues. The algorithm achieves this by an open-loop control; that is, during this stage no information is transferred in a direction opposite to that of the packets. An additional novelty of our algorithms is the application of a dynamic routing problem to solve a static one. The dynamic problem in question seems easy, as its networks is just a linear array. We show, however, that this problem is beyond the scope of the Adversarial Queuing Theory.