As parallelism becomes critically important in the semiconductor technology, high-performance computing, and cloud applications, parallel network systems will increasingly follow suit. Today, parallelism is an essential architectural feature of 40 100 400 Gigabit Ethernet standards, whereby high speed Ethernet systems are equipped with multiple parallel network interfaces. This creates new network topology abstractions and new technology requirements: instead of a single high capacity network link, multiple Ethernet end-points and interfaces need to be considered together with multiple links in form of discrete parallel paths. This new paradigm is enabling implementations of various new features to improve overall system performance. In this paper, we analyze the performance of parallel network systems with network coding. In particular, by using random LNC (RLNC), - a code without the need for decoding, we can make use of the fact that we have codes that are both distributed (removing the need for coordination or optimization of resources) and composable (without the need to exchange code information), leading to a fully stateless operation. We propose a novel theoretical modeling framework, including derivation of the upper and lower bounds as well as an expected value of the differential delay of parallel paths, and the resulting queue size at the receiver. The results show a great promise of network system parallelism in combination with RLNC: with a proper set of design parameters, the differential delay and the buffer size at the Ethernet receiver can be reduced significantly, while the cross-layer design and routing can be greatly simplified.
Previous work on linear network coding focused in general on improving network throughput and reliability. However, significant body of work in the last decade (e.g., @cite_24 @cite_32 @cite_3 @cite_23 @cite_11 ) addressed with network coding the end-to-end delays improvement in delay-constrained networks in broadcast and unicast scenarios. In @cite_24 , for instance, the delay performance of network coding was studied and compared it to scheduling methods. Lucani et. al, in @cite_7 tailored coding and feedback to reduce the expected delay. Paper @cite_4 studied the problem of minimizing the mean completion delay for instantly decodable network coding. In @cite_28 @cite_11 authors showed that network coding can outperform optimal routing in single unicast setting. More recent works, like @cite_25 , presented a streaming code that uses forward error correction to reduce in-order delivery delay over multiple parallel wireless networks. However, none of these works address delay in parallel network systems.
@cite_4 @cite_7 @cite_28 @cite_32 @cite_3 @cite_24 @cite_23 @cite_25 @cite_11
1965556172 2116673244 2534339435 2116661213 2518569826
In this paper, we consider the problem of minimizing the mean completion delay in wireless broadcast for instantly decodable network coding. We first formulate the problem as a stochastic shortest path (SSP) problem. Although finding the packet selection policy using SSP is intractable, we use this formulation to draw the theoretical properties of efficient selection algorithms. Based on these properties, we propose a simple online selection algorithm that efficiently minimizes the mean completion delay of a frame of broadcast packets, compared to the random and greedy selection algorithms with a similar computational complexity. Simulation results show that our proposed algorithm indeed outperforms these random and greedy selection algorithms. In networks with large latency, feedback about received packets may lag considerably the transmission of the original packets, limiting the feedback's usefulness. Moreover, time duplex constraints may entail that receiving feedback may be costly. In this work, we consider tailoring feedback and coding jointly in such settings to reduce the expected delay for successful in order reception of packets. We find that, in certain applications, judicious choices provide results that are close to those that would be obtained with a full-duplex system. We study two cases of data transmission: one-to-all broadcast and all-to-all broadcast. We also analyze important practical considerations weighing the trade off between performance and complexity in applications that rely on random linear network coding. Finally, we study the problem of transmission of information under the large latency and time duplexing constraints in the presence of random packet arrivals. In particular, we analyze the problem of using a batch by batch approach and an online network coding approach with Poisson arrivals. We present numerical results to illustrate the performance under a variety of scenarios and show the benefits of the proposed schemes as compared to typical ARQ and scheduling schemes. This paper considers network communications under a hard timeliness constraint , where a source node streams perishable information to a destination node over a directed acyclic graph subject to a hard delay constraint. Transmission along any edge incurs unit delay, and it is required that every information bit generated at the source at the beginning of time @math to be received and recovered by the destination at the end of time @math , where @math is the maximum allowed end-to-end delay. We study the corresponding delay-constrained unicast capacity problem. This paper presents the first example showing that network coding (NC) can achieve strictly higher delay-constrained throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained ( @math ) single-unicast case where the classic min-cut max-flow theorem implies that coding cannot improve throughput over routing. Motivated by the above findings, a series of investigation on the delay-constrained capacity problem is also made, including: 1) an equivalent multiple-unicast representation based on a time-expanded graph approach; 2) a new delay-constrained capacity upper bound and its connections to the existing routing-based results [ 2011]; 3) an example showing that the penalty of using random linear NC can be unbounded; and 4) a counter example of the tree-packing Edmonds’ theorem in the new delay-constrained setting. Built upon the time-expanded graph approach, we also discuss how our results can be readily extended to cyclic networks. Overall, our results suggest that delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation. This paper analyzes the gains in delay performance resulting from network coding. We consider a model of file transmission to multiple receivers from a single base station. Using this model, we show that gains in delay performance from network coding with or without channel side information can be substantial compared to conventional scheduling methods for downlink transmission. The capability of mobile devices to use multiple interfaces to support a single session is becoming more prevalent. Prime examples include the desire to implement WiFi offloading and the introduction of 5G. Furthermore, an increasing fraction of Internet traffic is becoming delay sensitive. These two trends drive the need to investigate methods that enable communication over multiple parallel heterogeneous networks, while also ensuring that delay constraints are met. This paper approaches these challenges using a multi-path streaming code that uses forward error correction to reduce the in-order delivery delay of packets in networks with poor link quality and transient connectivity. A simple analysis is developed that provides a good approximation of the in-order delivery delay. Furthermore, numerical results help show that the delay penalty of communicating over multiple paths is insignificant when considering the potential throughput gains obtained through the fusion of multiple networks.