Behaviour of Maximum-Throughput Dynamic Routing in Loopy Networks⋆ Venkataramana Badarla and Douglas J. Leith Hamilton Institute, NUI Maynooth, Ireland Abstract. Maximizing network throughput via back-pressure routing is the subject of a considerable body of literature. However, the associ- ated optimal throughput guarantees come at the cost of excessively high delays. Though there exists some proposals in literature for improving the delay performance, the impact of these proposals on the delay per- formance is very little in loopy networks (i.e., networks with routing loops). In this demonstration, with series of experiments over different topologies, we show that the basic back-pressure algorithm and two of its variants for improving delay performance induce extensive routing loops with associated high packet delay even in simple network topologies. 1 Introduction Throughput maximization is an important issue in current Internet and it would continue to be an issue in future Internet. Using dynamic multi-path routing, the state of art back-pressure routing[1] offers considerable gains in throughput over conventional single-path routing algorithms. Indeed, it guarantees to achieve the network capacity and so its throughput performance cannot be bettered by any algorithm. While maximizing network throughput, back-pressure routing comes with no guarantee on network delay. Indeed certain features of the back- pressure routing algorithm suggest that long delays will be common. Firstly, back-pressure routing uses queue buildup at nodes to create a “gradient” within the network that guides routing. However, this may come at the cost of increased queuing delay. Secondly, back-pressure routing tends to explore all paths in a network, including paths with loops and “dead-end” paths that cannot lead to the desired destination. Hence, packets generally may not take the shortest path to their destination, thereby leading to additional delay. The basic back-pressure algorithm is detailed in Algorithm 1. Each forward- ing node in the network uses per flow FIFO queuing and we let qnf (t) denote the number of packets queued for flow f at node n at time t. Roughly speaking, ⋆ This material is based upon works supported by the Science Foundation Ireland under Grant No. 07/IN.1/I901. whenever it has a transmission opportunity each node n forwards a packet from the flow f ∗ to the next hop m∗ (f ∗ ) that jointly maximizes the utility f (t) = qnf (t) − qmf  Un,m (t) Rn,m where Rn,m is the mean transmit rate of the link from node n to node m. Observe Algorithm 1 Basic back-pressure algorithm “ ” 1: For each flow f and neighbor node m, node n computes utility Un,m f (t) = qnf f (t) − qm (t) Rn,m , “ ” f f m∗ (f ) = arg maxm Un,m , f ∗ = arg maxf Un,m ∗ (f ) (ties broken arbitrarily). f ∗ ∗ 2: If Un,m ∗ (f ∗ ) > 0, then node n schedules flow f ∗ f and forwards min(qn (t), Rn,m∗ (f ∗ ) ) packets ∗ ∗ to neighbor m (f ). 3: Otherwise node n takes no action at time t. that this back-pressure algorithm tends to transmit packets to the neighbor(s) with the smallest queue and highest link rate and intuitively the queue back- logs provide a “gradient” down which packets are routed. However, it commonly occurs that qnf (t) and qm f (t) differ by only a small amount. The routing “gra- dient” is then both small and rapidly fluctuating, in which case routing loops can readily be induced. Furthermore, observe that even when a neighbor has no connectivity to the destination of a flow, packets will still be forwarded to this neighbor until such time as a sufficiently large queue backlog has developed to prevent further packets stop being forwarded in that direction. However, the packets already sent in that direction will never reach the flow destination. Back-pressure With Distance Weighting: In [2] it is noted that the utility f function Un,m can by modified by summing with a finite constant without affect- ing the stability properties of the basic back-pressure routing, and in particular, that selecting a constant based on the shortest-path distances from nodes n and m to the destination of flow f is a possible choice. We therefore consider a modified utility function of the form f M f (t) = qnf (t) − qm  Un,m (t) Rn,m + f Dm where the intuition is that since the utility is inversely proportional to the dis- f tance Dm , shortest paths are favored when making forwarding decisions. The design parameter M allows the relative weight of the distance term to be ad- justed. We refer to use of this utility function as distance aided routing. 2 Implementation, Demo Setup and Snapshot of Results We implemented the back-pressure algorithms as a DynamicRouter element within the Click router framework in Linux. The Click router framework provides a modular architecture that lies within the Linux queuing layer (i.e, between the network layer and the device driver layer) and interacts with the network layer and the interface device driver via the Click elements ToHost/FromHost and ToDevice/FromDevice, respectively. 1 SRC SRC 1 50 BP 4 4 4 45 Shadow queues with ε = 3% 10 40 Min resource with M=5 Dist aided with M=500 on y2-axes 4 4 35 Shortest path routing on y2-axes 2 2 3 4 30 8 25 Delay in seconds Delay in seconds 4 20 8 4 4 4 15 10 8 3 4 4 5 6 7 5 0 1 1 1 1 1 0.5 0.4 DEST 5 0.3 8 DEST 0.2 0.1 0 0.3 0.5 0.7 0.9 1 (a) (b) Arrival rate (λ) in Mbps Fig. 1. Network Topologies. Fig. 2. Delay performance over the topol- ogy in Fig. 1(a). Table 1. Demonstration setup for the Demo Session Item Description Soekris computers Single-board computers with 433MHz CPU, (quantity 10) 256MB RAM and four 100Mbps ethernet ports N/w topologies Shown in Figure 1 Performance met- a) packet delay b) throughput c) Buffer size at in- rics termediate nodes d) reassembly buffer at receiver Traffic type a) TCP using iperf and scp b) UDP using mgen Details of the demonstration setup, such as type of computers will be used, network topologies will be considered etc are given in Table 1. Fig 2 presents snapshot of the experimental results conducted over the topology in Fig 1(a). In Fig. 2(a), which shows measured delay performance, we can observe that the delay for back-pressure algorithm and its variants (shadow-queue and min- resource algorithms [3]) is excessively high (ranges from 3s to 45s) at all offered loads. Also can be observed that the proposed distance aided approach shows the lowest delays which are at par with the shortest path routing. More detailed results over the second topology will be shown during the live demonstration session at the conference venue. References 1. A. L. Stolyar, “Maximizing Queueing Network Utility subject to Stability: Greedy- Primal Dual Algorithm,” Queueing Systems, vol. 50, no.4, pp. 401-457, 2005. 2. L. Georgiadis et al, Resource Allocation and Cross Layer Control in Wireless Net- works 2006. 3. L. Bui et al, “Novel Architectures and Algorithms for Delay Reduction in Back- pressure Scheduling and Routing”, in Proc. IEEE Infocom Mini-Conference 2009.