On network coding and routing in dynamic wireless multicast networks
Tracey Ho, Jia-Qi Jin
California Institute of Technology Pasadena, CA Email: {tho, jin}@caltech.edu
H
arish Viswanathan
Lucent Technologies, Bell Labs Murray Hill, NJ Email: harishv@lucent.com
Abstract— We compare multicast network coding and routing for a time-varying wireless network model with interferencedetermined link capacities. We use dynamic back pressure algorithms that are optimal for intra-session network coding and routing respectively. Our results suggest that under such conditions, the gap in multicast capacity between network coding and routing can decrease relative to a collision-based wireless model with ?xed link capacities.
I. I NTRODUCTION In this paper we consider dynamic multicasting in timevarying wireless networks. We investigate the capacity bene?t of network coding relative to multicast routing, i.e. forwarding and replication over one or more multicast trees. Network coding has been shown to be necessary for achieving multicast capacity in some wired networks such as the multicast network of Figure 1 [1]; many known examples of such networks are extensions or generalizations of this basic example. Reference [16] gives an analogous example, shown in Figure 2, of a static wireless network with ?xed link rates and a half-duplex constraint, i.e. each node can either send or receive a single transmission at any one time. In this example, the optimal network coding solution, shown in Figure 3(a), achieves 4/3 times the multicast throughput of the optimal routing solution, shown in Figure 3(c). As we consider more realistic wireless network models, we move progressively further from the static wireless model that is closest to the original wired model. For instance, if we consider the effect of interference on link capacities, it is not clear to what extent the network coding and routing solutions of Figure 3 are affected, since their transmit scenarios involve different sets of interfering links. Also, channel conditions often vary and traf?c is usually bursty because either the sources generate traf?c in bursts or the network nodes employ queuing and scheduling across multiple sessions. In such scenarios, optimal scheduling, routing and coding should vary dynamically depending on the current state of the network – channel conditions and buffer occupancy. Routing, scheduling, rate, and power control in networks with bursty traf?c has recently received signi?cant attention in the context of wireless networks [2], [10], [12], [13], [14], [15], [19], [21], [22]. Much of the recent work in this area
1 This work was supported in part by Caltech’s Lee Center for Advanced Networking.
Fig. 1. Wired multicast network example, with a single node A multicasting information to two sink nodes E and F.
builds on the ideas of [3], [18] that describe algorithms for routing and scheduling ?ows using queue sizes, or differences in queue size between the queues at the source and the destination of a link, as the metric to select between different ?ows. Such an approach is usually said to be back-pressure based since heavily loaded nodes downstream slow down the ?ow coming down from nodes upstream. Such approaches are optimal in the sense of allowing transmission at the maximum possible arrival rates into the network for which the queues at the various network nodes can be stabilized. While the back-pressure approach has mostly been applied in the context of unicast transmissions, it has also been extended to the case of multicast transmissions [2], [17]. However, in the multicast case without network coding the algorithms are signi?cantly more complex, even for wired networks. We have recently extended the above back-pressure based dynamic routing and scheduling algorithms to include network coding and correlated sources [8]. Random network coding [6], introduced for the ?ow model, extends naturally to a timevarying network with bursty traf?c and provides a distributed implementation. For networks with one or more multicast
difference in length of corresponding virtual queues, summed over each session’s queues. For correlated sources, the sinks locally determine and control transmission rates across the sources. This gives a completely distributed algorithm for wired networks; in the wireless case, scheduling and power control among interfering transmitters is done centrally. This paper is organized as follows. We present the system and network coding model in Section II. Optimal back pressure algorithms for multicast with and without network coding are described in Section III. In Section IV, we compare the two algorithms on the example of Figure 2. We conclude with a summary in Section V.
Fig. 2. Wireless multicast network example, with a single node A multicasting information to two sink nodes E and F. The coordinates represent physical distances which are varied in our simulation experiments.
II. M ODEL A. Wireless network model We use a model similar to that in [15]. We consider a network composed of a set N of N = |N | nodes with communication links between them that are ?xed or timevarying according to some speci?ed ergodic processes, and transmission of a set of multicast sessions C through the network. Each session c ∈ C is associated with a set Sc ? N of sources, and an exogenous process of data arrivals at each of these sources which must be transmitted over the network to each of a set Tc ? N of sinks. Transmissions are assumed to occur in slotted time, with time slots of length T . Decisions on routing, scheduling, etc. are made at most once a slot. For simplicity, we assume ?xed length packets and link transmission rates that are restricted to integer multiples of the packet-length/time-slot quotient. That is, an integer number of packets can be transmitted in each slot. The link transmission rate ?ij from node i to node j , with other nodes n ∈ N transmitting independent information simultaneously, is given by the Shannon formula [5]
Fig. 3. Examples of typical schedules for coding (a)-(b) and routing (c)-(d). Each box shows a set of wireless links that can be simultaneously activated, termed a transmit scenario (TS). (a) and (c) give the optimal coding and routing schedules respectively for a static wireless model with ?xed link rates and a half-duplex constraint.
?ij (P , S ) = log 1 +
Pi Sij N0 +
n∈N
Pn Snj
sessions, each consisting of a set of sources and sinks such that data from all the sources is intended for all the sinks, our algorithm for routing, network coding, scheduling and rate control achieves stability for all input rates that can be stabilized with intra-session network coding. Apart from the potential capacity gain of allowing network coding within multicast sessions, we also obtain much reduced complexity compared to the existing algorithms of [17], which involves enumeration of all multicast trees used, and [2], which involves maintaining a virtual queue for every subset of sinks for every session. In our approach, each node has just one virtual queue for each sink of each session (for independent sources) or for each source-sink pair of each session (for correlated sources). Routing, network coding and scheduling decisions are made locally by comparing, for each link, the
where Pl is the power transmitted by node l, Slj is the channel gain from node l to node j and N0 is additive white Gaussian noise power over the signaling bandwidth. We assume that the channel conditions are ?xed over the duration of a slot, and known at the beginning of the slot. For simplicity of exposition we assume that the channel and arrival processes are independent and identically distributed across slots; a straightforward generalization to ergodic processes is possible using a similar approach as that in [15]. We denote by (a, Z ) a wireless broadcast link where a is the originating node and Z is the set of receiving nodes. Link rates ?(P , S ) = (?aZ (P , S )) are determined by the vector of transmit powers P (t) = (PaZ (t)) and a channel state vector S (t). S (t) is assumed to be constant over each time slot, i.e., state transitions occur only on slot boundaries t = kT , k integer. We also assume that S (t) takes values from a ?nite set and is ergodic; we denote by πS the time average probability of state S . P (t) is also held constant over each time slot, and is chosen from a compact set Π of power allocations representing limits on transmit power per node and/or across nodes.
B. Network coding We use the approach of distributed random linear network coding [4], [6], [7], in which network nodes form output data by taking random linear combinations of input data. The contents of each packet, as a linear combination of the input packets, are speci?ed by a coef?cient vector in the packet header, updated by applying to the coef?cient vectors the same linear transformations as to the data. The coef?cient vector is thus a function of the random code coef?cients specifying the linear combinations at intermediate nodes. A sink is able to decode when it receives a full set of packets with linearly independent coef?cient vectors. For simplicity, we consider the case where no restrictions are placed on coding among packets from the same multicast session. This asymptotically achieves optimal capacity, but in the worst-case decoding may not be possible until the end of the entire session. III. DYNAMIC BACK - PRESSURE ALGORITHMS A. Multicast with intra-session network coding In [8] we give a dynamic algorithm that uses queue state information to make network coding and transmit scenario decisions, without requiring any knowledge of the input or channel statistics. Back-pressure policy In each time slot [t, t + T ), the following are carried out: Scheduling: For each link (a, Z ), one session ? ? ? ? cβ cβ c? = arg max max max U ? U , 0 aZ a b c ? ? b∈Z
β ∈Tc
transmissions, the optimization can be done independently for each transmitter. This algorithm stabilizes any set of input rates stabilizable with intra-session network coding [8]: c Theorem 1: If input rates (λc i ) satisfy (λi + ) ∈ Λ, the back-pressure policy stabilizes the system and guarantees an average total buffer occupancy upper bounded by T BN , where ? ? 2 τmax ? 1 Ac i in 2? B= + (?out E max + ?max ) 2 N i,c T
B. Back pressure algorithm for multicast routing We compare our back pressure multicast network coding algorithm with a back pressure algorithm for optimal multicast routing, for the case of a single multicast session with two sinks. The routing algorithm is similar to that in [2] in that each node maintains a queue for every subset of sinks. The algorithms differ in their policies for updating queues, as the algorithm of [2] is for adversarial wired networks, whereas our algorithm is for non-adversarial wireless networks. In general, the number of queues is exponential in the number of sinks. We describe the algorithm for the case of two sinks, where each node maintains three queues: two individual queues containing data that is to be transmitted to each of the sinks and a common queue containing data that is to be (k) transmitted to both sinks. We denote by Ui , k = 1, 2, 3, respectively the lengths of these three queues at node i, and refer to data in the respective queues as commodity k = 1, 2, 3 data. Back pressure is used to control the branch points of the multicast distribution trees used. In each time slot [t, t + T ), the following are carried out: Balancing: At the start of each timeslot, for each non(3) (1) (2) sink node i, if Ui ? Ui ? Ui > 0, then an amount (3) (1) (2) Ui ? Ui ? Ui /3 of data is removed from the common queue and the same amount of data is added to each of the individual queues at i. Scheduling: For each link (a, Z ),
(k) ? ? Ub kaZ = arg max max Ua k b∈Z (k)
is chosen. Let
? waZ = β ∈Tc?
aZ
max max Ua aZ ? Ub aZ
b∈Z
c? β
c? β
, 0 .
(1)
Power control: The state S (t) is observed, and a power allocation P (t) = arg max
P ∈Π a,Z ? ?aZ (P , S (t))waZ
(2)
is chosen. Network coding: For each link (a, Z ), a random linear combination of data corresponding to each (session, sink) pair c? c? β aZ β ? (c? ? Ub aZ > 0 aZ , β ∈ TcaZ ) for which maxb∈Z Ua is sent at the rate offered by the power allocation. Each destination node d ∈ Z associates the received information with the virtual buffers corresponding to sinks β ∈ Tc? for aZ which d = arg maxb∈Z Ua ? Ub . If the originating queues are empty within the time slot, no data is sent. In a network where simultaneous transmissions interfere, optimizing (2) requires a centralized solution. In practice, the optimization (2) can be done heuristically using a greedy approach similar to that in [11], [20] but with the added ? guidance of weights waZ for prioritization among candidate links (a, Z ). If there are enough channels for independent
c? aZ β c? aZ β
.
If max Ua
b∈Z
? (kaZ )
? Ub
? (kaZ )
2 (3) > Ua ? j =1 b∈Z
min Ub ,
(j )
then we set
? waZ = max Ua b∈Z
? (kaZ )
? Ub
? (kaZ )
.
? Otherwise, we set kaZ = 0 and 2 ? (3) waZ = Ua ? j =1 b∈Z (j )
min Ub .
Power control: The state S (t) is observed, and a power allocation P (t) = arg max
P ∈Π a,Z ? ?aZ (P , S (t))waZ
is chosen. ? Routing: For each link (a, Z ), if kaZ = 0 and ? ? (kaZ ) (kaZ ) ? maxb∈Z Ua ? Ub > 0, commodity kaZ data is sent from a to arg maxb∈Z Ua aZ ? Ub aZ at the rate ? offered by the power allocation. Otherwise, if kaZ = 0 (3) (j ) 2 and Ua ? j =1 minb∈Z Ub > 0, data from the common queue at a is broadcast on (a, Z ) at the offered rate, and a (j ) corresponding amount is added to minb∈Z Ub , j = 1, 2. If the originating queues are empty within the time slot, no data is sent. This algorithm asymptotically achieves the optimal multicast throughput for routing. The proof is omitted for brevity. IV. S IMULATION EXPERIMENTS A. Experimental setup We run the two multicast algorithms of the previous section on the network of Fig 2, with a single node A multicasting information to two sink nodes E and F. We assume a common transmission power and a half-duplex constraint at each network node. The channel gain for from node i to node j is modeled as: |fij |2 Sij = k dij (3)
(k? ) (k? )
To investigate the effects of network geometry and SNR, the two algorithms were run for a number of different values for parameter a2 , de?ned in Figure 2, and SNR. Here we take k = 2 and ? = 1.5. For each choice of parameter values, a series of simulation runs was carried out to ?nd the maximum stable multicast rate. For each run, the throughput was increased by 0.01, until the source queue became unstable, giving an approximate maximum transmission rate of R, de?ned as the maximum value for which the network is stable at rate R and unstable at rate R + 0.01. The network was considered stable for a given transmission rate and policy if the maximum backlog in all queues of all nodes was bounded by 200 when run for 20,000 timeslots. B. Results The simulation results are summarized in Table I. The results show that under this time-varying wireless interference network model, the capacity gain of network coding over routing is lower than the 4/3 factor obtained by [16] in the ?xed-rate collision model, and that the gain tends to decrease with decreasing SNR. Table 1 also shows the proportion of different transmit scenarios used by the two policies, which varies depending on the SNR and network geometry. In the network coding case, the proportion of different transmit scenarios, particularly TS3 which shows signi?cant use by coding but not routing, gives a rough indication of the proportion of time network coding is used. V. C ONCLUSION We have compared multicast network coding and routing for a time-varying wireless network model with interference. Our results suggest that when link capacities are affected by interference, and power control, scheduling, network coding and routing are dynamically controlled in response to network conditions, the gap in multicast capacity between network coding and routing can decrease relative to a collision-based wireless model with ?xed link capacities. In such cases, the main advantage of network coding may be the reduction in complexity of optimization and operation. The coding advantage may also increase in situations where routing, power control and scheduling are not done optimally, as has been shown for the multiple unicasts case [9]. R EFERENCES
[1] R. Ahlswede, N. Cai, S.-Y.R. Li, and R.W. Yeung. Network information ?ow. IEEE Transactions on Information Theory, 46:1204–1216, 2000. [2] Baruch Awerbuch, Andr? e Brinkmann, and Christian Scheideler. Anycasting and multicasting in adversarial systems: routing and admission control, preliminary technical report, 2002. [3] Baruch Awerbuch and Tom Leighton. A simple local control approximation algorithm for multicommodity ?ow. In Proceedings of 34th IEEE Conference on Foundations of Computer Science, 1993. [4] P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing, October 2003. [5] Thomas Cover and Joy Thomas. Elements of Information Theory. Wiley, 1991. [6] T. Ho, R. Koetter, M. M? edard, D. R. Karger, and M. Effros. The bene?ts of coding over routing in a randomized setting. In Proceedings of 2003 IEEE International Symposium on Information Theory, June 2003.
where |fij | is the Rayleigh fading state and dij is the distance between i and j , and k is the propagation power loss exponent. We assume ? = E [|f |2 ] is the same for all (i, j ). Suppose P Pl = P for all links l, and let SNR = N . 0 The two algorithms asymptotically achieve, for linear coding and routing respectively, the optimal multicast throughput achievable with the following thirteen transmit scenarios, chosen so as to cover the network coding and routing schedules of Figure 3: ? transmit scenario 1, where A transmits to B, and C broadcasts to D and F. ? transmit scenario 2, where A transmits to C, and B broadcasts to D and E. ? transmit scenario 3, where D broadcasts to E and F. ? transmit scenario 4, where A broadcasts to B and C. ? transmit scenario 5, where B transmits to E, and C transmits to F, respectively. ? transmit scenario 6, where B transmits to E. ? transmit scenario 7, where C transmits to F. ? transmit scenario 8, where A transmits to B. ? transmit scenario 9, where A transmits to C. ? transmit scenario 10, where B broadcasts to D and E. ? transmit scenario 11, where C broadcasts to D and F. ? transmit scenario 12, where D transmits to E. ? transmit scenario 13, where D transmits to F.
TABLE I M AXIMUM TRANSMISSION RATES AND USAGE PROPORTIONS OF 13 TRANSMIT SCENARIOS FOR CODING ( SHOWN IN ROWS MARKED WITH “C”) AND ROUTING ( ROWS MARKED WITH “R”). E ACH PAIR OF ROWS CORRESPONDS TO A SET OF EXPERIMENTAL PARAMETERS . F OR EACH ROW, ENTRIES CORRESPONDING TO MORE HEAVILY UTILIZED TRANSMIT SCENARIOS ARE HIGHLIGHTED IN BOLD . T HE LAST COLUMN GIVES THE RATIO OF CODING THROUGHPUT TO ROUTING THROUGHPUT. SNR 1000 1000 100 100 10 10 1 1 10 10 √a2 √2/2 √2/2 √2/2 √2/2 √2/2 √2/2 √2/2 √2/2 √2/4 2/4 C R C R C R C R R C TS1 8e-4 8e-4 .010 .008 .071 .063 .182 .182 .054 .047 TS2 6e-4 .001 .010 .008 .069 .062 .182 .182 .058 .045 TS3 .198 .051 .193 .041 .170 .031 .102 .030 .159 .026 TS4 .012 .057 .015 .061 .048 .076 .043 .030 .103 .163 TS5 8e-4 .004 .008 .025 .050 .081 .107 .137 .080 .127 TS6 .003 .054 .010 .045 .017 .028 .016 .020 .017 .032 TS7 .003 .054 .010 .046 .017 .028 .015 .022 .017 .032 TS8 .179 .133 .165 .125 .103 .083 .032 .038 .121 .086 TS9 .180 .132 .165 .124 .104 .084 .031 . 038 .118 .087 TS10 .211 .153 .207 .154 .169 .131 .104 .073 .132 .093 TS11 .212 .151 .207 .153 .170 .131 .108 .073 .135 .093 TS12 1e-4 .105 6e-4 .106 .006 .101 .038 .088 .003 .085 TS13 1e-4 .105 7e-4 .105 .006 .100 .038 .088 .003 .085 Rate 4.11 3.56 2.86 2.53 1.67 1.54 .060 .056 1.99 1.84 Ratio 1.15 1.13 1.08 1.07 1.08
[7] T. Ho, M. M? edard, J. Shi, M. Effros, and D. R. Karger. On randomized network coding. In Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing, October 2003. [8] T. Ho and H. Viswanathan. Dynamic algorithms for multicast with intrasession network coding. In Proc. 43rd Annual Allerton Conference on Communication, Control, and Computing, 2005. edard. The importance of being oppor[9] S. Katti, D. Katabi, and M. M? tunistic. In Proc. 43rd Annual Allerton Conference on Communication, Control, and Computing, 2005. [10] Thierry Klein and Harish Viswanathan. Centralized power control in multihop wireless networks. In Proceedings of IEEE International Symposium on Information Theory, 2003. [11] Sayandev Mukherjee and Harish Viswanathan. Throughput range tradeoff of wireless mesh backhaul networks. IEEE Journal on Selected Areas in Communications, to appear, 2006. [12] Michael Neely. Energy optimal control for time varying networks. In Proceedings of the IEEE INFOCOM, 2005. [13] Michael Neely, Eytan Modiano, and Chih-Ping Li. Fairness and optimal stochastic control for heterogeneous networks. In Proceedings of the IEEE INFOCOM, 2005. [14] Michael Neely, Eytan Modiano, and C. Rohrs. Packet routing over parallel time-varying queues with application to satellite and wireless networks. In Proceedings of the Thirty-Ninth Annual Allerton Conference on Communications and Control, 2001. [15] Michael Neely, Eytan Modiano, and Charles E. Rohrs. Dynamic power allocation and routing for time-varying wireless networks. In Proceedings of IEEE Infocom, 2003. [16] Y. E. Sagduyu and A. Ephremides. Joint scheduling and wireless network coding. In Proc. 1st Workshop on Network Coding, Theory and Applications, 2005. [17] Saswati Sarkar and Leandros Tassiulas. A framework for routing and congestion control for multicast information ?ows. IEEE Transactions on Information Theory, 2002. [18] Leandros Tassiulas and Anthony F. Ephremides. Stability properties of constrained queuing systems and scheduling policies for maximum throughput in multihop networks. IEEE Transactions on Information Theory, 1992. [19] Harish Viswanathan and Krishnan Kumaran. Rate scheduling for multiple antenna downlink wireless systems. In Proceedings of the ThirtyNinth Annual Allerton Conference on Communications and Control, 2001. [20] Yunnan Wu, Philip A. Chou, Qian Zhang, Kamal Jain, Wenwu Zhu, and Sun-Yuan Kung. Network planning in wireless ad hoc networks: A cross-layer approach. IEEE Journal on Selected Areas in Communications, Special Issue on Wireless Ad Hoc Networks, 2005. [21] Edmund Yeh and Aaron Cohen. Throughput and delay optimal resource allocation in multiaccess fading channels. In Proceedings of IEEE International Symposium on Information Theory, 2003. [22] Edmund Yeh and Aaron Cohen. Throughput optimal power and rate control in queued multiaccess and fading channels. In Proceedings of IEEE International Symposium on Information Theory, 2004.