Maximizing network throughput via back-pressure routing is the subject of a considerable body of literature. However, the associated 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 performance 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.
Introduction 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
Unf,m(t) = qnf(t) − qmf(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 Unf,m(t) = “qnf(t) − qmf(t)” Rn,m, m∗(f) = arg maxm Unf,m, f∗ = arg maxf “Unf,m∗(f)” (ties broken arbitrarily).
∗
2: If Unf,m∗(f∗) > 0, then node n schedules flow f∗ and forwards min(qnf∗ (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
backlogs provide a “gradient” down which packets are routed. However, it commonly
occurs that qnf(t) and qmf(t) differ by only a small amount. The routing
“gradient” 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 [
Unf,m(t) = qnf(t) − qmf(t) Rn,m +
M
f Dm where the intuition is that since the utility is inversely proportional to the distance Dmf, shortest paths are favored when making forwarding decisions. The design parameter M allows the relative weight of the distance term to be adjusted. 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. 4 7 1 50 45 40 35 30 s 25 ond 20 sce 15 in 10 y leaD 50 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 inrics 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
minresource algorithms [