Minimal Adaptive Routing on the Mesh with Bounded Queue Size

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algorithms, we present an Ω(n²/k²) bound on the worst case time to route a static permutation of packets on ann×nmesh or torus with nodes that can hold up tok≥ 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as theh–hrouting problem. It also extends to a large class of dimension order routing algorithms, yielding an Ω(n²/k) time bound. To complement these lower bounds, we present two upper bounds. One is anO(n²/k+n) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achievesO(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds.     

Networks on which hot-potato routing does not livelock

Summary. Hot-potato routing is a form of synchronous routing which makes no use of buffers at intermediate nodes. Packets must move at every time step, until they reach their destination. If contention prevents a packet from taking its preferred outgoing edge, it is deflected on a different edge. Two simple design principles for hot potato routing algorithms are minimum advance, that advances at least one packet towards its destination from every nonempty node (and possibly deflects all other packets), and maximum advance, that advances the maximum possible number of packets. Livelock is a situation in which packets keep moving indefinitely in the network without any packet ever reaching its destination. It is known that even maximum advance algorithms might livelock on some networks. We show that minimum advance algorithms never livelock on tree networks, and that maximum advance algorithms never livelock on triangulated networks. Received: March 1999 / Accepted: August 1999     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).     

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

Abstract. The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to schedule the maximum number of packets subject to deadline constraints. This problem is studied in [1], where it is shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms are also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and two-dimensional meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are scheduled subject to their timing constraints. For the bufferless case, we provide constant factor approximation algorithms for the time-constrained scheduling problem with weighted packets on trees and meshes. We also provide logarithmic approximations for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if k packets are required to follow prescribed paths in an arbitrary graph, then unless NP = ZPP, there is no polynomial-time k ^1-ε -approximation, for any ε > 0 , to the optimal set of packets that can be scheduled.     

无线 Ad hoc 网络和传感网络中基于位置的、可靠的无信标传输路由方法

Existing position-based routing algorithms, where packets are forwarded in the geographic direction of the destination, normally require that the forwarding node should know the positions of all neighbors in its transmission range. This information on direct neighbors is gained by observing beacon messages that each node sends out periodically. Several beaconless greedy routing schemes have been proposed recently. However, none of the existing beaconless schemes guarantee the delivery of packets. Moreover, they incur communication overhead by sending excessive control messages or by broadcasting data packets. In this paper, we describe how existing localized position based routing schemes that guarantee delivery can be made beaconless, while preserving the same routes. In our guaranteed delivery beaconless routing scheme, the next hop is selected through the use of control RTS/CTS messages and biased timeouts. In greedy mode, the neighbor closest to destination responds first. In recovery mode, nodes closer to the source will select shorter timeouts, so that other neighbors, overhearing CTS packets, can eliminate their own CTS packets if they realize that their link to the source is not part of Gabriel graph. Nodes also cancel their packets after receiving data message sent by source to the selected neighbor. We analyze the behavior of our scheme on our simulation environment assuming ideal MAC, following GOAFR+ and GFG routing schemes. Our results demonstrate low communication overhead in addition to guaranteed delivery.     

Routing on Meshes with Buses

We consider the problem of routing packets on an MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination of exactly k packets) on a d-dimensional mesh with buses, which we call the (k,d)-routing problem. We give a general class of ``hard' permutations which we use to prove lower bounds for the (k,d)-routing problem, for all k,d≥ 1. For the (1,1)- and (1,2)-routing problems the worst-case permutations from this class are identical to ones published by other authors, as are the resulting lower bounds. However, we further show that the (1,d)-routing problem requires 0.72 ... n steps for d=3, 0.76 ... n steps for d=4, and slightly more than steps for all d≥ 5. We also obtain new lower bounds for the (k,d)-routing problem for k,d > 1, which improve on the bisection lower bound in some cases. These lower bounds hold for off-line routing as well. We develop efficient algorithms for the (k,1)-routing problem and for the problem of routing k-randomizations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and use them in a general (k,d)-routing algorithm which improves considerably on previous results. In particular, the routing time for the (1,d)-routing problem is bounded by steps with high probability (whp), whenever for some constant ε > 0, and the routing time for the (k,d)-routing problem is steps whp whenever for some constant ε > 0 and k≥ 3.6 ... d, matching the bisection lower bound. We then present a simple algorithm for the (2,2)-routing problem running in 1.39 ... n+o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensional meshes with buses, the (1,2)-routing problem, we give a more sophisticated algorithm that runs in 0.78 ... n+o(n) steps whp. Received May 18, 1994; revised June 23, 1995.     

Concurrent face traversal for efficient geometric routing

We present a concurrent face routing CFR algorithm. We formally prove that the worst case latency of our algorithm is asymptotically optimal. Our simulation results demonstrate that, on average, the path stretch, i.e., the speed of message delivery, achieved by CFR is significantly better than by other known geometric routing algorithms. In fact, it approaches the shortest possible path. CFR maintains its advantage over the other algorithms in pure form as well as in combination with greedy routing. CFR displays this performance superiority both on planar and non-planar graphs.     

Deterministic many-to-many hot potato routing

We consider algorithms for many-to-many hot potato routing. In hot potato (deflection) routing, a packet cannot be buffered, and is therefore always moving until it reaches its destination. We give optimal and nearly optimal deterministic algorithms for many-to-many packet routing in commonly occurring networks such as the hypercube, meshes, and tori of various dimensions and sizes, trees, and hypercubic networks such as the butterfly. All these algorithms are analyzed using a charging scheme that may be applicable to other algorithms as well. Moreover, all bounds hold in a dynamic setting in which packets can be injected at arbitrary times     

Potential Function Analysis of Greedy Hot-Potato Routing

We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise tech- niques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where: • The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival. • Packets always advance toward their destination if they can. Namely, a packet must leave its current intermediate node via a link which takes it closer to its destination, unless all these links are taken by other packets. Moreover, in this case all these other packets must advance toward their destinations. We use potential function analysis to obtain an upper bound of O(n k ^1/2 ) on the running time of a wide class of algorithms in the two-dimensional n × n mesh, for routing problems with a total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d) n ^d-1 k ^1/d ) on the running time of a wide class of algorithms in the d -dimensional n ^d mesh, for routing problems with a total of k packets. Received December 1993, and in final form March 1997.     

Compact Routing on Chordal Rings of Degree 4

A chordal ring G(n;c) of degree 4 is a ring of n nodes with chords connecting each vertex i to the vertex (i + c) mod n . In this paper we investigate compact routing schemes on such networks. We show an optimal boolean routing scheme for any such network that requires O( log n) bits of storage at each node, and O(1) time to compute a shortest path to any destination. This improves on the results of [16] which gives a linear time algorithm for such networks and [6] where efficient routing schemes for certain fixed values of c were developed. Further, we show several bounds on interval routing schemes for such networks. We show that while every chordal ring has an optimal interval routing scheme with at most intervals on any edge, there exist chordal rings for which any optimal interval routing scheme that labels the vertices around the ring in the graph requires intervals on some edges. Additionally, there are chordal rings which admit no optimal one-interval routing schemes, regardless of the vertex labeling. We also consider interval routing schemes under relaxed requirements for the lengths of paths. Received September 5, 1997; revised December 1, 1997.     

Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

A generalized greedy routing algorithm for 2-connected graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications.The essence of the geometric routing is the following: When an origin vertex u wants to send a message to a destination vertex w, it forwards the message to a neighbor t, solely based on the location information of u,w and all neighbors of u. In the greedy routing scheme, the decision is based on decreasing distance. For this idea to work, however, the decision needs not be based on decreasing distance. As long as the decision is made locally, this scheme will work fine.In this paper, we introduce a version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance, a generalized greedy routing algorithm uses other criteria to determine routing paths, solely based on local information. We present simple generalized greedy routing algorithms based on st-coordinates (consisting of two integers between 0 and n−1), which are derived from an st-orientation of a 2-connected plane graph. We also generalize this result to arbitrary trees. Both algorithms are natural and simple to be implemented.     

路标迭代提取和剔除的自适应空洞处理算法

针对无线传感器网络贪婪地理路由协议中的路由空洞问题,提出一种高效的基于路标迭代提取和剔除的自适应空洞处理算法.该算法中,当探测包贪婪转发遇到空洞时,在网络拓扑局部平面化的基础上,以左(右)手法则提取空洞边界并沿其逆(顺)时针周边模式双向转发,同时,分布式地进行路标的迭代提取和剔除,直到获取的路标使得后续的数据包依次以它们为中间目标节点进行传输而不再遇到空洞为止.仿真结果表明,该协议能够以较小的控制开销代价获得次最优的传输路径,极大地提高了路由协议的性能,可以应用于无法消除路由空洞的大规模无线传感器网络贪婪地理路由协议.     

Greedy hot-potato routing on the two-dimensional mesh

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 ofk packets with maximal source-to-destination distanced _max is delivered in 2(k-1)+d _max. The second algorithm improves this bound tok+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. Ishai Ben-Aroya received the B.A. and M.Sc. in computer science from the Technion (Israel Institute of Technology). He is currently working with Microsoft Israel R&D group. His main interests include Routing Algorithms, Cryptography and Computer Security. Tamar Eilam received the B.A. degree in Computer Science from the Technion IIL in 1995, and is currently studying towards her M.A. degree. Assaf Schuster received his B.A., M.A. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem (the last one in 1991). He is currently a lecturer at the Technion IIL. His main interests include Networks and Routing Algorithms, Parallel and Distributed Computation, Optical Computation and Communication, Dynamically Reconfiguring Networks, and Greedy Hot Potato Routing.This work was supported in part by the French-Israeli grant for cooperation in Computer Science, and by a grant from the Israeli Ministry of Science. An extended abstract appeared in proc. 2nd European Symposium on Algorithms, September 1994     

Direct routing: Algorithms and complexity

Direct routing is the special case ofbufferless routing whereN packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct routing:

Routing Permutations on Graphs via Factors

We deal with the permutation routing problem on graphs modeling interconnection networks. In our model, calledrouting via factors, at each routing step, the communication pattern is a directed 1-factor in a symmetric digraph. This adds a new feature, that of continuous packet movement, to preciously studied routing types, where the routing of a permutation is reduced to a sequence of permutations from a given class. We especially focus on bipartite graphs and we give sufficient conditions for a graph to be rearrangeable in our model. We propose a general technic for routing via factors that we apply to the 2D mesh and the hypercube.     

Hot Potato Worm Routing via Store-and-Forward Packet Routing

The theory of worm routing (rather than packet routing) has recently attracted increased attention as an abstraction of the underlying communication mechanisms in many parallel machines. Routing the worms in the hot potato style is a desired form of communication in high-speed optical interconnection networks. In this work, we develop a simple method for the design of parallel hot potato worm routing algorithms. Our basic approach is to simulate known packet routing algorithms, so that in each step worms are moved around instead of packets. By plugging in known results for packet routing, we get the fastest (so far) deterministic batch worm routing algorithms. Although the results are given for permutation routing on the mesh and the hypercube, the general method can be applied to many other networks and to more general communication patterns as well. Moreover, once better routing algorithms are found for the underlying network, the worm routing algorithms improve as well.     

高动态航空自组网中考虑优先级的逐跳路由协议

针对航空自组网频繁的拓扑变化、网络断开的问题,提出一种考虑优先级的逐跳路由（priority concern hop-by-hop routing,PCHHR）协议。PCHHR依据运动方向优先、距离次之的原则选择下一跳路由节点,优先选择向目的节点运动的邻居作为下一跳节点,次优选择距离目的节点最近的邻居作为下一跳节点;区分数据报文的时延需求,优先转发时延约束小的数据。仿真结果表明,PCHHR在较低的控制开销和端到端时延下,总体数据分组投递率高于航空路由协议（aeronautical routing protocol,AeroRP）、贪婪转发路由和传统的端到端路由协议,提高了高实时性数据分组的投递率。     

An Energy-Aware Geographic Routing Protocol for Mobile Ad Hoc Networks

Mobile ad hoc networks (MANET) are characterized by multi-hop wireless links and resource constrained nodes. To improve network lifetime, energy balance is an important concern in such networks. Geographic routing has been widely regarded as efficient and scalable. However, it cannot guarantee packet delivery in some cases, such as faulty location services. Moreover, greedy forwarding always takes the shortest local path so that it has a tendency of depleting the energy of nodes on the shortest path. The matter gets even worse when the nodes on the boundaries of routing holes suffer from excessive energy consumption, since geographic routing tends to deliver data packets along the boundaries by perimeter routing. In this paper, we present an Energy-Aware Geographic Routing (EGR) protocol for MANET that combines local position information and residual energy levels to make routing decisions. In addition, we use the prediction of the range of a destination''s movement to improve the delivery ratio. The simulation shows that EGR exhibits a noticeably longer network lifetime and a higher delivery rate than some non-energy-aware geographic routing algorithms, such as GPSR, while not compromising too much on end-to-end delivery delay.     

Some permutation routing algorithms for low-dimensional hypercubes

Oblivious permutation routing in binary d-cubes has been well studied in the literature. In a permutation routing, each node initially contains a packet with a destination such that all the 2^d destinations are distinct. Kaklamanis et al. (Math. Syst. Theory 24 (1991) 223–232) used the decomposability of hypercubes into Hamiltonian circuits to give an asymptotically optimal routing algorithm. The notion of “destination graph” was first introduced by Borodin and Hopcroft to derive lower bounds on routing algorithms. This idea was recently used by Grammatikakis et al. (Proceedings of the Advancement in Parallel Computing, Elsevier, Amsterdam, 1993) to construct many–one routing algorithms for the binary 2-cube and 3-cube. In the present paper, further theoretical development is made along this line. It is then applied to obtain algorithms for binary d-cubes with d up to 12, which compare favorably with the above-mentioned “Hamiltonian circuit” algorithm. Some results on t-nary cubes with t3 are also obtained.