Information Technology Reference
In-Depth Information
4.5 Network-Coding-Based Distributed Topology Con-
trol
Jafarisiavoshani et al. [Jafarisiavoshani et al., 2007] proposed an interesting
topology control algorithm based on network coding [Ahlswede et al., 2000]. In
simple terms, using network coding, a source peer sends out to its neighbors a
coded packet which is a linear combination (e.g., based on bit-wise XOR oper-
ations) of multiple packets that it receives from other neighbors. By attaching
also a coding vector to the combined packet, the source allows each receiving
neighbor to decode the desired original packet from the combination.
Avalanche [Gkantsidis and Rodriguez, 2005] is a network-coding-based
P2P system, in which peers randomly combine their received packets and
propagate such linear combinations to their neighbors. A peer receiving a suf-
ficient number of linear combinations solves a system of linear equations (based
on the coding vectors retrieved) and retrieves the desired source packets.
Jafarisiavoshani et al.'s novel insight [Jafarisiavoshani et al., 2007] is that
coding vectors the peers receive from their neighbors can be used to passively
infer bottleneck information. This allows individual peers to initiate topology
changes to correct problematic connections. In particular, peers, by keeping
track of the coding vectors they receive, can detect problems in both the
overlay topology and the underlying physical links. The following example
illustrates these points.
Consider the example P2P network depicted in Figure 4.6(a) where the
edges correspond to logical (overlay network) links. The source S has n pack-
ets to distribute to four peers. Peers A, B, and C are directly connected to
the source S, and also among themselves with logical links, while peer D is
connected to peers A, B, and C. In this overlay network, each peer has a con-
stant degree of three (three neighbors), and there exists three edge-disjoint
paths between any pair of peers (in particular, between the source and any
other peer).
Now, consider (as shown in Figure 4.6(b)) that the logical links SA, SB,
and SC share the bandwidth of the same underlying physical link, which forms
a bottleneck between the source and the remaining peers of the network. As
a result, let us assume the bandwidth on each of these links is only 1/3 of
the bandwidth of the remaining links. Peer D can infer this information by
observing the coding vectors it receives from its neighbors A, B, and C.
Specifically, when peer A receives a coded packet from the source, it will
forward a linear combination of packets it has already collected to peers B, C,
and D. Now each of peers B and C, once they receive the packet from peer A,
they also attempt to send a coded packet to peer D. But these packets will
not bring new information to peer D, because they are already contained in
the combination of coding vectors that peer D has already received. Similarly,
when peers B and C receive a new packet from the source, peer D will end
Search WWH ::




Custom Search