Title :
Network coding with shortcuts
Author :
Crisóstomo, Sérgio ; Barros, João ; Bettstetter, Christian
Author_Institution :
Univ. do Porto, Porto, Portugal
Abstract :
Information dissemination in communication networks is a key function whose effectiveness depends both on the chosen dissemination algorithm and on the underlying network topology. A series of contributions in statistical physics has uncovered the specific topological properties of small-world networks that potentiate the spread of information, most strikingly small network diameters and large clustering coefficients. Simultaneously, the spectra of dissemination algorithms, typically based on message replication, was recently enlarged by the advent of the network coding paradigm, in which intermediate nodes are allowed to mix information flows through non-trivial linear operations. Intrigued by the dissemination of information in broadcast environments with small-world topologies, we compare the behavior of competing replication based algorithms and their network coding counterparts. We show, both analytically and through simulation, that network coding requires a smaller number of transmissions and shorter propagation delays, conjugated with impressive steadiness under distinct topological configurations.
Keywords :
encoding; statistical analysis; telecommunication network topology; clustering coefficients; communication networks; information dissemination; information flows; network coding; network topology; propagation delays; statistical physics; Algorithm design and analysis; Analytical models; Broadcasting; Clustering algorithms; Communication networks; Floods; Network coding; Network topology; Peer to peer computing; Physics;
Conference_Titel :
Communication Systems, 2008. ICCS 2008. 11th IEEE Singapore International Conference on
Conference_Location :
Guangzhou
Print_ISBN :
978-1-4244-2423-8
Electronic_ISBN :
978-1-4244-2424-5
DOI :
10.1109/ICCS.2008.4737366