Classifying Networks For Network Coding
Loading...
Authors
Manley, Eric D.
Janssen, William
Issue Date
2011-04
Type
Article
Language
en_US
Keywords
Network coding , Graph theory , Multicast
Alternative Title
Abstract
Network coding is a relatively recent development in the realm of maximizing information
transfer in communications and computer networks. Traditional networks operate by simply
storing and forwarding data along. Network coding, however, allows intermediate network
nodes to combine data using arithmetic operations. In many instances, this can lead
to more efficient use of network resources. Since there is a significant throughput input in
some networks, some studies have been done on what kinds of networks will benefit from
coding. A coding advantage is defined as a situation where a network coded graph has a
lower cost to send given information per unit time session than the same un-coded graph. It
has been proven that for two simple single-sender-single-receiver communication sessions
that a graph must have one of two special graph-theoretic structures called the butterfly and
grail in order to yield a coding advantage. We decided to focus our efforts on a different
traffic scenario: a multicast session with a single sender and multiple receivers. Through
our research we proved that a multicast-version of the butterfly network structure is needed
within a single session multicast with two sinks and one source in order to gain a coding
advantage. We also performed a simulation-based study in order to study the structures of
multicast sessions with a larger number of receivers. The study involved the random generation
of networks using several graph generation techniques. We also considered a variety
of different edge-weighting constraints. Given a particular graph with set edge weights, the
coding advantage problem was modeled as a linear program and run through the simulator
to determine if a coding advantage was gained. Based on visual inspection of these results,
it appears that variations of the multicast butterfly are ultimately the dominant structure
allowing for a coding advantage. We also found that many types of random networks only
very rarely resulted in a coding advantage. Only the graphs generated using the rectangular
grid method showed a coding advantage, with a coding advantage percentage of 0.005%
for 4 sinks in a 30 node network, with the coding advantage percentage going up as the
number of sinks within the network increased.
Description
Citation
Proceedings of the Midwest Instruction & Computing Symposium
Publisher
MICS