BATS Coding Scheme for Multi-hop Data Transport

2.4. Coding Parameters in DDP Packets

Here we provide an example of embedding the aforementioned BATS coding parameters into the DDP packets which will be used for recoding and decoding. A DDP can form a DDP packet using a coded packet by adding necessary information that can help to deliver the DPP packet to the next node, e.g., the DDP protocol version, addresses and session identifiers. We will not go into the details of formatting these fields in a DDP packet, but focus on how to format the coding parameters and the coded packet in a DDP packet.¶

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                K              | Mq  |          BID            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                  O                           T
      +-----------------------+-------------------------------+
      |   coefficient vector  |          coded data           |
      +-----------------------+-------------------------------+

3.1. Common Parts

The T octets of a source packets are treated as a column vector of T elements in GF(256). The O octets of coefficient vector are treated as a column vector of O elements in GF(q), where q=2 or q=256. Linear algebra and matrix operations over finite fields are assumed in this section.¶

For the two elements of GF(2), their multiplication corresponds to a logical AND operation and their addition is an logical XOR operation. An element of the field GF(256) can be represented by a polynomial with binary coefficients and degree lower or equal to 7. The addition between two elements of GF(256) is defined as the addition of the two binary polynomials. The multiplication between two elements of GF(256) is the multiplication of the two binary polynomials modulo a certain irreducible polynomial of degree 8, called a primitive polynomial. One example of such a primitive polynomial for GF(256) is:¶

• x⁸ + x⁴ + x³ + x² + 1¶

A common primitive polynomial should be specified for all the finite field multiplications over GF(256). Note that a binary polynomial of degree less than 8 can be represented by a binary sequence of 8 bits, i.e., an octet.¶

Suppose that a pseudorandom number generator Rand() which generates an unsigned integer of 32 bits is shared by both encoding and decoding. The pseudorandom generator can be initialized by Rand_Init(S) with seed S. When S is not provided, the pseudorandom generator is initialized arbitrarily. One example of such a pseudorandom generator is defined in RFC 8682 [RFC8682].¶

A function called BatchSampler is used in both encoding and decoding. The function takes two integers j and d as input, and generates an array idx of d integers and a d x M matrix G. The function first initializes the pseudorandom generator with j, sample d distinct integers from 0 to K-1 as idx, and sample d*M integers from 0 to 255 as G. See the pseudocode in Figure 6.¶

function BatchSampler(j,d)
    // initialize the pseudorandom generator by seed j.
    Rand_Init(j)
    // sample d distinct integers between 0 and K-1.
    for k = 0, ..., d-1 do
        r = Rand() % K
        while r already exists in idx do
            r = Rand() % K
        idx[k] = r

    // sample d x M matrix
    for r = 0, ..., d-1 do
        for c = 0,...,M-1 do
            G[r,c] = Rand() % 256

    return idx, G

3.2. Outer Code Encoder

Define a function called DegreeSampler that returns an integer d using the degree distribution DD. We expect that the empirical distribution of the returning d converges to DD(d) when d < K. One design of DegreeSampler is illustrated in Figure 7. Note that when K < MAX_DEG, the degree value returned by DegreeSampler does not exactly follow the distribution DD, which however would not affect the practical decoding performance for the outer decoder to be described in Section 3.4.¶

function DegreeSampler(j, DD)
    Let CDF be an array
    CDF[0] = 0
    for i = 1, ..., MAX_DEG do
        CDF[i] = CDF[i-1] + DD[i]
    Rand_Init(j)
    r = Rand() % CDF[MAX_DEG]
    for d = 1, ..., MAX_DEG do
        if r >= CDF[d] do
            return min(d,K)
    return min(MAX_DEG,K)

Let b[0], b[1], ..., b[K-1] be the K source packets. A batch with BID j is generated using the following steps.¶

• Obtain a degree d by calling DegreeSampler with input j.¶
• Obtain idx and G[j] by calling BatchSampler with input j and d.¶
• Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d-1]]). Form the batch X[j] = B[j]*G[j], whose dimension is T x M.¶
• Form the TO x M matrix Xr[j], where the first O rows of Xr[j] form the M x M identity matrix I with entries in GF(q), and the last T rows of Xr[j] is X[j].¶

See the pseudocode of the batch generating process in Figure 8.¶

function GenBatch(j)
    d = DegreeSampler(j)
    (idx, G) = BatchSampler(j,d)
    B = (b[idx[0]], b[idx[i]], ..., b[idx[d-1]])
    X = B * G
    Xr = [I; X]
    return Xr

3.3. Inner Code Encoder (Recoder)

In general, the inner code of a BATS code comprises (random) linear network coding applied on the coded packets belonging to the same batch. The recoded packets have the same BID. Suppose that coded packets xr[i], i = 0, 1, ..., r-1, which have the same BID j, have been received at an intermediate node, and Mr recoded packets are supposed to be generated. Following traditional random linear network coding, a recoded packet can be generated by random linear combination: (randomly) choose a sequence of coefficients c[i], i = 0, 1, ..., r-1 from GF(q), and generate c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet. This recoding approach, called random linear recoding, achieves good network coding performance for multicast when the batch size is sufficiently large.¶

For unicast communications in a single path as illustrated in Figure 1, it is not necessary to generate all the Mr recoded packets using random linear combination. Instead, xr[i], i = 0, 1, ..., r-1, are directly used as recoded packets, and max(Mr-r,0) recoded packets are generated using linear combinations. Compared with random linear recoding, this recoding approach, called systematic recoding, can reduce both the computation cost and also the recoding latency that accumulates linearly with the number of nodes. Note that the use of systematic recoding may not always achieve the optimal network coding performance as random linear recoding in more complicated communication scenarios that include multiple paths and multiple destination nodes.¶

3.4. Outer Decoder

The decoder receives a sequence of batches Yr[j], j = 0, 1, ..., n-1, each of which is a TO-row matrix over GF(256). Let Y[j] be the submatrix of the last T rows of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; when q = 2, let H[j] be the matrix over GF(256) formed by embedding each bit in the first M/8 rows of Yr[j] into GF(256). For successful decoding, we require that the total rank of all the batches is at least K.¶

The same degree distribution DD used for the outer encoder is supposed to be known by the outer decoder. By calling DegreeSampler and BatchSampler with input j, we obtain d[j], idx[j] and G[j]. According to the encoding and recoding processes described in Section 3.2 and Section 3.3, we have the system of linear equations Y[j] = B[j]G[j]H[j] for each received batch with ID j, where B[j] = (b[idx[j,0]], b[idx[j,1]], ..., b[idx[j,d-1]]) is unknown.¶

We first describe a belief propagation (BP) decoder that can efficiently solve the source packets when a sufficient number of batches have been received. A batch j is said to be decodable if rank(G[j]H[j]) = d[j] (i.e., the system of linear equations Y[j] = B[j]G[j]H[j] with B[j] as the variable matrix has a unique solution). The BP decoding algorithm has multiple iterations. Each iteration is formed by the following steps:¶

• Decoding step: Find a batch j that is decodable. Solve the corresponding system of linear equations Y[j] = B[j]G[j]H[j] and decode B[j].¶
• Substitution step: Substitute the decoded source packets into undecodable batches. Suppose that a decoded source packet b[k] is used in generating an undecodable Y[j]. The substitution involves 1) removing the entry in idx[j] corresponding to k, 2) removing the row in G[j] corresponding to b[k], and 3) reducing d[j] by 1.¶

The BP decoder repeats the above steps until no batches are decodable during the decoding step.¶

When the degree distribution DD in the outer code encoder (see Section 3.2) is properly designed, the BP decoder guarantees a high probability for the recovery of a given fraction of the source packets when K is large. To recover all the source packets, a precode can be applied to the source packets to generate a fraction of redundant packets before applying the outer code encoding. Moreover, when the BP decoder stops which may happen with a high probability when K is relatively small, it is possible to continue with inactivation decoding, where certain source packets are treated inactive so that a similar belief propagation process can be resumed. The reader is referred to RFC 6330 [RFC6330] for the design of a precode with a good inactivation decoding performance.¶

4.1. Coding Design Issues

When the number of batches is sufficiently large, the BATS code specification in Section 3 has nearly optimal performance in the sense that the decoding can be successful with a high probability when the total rank of all the batches used for decoding is just slightly larger than the number of source packet K. But when K is small, the degree sampler function in Figure 7 and the BatchSampler function in Figure 6 based on a pseudorandom generator may not sample all the source packets evenly, so that some of the source packets are not well protected. One approach to solve this issue is to generate a deterministic degree sequence when the number of batches is relatively small, and design a special pseudorandom generator that has a good sampling performance when K is small.¶

There are research issues related to recoding discussed in Section 3.3. One question is how many recoded packets to generate for each batch. Though it is asymptotically optimal when using the same number of recoded packets for all batches, it has been shown that transmitting a different number of recoded packets for different batches can improve the recoding efficiency. The intuition is that for a batch with a lower rank, a smaller number of recoded packets need to be transmitted. This kind of recoding scheme is called adaptive recoding [Yin19].¶

Packet loss in network communication is usually bursty, which may harm the recoding performance. One way to resolve this issue is to transmit the packets of different batches in a mixed order, which is also called batch interleaving [Yin20]. How to efficiently interleave batches without increasing too much end-to-end latency is a research issue.¶

Though we only focus on the BATS coding scheme with one source node and one destination node, a BATS coding scheme can be used for multiple source and destination nodes. To benefit from multiple source nodes, we would need different source nodes to generate statistically independent batches. For communicating the same data to multiple destination nodes, which is also called multicast, it is well-known that linear network coding [Li03] achieves the mulicast capacity. BATS codes can benefit from network coding due to its inner code, but how to efficiently implement multicast needs further research.¶

4.2. Protocol Design Issues

The baseline scheme in this document focuses on reliable communication. There are other issues to be considered towards designing a fully functional DDP based on a BATS coding scheme. Here we discuss some network management issues that are closely related to a BATS coding scheme: routing, congestion control and media access control.¶

The outer code of a BATS code can be regarded as a channel code for the channel induced by the inner code, and hence the network management algorithms should try to maximize the capacity of the channel induced by the inner code. A network utility maximization problem [Dong20] for BATS coding can be applied to study routing, congestion control and media access control jointly. Compared with the network utility maximization for Internet, there are two major differences. First, the network flow rate is not measured by the rate of the raw packets. Instead, a rank based measurement induced by the inner code is applied for BATS coding schemes. Second, due to recoding, the raw packet rate may not be the same for different links of a flow, i.e., no flow conservation for BATS coding schemes. These differences affect both the objective and the constraints of the utility maximization problem.¶

Practical congestion control, routing and media access control algorithms for BATS coding schemes deserve more research efforts. Due to the recoding operation, congestion control cannot be only performed end-to-end. The rate of transmitting batches can be controlled end-to-end, but the number of recoded packets generated for a batch must be controlled at the intermediate nodes, which introduces new research issues for congestion control. For routing, the BATS coding scheme is flexible for implementing multi-path data transmission, and different batches can be transmitted on a different path between a source node and a destination node. Under the scenario of BATS coding schemes, media access control can have some different considerations: Retransmission is not necessary, and a reasonably high packet loss rate can be tolerated.¶

4.3. Application Related Issues

There are more research issues pertaining to different applications. The reliable communication technique provided by BATS codes can be used for a broad range of network communication scenarios. In general, a BATS coding scheme is suitable for data delivery in networks with multiple hops and unreliable links.¶

One class of typical application scenario is wireless mesh and ad hoc networks [Toh02], including vehicular networks, wireless sensor networks, smart lamppost networks, etc. These networks are characterized by a large number of network devices connected wirelessly with each other without a centralized network infrastructure. A BATS coding scheme is suitable for high data load delivery in such networks without the requirement that the point-to-point/one-hop communication is highly reliable. Therefore, employing a BATS coding scheme can provide more freedom for media access control, including power control, and physical-layer design so that the overall network throughput can be improved.¶

Another typical application scenario of BATS coding schemes is underwater acoustic networks [Sprea19], where the propagation delay of acoustic waves in underwater can be as long as several seconds. Due to the long delay, feedback based mechanisms become inefficient. Moreover, point-to-point/one-hop underwater acoustic communication (for both the forward and reverse directions) is highly unreliable. Due to these reasons, traditional networking techniques developed for radio and wireline networks cannot be directly applied to underwater networks. As a BATS coding scheme does not rely on the feedback for reliability communication and can tolerate highly unreliable links, it makes a good candidate for developing data delivery protocols for underwater acoustic networks.¶

Last but not least, due to its capability of performing multi-source multi-destination communications, a BATS coding scheme can be applied in various content distribution scenarios. For example, a BATS coding scheme can be a candidate for the erasure code used in the liquid data networking framework [Byers20] of CCN (content centric networking), and provides the extra benefit of network coding [Zhang16].¶