Queueing Analysis of the Decoding Process for Intra-session Network Coding with Random Linear Codes
Efficient designs for intra-session network coding based practical applications largely rely on a better understanding on its queueing behaviors. However, few work devote on this topics. In this paper, we build a multi-channel batch service queueing syste
- PDF / 235,158 Bytes
- 8 Pages / 429.725 x 659.895 pts Page_size
- 41 Downloads / 208 Views
Abstract. Efficient designs for intra-session network coding based practical applications largely rely on a better understanding on its queueing behaviors. However, few work devote on this topics. In this paper, we build a multichannel batch service queueing system (MN/Dm/1) with control feedbacks to describe the decoding process of intra-session network coding with random linear codes and try to answer several fundamental questions, including for example, how to analyze braking redundancy? Under what condition is the system stable? How’s quantitative relationship between the inter-decoding delay and the generation granularity? Keywords: Intra-session network coding, Segment granularity, Control feedbacks, Queueing analysis.
1 Introduction Network coding has enjoyed much popularity within the research community since it was first introduced in its seminal paper by Ahlswede et al. [1]. With network coding, intermediate nodes encode multiple data packets algebraically together by using, for example, bitwise XOR or linear combination in Galois field, while destination nodes perform decoding operations to recover the original data. The benefits of network coding include improving network throughput, reducing energy consumption, enhancing network reliability, and much more. According to the operations on sessions, network coding can be classified into inter-session and intra-session [2]. Intra-session network coding only allows intermediate nodes to encode the packets within the same session, which has found its success in peer-to-peer systems for content dissemination [3, 4]. Since with random linear codes, the coding coefficients can be chosen randomly and independently, and can be implemented in a fully distributed fashion, it is often utilized as the practical form for intra-session network coding [5]. In the practical applications, to maintain a tractable computation overhead, each session is split into multiple generations with equal number of packets. The number of packets in each generation, as the intra-session coding range, is called generation granularity. During the data dissemination from multiple upstream nodes, each destination has to hold its decoding operation until the number of coded packets H. Tan (Ed.): Knowledge Discovery and Data Mining, AISC 135, pp. 481–488. © Springer-Verlag Berlin Heidelberg 2012 springerlink.com
482
Y. Yuan et al.
buffered in its queue achieves the generation granularity. Once the decoding operation can be activated, destinations send braking messages to their upstream nodes in order to switch the data transmission to the next generation. This kind of dissemination protocol leads to highly resilient data transmissions in a multiple-sources fashion without the needs of explicit cooperation. Most related work on generation based intra-session network coding focus on protocol design and system implementation [3, 4]. An efficient design of these practical applications largely relies on a better understanding on the stochastic behavior of the decoding process for intra-sessio
Data Loading...
