Search

To reduce recovery cost of repairing multiple failed nodes, many repair schemes have been proposed for erasure codes based distributed storage systems. However, most of the existing researches ignore the network topology of storage devices. Motivated by such considerations, we combine delay repair schemes with network topology and propose a tree-structured model based on fountain codes with large value of $\left ({n,k,r }\right)$ to improve the repair efficiency. More precisely, with the consideration of network topology, a new target named data recovery cost is defined to measure the efficiency of coded fragment download and source file reconstruction, and then the optimal recovery threshold is derived to minimize the average data recovery cost of general tree-structured model. Moreover, we analyze and compare the average data recovery cost of general tree-structure with different systematic parameters. To further improve the data transmission efficiency, an optimal tree-structured scheme based on improved tabu search algorithm (ITSA-ORT) is proposed. Compared with other algorithms, the ITSA-ORT scheme uses Prim algorithm to generate the initial solution and then uses special method to obtain the corresponding neighborhood structure. The experimental results show that the proposed scheme can find a globally optimal solution and obtain lower cost of data recovery. In addition, the ITSA-ORT scheme has lower computational complexity than the optimal tree-structured scheme based on particle swarm optimization algorithm (PSO-ORT) and the optimal tree-structured scheme based on firefly algorithm (FA-ORT).

Coded caching in wireless networks and storage systems is studied. Caching based on two types of codes, index codes and fountain codes, is investigated in terms of network throughput and security. It is shown that index coding can significantly increase the multicast transmission rate in Information Centric Networks (ICN). Also, it is proved that index codes can be efficiently used to increase the multicasting transmission rate in cellular networks. It is proved that a simple graph coloring-based algorithm for index coding achieves order optimal capacity gains both for cellular and ICN networks. A new decentralized caching scheme based on Random Linear Fountain (RLF) codes is then introduced and it is shown that RLF-based coded caching performs close to optimal in terms of reducing the average number of transmission hops in wireless ad hoc and cellular networks. Therefore, considerable capacity gains can be achieved using RLF-based coded caching in wireless networks. It is shown that the RLF codes can significantly reduce the overcaching in wireless networks. Further, it is shown that using coded caching based on RLF codes we can achieve asymptotic perfect secrecy. In the limiting case of large number of coded files, the conditions of Shannon secrecy theorem are met and the problem can be modelled by a Shannon cipher system which is perfectly secure. Finally, a new storage policy based on RLF codes for storage systems along with a Private Information Retrieval (PIR) scheme for these systems is proposed and it is proved that perfect privacy and secrecy is achievable in these systems.

Long-range wide-area network (LoRaWAN) is an energy-efficient and inexpensive networking technology that is rapidly being adopted for many Internet-of-Things applications. In this study, we perform extensive measurements on a new LoRaWAN deployment to characterise the spatio-temporal properties of the LoRaWAN channel. Our experiments reveal that LoRaWAN frames are mostly lost due to the channel effects, which are adverse when the end-devices are mobile. The frame losses are up to 70 percent, which can be bursty for both mobile and stationary scenarios. Frame losses result in data losses since the frames are transmitted only once in the basic configuration. To reduce data losses in LoRaWAN, we design a novel coding scheme for data recovery called DaRe that works on the application layer. DaRe combines techniques from convolutional and fountain codes. By implementing DaRe, we show that 99 percent of the data can be recovered with a code rate of 1/2 when the frame loss is up to 40 percent. Compared to the repetition coding scheme, DaRe provides 21 percent higher data recovery and can save up to 42 percent of the energy consumed on a transmission for 10-byte data units. We also show that DaRe provides better resilience to bursty frame losses.

Ensuring low energy consumption is a crucial issue in underwater communications, since battery replacement may be difficult and expensive in these scenarios. We analyze in this paper the energy consumption of a multi-hop underwater acoustic network (UWAN) employing fountain codes. Moreover, in order to reduce this energy consumption we optimize the modulation order assuming differential phase-shift keying ( $M$ -DPSK), as well as the number of hops. We investigate the required number of fountain-encoded packets for different modulation orders. Our results show that, by optimizing the modulation order, the number of hops and the number of fountain packets, we can obtain important energy savings, especially for long distances. In addition, with the proposed scheme the energy consumption decreases significantly compared to the case without fountain codes, reaching up to 40% of savings.

International audience; In this paper, we address the problem of building adaptive network coding coefficients under dynamic network conditions (e.g., varying link quality and changing number of relays). In existing linear network coding solutions including deterministic network coding and random linear network coding, coding coefficients are set by a heuristic or randomly chosen from a Galois field with equal probability, which can not adapt to dynamic network conditions with good decoding performance. We propose INCdeep, an adaptive Intelligent Network Coding with Deep Reinforcement Learning. Specifically, we formulate a coding coefficients selection problem where network variations can be automatically and continuously expressed as the state transitions of a Markov decision process (MDP). The key advantage is that INCdeep is able to learn and dynamically adjust the coding coefficients for the source node and each relay node according to ongoing network conditions, instead of randomly. The results show that INCdeep has generalization ability that adapts well in dynamic scenarios where link quality is changing fast, and it converges fast in the training process. Compared with the benchmark coding algorithms, INCdeep shows superior performance, including higher decoding probability and lower coding overhead through simulations and experiments.

Securing wireless communication using different techniques has been an interesting topic for research, especially with the increasing demand on fast and secure transmission. In this research, we conduct a performance analysis on a UAV based system in the presence of a ground eavesdropper/jammer operating in full-duplex mode, where a legitimate transmitter located on ground is securing its message to the UAV using fountain coding technique at the physical layer level. A performance analysis is conducted based on the intercept probability and quality of service violating probability, which are two parameters related to fountain coding techniques. The theoretical results are verified via simulation by considering the movement nature of the UAV and the transmission power of the ground stations. Scopus

In this paper upper and lower bounds on the probability of decoding failure under maximum likelihood decoding are derived for different (nonbinary) Raptor code constructions. In particular four different constructions are considered; (i) the standard Raptor code construction, (ii) a multi-edge type construction, (iii) a construction where the Raptor code is nonbinary but the generator matrix of the LT code has only binary entries, (iv) a combination of (ii) and (iii). The latter construction resembles the one employed by RaptorQ codes, which at the time of writing this article represents the state of the art in fountain codes. The bounds are shown to be tight, and provide an important aid for the design of Raptor codes., Comment: Accepted in IEEE Transactions on Information Theory

Cloud storage has gained increasing attention from the industry and research communities with concerns about data stored in cloud computing environments, despite its many advantages. The reasons come from economic viability to the latency along with behavioral changes that may affect the applications that use data stored remotely. Among those challenges, there is the problem of ensuring the integrity and retrievability of users' data in the cloud. Several schemas have been proposed: proof of data possession (PDP), proof of retrievability (PoR), and proof of ownership (PoW) that differ on the approach to guarantee the effective retrieval of data stored remotely. In this paper, a novel PoR protocol is proposed: hyper-scalability, availability, and integrity layer (Hy-SAIL), where a new PoR scheme adds higher availability to data stored and a flexible manner to perform integrity checks. It is demonstrated that Hy-SAIL leads to an efficient and scalable cryptographic system that meets near-optimal bounds in terms of communication and storage complexities. It is also proposed a new adversarial model that aggregates the main functionalities of a realistic adversary in cloud computing environments. Hy-SAIL operates on data that are not affected by any kind of incremental change or update, which is the characteristic of various file types stored in clouds, such as stored video and audio streams. When compared to other systems, such as HAIL, Hy-SAIL is more scalable and efficient. The results collected with an unoptimized implementation of Hy-SAIL point to a better perspective than other approaches.

In this paper, we propose new serial decoding of Luby transform (LT) codes over additive white Gaussian noise channels. LT encoder generates a potentially limitless number of encoded packets, and the decoder incrementally collects the packets to ensure successful recovery of the information. In the proposed algorithm, the newly coming code nodes are the first to pass the messages, and it is their neighboring source nodes that will receive these input messages and update their output messages; then, the next neighboring code nodes that have not been covered are to be included in the updating group; in this greedy way, the message propagation is conducted from neighbors to neighbors. The analysis demonstrates that the proposed algorithm has a faster convergence speed than the conventional ones, and simulation shows that it has an effective bit error rate performance.

Radio blackout due to a plasma sheath during reentry has attracted much attention over several decades. However, radio blackout has long puzzled the aerospace industry and has not yet been completely resolved. A communication method based on adaptive classification fountain code is proposed to improve the transmission reliability of important information during a spacecraft's reentry. According to the deterioration of the plasma sheath channel, the classification parameters of the source information are adjusted to protect the most important information. This method allows the reliable transmission of the most important information. The deterioration of the communication quality of the plasma sheath channel is detected from the voltage standing wave ratio of the transmitting antenna in real time. The simulation results show that the transmission reliability of important information almost doubles when using the transmission method of adaptive classification fountain code. In contrast to the traditional communication method, the proposed method can be applied to TT&C (telemetry, tracking, and command) and communication of reentry vehicles and near-space hypersonic vehicles in the future, reducing the interruption time of communication blackout.

In this paper, a transmission redundancy optimization strategy for fountain codes that uses an adaptive filtering technique as well as recent results concerning the upper bound of the source packet erasure probability for fountain codes over finite fields is proposed. The performance of the proposed strategy was evaluated in static and simulated realistic underwater acoustic channel environments simulated by a recently proposed statistical underwater acoustic channel model. The goal of this investigation is to improve the communication efficiency of underwater acoustic sensor networks that use communication protocols based on fountain codes. The performance of the proposed strategy is compared with the recently proposed approaches of discrete stochastic approximation (DSA) and the joint power and rate control (JPR) schemes. The simulation results demonstrate that the strategy proposed in this paper performs better than the existing schemes in both static and simulated realistic environments. The proposed strategy is 4.75 times better than the DSA in the static convergence performance evaluation. Further analysis shows that in the presence of a simulated realistic environment, compared to DSA and JPR, the strategy proposed in this paper reduces the overall transmission redundancy by approximately 11.4% and 52.6%, respectively. It also improves the average communication efficiency by 1.3% and 12.5%, respectively. The average optimization error relative to optimal redundancy is improved by approximately 62.1% and 92.5%, respectively. These numerical results are obtained by employing the specific simulation parameters and the simulated environment mentioned in this paper.

The transmission of video files in Vehicular Adhoc Networks (VANETs) has become very prevalent as commuters prefer video data during travel. The delay with which the data is received becomes very significant as video packets received after their scheduled deadlines become useless. The performance of the network may significantly be reduced on such packet drops especially with mobile networks. This work aims at the reduction of end to end delay of video packets by applying the two techniques- Network Coding (NC) and RaptorQ (RQ) codes. The techniques are implemented in four VANET scenarios and an extensive analysis is done by varying the packet sizes during the transmission of three files of various sizes. The End to End Delay (EED) and Packet Delivery Ratio (PDR) are measured and plotted for all scenarios. The results show the influence of packet size on these parameters considered and the suitability of the techniques applied. The observations also show that RQ proves better for smaller files and NC suits better when the file size increases.

In this paper, we propose and evaluate the performance of fountain codes (FCs) based secure transmission protocols in multiple-input-multiple-output (MIMO) wireless systems, in presence of a passive eavesdropper. In the proposed protocols, a source selects its best antenna to transmit fountain encoded packets to a destination that employs selection combining (SC) or maximal ratio combing (MRC) to enhance reliability of the decoding. The transmission is terminated when the destination has a required number of the encoded packets to reconstruct the original data of the source. Similarly, the eavesdropper also has the ability to recover the source data if it can intercept a sufficient number of the encoded packets. To reduce the number of time slots used, the source can employ non-orthogonal multiple access (NOMA) to send two encoded packets to the destination at each time slot. For performance analysis, exact formulas of average number of time slots (TS) and intercept probability (IP) over Rayleigh fading channel are derived and then verified by Monte-Carlo simulations. The results presented that the protocol using NOMA not only reduces TS but also obtains lower IP at medium and high transmit signal-to-noise ratios (SNRs), as compared with the corresponding protocol without using NOMA.

In this paper we investigate the performance of caching schemes based on fountain codes in a heterogeneous satellite network. We consider multiple cache-aided hubs which are connected to a geostationary satellite through backhaul links. With the aimof reducing the average number of transmissions over the satellite backhaul link, we propose the use of a caching scheme based on fountain codes. We derive a simple analytical expression of the average backhaul transmission rate and provide a tightupper bound on it. Furthermore, we show how the performance of the fountain code based caching scheme is similar to that of a caching scheme based on maximum distance separable codes., Comment: arXiv admin note: substantial text overlap with arXiv:1807.05619

This paper evaluates intercept probability (IP) of a cooperative cognitive radio network. Using Fountain codes, a secondary source continuously generates encoded packets, and sends them to secondary destination and relay nodes that attempt to receive a sufficient number of the encoded packets for recovering the source data. If the relay can sufficiently collect the packets before the destination, it replaces the source to transmit the encoded packets to the destination. Also in the secondary network, a passive eavesdropper attempts to illegally receive the packets sent by the source and relay nodes, and if it can accumulate enough encoded packets, the source data is intercepted. To enhance secrecy performance, in terms of IP, a cooperative jammer is used to transmit noises on the eavesdropper. We also propose a simple transmit power allocation method for the secondary transmitters such as source, relay and jammer so that outage performance of a primary network is not harmful. We derive an exact closed-form expression of IP over Rayleigh fading channel, and verify it by performing Monte-Carlo simulations.

Degree distribution plays a great role in the performance of Luby transform codes. Typical degree distributions such as ideal soliton distribution and robust soliton distribution are easy to implement and widely used. Nevertheless, their adaptabilities are not always outstanding in various code lengths, especially in the case of short length. In this paper, our work is to optimize degree distributions for the short-length LT codes by using swarm intelligence algorithm, considering its conceptual simplicity, high efficiency, flexibility, and robustness. An optimization problem model based on sparse degree distributions is proposed in the first place. Then, a solution on the basis of an enhanced chicken swarm optimization algorithm, termed as ECSO, is designed for the problem. In ECSO, substitution of bottom individuals, revision of chicks’ update equation, and introduction of differential evolution are designed to enhance the ability of optimization. Simulation comparisons show that the proposed solution achieves much better performance than two other swarm intelligence-based solutions.

Prolonging the lifetime and providing a reliable communication performance of underwater acoustic sensor network (UASN) nodes are challenging issues due to the severe nature of the underwater acoustic channel. Traditional methods that ensure the reliability of communications by using retransmissions such as automatic repeat request (ARQ) negatively affect the lifetime of UASNs since they are not energy efficient. Fountain codes (FC), which is a forward error correction technique, aim to solve the energy efficiency problem of ARQ method by transmitting the original data frame and some redundant frames together in the network without using retransmissions. The number of redundant frames to be transmitted is dynamically adjusted to achieve a predetermined reliability criterion at the receiver node. In this study, an integer linear programming (ILP) method is proposed which maximizes the lifetime of UASNs by using FCs. Our results show that FC method provides better performance metrics (e.g., network lifetime, end-to-end delay, and energy consumption) than the traditional ARQ method.

In this paper, we propose a rateless, three-stage, two-way multiply-and-forward (MF) relaying system over the Rayleigh flat fading channel, where two source nodes communicate with each other through a relay node and all nodes work on half-duplex and time-division mode. We thoroughly analyze the signals during all three stages in the proposed MF system and derive the closed-form symbol error rate (SER) expressions for an uncoded MF-two-way relay network (MF-TWRN). Furthermore, we provide the equivalent point-to-point fading channel model, which is employed to carry out the asymptotic performance analysis. We finally put forth an optimization model for the MF-TWRN with fountain codes. Simulation results show that our optimized degree distribution can provide outstanding performance for the MF-TWRN compared to those in the literature.

We propose a coded distributed computing scheme based on Raptor codes to address the straggler problem. In particular, we consider a scheme where each server computes intermediate values, referred to as droplets, that are either stored locally or sent over the network. Once enough droplets are collected, the computation can be completed. Compared to previous schemes in the literature, our proposed scheme achieves lower computational delay when the decoding time is taken into account., Accepted at the 2018 International Symposium on Turbo Codes & Iterative Information Processing, Hong Kong

We address the use of linear randon fountain codes caching schemes in a heterogeneous satellite network. We consider a system composed of multiple hubs and a geostationary Earth orbit satellite. Coded content is memorized in hubs' caches in order to serve immediately the user requests and reduce the usage of the satellite backhaul link. We derive the analytical expression of the average backhaul rate, as well as a tight upper bound to it with a simple expression. Furthermore, we derive the optimal caching strategy which minimizes the average backhaul rate and compare the performance of the linear random fountain code scheme to that of a scheme using maximum distance separable codes. Our simulation results indicate that the performance obtained using fountain codes is similar to that of maximum distance separable codes.

This article describes and evaluates the performance of DETIboot, a system conceived for securely deploying temporary Linux systems into countless receiving hosts close enough to a Wi-Fi DETIboot server. This system was created with the ultimate goal of installing, in numerous students’ laptops and just-in-time, special Linux distributions for being temporarily used in practical classes. In this document we present an overview of DETIboot, a comprehensive description of the coding used in the broadcast communication and a detailed performance evaluation in a spacious auditorium. This evaluation did not involve security features to reduce the amount of variables influencing the final results. However, previous experiments allow us to extrapolate a maximum of 5% increase in the download time due to security. On average, it took us 50.1 s to download a 225 MiB Slax Linux over 802.11g, taking on average 15% more time than the theoretical lower bound of our setup (43.4 s). The influence of the position of receivers in the auditorium was not prominent. published

This paper investigates the system performance evaluation framework of systematic rateless-coded (SRCed) transmissions for user experience in future 5G systems. To this end, we define the application-layer information loss ratio (AILR), i.e., the ratio of the number of unsuccessfully decoded messages to that of the total transmitted messages, as a system performance index from the perspective over network application layer, which can be used as an evaluation framework on the users' experience in the viewpoint of 5G transmission systems. By using the integer partition theory, we analytically derive some theoretical results and then obtain an exact expression of the AILR for SRCed transmissions. Simulation and numerical results are provided to demonstrate the validness of our analytical results, which also show that the SRCed transmission achieves much better system performance than existing coded transmission methods in terms of AILR. Moreover, by using our presented AILR expression, the proper system configuration can be easily determined without a heavy burden of Monte Carlo simulations. It also illustrates some inherent relationships between system parameters by using SRCed transmission on application layer, which can be easily carried out to achieve a better performance in the viewpoint of users' experiences. First, for a given channel condition, the larger the message length is, the smaller the ratio of the message length to the source symbol length should be selected. Second, for a given message length, the better the channel condition is, the larger the ratio of the message length to the source symbol length should be selected.

We consider a multihop network where a source node must reliably deliver a set of data packets to a given destination node. To do so, the source applies a fountain code and floods the encoded packets through the network, until they reach their destination or are lost in the process. We model the probability that the destination can recover the original transmissions from the received coded packets as a function of the network topology and of the code redundancy, and show that our analytical results predict the outcome of simulations very well. These results are employed to design distributed forwarding policies that achieve a good tradeoff between the success probability and the total number of transmissions required to advance a packet towards the destination. We finally develop in detail the case where intermediate relays can inject additional redundancy in the network, provided that they have successfully decoded the source packets. pub

In this paper we analyze LT and Raptor codes under inactivation decoding. A first order analysis is introduced, which provides the expected number of inactivations for an LT code, as a function of the output distribution, the number of input symbols and the decoding overhead. The analysis is then extended to the calculation of the distribution of the number of inactivations. In both cases, random inactivation is assumed. The developed analytical tools are then exploited to design LT and Raptor codes, enabling a tight control on the decoding complexity vs. failure probability trade-off. The accuracy of the approach is confirmed by numerical simulations., Accepted for publication in IEEE Transactions on Communications

We propose a percolation based M2M networking architecture and its data transmission method. The proposed network architecture can be server free and router free, which allows us to operate routing efficiently with percolations based on six degrees of separation theory in small world network modeling. The data transmission can be divided into two phases routing and data transmission phase. In the routing phase, probe packets will be transmitted and forwarded in the network thus path selections are performed based on small world strategy. In the second phase, the information will be encoded, say, with the fountain codes, and transmitted using the paths selected at the first phase. In such a way, an efficient routing and data transmission mechanism can be built, allowing us to construct a low cost, flexible and ubiquitous network. Such a networking architecture and data transmission can be used in many M2M communications, such as the stub network of internet of things, and deep space networking, and so on. Soujanya Ambala | Dr. Srinivas Ambala | Sreedhar Ambala "M2M Networking Architecture for Data Transmission and Routing" Published in International Journal of Trend in Scientific Research and Development (ijtsrd), ISSN: 2456-6470, Volume-1 | Issue-1 , December 2016, URL: https://www.ijtsrd.com/papers/ijtsrd79.pdf Paper URL: http://www.ijtsrd.com/computer-science/computer-network/79/m2m-networking-architecture-for-data-transmission-and-routing/soujanya-ambala

A novel approach to provide unequal error protection (UEP) using rateless codes over erasure channels, named Expanding Window Fountain (EWF) codes, is developed and discussed. EWF codes use a windowing technique rather than a weighted (non-uniform) selection of input symbols to achieve UEP property. The windowing approach introduces additional parameters in the UEP rateless code design, making it more general and flexible than the weighted approach. Furthermore, the windowing approach provides better performance of UEP scheme, which is confirmed both theoretically and experimentally. A novel approach to provide unequal error protection (UEP) using rateless codes over erasure channels, named Expanding Window Fountain (EWF) codes, is developed and discussed. EWF codes use a windowing technique rather than a weighted (non-uniform) selection of input symbols to achieve UEP property. The windowing approach introduces additional parameters in the UEP rateless code design, making it more general and flexible than the weighted approach. Furthermore, the windowing approach provides better performance of UEP scheme, which is confirmed both theoretically and experimentally.

In this contribution, we consider the application of Digital Fountain (DF) codes to the problem of data transmission when side information is available at the decoder. The side information is modelled as a "virtual" channel output when original information sequence is the input. For two cases of the system model, which model both the virtual and the actual transmission channel either as a binary erasure channel or as a binary input additive white Gaussian noise (BIAWGN) channel, we propose methods of enhancing the design of standard non-systematic DF codes by optimizing their output degree distribution based on the side information assumption. In addition, a systematic Raptor design has been employed as a possible solution to the problem. ©2008 IEEE.

In this paper q-ary Raptor codes under ML decoding are considered. An upper bound on the probability of decoding failure is derived using the weight enumerator of the outer code, or its expected weight enumerator if the outer code is drawn randomly from some ensemble of codes. The bound is shown to be tight by means of simulations. This bound provides a new insight into Raptor codes since it shows how Raptor codes can be analyzed similarly to a classical fixed-rate serial concatenation., Accepted for publication in Proc. of IEEE Globecom 2017

In this paper, we investigate trade-off between security and reliability of Fountain codes (FCs) based low-energy adaptive clustering hierarchy (LEACH) networks, where the encoded packets are sent to the destination by using a cluster-based multi-hop transmission scheme with the assistance of cluster heads (CHs). With presence of an eavesdropper, a cooperative harvest-to-jam technique is employed to reduce the quality of the eavesdropping channels. Particularly, each cluster randomly selects a cluster node that generates artificial noises on the eavesdropper. For performance evaluation, we derive exact closed-form expressions of outage probability (OP) and intercept probability (IP) over Rayleigh fading channels. We then perform Monte Carlo simulations to verify the theoretical results, and compare the performance of the proposed scheme with that of the conventional LEACH scheme without using the jamming technique.

We introduce a novel packet retransmission technique which improves the efficiency of automatic retransmission query (ARQ) protocols in the context of satellite broadcast/multicast systems. The proposed coded ARQ technique, similarly to fountain coding, performs transmission of redundant packets, which are made by linear combinations of the packets composing the source block. Differently from fountain codes, the packets for the linear combinations are selected on the basis of the retransmission requests coming from the user terminals. The selection is performed in a way that, at the terminals, the source packets can be recovered iteratively by means of simple back-substitutions. This work aims at providing a simple and efficient alternative to reliable multicast protocols based on erasure correction coding techniques.

This monograph describes the theory behind Raptor codes, and elucidates elements of the processes behind the design of two of the most prominent members of this class of codes: R10 and RaptorQ (RQ). R10 has already been adopted by a number of standards' bodies, and RQ is in the process of entering various standards at the time of writing of this monograph. The monograph starts with the description of some of the transmission problems, which inspired the invention of Fountain codes. Thereafter, Luby transform codes (LT codes) and Raptor codes are introduced and insights are provided into their design. These codes are currently the most efficient realizations of Fountain codes. Different algorithms are introduced for encoding and decoding various versions of these codes, including their systematic versions. Moreover, a hybrid decoding algorithm called "inactivation decoding" is introduced, which is an integral part of all modern implementations of Raptor codes. The R10 and RQ codes have been continued and will continue to be adopted into a number of standards and thus there are publicly available specifications that describe exactly how to implement these codes. However, the standards' specifications provide no insight into the rationale for the design choices made. One of the primary purposes of this document is to provide this design rationale. We provide results of extensive simulations of R10 and RQ codes to show the behavior of these codes in many different scenarios.

Raptor code ensembles with linear random outer codes in a fixed-rate setting are considered. An expression for the average distance spectrum is derived and this expression is used to obtain the asymptotic exponent of the weight distribution. The asymptotic growth rate analysis is then exploited to develop a necessary and sufficient condition under which the fixed-rate Raptor code ensemble exhibits a strictly positive typical minimum distance. The condition involves the rate of the outer code, the rate of the inner fixed-rate Luby Transform (LT) code and the LT code degree distribution. Additionally, it is shown that for ensembles fulfilling this condition, the minimum distance of a code randomly drawn from the ensemble has a linear growth with the block length. The analytical results can be used to make accurate predictions of the performance of finite length Raptor codes. These results are particularly useful for fixed-rate Raptor codes under maximum likelihood erasure decoding, whose performance is driven by their weight distribution., Comment: Accepted for publication in the IEEE Journal on Selected Areas in Communications

The File Broadcast Protocol (FBP) was developed as a part of the DETIboot system. DETIboot allows a host to broadcast an operating system image through an 802.11 wireless network to an arbitrary number of receivers. Receivers can load the image and immediately boot a Linux live session. The initial version of FBP had no security mechanisms. In this paper we present an authentication protocol developed for FBP that ensures a correct file distribution from the intended source to the receivers. The performance evaluations have shown that, with the best operational configuration tested, the file download time is increased by less than 5%.

We provide two analytical tools to model the inactivation decoding process of LT codes. First, a model is presented which derives the expected number of inactivations occurring in the decoding process of an LT code. This analysis is then extended allowing the derivation of the distribution of the number of inactivations. The accuracy of the method is verified by Monte Carlo simulations. The proposed analysis opens the door to the design of LT codes optimized for inactivation decoding., Comment: Presented at the 53rd Annual Allerton Conference on Communication, Control, and Computing, 2015

We present a simple model of inactivation decoding for LT codes which can be used to estimate the decoding complexity as a function of the LT code degree distribution. The model is shown to be accurate in variety of settings of practical importance. The proposed method allows to perform a numerical optimization on the degree distribution of a LT code aiming at minimizing the number of inactivations required for decoding., 6 pages, 7 figures

We present within this work recent advances on packet-level coding for a reliable multicast via satellite, based on the adoption of non-binary fountain codes, discussing design and implementation challenges. In particular, we describe the integration of fountain codes on two laboratory demonstrator systems and we provide a finite length encoding/decoding complexity analysis. Based on numerical results, we assess the performance improvement, in terms of decoding failure rate, obtained by moving to higher order Galois fields and we compare, in terms of required retransmissions, a scheme based on non-binary fountain codes to a scheme based on the traditional Selective Repeat Automatic Repeat reQuest (SR-ARQ) protocol. In conclusion, the results show the superiority of non-binary fountain codes with respect to traditional schemes.

International audience; This paper concentrates on the proper use of fountain codes for the transmission of sporadic data in a wireless sensor network (WSN). Fountain codes offer great perspectives for the self-organization of WSNs: they self adapt to the channel error rate without control packets. Deploying fountain codes in a WSN raises two problems. First, the size of the data transmitted by a sensor is small in comparison to the size usually considered with fountain codes. Second, WSNs mostly rely on multi-hop transmissions. It implies a non null transmission duration for the end-to-end acknowledgement of the reception. During this period of time, the source is still transmitting useless packets, creating a specific overhead we define as the overflow. This paper brings the overflow problem to light and analyses its impact on the network performance. Our work can be viewed as the networking counterpart of the results presented by Pakzad et al. at ISIT 2005 applied to WSNs.

We propose two new protocols based on physical layer network coding for collision resolution in multiple access networks.When a collision occurs the receiver decodes the sum of the collided packets and after a number of transmissions, equal to or slightly higher than the number of original packets, it can recover all of them. One of the proposed protocols based on fountain codes can resolve collisions by sending out just one acknowledgement (ACK), thus being particulary suited to networks with large round trip delays such as satellite networks. We carry out a comparison of the average delay achieved by the proposed schemes with other access techniques, and show how the performance can be improved with little coordination at the receiver.

Application-layer forward error correction (FEC) is used in many multimedia communication systems to address the problem of packet loss in lossy packet networks. One powerful form of application-layer FEC is unequal error protection which protects the information symbols according to their importance. We propose a method for unequal error protection with a Fountain code. When the information symbols were partitioned into two protection classes (most important and least important), our method required a smaller transmission bit budget to achieve low bit error rates compared to the two state of the art techniques. We also compared our method to the two state of the art techniques for video unicast and multicast over a lossy network. Simulations for the scalable video coding (SVC) extension of the H.264/AVC standard showed that our method required a smaller transmission bit budget to achieve high quality video. DFG Research Training Group GK- 1042

International audience; This paper evaluates the performance of two seminal rateless erasure codes, LT Codes and Online Codes. Their properties make them appropriate for coping with communication channels having an unbounded loss rate. They are therefore very well suited to peer-to-peer systems. This evaluation targets two goals. First, it compares the performance of both codes in different adversarial environments and in different application contexts. Second, it helps understanding how the parameters driving the behavior of the coding impact its complexity. To the best of our knowledge, this is the first comprehensive study facilitating application designers in setting the optimal values for the coding parameters to best fit their P2P context.

Fountain codes are a robust solution for data multicasting to a large number of receivers which experience variable channel conditions and different packet loss rates. However, the standard fountain code design becomes inefficient if all receivers have access to some side information correlated with the source information. We focus our attention on the cases where the correlation of the source and side information can be modelled by a binary erasure channel (BEC) or by a binary input additive white Gaussian noise channel (BIAWGNC). We analyse the performance of fountain codes in data multicasting with side information for these cases, derive bounds on their performance and provide a fast and robust linear programming optimization framework for code parameters. We demonstrate that systematic Raptor code design can be employed as a possible solution to the problem at the cost of higher encoding/decoding complexity, as it reduces the side information scenario to a channel coding problem. However, our results also indicate that a simpler solution, non-systematic LT and Raptor codes, can be designed to perform close to the information theoretic bounds. Fountain codes are a robust solution for data multicasting to a large number of receivers which experience variable channel conditions and different packet loss rates. However, the standard fountain code design becomes inefficient if all receivers have access to some side information correlated with the source information. We focus our attention on the cases where the correlation of the source and side information can be modelled by a binary erasure channel (BEC) or by a binary input additive white Gaussian noise channel (BIAWGNC). We analyse the performance of fountain codes in data multicasting with side information for these cases, derive bounds on their performance and provide a fast and robust linear programming optimization framework for code parameters. We demonstrate that systematic Raptor code design can be employed as a possible solution to the problem at the cost of higher encoding/decoding complexity, as it reduces the side information scenario to a channel coding problem. However, our results also indicate that a simpler solution, non-systematic LT and Raptor codes, can be designed to perform close to the information theoretic bounds.

International audience; Ad hoc networks are one operational mode of IEEE 802.11 Wireless Local Area Networks (WLANs) in which users form themselves the network and act as routers to one another. When the density of such a network is high, capacity becomes limited by the interference resulting from the collisions between simultaneously transmitted packets. Interference gets even worse in the case of reliable transport based on TCP as data packets interfere with the acknowledgements sent back in the reverse direction. In this context, the term Ad Hoc Horizon refers to the number of nodes and hops beyond which TCP performance is no longer satisfactory in terms of throughput. We investigate in this work this Horizon in the presence of a transport scheme based on Fountain Codes instead of TCP. Fountain codes are rateless, low complexity codes, which allow for open-loop reliable transport, without acknowledgements in the reverse direction; this would in turn decrease interference and increase the Horizon. Indeed, our results show a Horizon almost twice as large as that obtained with TCP

—In this contribution, duals of fountain codes are introduced and their use for lossy source compression is investigated. It is shown both theoretically and experimentally that the source coding dual of the binary erasure channel coding problem, binary erasure quantization, is solved at a nearly optimal rate with application of duals of LT and raptor codes by a belief propagation-like algorithm which amounts to a graph pruning procedure. Furthermore, this quantizing scheme is rate adaptive, i.e., its rate can be modified on-the-fly in order to adapt to the source distribution, very much like LT and raptor codes are able to adapt their rate to the erasure probability of a channel. In this contribution, duals of fountain codes are introduced and their use for lossy source compression is investigated. It is shown both theoretically and experimentally that the source coding dual of the binary erasure channel coding problem, binary erasure quantization, is solved at a nearly optimal rate with application of duals of LT and raptor codes by a belief propagation-like algorithm which amounts to a graph pruning procedure. Furthermore, this quantizing scheme is rate adaptive, i.e., its rate can be modified on-the-fly in order to adapt to the source distribution, very much like LT and raptor codes are able to adapt their rate to the erasure probability of a channel.

Date of Conference: 7-9 May 2007 Conference Name: 3DTV Conference, IEEE 2007 The transmission of fully compatible H.264/AVC multi-view video coded streams over packet erasure networks is examined. Macroblock classification into unequally important slice groups is considered using the Flexible Macroblock Ordering (FMO) tool of H.264/AVC Systematic LT codes are used for error protection due to their low complexity and advanced performance. The optimal slice grouping and channel rate allocation are jointly determined by an iterative optimization algorithm based on dynamic programming. The experimental evaluation clearly demonstrates the validity of the proposed method.

An online fountain code is defined as a fountain code for which an optimal encoding strategy can be found efficiently given any instantaneous decoding state. This property is important for data distribution in practical networks. In this paper, we formalize the problem of online fountain code construction, and propose new online fountain codes that outperform known ones in having factor 3–5 lower redundancy overhead. The bounding of the code overhead is carried out using the analysis of the dynamics of random-graph processes.

Application Layer Forward Error Correction (AL-FEC) is an innovative way to provide reliability in mobile broadcast systems. Conventional data such as multimedia files or multimedia streams are extended with repair information which can be used to recover lost data at the receiver. AL-FEC is integrated into content delivery protocols (CDPs) to support reliable delivery. Several standardization committees such as 3GPP and DVB have recognized the importance of AL-FEC and have standardized Raptor codes as the most powerful FEC codes to be used for such applications. The major characteristics of Raptor codes are channel efficiency, low-complexity, and flexibility. An important consideration when using application layer codes is system integration. With the right system design including AL-FEC, the efficiency and/or quality of delivery services can be significantly enhanced. This work shows these benefits in selected use cases, specifically focussing on 3G based multimedia broadcasting within the MBMS standard.

Our aim in this paper is to study the performance of broadcasting algorithms for underwater acoustic sensor networks (UWASNs). The targeted scenario is very simple; we consider a source (the initiator of the broadcast transmission) and a number of nodes randomly placed within a given geographical area. For an efficient broadcast transmission we advocate the use of a hybrid ARQ scheme, where Fountain Codes (FC) are exploited to enhance the efficiency of the data dissemination process in the face of poor and possibly unknown channel conditions. FC codes, being rateless, are in fact able to adapt to diverse error rates and correct packet losses on the fly through the transmission of additional redundancy packets. The main contribution of this paper is a mathematical model to characterize the performance of fountain codes as applied to broadcasting in underwater networks. Our analysis allows us to find performance metrics such as transmission delay, reliability (e.g., percentage of covered users) and power consumption. Relevant tradeoffs are highlighted and quantified; in particular the implications of transmission power on covered distance, rate and delay are discussed. Even though we do not propose a practical broadcasting protocol here, the results and tradeoffs we obtain are essential to a proper design of practical schemes.

Digital media have become an integral part of modern lives. Whether surfing the web, making a wireless phone call, watching satellite TV, or listening to digital music, a large part of our professional and leisure time is filled with all things digital. The replacement of analog media by their digital counterparts and the explosion of Internet use has had a perhaps un-intended consequence. Whereas analog media were previously replaced by digital media mostly only to preserve quality, the existence of high speed computer networks makes digital media available to potentially anyone, anywhere, and at any time. This possibility is the basis for modern scientific and economic developments centered around the distribution of digital data to a worldwide audience. The success of web sites like Apple’s i Tunes store or You Tube is rooted in the marriage of digital data and the Internet. Reliable transport of digital media to heterogeneous clients becomes thus a central and at time critical issue. Receivers can be anywhere and they may be connected to networks with widely differing fidelities. In this paper we will give a soft introduction into a new method for solving the data distribution problem. We take four fundamental data transmission problems as examples: delivery of data from one sender to one receiver over a long distance, delivery of data from one sender to multiple receivers, delivery of the same data from multiple senders to one receiver, and finally, delivery of data from many senders to many receivers. Examples of such data transmission scenarios are abundant: the first one is encountered whenever a large piece of data is downloaded from a distant location; satellite data distribution, or distribution of data to mobile receivers is a prime example of the second scenario. The application space for the third example is emerging, and includes scenarios like disaster recovery: data is replicated across multiple servers and accessed simultaneously from these servers. A prime example for the fourth scenario is the popular peer-to-peer data distribution. We argue that current data transmission protocols are not adequate to solve these data distribution problems, and hence lack the ability to solve some of today’s and many of tomorrow’s data delivery problems. This is because these transmission protocols were designed at a time when the Internet was still in its infancy, and the problem of bulk data distribution was not high on the agenda. We then introduce fountain codes and show how they can be used to solve all of these data transmission problems at the same time. For a given piece of content, a fountain code produces a potentially limitless stream of data such that any subset of this data of size essentially equal to the original content is sufficient to recover the original data. Just like the case of filling a glass of water under a fountain where it does not matter which particular drops fill the glass, with a fountain code it does not matter which particular pieces of output data are received, as long as their cumulative size is right. We introduce a very simple, but inefficient, fountain code and refine it to LT-codes, the first class of efficient fountain codes, and then to Raptor codes, the state-of-the-art in this field. We discuss tools that allow us to design these fountains, and analyze their performance. We also briefly discuss Raptor codes that are standardized for various data transmission scenarios.