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 ﬁgure. 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 ﬁrst 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 ﬁgure. Summing up, one ﬁnds

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 sufﬁce 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 ﬁgure, 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 ﬁgure 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 ﬁgure, 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.