70 5. ROUTING
Figure 5.13 illustrates the procedure.The packets {P 1,...,P4}are to be sent. One calculates
the packets {C1,...,C7} as indicated in the figure. The meaning of the graph is that a packet Cj
is the sum of the packets Pi it is attached to, bit by bit modulo 2. For instance,
C1 = P 1,C2 = P 1 + P 2,C3 = P 1 + P 2 + P 3,
and so on.
Now assume that the packets C1,C3,C5,C6 (shown shaded in Figure 5.13) are received
by the destination. Following the algorithm described above, one first looks for a packet Cj that is
equal to one of the Pi. Here, one sees that C1 = P 1. One then adds P 1 to all the packets Cj that
used that packet. Thus, one replaces C3 by C3 + C1. One removes P 1 from the graph and one is
left with the graph shown in the left part of Figure 5.14.
P2 P3 P4
C1 + C3 C5 C6
P3
C5 + C6
P2
C1 + C3
P2
C1 + C3
+ C5 + C6
Figure 5.14: Updates in decoding algorithm.
The algorithm then continues as shown in the right part of the figure. Summing up, one finds
successively that P 1 = C1, P 4 = C5, P 3 = C5 + C6, and P 2 = C1 + C3 + C5 +C6.
In practice,one chooses a distribution on the number D of packets Pithat are used to calculate
each Cj . For instance, say that D is equally likely to be 1, 2, or 3. To calculate C1, one generates
the random variable D with the selected distribution. One then picks D packets randomly from
{P 1,...,Pn} and one adds them up bit by bit modulo 2. One repeats the procedure to calculate
C2,...,Cm. Simulations show that with m 1.05 × n, the algorithm has a good likelihood to
recover the original packets from any n of the packets {C1,...,Cm}. For instance, if n = 1000,one
needs to send 1050 packets so that any 1000 of these packets suffice to recover the original 1000
packets, with a high probability.
5.4.4 NETWORK CODING
Network coding is an in-network processing method that can increase the throughput of multicast
transmissions in a network. We explain that possibility in Figure 5.15.
In the figure, source S sends packets to both Y and Z. b
1
and b
2
represent the bits to be
transmitted. Say that the rate of every link in the network is R packets per second. The figure on
the left has two parallel links from W to X. By using the coding in the intermediate node, as shown
5.4. ANYCAST, MULTICAST 71
S
TU
W
X
YZ
X
S
TU
W
X
YZ
X
b
1
b
2
b
1
b
2
b
1
b
1
b
1
b
1
b
2
b
1
b
2
b
1
b
2
b
1
b
1
b
2
b
2
b
1
b
2
b
1
b
2
Figure 5.15: Multicast from S to X and Y without (left) and with (right) network coding.
in the right part of the figure, the network can deliver packets at the rate of 2R to both Y and Z.
Without network coding,as shown on the left,the network can only deliver one bit to Y and two bits
to Z (or, two bits to Y and one bit to Z). One can show that the network can achieve a throughput
of 1.5R to both Y and Z without network coding.
The general result about network coding and multicasting is as follows. Consider a general
network and assume that the feasible rate from S to any one node in
N is at least R. Then, using
network coding, it is possible to multicast the packets from S to
N at rate R. For instance, in the
network of Figure 5.15, the rate from S to Y is equal to 2R as we can see by considering the two
disjoint paths ST Y and SUWXY. Similarly, the rate from S to Z is also 2R.Thus,one can multicast
packets from S to Y and Z at rate 2R.
Network coding can also be useful in wireless networks, as the following simple example
shows. Consider the network in Figure 5.16.There are two WiFi clients X and Y that communicate
via access point Z. Assume that X needs to send packet A to Y and that Y needs to send packet B
to X.
A
B
A BA B
(1) (2)
(3)
XY
Z
Figure 5.16: Network coding for a WiFi network.
The normal procedure for X and Y to exchange A and B requires transmitting four packets
over the wireless channel: packet A from X to Z, packet A from Z to Y , packet B from Y to Z,
and packet B from Z to X. Using network coding, the devices transmit only three packets: packet

Get Communication Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.