Research On Network Coding Revenue

Network Coding encourages information coding across a communication net-work. By coding at the intermediate nodes, different information flows can be "mixed" during transmission, so that less bandwidth is consumed and larger throughput is achievable. In multicast communications, it is proved that with network coding the optimal multicast rate is the min-cut upper-bound, which is usually not achievable by routing (Store-and-Forward).The research on the benefits of network coding concerns the comparison of network coding to routing. Its main task is to answer "when is network coding necessary to achieve the optimal performance?" and "compared to routing, how much improvement can network coding make?" questions. Study on the benefits of network coding helps to understand network coding, identify the scenario when network coding is useful.The benefits of network coding in multicast communications is of two folds: higher throughput and less cost. In this paper, we study three practical factors that affects the benefits of network coding:the full duplex links, the broadcast links and the characteristic of network topology.First, for networks with full duplex links, we use bi-directed network mod-el and introduce the parameter of link capacity (price) balance ratio α (α) to upper-and lower-bound the benefits of network coding. The link capaci-ty(price) balance ratio is the max ratio of link capacities(prices) of pair of opposite links. We prove that in a completely capacity-balanced network, net-work coding can not improve the multicast throughput. For general bi-directed networks, we prove that the coding advantage is no more than α, which im-proves the previous upper-bound2(α+1). The other bounds are brand new. We also propose an a-approximated polynomial time algorithm for finding the optimal routing solution in bi-directed networks.Second, for networks with broadcast links, we use hyper-network model, and introduce the max hyper-link size β to upper-and lower-bound the ben-efits of network coding. In hyper-networks, each link may connect more than two nodes. Hyper-networks well model the bus Ethernet and wireless network-s. According whether flows of different direction share the same link capacity, hyper-networks can be divided into two types:undirected hyper-networks and directed-network. For undirected hyper-networks, we prove that the coding advantage is no more than β, which generalize the conclusion that coding ad-vantage in undirected networks is upper bounded by2. On the other hand, we also consider a special type of directed hyper-networks-omni-directed hyper-networks, and combine the link balance ratio and the max hyper-link size to upper-and lower-bound the benefits of network coding. These conclusions generalize our previous results in bi-directed networks.Finally, we propose to study the benefits of network coding from the graph minor perspective. Unlike the previous two parts, where we concentrate on the local(link level) characteristics, we now using graph minor to study how network topology affects the benefits of network coding. Graph minor is an important concept to model the containment relationship in graph theory. Many types of graphs can be defined in terms of the containment of specific graph minors. For example, a connected graph is a tree if and only if it does not contain K3minor; a graph is a planar graph if and only if it does not contain either K5minor nor K3,3minor. We prove that, if the network topology does not contain K4minor,network coding can not improve the multicast rate when there are two information flows to be multicasted, and conjectured this property holds for multicasting any number of information flows.