PaperlayerView exact revision on arXiv

Source-linked AI summary

Batched Sparse Codes

Shenghao Yang, Raymond W. Yeung

arXiv:1206.5365v2cs.IT

TL;DR

Packet-loss networks can benefit from network coding, but existing schemes may require computational and storage resources that grow with the number of transmitted packets. The paper introduces BATS codes, combining a fountain-code outer code with random linear network coding, and reports high rates alongside resource requirements designed to remain bounded at intermediate nodes.

  • Problem

    Network coding improves transmission over lossy networks but can impose computational, storage, and coding-vector costs that grow with the number of input packets.

  • Method

    BATS codes combine a fountain-code outer code with an inner code using random linear coding at intermediate network nodes.

  • Results

    0.8 packet per use is achieved with erasure codes on both links versus 0.64 packet per use for routing in the example network.

  • Takeaways & Limitations

    The paper targets network-coding devices with limited storage and computational capabilities while retaining high transmission rates and small overhead.

Abstract

from arXiv · show

Network coding can significantly improve the transmission rate of communication networks with packet loss compared with routing. However, using network coding usually incurs high computational and storage costs in the network devices and terminals. For example, some network coding schemes require the computational and/or storage capacities of an intermediate network node to increase linearly with the number of packets for transmission, making such schemes difficult to be implemented in a router-like device that has only constant computational and storage capacities. In this paper, we introduce BATched Sparse code (BATS code), which enables a digital fountain approach to resolve the above issue. BATS code is a coding scheme that consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code. It works with the inner code that comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capacities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. Almost capacity-achieving BATS code schemes are devised for unicast networks, two-way relay networks, tree networks, a class of three-layer networks, and the butterfly network. For general networks, under different optimization criteria, guaranteed decoding rates for the receiving nodes can be obtained.

I. INTRODUCTION

The introduction motivates network coding for packet-loss networks while highlighting the computational, storage, and overhead costs that make baseline schemes difficult to implement at scale. It frames the paper's goal as achieving high transmission rates with low source and destination complexity, constant intermediate-node resources, and small overhead.

  • Related approaches: Fountain codes offer ratelessness, universality, and low encoding and decoding complexity without feedback in routing networks.The source transmits coded packets, and a destination can decode after receiving slightly more than the number of input packets, regardless of which packets arrive.
  • Motivation: Network coding can achieve multicast capacity, and random linear combinations at source and intermediate nodes tolerate packet loss without per-link erasure codes.A destination decodes when it receives enough coded packets with linearly independent coding vectors.
  • Motivation: 0.8 packet per use is achievable with erasure codes on both links, compared with 0.64 packet per use for routing in the example network.The example considers links that each transmit one packet per use with packet loss rate 0.2.
  • Limitations of existing schemes: Baseline RLNC becomes difficult to implement for large input sets because its computational, storage, and coding-vector overheads grow with the number of packets.For K input packets, source encoding costs O(TK), an intermediate node may buffer K packets and perform O(TK) operations, and decoding costs O(K2 + TK) per packet.
  • Paper objective: The paper seeks a network-coding scheme suitable for devices with limited resources while retaining high transmission rate and small protocol and coding-vector overhead.The stated design goals include low source encoding and destination decoding complexity, constant intermediate-node computation and buffering, and high transmission rate.

A. Related Works

Prior approaches reduce network-coding complexity through chunks, feedback, restricted combinations, or fountain codes, but face scheduling, scalability, degree-distribution, or buffering limitations.

  • Chunk-based approaches: Chunk-based network coding reduces computational complexity and coding-vector overhead, but requires individually decoding many chunks.Sequential scheduling requires feedback and is not scalable for multicast, while random scheduling requires intermediate nodes to cache all chunks.
  • Chunk-based approaches: Chunked and Gamma codes use fixed-rate coding, so a given input size permits only a fixed number of generated chunks.
  • Fountain-code approaches: Fountain-code approaches avoid fixed rates, but intermediate coding changes packet degrees, complicating the degree distribution needed for belief-propagation decoding.Existing heuristics target special topologies or scenarios and are difficult to extend to general networks.
  • Resource constraints: Existing methods can require intermediate-node buffers that grow linearly with the number of transmitted packets, conflicting with constant-buffer operation.
  • Other approaches: Some alternatives constrain packet combinations or use feedback and specialized algebraic constructions, trading generality or scalability for lower overhead or complexity.Error-correction-based methods limit how many packets can be combined, while link-by-link feedback and permutation-matrix approaches address specific costs.

B. Our Solution

BATS codes combine a fountain-code outer code with random linear network coding as an inner code, preserving rateless operation while keeping intermediate-node requirements independent of file size.

  • Code construction: BATS codes combine a matrix-based fountain outer code with an inner linear network code that combines packets only within each batch.The inner code preserves batch degrees, enabling joint belief-propagation decoding.
  • Network operation: BATS codes suit networks supporting linear intermediate coding, tolerate packet loss and changing topology, and allow arbitrary batch-transfer rank deficiency.They also operate over small finite fields, unlike many random linear network-coding schemes requiring large fields.
  • Code construction: The design resolves chunk scheduling and fountain-degree issues: rateless batches remove sequential-scheduling feedback, while inner coding preserves batch degrees.
  • Complexity and storage: The encoding, recoding, buffering, decoding, and coding-vector requirements are constant in K: O(TM), O(TM), O(M), average O(M^2 + TM), and M symbols per packet, respectively.Here K is the total number of packets for transmission.
  • Achievable rates: Outer-code degree distributions are optimized from empirical rank distributions, and BP decoding has theoretical conditions plus numerically near-expected achievable rates.Finite-length performance can additionally use Gaussian elimination, inactivation decoding, finite-length analysis, and tuned precodes.

C. Organization of this Paper

The paper introduces BATS codes, analyzes their BP decoding and degree distributions, develops finite-length techniques, and demonstrates network applications before concluding.

  • Analysis: Sections II–IV introduce BATS codes, analyze BP decoding, and prove a necessary and sufficient recovery condition.
  • Optimization and rates: Section V studies degree-distribution optimization and achievable rates, including optimization for multiple rank distributions.
  • Finite-length design: Section VI discusses outer-code design and decoding techniques for good finite-length performance.
  • Applications and conclusion: Section VII gives network-use examples and inner-code designs, followed by concluding remarks in Section VIII.

II. BATS CODES

BATS codes represent packets as matrices over a finite field, supporting both set-based and matrix-based notation for input packets.

  • Each input packet is a column vector with T symbols over a finite field F of size q.
  • The input packets are juxtaposed to form a matrix B = [b1, b2, · · ·, bK].
  • The same notation treats B as both a packet matrix and a set, allowing membership and subset expressions such as bi ∈ B and B′ ⊂ B.

A. Encoding of Batches

The outer code generates batches by randomly selecting input contributors and applying generator matrices, while a Tanner graph represents these relationships.

  • Each batch is a set of M coded packets generated from a subset of input packets using a di×M generator matrix Gi.
  • A degree distribution Ψ samples each batch degree di, after which di input packets are chosen uniformly at random as contributors.
  • The generator matrices are analyzed as totally random matrices, although deterministic choices such as full-rank or MDS matrices are also described but not evaluated.
  • BATS can generate an unlimited number of batches, making it a rateless code for M > 1.
  • The Tanner graph connects K input variable nodes to batch check nodes, with edges indicating contributor relationships and each batch labeled by Gi.

B. Transmission of Batches

BATS transmits batches through an inner network code that preserves batch separation and models each batch as a linear operator channel.

  • Intermediate nodes recode only packets from the same batch, while packet loss and dynamic network topology remain allowed.
  • The inner code requires O(MT) finite-field operations per packet, independent of the number K of input packets.
  • Its coding-vector overhead is bounded by M, and batch separation means intermediate nodes need not retain all batches for coding.
  • The empirical transfer-matrix rank distribution determines the outer code’s maximum achievable rate and supports nearly optimal outer-code design.
  • The network maps each batch input Xi to output Yi = XiHi, where Hi is the transfer matrix known to the receiver.
  • With receiver-side channel-state information, the linear operator channel has a characterized capacity, and random linear codes can achieve its rank-based upper bound.

C. Belief Propagation Decoding

BATS decoding uses a bipartite graph and belief propagation to recover input packets through locally solvable batches and graph updates.

  • The decoding graph combines the outer and inner stages, associating each check node with the overall transfer matrix GiHi.
  • The proposed belief-propagation decoder avoids the high computational cost of Gaussian elimination when K is large.
  • A batch is decodable when rk(GiHi) equals its degree di, allowing its contributors to be recovered from Yi = BiGiHi.
  • After decoding a batch, the algorithm substitutes recovered packets into undecoded batches, reduces their degrees, and repeats until no check node remains decodable.
  • The paper’s main task is to analyze BATS-code performance under belief-propagation decoding.

D. Computational Complexity

The section derives encoding and decoding costs for BATS codes in finite-field operations, with complexity expressed using batch count, field dimension, and average degree.

  • Encoding n batches costs O(TM∑d dΨ_d) finite field operations and converges to O(TMnΨ̄) as n grows.Here Ψ̄ is the average degree.
  • The degree of a check node decreases during decoding, and a check node is decodable when its degree equals its rank.
  • The decoding process includes decodable-check-node processing and decoding-graph updates.
  • For large n, decoding complexity converges to O(nM^3+TMnΨ̄), with the second term usually dominant.The complexity analysis treats T and M as given while K and n tend to infinity.

E. Precoding

Precoding reduces the degree requirements of BATS codes by first applying an erasure code to input packets, then batch-encoding the resulting intermediate packets.

  • Without precoding, achieving reliable recovery requires expected degree at least c′K log(K) for some positive constant c′.
  • Precoding applies a traditional erasure code before batch encoding, producing intermediate input packets for the BATS encoder.
  • A precode can recover the original input packets after only a fixed fraction of intermediate input packets is recovered.
  • BP recovery of a fraction of the input packets requires a degree distribution with bounded maximum degree, while the resulting encoding and BP decoding complexities are O(TKM) and O(KM^2+TKM).

III. ANALYSIS OF BP DECODING

The BP-decoding analysis adapts differential-equation methods to BATS codes, whose decoding state must track both check-node degree and rank.

  • The paper adopts Wormald’s differential-equation approach, previously used to analyze Tornado and LDPC codes over erasure channels.
  • BATS decoding has a more complex criterion than fountain-code decoding because it depends jointly on each check node’s degree and rank.
  • The analysis tracks the evolution of check-node ranks in addition to their degrees during BP decoding.

A. Random Decoding Graph

The analysis models BATS decoding as a random degree-rank graph process and derives high-probability conditions for BP recovery and achievable rates.

  • A BATS instance uses i.i.d. check-node degrees, uniformly random variable-node connections, totally random generator matrices, and transfer matrices whose empirical ranks converge to h.
  • The random decoder repeatedly removes an edge whose check-node degree equals its rank, updates connected-node degrees and generator-matrix ranks, and stops when no such edge remains.
  • The degree-rank state process is represented by residual-graph edge counts, whose normalized values converge in probability to deterministic limits.
  • Theorem 1 gives a sufficient condition for BP decoding to succeed with high probability, including decoding at least η̄K variable nodes when ρ_0(τ)>0 throughout the relevant interval.
  • When ρ_0(τ)<0 at some point in the interval, the corresponding high-probability sufficient-success condition does not hold.
  • Under convergence of the empirical rank distribution to h, every rate at most η̄θ̂ is η̄-achievable by BATS codes using BP decoding.
  • Rates above θ̂ are not η̄-achievable, and increasing the maximum degree beyond D=⌈M/η⌉−1 does not improve the optimal value.

B. Achievable Rates

The achievable BATS-code rate is characterized through rank distributions and optimization bounds, with numerical results showing near-capacity performance for many distributions.

  • BP decoding recovers at least a fraction ¯η of the input packets asymptotically, yielding an achievable rate proportional to ¯ηˆθ.
  • Both the upper and lower bounds converge to κhκ for rank distributions concentrated at rank κ, matching the corresponding LOC capacity.
  • The optimization and numerical evaluation use rank-distribution sampling with M = 16 and q = 28 across 4 × 10^4 distributions.
  • For η = 0.005, more than 99.1% of tested rank distributions have normalized achievable value ˜θ > 0.96, while the minimum is 0.9057.The results show that smaller η increases ˆθ.
  • For the tested distributions, the normalized upper-bound ratio exceeds 0.999, placing the bound very close to capacity.

C. Optimizations for Multiple Rank Distributions

The paper optimizes BATS degree distributions for multiple destination rank distributions, balancing multicast performance, fairness, and universality.

  • A degree distribution optimized for one destination can perform poorly for another, motivating optimization over sets of rank distributions.
  • For three destination distributions, the optimized BATS code achieves a multicast rate very close to the minimum expected rank.
  • Solving the set-based optimization over B(µ) provides a guaranteed multicast rate for any rank-distribution set whose minimum expected rank is µ.
  • For M = 16, q = 256, and ¯η = 0.99, the guaranteed rate example is ¯ηˆθB(10) = 8.10.
  • Universality is limited: for M = 16, optimizing over all rank distributions yields a worst-case guaranteed rateless rate of ¯ηˆα = 0.5274.
  • Finite-block designs combine inactivation decoding and degree-distribution optimization, achieving average overhead below 3 packets per 1600 packets.

A. Line Networks

BATS codes use bounded per-node buffering in line networks while approaching min-cut rates asymptotically, with performance extending to several network topologies and applications.

  • A. Line Networks: Each intermediate node caches at most M −1 packets, and the resulting scheme is asymptotically optimal despite an initial delay.
  • A. Line Networks: For a line network with link erasure probability ϵ, Scheme 1 achieves a normalized rate very close to 1 −ϵ when M is sufficiently large.
  • A. Line Networks: For fixed network length, batch size trades off against achievable rate; with ϵ = 0.2, M approximately 32 is nearly rate-optimal for practical parameters.
  • A. Line Networks: Including coding-vector overhead, the normalized rate can approach (1 −M/T) times the relevant normalized expected-rank quantity.
  • Using sufficiently large batches, BATS codes approach min-cut capacity in unicast, tree, three-layer, and butterfly networks.
  • BATS coding also supports robust, storage-efficient batch caching in CDN networks and avoids rare-batch issues in peer-to-peer distribution.
Loading 1206.5365v2…