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.
展开▼
