We analyze inter-session network coding in a wired network using game theory. We assume that users are selfish and act as strategic players to maximize their own utility, which leads to a resource allocation game amon...
详细信息
We analyze inter-session network coding in a wired network using game theory. We assume that users are selfish and act as strategic players to maximize their own utility, which leads to a resource allocation game among users. In particular, we study a butterfly network, where a bottleneck link is shared by networkcoding and routing flows. We assume that networkcoding is performed using pairwise XOR operations. We prove the existence of Nash equilibrium for a wide range of utility functions. We also show that the number of Nash equilibria can be large (even infinite) for certain choices of parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding, where the Nash equilibrium is always unique. We characterize the worst-case efficiency bound, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA in comparison with the case where a single pricing scheme is used. However, even when a discriminatory pricing scheme is used, the PoA is still worse than for the case when networkcoding is not applied. This implies that, although inter-session network coding can improve performance compared to routing, it is much more sensitive to users' strategic behavior.
Next generation wireless networks will carry traffic from a wide range of applications, and many of them may require packets to be delivered before their respective deadlines. In this paper, we investigate using inter...
详细信息
Next generation wireless networks will carry traffic from a wide range of applications, and many of them may require packets to be delivered before their respective deadlines. In this paper, we investigate using inter-session network coding to send packets wirelessly for two deadline-constrained unicast sessions. In particular, each unicast session aims to transmit a file, whose packets have hard sequential deadline constraints. We first characterize the corresponding deadline-constrained capacity region under heterogeneous channel conditions and heterogeneous deadline constraints. We show that this deadline-constrained capacity region can be achieved asymptotically by modifying the existing generation-based (G-B) schemes. However, despite its asymptotic optimality, the G-B scheme has very poor performance for small and medium file sizes. To address these problems, we develop a new immediately-decodable networkcoding (IDNC) scheme that empirically demonstrates much better performance for short file sizes, and we prove analytically its asymptotic optimality when used to send large files. Our analysis uses a novel version of drift analysis, which could also be of independent interest to other IDNC schemes.
Intra-sessionnetworkcoding has been shown to offer significant gains in terms of achievable throughput and delay in settings where one source multicasts data to several clients. In this paper, we consider a more gen...
详细信息
Intra-sessionnetworkcoding has been shown to offer significant gains in terms of achievable throughput and delay in settings where one source multicasts data to several clients. In this paper, we consider a more general scenario where multiple sources transmit data to sets of clients over a wireline overlay network. We propose a novel framework for efficient rate allocation in networks where intermediate network nodes have the opportunity to combine packets from different sources using randomized networkcoding. We formulate the problem as the minimization of the average decoding delay in the client population and solve it with a gradient-based stochastic algorithm. Our optimized inter-session network coding solution is evaluated in different network topologies and is compared with basic intra-sessionnetworkcoding solutions. Our results show the benefits of proper coding decisions and effective rate allocation for lowering the decoding delay when the network is used by concurrent multicast sessions.
In this work, we propose a distributed rate allocation algorithm that minimizes the average decoding delay for multimedia clients in inter-session network coding systems. We consider a scenario where the users are org...
详细信息
In this work, we propose a distributed rate allocation algorithm that minimizes the average decoding delay for multimedia clients in inter-session network coding systems. We consider a scenario where the users are organized in a mesh network and each user requests the content of one of the available sources. We propose a novel distributed algorithm where network users determine the coding operations and the packet rates to be requested from the parent nodes, such that the decoding delay is minimized for all clients. A rate allocation problem is solved by every user, which seeks the rates that minimize the average decoding delay for its children and for itself. Since this optimization problem is a priori non-convex, we introduce the concept of equivalent packet flows, which permits to estimate the expected number of packets that every user needs to collect for decoding. We then decompose our original rate allocation problem into a set of convex subproblems, which are eventually combined to obtain an effective approximate solution to the delay minimization problem. The results demonstrate that the proposed scheme eliminates the bottlenecks and reduces the decoding delay experienced by users with limited bandwidth resources. We validate the performance of our distributed rate allocation algorithm in different video streaming scenarios using the NS-3 network simulator. We show that our system is able to take benefit of inter-session network coding for simultaneous delivery of video sessions in networks with path diversity.
This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing ar...
详细信息
This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear networkcoding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-sessioncoding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-sessioncoding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared.
In the literature, an opportunistic inter-session network coding scheme needs to exchange extra control messages to maintain traffic flow states to operate. However, such a requirement increases the implementation com...
详细信息
In the literature, an opportunistic inter-session network coding scheme needs to exchange extra control messages to maintain traffic flow states to operate. However, such a requirement increases the implementation complexity of a networkcoding scheme. In this paper, we propose a rule-based networkcoding scheme (RNC) that performs opportunistic intersessionnetworkcoding using a stateless design. By exploiting this stateless design, the proposed coding scheme is easy to implement and deploy. In addition, in this paper based on RNC we study the hidden terminal problems between different coding structures. Such a problem may result in severe packet collisions in a network-coding-based network and thus degrade networkcoding performance. To alleviate this problem, based on RNC we propose a smart handshake procedure (called RNC-SHP) over the IEEE 802.16(d) mesh coordinated distributed scheduling (CDS) mode to reduce the number of hidden terminals between pairwise networkcoding structures. Our simulation results show that the proposed RNC schemes can greatly outperform the original routing-based scheme on end-to-end flow goodputs and packet delays. (C) 2011 Elsevier B.V. All rights reserved.
We present a novel receiver-driven p2p system for delivery of multiple concurrent time constrained data streams in overlay networks. We propose an effective combination of rateless coding with intra- and inter-session...
详细信息
ISBN:
(纸本)9781612843490
We present a novel receiver-driven p2p system for delivery of multiple concurrent time constrained data streams in overlay networks. We propose an effective combination of rateless coding with intra- and inter-session network coding to efficiently exploit the path diversity in the streaming overlay. network nodes can decide to forward rateless coded packets or to code them in intra-or inter-session mode before transmission. The transmission strategy is determined based on the availability of data sources and the demands of the children nodes. Each network node solves independently a simple flow maximization problem in order to determine the optimal coding policy. The overall system is evaluated for various networks and the results outline the advantages of the proposed approach over intra-sessionnetworkcoding based schemes in terms of clients' satisfaction, innovative flow rate and decoding delay.
Wireless sensor networks (wsns) typically provide several paths from a source to a destination, and by using such paths efficiently. This has the potential not only to increase multiplicatively the achieved end-to-end...
详细信息
ISBN:
(纸本)9783642181283
Wireless sensor networks (wsns) typically provide several paths from a source to a destination, and by using such paths efficiently. This has the potential not only to increase multiplicatively the achieved end-to-end rate, but also to provide robustness against performance fluctuations of any single link in the system. networkcoding is a new technique which improves the network performance. This paper we analyze how to using networkcoding according to the characteristic of multi-path routing in the wsns. As a result, an optimization multi-path inter-session network coding is designed to improve the wsns performance.
Energy consumption and time delay,i.e.,the amount of energy and time consumed by all nodes for transmitting data,are two critical factors for estimating the efficiency of algorithms in wireless sensor *** focus on the...
详细信息
Energy consumption and time delay,i.e.,the amount of energy and time consumed by all nodes for transmitting data,are two critical factors for estimating the efficiency of algorithms in wireless sensor *** focus on the application of time-driven data gathering,where all nodes act as sources at the same time,transmitting data to an immobile sink node,and propose an efficient algorithm called DGNC for this scenario using inter-session network coding and opportunistic *** theoretically quantify the energy and time delay saving that our algorithm could offer in a rectangular grid network,and demonstrate the fact by simulation results in random networks,which DGNC could offer significant benefits in terms of both energy consumption and time delay in time-driven data gathering.
In this paper we consider the problem of transmitting packets through multiple unicast sessions when inter-session linear networkcoding is permitted. We propose and formulate two new capacity regions for this problem...
详细信息
ISBN:
(纸本)9789639799127
In this paper we consider the problem of transmitting packets through multiple unicast sessions when inter-session linear networkcoding is permitted. We propose and formulate two new capacity regions for this problem. Distributed rate allocation algorithms and coding schemes are also provided for these capacity regions. The two capacity regions are compared with other known capacity regions in the literature to represent their benefits in terms of throughput, fairness, complexity, and ease of implementation.
暂无评论