<?xml version='1.0' encoding='utf-8'?> version="1.0" encoding="UTF-8"?>
<!DOCTYPE rfc [
  <!ENTITY nbsp    "&#160;">
  <!ENTITY zwsp   "&#8203;">
  <!ENTITY nbhy   "&#8209;">
  <!ENTITY wj     "&#8288;">
]>
<!-- This template is for creating an Internet Draft using xml2rfc,
    which is available here: http://xml.resource.org. -->
<?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?>
<!-- used by XSLT processors -->
<!-- For a complete list and description of processing instructions (PIs),
    please see http://xml.resource.org/authoring/README.html. -->
<!-- Below are generally applicable Processing Instructions (PIs) that most I-Ds might want to use.
    (Here they are set differently than their defaults in xml2rfc v1.32) -->
<?rfc strict="yes" ?>
<!-- give errors regarding ID-nits and DTD validation -->
<!-- control the table of contents (ToC) -->
<?rfc toc="yes"?>
<!-- generate a ToC -->
<?rfc tocdepth="4"?>
<!-- the number of levels of subsections in ToC. default: 3 -->
<!-- control references -->
<?rfc symrefs="yes"?>
<!-- use symbolic references tags, i.e, [RFC2119] instead of [1] -->
<?rfc sortrefs="yes" ?>
<!-- sort the reference entries alphabetically -->
<!-- control vertical white space
    (using these PIs as follows is recommended by the RFC Editor) -->
<?rfc compact="yes" ?>
<!-- do not start each main section on a new page -->
<?rfc subcompact="no" ?>
<!-- keep one blank line between list items -->
<!-- end of list of popular I-D processing instructions -->

<rfc xmlns:xi="http://www.w3.org/2001/XInclude" submissionType="IRTF" category="info" consensus="true" docName="draft-irtf-nwcrg-bats-07" number="9426" ipr="trust200902" obsoletes="" updates="" submissionType="IETF" xml:lang="en" tocInclude="true" tocDepth="4" symRefs="true" sortRefs="true" version="3">

  <!-- xml2rfc v2v3 conversion 3.9.0 -->
  <!-- category values: std, bcp, info, exp, and historic
       ipr values: trust200902, noModificationTrust200902, noDerivativesTrust200902,
       or pre5378Trust200902
       you can add the attributes updates="NNNN" and obsoletes="NNNN"
       they will automatically be output with "(if approved)" -->

  <!-- ***** FRONT MATTER ***** -->

  <front>
    <!-- The abbreviated title is used in the page header - it is only necessary if the
         full title is longer than 39 characters -->
    <title abbrev="BATS Code">BATS Code">BATched Sparse (BATS) Coding Scheme for Multi-hop Data Transport</title>
    <seriesInfo name="Internet-Draft" value="draft-irtf-nwcrg-bats-07"/>
    <!-- add 'role="editor"' below for the editors if appropriate -->
    <!-- Another author who claims to be an editor --> name="RFC" value="9426"/>
    <author fullname="Shenghao Yang" initials="S" surname="Yang">
      <organization>CUHK(SZ)</organization>
      <organization>CUHK(SZ) &amp; n-hop technologies</organization>
      <address>
        <postal>
          <street/>
          <!-- Reorder these if your country does things differently -->
          <city>Shenzhen</city>
          <region>Guangdong</region>
          <code/>
          <country>China</country>
        </postal>
        <phone>+86 755 8427 3827</phone>
        <email>shyang@cuhk.edu.cn</email>
        <!-- uri and facsimile elements may also be added -->
      </address>
    </author>
    <author fullname="Xuan Huang" initials="X" surname="Huang">
      <organization>CUHK</organization>
      <address>
        <postal>
          <street/>
          <!-- Reorder these if your country does things differently -->
          <city>Hong Kong</city>
          <region>Hong Kong SAR</region>
          <code/>
          <country>China</country>
        </postal>
        <phone>+852 3943 8375</phone>
        <email>1155136647@link.cuhk.edu.hk</email>
        <!-- uri and facsimile elements may also be added -->
      </address>
    </author>
    <author surname="R.W. Yeung" fullname="Raymond W. Yeung">
      <organization>CUHK</organization> Yeung" initials="R" surname="Yeung">
      <organization>CUHK &amp; n-hop technologies</organization>
      <address>
        <postal>
          <street/>
          <!-- Reorder these if your country does things differently -->
          <city>Hong Kong</city>
          <region>Hong Kong SAR</region>
          <code/>
          <country>China</country>
        </postal>
        <phone>+852 3943 8375</phone>
        <email>whyeung@ie.cuhk.edu.hk</email>
        <!-- uri and facsimile elements may also be added -->
      </address>
    </author>
    <author fullname="John K. Zao" surname="J.K. Zao">
      <!--organization>National Chiao Tung University</organization-->
      <organization>NCTU</organization> surname="Zao" initials="J.">
      <organization>CUHK</organization>
      <address>
        <postal>
          <street/>
          <!-- Reorder these if your country does things differently -->
          <city>Hsinchu</city>
          <region>Taiwan</region>
          <city>Hong Kong</city>
          <region>Hong Kong SAR</region>
          <code/>
          <country>China</country>
        </postal>
        <phone/>
        <email>jkzao@ieee.org</email>
        <!-- uri and facsimile elements may also be added -->
        <phone>+852 3943 8346</phone>
        <email>johnzao@ie.cuhk.edu.hk</email>
      </address>
    </author>
    <date year="2023" month="January" day="4"/>
    <!-- If the month and year are both specified and are the current ones, xml2rfc will fill
         in the current day for you. If only the current year is specified, xml2rfc will fill
         in the current day and month month="July"/>
    <workgroup>Coding for you. If the year is not the current one, it is
         necessary to specify at least a month (xml2rfc assumes day="1" if not specified for the
         purpose of calculating the expiry date).  With drafts it is normally sufficient to
         specify just the year. -->

    <!-- Meta-data Declarations -->

    <area>IRTF</area>
    <workgroup>NWCRG</workgroup>
    <!-- WG name at the upperleft corner of the doc,
         IETF is fine for individual submissions.
         If this element is not present, the default is "Network Working Group",
         which is used by the RFC Editor as a nod to the history of the IETF. --> Efficient Network Communications</workgroup>
    <keyword>BATS code</keyword>
    <keyword>multi-hop</keyword>
    <!-- Keywords will be incorporated into HTML output
         files in a meta tag but they have no effect on text or nroff
         output. If you submit your draft to the RFC Editor, the
         keywords will be used for the search engine. -->
    <abstract>
      <t>Linear
      <t>In general, linear network coding can in general improve the network communication performance in terms of throughput, latency latency, and reliability. BATched Sparse (BATS) code is a class of efficient linear network coding scheme with a matrix generalization of fountain codes as the outer code, code and batch-based linear network coding as the inner code. This document describes a baseline BATS coding scheme for communication through multi-hop networks, networks and discusses the related research issues towards a more sophisticated BATS coding scheme. This document is a product of the Coding for Efficient Network Communications Research Group (NWCRG).</t>
    </abstract>
  </front>
  <middle>
    <section numbered="true" toc="default">
      <name>Introduction</name>
      <t>This document specifies a baseline <xref target="Yang14" format="default">BATched Sparse (BATS) code</xref> scheme for data delivery in multi-hop networks, networks and discusses the related research issues towards a more sophisticated scheme. The BATS code described here includes an outer code and an inner code. The outer code is a matrix generalization of fountain codes (see also the RapterQ RaptorQ code described in <xref target="RFC6330" format="default">RFC&nbsp;6330</xref>), format="default"/>), which inherits the advantages of reliability and efficiency and possesses the extra desirable property of being compatible with network coding compatible. coding. The inner code, also called recoding, is formed by linear network coding for combating packet loss, improving the multicast efficiency, etc. A detailed design and analysis of BATS codes are provided in the <xref target="Yang17" format="default">BATS monograph</xref>.</t>
      <t>A BATS coding scheme can be applied in multi-hop networks formed by wireless communication links, which are inherently unreliable due to interference, fading, multipath, etc. Existing transport  protocols like TCP use end-to-end retransmission, while network protocols such as IP might enable store-and-forward at the relays, relays so that packet loss would accumulate along the way.</t>
      <t>A BATS coding scheme can be used for various data delivery applications applications, like file transmission, video streaming over wireless multi-hop networks, etc. Different from traditional the forward error correcting correction (FEC) schemes that are applied either hop-by-hop or end-to-end, the BATS coding scheme combines the end-to-end coding (the outer code) with certain hop-by-hop coding (the inner code), code) and hence can potentially achieve better performance.</t>
      <t>The baseline coding scheme described here considers a network with multiple communication flows. For each flow, the source node encodes the data for transmission separately. Inside However, inside the network, however, it is possible to mix the packets from different flows for recoding. In this document, we describe a simple case where recoding is performed within each flow. Note that the same encoding/decoding scheme described here can be used with different recoding schemes as long as they follow the principle as we illustrate in this document.</t>
      <t>In this document, we focus on the case that each flow has only one destination node. Communicating the same data to multiple destination nodes is called multicast. Refer to <xref target="research" format="default"/> for the further discussion of multicast. </t>
      <t>The purpose of the baseline BATS coding scheme is twofold. First, it provides researchers and engineers a starting point for developing network communication applications/protocols based on BATS codes. Second, it helps to make the research issues clearer towards a sophisticated BATS code based network protocol. protocol based on BATS codes. Important research directions include the security issues, congestion control and control, routing algorithms for BATS codes, etc. </t>
      <t> This document is a product of and represents the collaborative work and consensus of the Coding for Efficient Network Communications Research Group (NWCRG). It is not an IETF product and is not an IETF standard.</t>
      <section numbered="true" toc="default">
        <name>Requirements Language</name>
        <t>The
        <t>
    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
        "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>", "<bcp14>REQUIRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL
    NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>", "<bcp14>RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
    "<bcp14>MAY</bcp14>", and "OPTIONAL" "<bcp14>OPTIONAL</bcp14>" in this document are to be interpreted as
    described in BCP&nbsp;14 <xref target="RFC2119" format="default">RFC 2119</xref>.</t> target="RFC2119"/> <xref target="RFC8174"/>
    when, and only when, they appear in all capitals, as shown here.
        </t>
      </section>
      <!--Requirements Language-->
    </section>
    <!--Introduction-->
    <section anchor="procedures" numbered="true" toc="default">
      <name>A Use Case of the BATS Coding Scheme</name>
      <t>The BATS coding scheme described in this document can be used, for example, by a Data Delivery Protocol (DDP). Though this document is not about a DDP, in this section, we briefly illustrate in this section how a BATS coding scheme is employed by a DDP to make the role of the coding scheme clear. Some terms that will be used in this section are summarized here:</t>
      <ul
      <dl newline="false" spacing="normal">
          <li>DDP: data delivery protocol.</li>
          <li>DDP packet: the
          <dt>DDP:</dt> <dd>Data Delivery Protocol</dd>
          <dt>DDP packet:</dt> <dd>the packet formed by a DDP employing a BATS coding scheme.</li>
          <li>source packet: the scheme</dd>
          <dt>source packet:</dt> <dd>the packet formed by the data for delivery.</li>
          <li>outer encoder: the delivery</dd>
          <dt>outer encoder:</dt> <dd>the outer code encoder of a BATS code.</li>
          <li>recoder: the code</dd>
          <dt>recoder:</dt> <dd>the inner code encoder of a BATS code.</li>
          <li>outer decoder: the code</dd>
          <dt>outer decoder:</dt> <dd>the outer code decoder of a BATS code.</li>
          <li>coded packet: the code</dd>
          <dt>coded packet:</dt> <dd>the packet generated by the outer code encoder or a recoder.</li>
          <li>batch: a recoder</dd>
          <dt>batch:</dt> <dd>a set of coded packets generated by a BATS coding scheme from the same subset of the source packets.</li>
          <li>recoded packet: a packets</dd>
          <dt>recoded packet:</dt> <dd>a coded packet generated by a recoder.</li>
          <li>degree: the recoder</dd>
          <dt>degree:</dt> <dd>the number of source packets used to generate a batch by the outer encoder. The (The degree can be different for a different batch.</li>
        </ul> batch.)</dd>
        </dl>
        <t>Other common terms can be found in <xref target="RFC8406" format="default">RFC 8406</xref>.</t> format="default"/>.</t>

      <section numbered="true" toc="default">
        <name>Introduction</name>
        <t>We describe a data delivery process DDP that involves one source node, one destination node, and multiple intermediate nodes in between. A BATS coding scheme includes an outer code encoder (also called outer encoder), an inner code encoder (also called recoder), and an outer decoder which that decodes the outer code and the inner code jointly jointly, as illustrated in <xref target="network_model" format="default"/>. The functions of the outer encoder, recoder recoder, and outer decoder are described below: </t>
        <figure anchor="network_model">
          <name>A network model Network Model for data delivery.</name> Data Delivery</name>
          <artwork name="" type="" align="left" align="center" alt=""><![CDATA[
        |
        |  {set of source packets}
        v
+-+-+-+-+-+-+-+-+
| outer encoder |
|       v       | source node
|    recoder    |
+-+-+-+-+-+-+-+-+
        |
        |  {set of DDP packets}
        v
+-+-+-+-+-+-+-+-+
|               |
|    recoder    | intermediate node
|               |
+-+-+-+-+-+-+-+-+
        |
        |  {set of DDP packets}
        v
       ...
        |
        |  {set of DDP packets}
        v
+-+-+-+-+-+-+-+-+
|               |
| outer decoder | destination node
|               |
+-+-+-+-+-+-+-+-+
        |
        |  {set of source packets}
        v
]]></artwork>
        </figure>

        <t>At the source node, the DDP first processes the data to be delivered into a number of source packets packets, each of the same number of bits (see details in <xref target="ddp_padding" format="default" />), and then provides all the source packets to the outer encoder. The outer encoder will further generate a sequence of batches, each consisting of a fixed number of coded packets (see the description in <xref target="ddp_encoder" format="default" />).</t>

        <t>Each batch generated at the source node is further processed by the recoder separately. The recoder may generate a number of new coded packets using the existing coded packets of the batch (see the description in <xref target="ddp_recoder" format="default" />). After it is processed by the recoder, the The DDP forms and transmits the DDP packets using the coded packets, together with the corresponding batch information.</t>

        <t>We assume that a DDP packet is either correctly received or completely erased during the communication. The DDP extracts the coded packets and the corresponding batch information from its received DDP packets. A recoder is employed at an intermediate node that does not need the data, data and generates recoded packets for each batch (see the description in <xref target="ddp_recoder" format="default" />). The DDP forms and transmits DDP packets using the recoded packets and the corresponding batch information.</t>

        <t>The outer decoder is employed at the destination node that needs the data. The DDP extracts the coded packets and the corresponding batch information from its received DDP packets. The outer decoder tries to recover the transmitted data using the received batches (see the description in <xref target="ddp_decoder" format="default" />). The DDP sends the decoded data to the application that needs the data.</t>
      </section>
      <!--Introduction-->
      <section numbered="true" toc="default">
        <name>Data Delivery
        <name>DDP Procedures</name>
        <t>Suppose that the DDP has F octets of data for transmission. We describe the procedures of one BATS session for transmitting the F octets. There is a limit on F of a single BATS session. If the total data has more than the limit, the data needs to be transmitted using multiple BATS sessions. The limit on F of a single BATS session depends on the coding parameters to be that are discussed in this section, section and will be calculated the calculations described at the end of <xref target="packetformat" />.</t>
        <section anchor="ddp_padding" numbered="true" toc="default">
          <name>Source Node Data Partitioning and Padding</name>
          <t>
            The DDP first determines the following parameters:
          </t>
          <ul spacing="normal">
            <li>Batch
            <li>batch size (M): the number of coded packets in a batch generated by the outer encoder.</li>
            <li>Recoding encoder</li>
            <li>recoding field size (q): the number of elements in the finite field for recoding. recoding, i.e., q is 2 or 2^8</li> 2<sup>8</sup></li>
            <li>BATS payload size (TO): the number of payload octets in a BATS packet, including the coded data and the coefficient vector.</li> vector</li>
          </ul>
          <t> Based on the above parameters, the parameters T, CO CO, and K are calculated as follows:
          </t>
          <ul spacing="normal">
            <li>CO: the number of octets of a coefficient vector, calculated as CO = ceil(M*log2(q)/8), ceil(M * log2(q) / 8), which is also called the coefficient vector overhead.</li> overhead</li>
            <li>T: the number of data octets of a coded packet, calculated as T = TO - CO.</li> CO</li>
            <li>K: number of source packets, calculated as K = floor(F/T)+1. </li> floor(F / T) + 1</li>
          </ul>
          <t>
	        The data MUST <bcp14>MUST</bcp14> be padded to have T*K octets, which will be partitioned into K source packets b[0], ..., b[K-1], b[K - 1], each of T octets.
	        In our padding scheme, b[0], ..., b[K-2] b[K - 2] are filled with data octets, and b[K-1] b[K - 1] is filled with the remaining data octets and padding octets.
	      Let P = K*T-F K * T - F denote the number of padding octets. We use b[K-1, b[K - 1, 0], ..., b[K-1, T-P-1] b[K - 1, T - P - 1] to denote the T-P T - P source octets and b[K-1, T-P], b[K - 1, T - P], ..., b[K-1, T-1] b[K - 1, T - 1] to denote the P padding octets in b[K-1], b[K - 1], respectively. The padding insertion process is shown in <xref target="data_padding" format="default"/>.</t>
          <figure anchor="data_padding">
            <name>Data Padding Insertion Process</name>
            <artwork name="" type="" align="left" alt=""><![CDATA[
            <sourcecode type="pseudocode"><![CDATA[
    Z = T - P
    j = 1
    v = 1
    Let bl be the last source packet b[K-1] b[K - 1]
    for i = Z, Z+1, Z + 1, ..., T-1 T - 1 do
      bl[i] = j
      if i+1 i + 1 >= v+Z v + Z do
        j += 1
        v += j
             ]]></artwork>
             ]]></sourcecode>
          </figure>
        </section>
        <!--Padding-->
	  <section anchor="ddp_encoder" numbered="true" toc="default">
          <name>Source Node Outer Code Encoding Procedure</name>
          <t>
          The DDP provides the BATS encoder with the following information:
          </t>
          <ul spacing="normal">
            <li>Batch
            <li>batch size (M): the number of coded packets in a batch.</li>
            <li>Recoding batch</li>
            <li>recoding field size (q): the number of elements in the finite field for recoding.</li>
            <li>Maximum recoding</li>
            <li>maximum degree (MAX_DEG): a positive integer that specifies the largest degree can be used.</li>
            <li>Degree used</li>
            <li>degree distribution (DD): an unsigned integer array of size MAX_DEG+1. The i-th entry DD[i] is the probability that i is chosen as the degree, where i is between 0 and MAX_DEG.</li>
            <li>A
            <li>a sequence of batch IDs (BID) (BIDs) (j, j = 0, 1, ...).</li>
            <li>Number ...)</li>
            <li>number of source packets (K).</li>
            <li>Packet (K)</li>
            <li>packet size (T): the number of octets in a source packet.</li>
            <li>Source packet</li>
            <li>source packets (b[i], i = 0, 1, ..., K-1).</li> K - 1)</li>
          </ul>
          <t>
          Using this information, the outer encoder generates M coded packets for each batch ID BID using the following steps to be that are described in details at detail in <xref target="encoder" format="default"/>:</t>
          <ul spacing="normal">
            <li> Obtain a degree d by sampling DD. Roughly, the value d is chosen with probability DD[d].</li>
            <li> Choose d source packets uniformly at random from all the K source packets. It is allowed that a source packet is used by mutiple multiple batches.</li>
            <li> Generate M coded packets using the d source packets.</li>
          </ul>

          <t>The DDP receives from

          <t>From the outer encoder encoder, the DDP receives a sequence of batches, where the batch with ID j has
          </t>
          <ul spacing="normal">
            <!--li>a degree d[j], and</li-->
            <li>M M coded packets (x[j,i], i =0, 1, ..., M-1), M - 1), each containing TO octets.</li>
          </ul> octets.
          </t>
          <t>
          The DDP will use the batches to form DDP packets to be transmitted to other network nodes towards the destination nodes. The DDP MUST <bcp14>MUST</bcp14> deliver with each coded packet with its batch ID, which will be further used by both the recoder and decoder.
          </t>
	        <t>The DDP MUST <bcp14>MUST</bcp14> deliver some of the information used by the encoder to each recoder of the recoders and the decoder, either embedded in the DDP packets or transmitted using separated protocol messages: messages.
          For recoders, the DDP MUST <bcp14>MUST</bcp14> deliver the following information to each recoder:
          </t>
          <ul spacing="normal">
            <li>M: batch size</li>
            <li>q: recoding field size.</li> size</li>
          </ul>
          <t>
          For the decoder, the DDP MUST <bcp14>MUST</bcp14> deliver the following information to the decoder:
          </t>
          <ul spacing="normal">
            <li>M: batch size</li>
            <li>q: recoding field size</li>
            <li>K: the number of source packets</li>
            <li>T: the number of octets in a source packet</li>
            <li>DD: the degree distribution.</li> distribution</li>
          </ul>

          <t>
          The BID is used by both recoders and decoders. We will illustrate in In <xref target="parameters" /> that target="parameters"/>, we illustrate how to embed BID, M, q, and K into DDP packets. The degree distribution DD does not need to be changed frequently. See Section 6 in of <xref target="Yang17" /> about how to design a good degree distribution. Once designed, the degree distribution can be shared between the source node and the destination node by the DDP, which is not further discussed here.
          </t>
        </section>
        <section anchor="ddp_recoder" numbered="true" toc="default">
          <name>Recoding Procedures</name>
          <t>Both the source node and the intermediate nodes perform recoding on the batches before transmission. At the source node, the recoder receives the batches from the outer code encoding procedure. At an intermediate node, the DDP receives the DDP packets from the other network nodes.
If the DDP choose chooses not to recode, it just forwards the DDP packets it received.
Otherwise, the DDP should be able to extract coded packets and the corresponding batch information from these packets.
          </t>
          <t>
            For a received batch, the DDP determines a positive integer Mr, (Mr) and the number of recoded packets to be transmitted for the batch, and DDP provides the recoder with the following information:
          </t>
          <ul spacing="normal">
            <li>the
            <li>M: batch size M,</li>
            <li>the size</li>
            <li>q: recoding field size q,</li> size</li>
            <li>a number of received coded packets of the same batch, each containing TO octets, and</li>
            <li>the octets</li>
            <li>Mr: the number of recoded packets to be generated (Mr).</li> generated</li>
          </ul>
          <t>
	      The recoder uses the information provided by the DDP to generate Mr recoded packets, each containing TO octets, to be which are described in <xref target="recoder" format="default"/>. The DDP uses the Mr recoded packets to form the DDP packets for transmitting.
          </t>
        </section>
        <section anchor="ddp_decoder" numbered="true" toc="default">
          <name>Destination Node Procedures</name>
          <t>
          At the destination node, the DDP receives DDP packets from an intermediate network node, node and should be able to extract coded packets and the corresponding batch information from these packets. The DDP then employs an outer decoder to recover the data transmitted by the source node.
          </t>
          <t>
          The DDP provides the outer decoder (to be described in <xref target="decoder" format="default"/>) with the following information:
          </t>
          <ul spacing="normal">
            <!-- <t>F: number of octets in the data,</t> -->
            <li>M: batch size,</li> size</li>
            <li>q: recoding field size,</li> size</li>
            <li>K: the number of source packets</li>
            <li>T: the number of octets of a source packet</li>
            <li>A
            <li>a sequence of batches, each of which is formed by a number of coded packets belonging to the same batch, with their corresponding BIDs.</li> BIDs</li>
          </ul>
          <t> The decoder uses this information to decode the outer code and the inner code jointly and recover the K source packets (see details in <xref target="decoder" />). If successful, the decoder returns the recovered K source packets to the DDP, which will use the K source packets to form the F octets data. The recommended padding deletion process is shown as follows:</t>
          <figure anchor="data_depadding">
            <name>Data Padding Deletion Process</name>
            <artwork name="" type="" align="left" alt=""><![CDATA[
            <sourcecode type="pseudocode"><![CDATA[
    // this procedure returns the number P of padding octets
    // at the end of b[K-1] b[K - 1]
    Let bl be the last decoded source packet b[K-1] b[K - 1]
    PL = bl[T-1] bl[T - 1]
    if PL == 1 do
        return P = 1
    WI = T - 1
    while bl[WI] == PL do
        WI = WI - 1
    return P = (1 + bl[WI]) * bl[WI] + T - WI - 1
             ]]></artwork>
             ]]></sourcecode>
          </figure>
        </section>
      </section>
      <section numbered="true" toc="default">
        <name>Recommendation for the Parameters</name>
        <t>
        The recommendation for the parameters M and q is shown as follows:
        </t>
        <ul spacing="normal">
          <li>When q=2, M=16,32,64,128</li>
          <li>When q=256, M=4,8,16,32</li>
          <li>when q = 2, M = 16, 32, 64, 128</li>
          <li>when q = 256, M = 4, 8, 16, 32</li>
        </ul>
        <t>
        It is RECOMMENDED <bcp14>RECOMMENDED</bcp14> that K is at least 128. The encoder/decoder SHALL <bcp14>SHALL</bcp14> support an arbitrary positive integer value less than 2^16. 2<sup>16</sup>. However, the BATS coding scheme to be described is not optimized for small K.
        </t>
      </section>
      <!--Recommendation for the Parameters-->
    <section anchor="parameters" numbered="true" toc="default">
        <name>Coding Parameters in DDP Packets</name>
        <t>Here
        <t>Here, we provide an example of embedding the aforementioned BATS coding parameters into the DDP packets which that 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 DDP packet to the next node, e.g., node (e.g., the DDP protocol version, addresses version of the DDP, addresses, and session identifiers. identifiers). We will not go into the details of formatting these fields in a DDP packet, but we focus on how to format the coding parameters and the coded packet in a DDP packet.</t>

        <section numbered="true" toc="default">
          <name>Coding Parameter Format</name>
          <t> Here
          <t>Here, we provide an example of using 32 bits (4 octets) to embed the parameters K, M, q, and BID. The 32 bits are separated into three subfields, denoted as K, Mq Mq, and BID, respectively, as illustrated in <xref target="packet_header"/>.</t>
          <figure anchor="packet_header">
            <name>Coding parameter field format.</name> Parameter Field Format</name>
            <artwork name="" type="" align="left" align="center" alt=""><![CDATA[
 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            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork>
          </figure>
          <ul
          <dl newline="false" spacing="normal">
            <li>K: 16-bit
            <dt>K:</dt> <dd>16-bit unsigned integer, specifying the number of source packets of the BATS session.</li>
            <li>Mq: 3-bit session</dd>
            <dt>Mq:</dt> <dd>3-bit unsigned integer to specify integer, specifying the value of M and q q, as shown in <xref target="Mq_value" format="default"/>.</li>
            <li>BID: 13-bit format="default"/></dd>
            <dt>BID:</dt> <dd>13-bit unsigned integer, specifying the batch ID of the batch the packet belongs to.</li>
            <!--li>d: 8-bit unsigned integer, specifying the batch degree of the batch the packet belongs to.</li-->
          </ul> to</dd>
          </dl>
          <table anchor="Mq_value" align="center">
            <name>Values of the Mq field</name> Field</name>
            <thead>
              <tr>
                <th align="left">Mq</th>
                <th align="left">M</th>
                <th align="left">q</th>
                <!-- <th align="left">O</th> -->
              </tr>
            </thead>
            <tbody>
	      <tr>
                <td align="left">000</td>
                <td align="left">16</td>
                <td align="left">2</td>
                <!-- <td align="left">2</td> -->
              </tr>
              <tr>
                <td align="left">010</td>
                <td align="left">32</td>
                <td align="left">2</td>
                <!-- <td align="left">2</td> -->
              </tr>
              <tr>
                <td align="left">100</td>
                <td align="left">64</td>
                <td align="left">2</td>
                <!-- <td align="left">4</td> -->
              </tr>
              <tr>
                <td align="left">110</td>
                <td align="left">128</td>
                <td align="left">2</td>
                <!-- <td align="left">8</td> -->
              </tr>
              <tr>
                <td align="left">001</td>
                <td align="left">4</td>
                <td align="left">256</td>
                <!-- <td align="left">8</td> -->
              </tr>
              <tr>
                <td align="left">011</td>
                <td align="left">8</td>
                <td align="left">256</td>
                <!-- <td align="left">16</td> -->
              </tr>
              <tr>
                <td align="left">101</td>
                <td align="left">16</td>
                <td align="left">256</td>
                <!-- <td align="left">32</td> -->
              </tr>
              <tr>
                <td align="left">111</td>
                <td align="left">32</td>
                <td align="left">256</td>
                <!-- <td align="left">64</td> -->
              </tr>
            </tbody>
          </table>

	  <t>The choice of the coding parameters depends on the computation cost, the network conditions conditions, and the expected end-to-end coding performance. Usually, a larger batch size M will have a better coding performance, performance but higher computation cost for encoding, recoding recoding, and decoding. The field size q affects the coefficient vector overhead, overhead and also the computation cost for recoding. Within a BATS session, the BID field should be different for all batches, and hence hence, the maximum number of batches that can be generated for the outer encoder is 2^13. 2<sup>13</sup>. For different BATS sessions, batches can use the same BID.</t>
        </section>
        <section anchor="packetformat" numbered="true" toc="default">
          <name>Coded Packet Format</name>
          <figure anchor="packet_payload">
            <name>Code packet format Packet Format in a DDP packet.</name> Packet</name>
            <artwork name="" type="" align="left" align="center" alt=""><![CDATA[
            CO                          T
+-----------------------+-------------------------------+
|   coefficient vector  |          coded data           |
+-----------------------+-------------------------------+
]]></artwork>
          </figure>
          <t>
          A coded packet has TO=T+CO octets, where the first CO octets contain the coefficient vector and the remaining T octets contain the coded data.
          <!-- Information in both fields MAY be encoded in JSON (ASCII) or protobuf (binary) formats -->
          </t>
          <ul
          <dl newline="false" spacing="normal">
            <li>coefficient vector: CO
            <dt>coefficient vector:</dt> <dd>CO = M*log2(q)/8 M * log2(q) / 8 octets. For the values of M and q in <xref target="Mq_value" format="default"/>, CO is at most 32 octets when q is 256 and 6 octets when q is 2. </li>
            <li>coded data: T </dd>
            <dt>coded data:</dt> <dd>T octets. T should be chosen so that the whole DDP packet is at most PMTU.</li>
          </ul> Path MTU (PMTU).</dd>
          </dl>

	  <t>Using the above formation, we can calculate the largest file size F (F) for different parameters. For example, when q=2 q = 2 and M=128, M = 128, we have CO = 6 octets. Counting the 4 octets for embedding the coding parameters, we can choose T = PMTU-H-10, PMTU - H - 10, where H is the header length of a DDP packet. As K can be at most 2^16-1, 2<sup>16</sup> - 1, F can be at most (PMTU-H-10)(2^16-1) (PMTU - H - 10)(2<sup>16</sup> - 1) octets. In this case, K/M K / M is about 2^9 2<sup>9</sup> and the BID field allows transmitting 2^4*K/M 2<sup>4</sup> * K / M batches. </t>
        </section>
        <!-- <section title="Packet Footer">
        <figure anchor="packet_footer" title="BATS packet footer format."><artwork><![CDATA[
      0                   1                   2
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |            signature          |  parity check |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      ]]></artwork>
        </figure>
        <t>
          The footer has three octets.
          <list style="symbols">
            <t>signature: 2 octets. A signature of the individual packet to prevent pollution attack.</t>
            <t>parity check: 1 octet. A parity check field used to verity the correctness of the packet.</t>
          </list>
        </t>
      </section> -->
    </section>
    </section>
    <section anchor="specification" numbered="true" toc="default">
      <name>BATS Code Specification</name>
      <section anchor="common" numbered="true" toc="default">
        <name>Common Parts</name>
        <t>
          The T octets of a source packets packet are treated as a column vector of T elements in GF(256). The CO octets of a coefficient vector are treated as a column vector of CO elements in GF(q), where q=2 q = 2 or q=256. q&nbsp;=&nbsp;256. Linear algebra and matrix operations over finite fields are assumed in this section.
        </t>
        <t>
	  For the two elements of GF(2), their multiplication corresponds to a logical AND operation operation, and their addition is a 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:
        </t>
          <ul empty="true" spacing="normal" bare="false">
            <li>x<sup>8</sup>
            <t indent="3">x<sup>8</sup> + x<sup>4</sup> + x<sup>3</sup> + x<sup>2</sup> + 1 </li>
          </ul> </t>
        <t>
        A common primitive polynomial MUST <bcp14>MUST</bcp14> 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.
        </t>
        <t> Suppose that a pseudorandom number generator Rand() generator, Rand(), which generates an unsigned integer of 32 bits 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 <xref target="RFC8682" format="default">RFC&nbsp;8682</xref>.</t> format="default"/>.</t>
        <t>A function called BatchSampler is used in both encoding and decoding. The function takes two integers integers, j and d d, as input, 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 <xref target="batch_sampler" format="default"/>. </t>
        <figure anchor="batch_sampler">
          <name>Batch Sampler Function</name>
          <artwork name="" type="" align="left" alt=""><![CDATA[
          <sourcecode type="pseudocode"><![CDATA[
function BatchSampler(j,d) BatchSampler(j, d)
    // initialize the pseudorandom generator by seed j.
    Rand_Init(j)
    // sample d distinct integers between 0 and K-1. K - 1.
    for k = 0, ..., d-1 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 d - 1 do
        for c = 0,...,M-1 0, ..., M - 1 do
            G[r,c]
            G[r, c] = Rand() % 256

    return idx, G
        ]]></artwork>
        ]]></sourcecode>
        </figure>
      </section>
      <section anchor="encoder" numbered="true" toc="default">
        <name>Outer Code Encoder</name>
        <t>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 &lt; K. One design of DegreeSampler is illustrated in <xref target="degree_sampler" format="default"/>. Note that when K &lt; 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 <xref target="decoder" />.
        </t>
        <figure anchor="degree_sampler">
          <name>Degree Sampler Function.</name>
          <artwork name="" type="" align="left" alt=""><![CDATA[ Function</name>
          <sourcecode type="pseudocode"><![CDATA[
function DegreeSampler(j, DD)
    Let CDF be an array
    CDF[0] = 0
    for i = 1, ..., MAX_DEG do
        CDF[i] = CDF[i-1] 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) min(d, K)
    return min(MAX_DEG,K)
       ]]></artwork> min(MAX_DEG, K)
       ]]></sourcecode>
        </figure>
        <t>
          Let b[0], b[1], ..., b[K-1] be the K source packets. A batch with BID j is generated using the following steps.
        </t>
        <ul spacing="normal">
          <li>Obtain a degree d by calling DegreeSampler with input j.
            </li>
          <li>Obtain idx and G[j] by calling BatchSampler with input j and d.
            </li>
          <li>Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d-1]]). b[idx[d - 1]]). Form the batch X[j] = B[j]*G[j], B[j] * G[j], whose dimension is T x M.
            </li>
          <li>Form the TO x M matrix Xr[j], where the first CO rows of Xr[j] form the M x M identity matrix I with entries in GF(q), GF(q) and the last T rows of Xr[j] is X[j].
            </li>
        </ul>
        <t>See the pseudocode of the batch generating process in <xref target="gen_batch" format="default"/>.</t>
        <figure anchor="gen_batch">
          <name>Batch Generation Function.</name>
          <artwork name="" type="" align="left" alt=""><![CDATA[ Function</name>
          <sourcecode type="pseudocode"><![CDATA[
function GenBatch(j)
    d = DegreeSampler(j)
    (idx, G) = BatchSampler(j,d) BatchSampler(j, d)
    B = (b[idx[0]], b[idx[i]], ..., b[idx[d-1]]) b[idx[d - 1]])
    X = B * G
    Xr = [I; X]
    return Xr
       ]]></artwork>
       ]]></sourcecode>
        </figure>
      </section>
      <section anchor="recoder" numbered="true" toc="default">
        <name>Inner Code Encoder (Recoder)</name>
        <t>
          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, r - 1, which have the same BID j, have been received at an intermediate node, node and Mr recoded packets are supposed to be generated. Following traditional random linear network coding, a recoded packet can be generated by a random linear combination: (randomly) choose a sequence of coefficients c[i], i = 0, 1, ..., r-1 r - 1 from GF(q), GF(q) and generate c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] 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.</t>

       <t>
	 For unicast communications in a single path path, as illustrated in <xref target="network_model" format="default"/>, it is not necessary to generate all the Mr recoded packets using a random linear combination. Instead, xr[i], i = 0, 1, ..., r-1, r - 1 are directly used as recoded packets, and max(Mr-r,0) 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.
        </t>
      </section>
      <section anchor="decoder" numbered="true" toc="default">
        <name>Outer Decoder</name>
        <t> The decoder receives a sequence of batches batches, Yr[j], j = 0, 1, ..., n-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.</t>

        <t> 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] idx[j], and G[j]. According to the encoding and recoding processes described in Sections <xref target="encoder" format="default"/> format="counter"/> and <xref target="recoder" format="default"/>, format="counter"/>, 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, 0]], b[idx[j, 1]], ..., b[idx[j,d-1]]) b[idx[j, d - 1]]) is unknown.
        </t>
        <t> 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:
        </t>
        <ul spacing="normal">
          <li> Decoding step: 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].</li>
          <li> Substitution step: 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. </li>
        </ul>
        <t>
        The BP decoder repeats the above steps until no batches are decodable during the decoding step.
        </t>

	<t>When the degree distribution DD in the outer code encoder (see <xref target="encoder" format="default"/>) 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 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 as inactive so that a similar belief propagation process can be resumed. The reader is referred to <xref target="RFC6330" format="default">RFC&nbsp;6330</xref> format="default"/> for the design of a precode with a good inactivation decoding performance. </t>
      </section>
    </section>
    <section anchor="research" numbered="true" toc="default">
      <name>Research Issues</name>
      <t>The baseline BATS coding scheme described in Sections <xref target="procedures" format="default"/> format="counter"/> and <xref target="specification" format="default"/> format="counter"/> needs various refinement refinements and complement complements towards becoming a more sophisticated network communication application. Various related research issues are discussed in this section, but the security related security-related issues are left to <xref target="Security" format="default"/>. </t>
      <section anchor="coding" numbered="true" toc="default">
        <name>Coding Design Issues</name>
        <t>When the number of batches is sufficiently large, the BATS code specification in <xref target="specification" format="default"/> 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 DegreeSampler function in <xref target="degree_sampler" format="default"/> and the BatchSampler function in <xref target="batch_sampler" format="default"/> based on a pseudorandom generator may not sample all the source packets evenly, 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, small and design a special pseudorandom generator that has a good sampling performance when K is small.</t>
        <t>There are research issues related to recoding discussed in <xref target="recoder" format="default"/>. 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 For a batch with a lower rank, the intuition is that a smaller number of recoded packets need to be transmitted. This kind of recoding scheme is called <xref target="Yin19" format="default">adaptive recoding</xref>.</t>
        <t>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 <xref target="Yin20" format="default">batch interleaving</xref>. How to efficiently interleave batches without increasing end-to-end latency too much is a research issue.</t>
        <t> 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. It is well-known that <xref target="Li03" format="default">linear network coding</xref> achieves the multicast capacity. BATS codes can benefit from network coding due to its inner code. For multicast, each destination node performs independently performs the same operations as described in this document, but the inner code should be improved to taking take multiple destination node nodes into consideration. How to efficiently implement multicast needs further research.</t>
      </section>
      <section anchor="protocol" numbered="true" toc="default">
        <name>Protocol Design Issues</name>
        <t>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 Here, we discuss some network management issues that are closely related to a BATS coding scheme: routing, congestion control control, and media access control.</t>
        <t>The outer code of a BATS code can be regarded as a channel code for the channel induced by the inner code, and hence hence, the network management algorithms should try to maximize the capacity of the channel induced by the inner code. A <xref target="Dong20" format="default">network utility maximization problem</xref> for BATS coding can be applied to study routing, congestion control control, and media access control jointly. Compared with the network utility maximization for the 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 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. </t>
        <t>Practical congestion control, routing routing, and media access control algorithms for BATS coding schemes deserve more research efforts. The rate of transmitting batches can be controlled end-to-end. Due to the recoding operation, however, congestion control cannot be only performed end-to-end. The number of recoded packets generated for a batch must be controlled at the intermediate nodes, which introduces new research issues for congestion control. A BATS coding scheme is an extension of forward erasure correction coding. See <xref target="RFC9265" format="default">RFC&nbsp;9265</xref> format="default"/> for more discussion of forward erasure correction coding and congestion control.</t>
	<t>For routing, the BATS coding scheme is flexible for implementing data transmission on multiple paths simultaneously. For unicast, it is optimal to transmit all the packets of a batch on the same path between the source node and the destination node, and for multicast, network coding gain can be obtained by transmitting packets of the same batch on different paths <xref target="Yang17" format="default"/>. Last, Lastly, 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. </t>
      </section>
      <section anchor="application" numbered="true" toc="default">
        <name>Usage Scenario Considerations</name>
        <t>There are more research issues pertaining to various usage scenarios. 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.</t>
        <t>One class of typical usage scenario is <xref target="Toh02" format="default">wireless mesh and ad hoc networks</xref>, 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 point-to-point or 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. </t>
        <t>Another typical usage scenario of BATS coding schemes is <xref target="Sprea19" format="default">underwater acoustic networks</xref>, where the propagation delay of acoustic waves in underwater can be as long as several seconds. Due to the long delay, feedback based 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 the 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.</t>
        <t>Last but not least, due to its capability of performing multi-source 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 <xref target="Byers20" format="default">liquid data networking framework</xref> of CCN (content centric networking), content-centric networking (CCN) and provides the extra <xref target="Zhang16" format="default">benefit of network coding</xref>. </t>
      </section>
    </section>
    <!-- This PI places the pagebreak correctly (before the section title) in the text output. -->
    <section anchor="IANA" numbered="true" toc="default">
      <name>IANA Considerations</name>
      <t>This memo includes document has no request to IANA.</t> IANA actions.</t>
    </section>
    <section anchor="Security" numbered="true" toc="default">
      <name>Security Considerations</name>
      <t>
        Subsuming both random linear network codes (RLNC) (RLNCs) and fountain codes, BATS codes naturally inherit both their desirable security capability of preventing eavesdropping, eavesdropping as well as their vulnerability towards pollution attacks. In this section, we discuss some related research issues.
      </t>
      <section numbered="true" toc="default">
        <name>Preventing Eavesdropping</name>
        <t>Suppose that an eavesdropper obtains a batch where the degree value d is strictly larger than the batch size M. Even if the eavesdropper has all the related encoding information, the system of linear equations related to this batch does not have a unique solution, and the probability that the eavesdropper can guess the d source packets used for encoding the batch correctly is 2^(-(d-M)T)&#60;=2^(-T), 2<sup>(-(d-M)T)</sup>&lt;=2<sup>(-T)</sup>, where T is the number of octets of a source packet (see also <xref target="Bhattad07" format="default"/>). When inactivation decoding is applied, we can design the degree distribution DD so that the smallest degree is M+1, M+1 and hence prevent the eavesdropper from decoding source packets from individual batches.</t>
	  <t>
	    If we allow the eavesdropper to collect multiple batches and use inactivation decoding, the same security holds if the total rank of all the batches collected by the eavesdropper is less than the number of source packet. Therefore, if the DDP can manage to restrict the eavesdropper from collecting a sufficient number of coded packets, the native security of BATS code is effective when T is sufficiently large. Here Here, by native security, "intrinsic security", we mean the security protection provided by the BATS coding scheme without extra enhancement.
	  </t>
	  <t>
	  If the eavesdropper can collect a sufficient number of coded packets for correctly decoding, the native intrinsic security of BATS code is ineffective. One solution in this case is to encrypt the whole data before using the BATS code scheme. Better schemes are desired towards reducing the computation cost of the whole data encryption solution. This is a research issue that depends on specific BATS code schemes, schemes and will not be further discussed here.
        </t>
        <t>
          The threat exists for eavesdropping on the initial encoding process, which takes place at the encoding nodes. In these nodes, the transported data are presented in plain text and can be read along their transfer paths. Hence, information isolation between the encoding process and all other user processes running on the source node MUST <bcp14>MUST</bcp14> be assured.
        </t>
        <t>
          In addition, the authenticity and trustworthiness of the encoding, recoding recoding, and decoding program running on all the nodes MUST <bcp14>MUST</bcp14> be attested by a trusted authority. Such a measure is also necessary in countering pollution attacks.
        </t>
      </section>
      <section numbered="true" toc="default">
        <name>Privacy-Preserving
        <name>Privacy Preservation against Traffic Analysis</name>
        <t> A security issue closely related to eavesdropping is traffic analysis. Even when eavesdropping is prevented, tracking the traffic flow patterns can help an attacker to know a certain information about the communication. Preventing traffic analysis is critical for communications that need to be anonymous. In <xref target="Fan09" format="default"/>, a an approach based on  homomorphic encryption based approach is proposed for network coding to prevent traffic analysis. However, homomorphic encryption could be too computationally expensive for practical applications and cannot help with the traffic analysis by monitoring the frequency and timing of network traffic. </t>

        <t>  The network traffic using network coding does not necessarily satisfy the flow conservation property, and hence hence, network coding can be used as a tool for defeating traffic analysis. For example, redundant network traffic can be generated by network coding to make it harder for an attacker to learn the true communication. Moreover, traffic analysis countermeasures can benefit from multipath communication <xref target="Yang15" format="default"/>, and network coding makes multiple-path multipath communication more flexible and efficient. Therefore, using network coding brings new research issues for both traffic analysis and its countermeasure.
	</t>
      </section>
      <section numbered="true" toc="default">
        <name>Countermeasures against Pollution Attacks</name>
        <t>Like all network codes, BATS codes are vulnerable to pollution attacks. In these attacks, one or more compromised coding node(s) can pollute the coded messages by injecting forged  packets into the network and thus prevent the receivers from recovering the transported data correctly. Moreover, a small number of polluted packets can infect a large number of packets by recoding and decoding <xref target="Zhao07" format="default"/>.
        </t>
        <t>The research community has long been investigating the use of homomorphic signatures to identify the forged packets and stall the attacks (see <xref target="Zhao07" format="default"/>, <xref target="Yu08" format="default"/>, and <xref target="Agrawal09" format="default"/>). In these schemes, the source node attaches a signature to each packet to transmit, and the signature is allowed to be processed by network coding in the same way as the payload. All the intermediate nodes and the destination node can verify the signature attached to a received packet. However, these countermeasures are regarded as being too computationally expensive to be employed in broadband communications. </t>
        <t>A system-level approach based on <xref target="TC-Wikipedia" format="default">trusted computing</xref> can provide an alternative to protect BATS codes against pollution attacks. Trusted computing consists of software and hardware technologies so that a computer behaves as expected. Suppose that all the network nodes employ trusted computing. Two nodes will first gain trust with each other, other and then negotiate an authentication method for exchanging the coded packets of the BATS coding scheme. A network node would not use any packets received from other nodes without trust to avoid the pollution attack.
        </t>
      </section>
    </section>

        <!--section anchor="Acknowledgements" title="Acknowledgements">
        <t></t>
        </section-->

    <!-- Possibly a 'Contributors' section ... -->
  </middle>
  <!--  *****BACK MATTER ***** -->
    <back>
    <!-- References split into informative and normative -->
      <!-- There are 2 ways to insert reference entries from the citation libraries:
         1. define an ENTITY at the top, and use "ampersand character"RFC2629; here (as shown)
         2. simply use a PI "less than character"?rfc include="reference.RFC.2119.xml"?> here
            (for I-Ds: include="reference.I-D.narten-iana-considerations-rfc2434bis.xml")

         Both are cited textually in the same manner: by using xref elements.
         If you use the PI option, xml2rfc will, by default, try to find included files in the same
         directory as the including file. You can also define the XML_LIBRARY environment variable
         with a value containing a set of directories to search.  These can be either in the local
         filing system or remote ones accessed by http (http://domain/dir/... ).-->
      <references>
      <name>References</name>
      <references>
        <name>Normative References</name>
        <!--?rfc include="http://xml.resource.org/public/rfc/bibxml/reference.RFC.2119.xml"?-->
        <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.2119.xml"/> href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.2119.xml"/>
	<xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.8174.xml"/>
        <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.8682.xml"/> href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.8682.xml"/>
        <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.8406.xml"/> href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.8406.xml"/>
      </references>
      <references>
        <name>Informative References</name>
        <!-- Here we use entities that we defined at the beginning. -->
        <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.6330.xml"/> href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.6330.xml"/>
	<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.9265.xml"/>
        <!-- A reference written by by an organization not a person. --> href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.9265.xml"/>

          <reference anchor="Yang14">
          <front>
            <title>Batched Sparse Codes</title>
            <author initials="S." surname="Yang" fullname="Shenghao Yang">
                 </author>
            <author initials="R.W." initials="R." surname="Yeung" fullname="Raymond W. Yeung">
              </author>
            <date year="2014"/> year="2014" month="September"/>
          </front>
	  <seriesInfo name="IEEE name="DOI" value="10.1109/TIT.2014.2334315"/>
	  <refcontent>IEEE Transactions on Information Theory" value="60(9), 5322-5346"/> Theory, Vol. 60, Issue 9, pgs. 5322-5346</refcontent>
        </reference>

        <reference anchor="Yang17">
          <front>
            <title>BATS Codes: Theory and Practice</title>
            <author initials="S." surname="Yang" fullname="Shenghao Yang">
              </author>
            <author initials="R.W." initials="R." surname="Yeung" fullname="Raymond W. Yeung">
              </author>
            <date year="2017"/> year="2017" month="September"/>
          </front>
          <seriesInfo name="Morgan
	  <refcontent>Morgan &amp; Claypool Publishers" value=""/> Publishers</refcontent>
        </reference>

        <reference anchor="Yin19">
          <front>
            <title>A Unified Adaptive Recoding Framework for Batched Network Coding</title>
            <author initials="H.H.F." initials="H." surname="Yin" fullname="Hoover H.F. Yin"/>
            <author initials="B." surname="Tang" fullname="Bin Tang"/>
            <author initials="K.H." initials="K." surname="Ng" fullname="Ka Hei Ng"/>
            <author initials="S." surname="Yang" fullname="Shenghao Yang">
              </author> Yang"/>
            <author initials="X." surname="Wang" fullname="Xishi Wang">
              </author> Wang"/>
            <author initials="Q." surname="Zhou" fullname="Qiaoqiao Zhou">
              </author> Zhou"/>
            <date year="2019"/> year="2019" month="July"/>
          </front>
	  <seriesInfo name="ISIT" value=""/> name="DOI" value="10.1109/ISIT.2019.8849277"/>
	  <refcontent>2019 IEEE International Symposium on Information Theory (ISIT)</refcontent>
        </reference>

        <reference anchor="Yin20">
          <front>
            <title>A Protocol Design Paradigm for Batched Sparse Codes</title>
            <author initials="H.H.F." initials="H." surname="Yin" fullname="Hoover H.F. Yin"/>
            <author initials="R.W." initials="R." surname="Yeung" fullname="Raymond W. Yeung">
              </author> Yeung"/>
            <author initials="S." surname="Yang" fullname="Shenghao Yang">
              </author> Yang"/>
            <date year="2020"/> year="2020" month="July"/>
          </front>
	  <seriesInfo name="Entroy" value=""/> name="DOI" value="10.3390/e22070790"/>
	  <refcontent>Entropy</refcontent>
        </reference>

        <reference anchor="Dong20">
          <front>
            <title>Network Utility Maximization for BATS Code enabled Enabled Multihop Wireless Networks</title>
            <author initials="Y." surname="Dong" fullname="Yanyan Dong"/>
            <author initials="S." surname="Jin" fullname="Shengh Jin">
              </author> Jin"/>
            <author initials="S." surname="Yang" fullname="Shenghao Yang">
              </author> Yang"/>
            <author initials="H.H.F." initials="H." surname="Yin" fullname="Hoover H.F. Yin"/>
            <date year="2020"/> year="2020" month="June"/>
          </front>
	  <seriesInfo name="ICC" value=""/> name="DOI" value="10.1109/ICC40277.2020.9148834"/>
	  <refcontent>ICC 2020 - 2020 IEEE International Conference on Communications (ICC)</refcontent>
        </reference>
        <reference anchor="Fan09">
          <front>
            <title>Weakly Secure
            <title>An Efficient Privacy-Preserving Scheme against Traffic Analysis Attacks in Network Coding</title>
            <author initials="Y." surname="Yanfei" fullname="Yanfei Fan"/>
            <author initials="Y." surname="Yixin" fullname="Yixin Jiang"/>
	    <author initials="H." surname="Haojin" fullname="Haojin Zhu"/>
	    <author initials="X." surname="Sherman" fullname="Xuemin (Sherman) Shen"/>
            <date year="2009"/> year="2009" month="April"/>
          </front>
	  <seriesInfo name="INFOCOM" value=""/> name="DOI" value="10.1109/INFCOM.2009.5062146"/>
	  <refcontent>IEEE INFOCOM 2009</refcontent>
        </reference>

	<reference anchor="Yang15">
	  <front>
	    <title>mTor: A multipath Tor routing beyond bandwidth throttling</title>
	    <author initials="L." surname="Yang" fullname="Lei Yang"/>
	    <author initials="F." surname="Fengjun" fullname="Fengjun Li"/>
	    <date year="2015"/> year="2015" month="September"/>
	  </front>
	  <seriesInfo name="NCS" value=""/> name="DOI" value="10.1109/CNS.2015.7346860"/>
	  <refcontent>2015 IEEE Conference on Communications and Network Security (CNS)</refcontent>
	</reference>

	<reference anchor="Bhattad07">
          <front>
            <title>An efficient privacy-preserving scheme against traffic analysis attacks in network coding</title>
            <title>Weakly Secure Network Coding</title>
            <author initials="K." surname="Bhattad" fullname="Kapil Bhattad"/>
            <author initials="K.R." initials="K." surname="Narayanan" fullname="Krishna R. Narayanan"/>
            <date year="2007"/> year="2005" month="April"/>
          </front>
          <seriesInfo name="ISIT" value=""/>
        </reference>

        <reference anchor="Zhao07">
          <front>
            <title>Signatures for content distribution with network coding</title>
            <author initials="F." surname="Zhao" fullname="Fang Zhao"/>
            <author initials="T." surname="Kalker"/> surname="Kalker" fullname="Ton Kalker"/>
            <author initials="M." surname="Medard"/> surname="Medard" fullname="Muriel Medard"/>
            <author initials="K.J." surname="Han"/> initials="K." surname="Han" fullname="Keesook J. Han"/>
            <date year="2007"/> year="2007" month="June"/>
          </front>
	  <seriesInfo name="ISIT" value=""/> name="DOI" value="10.1109/ISIT.2007.4557283"/>
	  <refcontent>2007 IEEE International Symposium on Information Theory</refcontent>
        </reference>

        <reference anchor="Byers20">
          <front>
            <title>Liquid Data Networking</title>
            <author initials="J.W." initials="J." surname="Byers" fullname="John W. Byers"/>
            <author initials="M." surname="Luby" fullname="Michael Luby"/>
            <date year="2020"/> year="2020" month="September"/>
          </front>
	  <seriesInfo name="ICN" value=""/> name="DOI" value="10.1145/3405656.3418710"/>
	  <refcontent>Proceedings of the 7th ACM Conference on Information-Centric Networking</refcontent>
        </reference>

        <reference anchor="Yu08">
          <front>
            <title>An Efficient Signature-Based Scheme for Securing Network Coding Against Pollution Attacks</title>
            <author initials="Z." surname="Yu"/>
            <author initials="Y." surname="Wei"/>
            <author initials="B." surname="Ramkumar"/>
            <author initials="Y." surname="Guan"/>
            <date year="2008"/> year="2008" month="April"/>
          </front>
	  <seriesInfo name="INFOCOM" value=""/> name="DOI" value="10.1109/INFOCOM.2008.199"/>
	  <refcontent>IEEE INFOCOM 2008 - The 27th Conference on Computer Communications</refcontent>
        </reference>

        <reference anchor="Agrawal09">
          <front>
            <title>Homomorphic MACs: MAC-based integrity MAC-Based Integrity for network coding</title> Network Coding</title>
            <author initials="S." surname="Agrawal" fullname="Shweta Agrawal"/>
            <author initials="D." surname="Boneh" fullname="Dan Boneh"/>
            <date year="2009"/> year="2009" month="May"/>
          </front>
	  <seriesInfo name="International name="DOI" value="10.1007/978-3-642-01957-9_18"/>
	  <refcontent>International Conference on Applied Cryptography and Network Security" value=""/> Security</refcontent>
        </reference>

        <reference anchor="TC-Wikipedia"> anchor="TC-Wikipedia" target="https://en.wikipedia.org/w/index.php?title=Trusted_Computing&amp;oldid=1151565594">
          <front>
            <title>Trusted Computing</title>
            <author/>
            <author>
	      <organization>Wikipedia</organization>
	    </author>
            <date year=""/> year="2023" month="April"/>
          </front>
          <seriesInfo name="Wikipedia" value="https://en.wikipedia.org/wiki/Trusted_Computing"/>
        </reference>

        <reference anchor="Sprea19">
          <front>
            <title>BATS Coding for Underwater Acoustic Communication Networks</title>
            <author initials="N." surname="Sprea" fullname="Nicolò Sprea"/>
            <author initials="M." surname="Bashir" fullname="Murwan Bashir"/>
            <author initials="D." surname="Truhachev" fullname="Dmitri Truhachev"/>
            <author initials="K.V." surname="Srinivas"/> initials="K." surname="Srinivas" fullname="K. V. Srinivas"/>
            <author initials="C." surname="Schlegel"/> surname="Schlegel" fullname="Christian Schlegel"/>
            <author initials="C." surname="Claudio surname="Sacchi" fullname="Claudio Sacchi"/>
            <date year="2019"/> year="2019" month="June"/>
          </front>
	  <seriesInfo name="OCEANS" value=""/> name="DOI" value="10.1109/OCEANSE.2019.8867299"/>
	  <refcontent>OCEANS 2019 - Marseille</refcontent>
        </reference>

        <reference anchor="Toh02">
          <front>
            <title>Ad Hoc Mobile Wireless Networks</title>
            <author initials="C.K." initials="C." surname="Toh" fullname="Chai Keong Toh"/>
            <date year="2002"/> year="2001" month="December"/>
          </front>
          <seriesInfo name="Prentice
	  <refcontent>Prentice Hall Publishers" value=""/> Publishers</refcontent>
        </reference>

        <reference anchor="Zhang16">
          <front>
            <title>Combing CCN with network coding: An architectural perspective</title>
            <author initials="G." surname="Zhang" fullname="Guoqiang Zhang"/>
            <author initials="Z." surname="Xu" fullname="Ziqu Xu"/>
            <date year="2016"/> year="2016" month="January"/>
          </front>
	  <seriesInfo name="Computer Networks" value=""/> name="DOI" value="10.1016/j.comnet.2015.11.008"/>
	  <refcontent>Computer Networks</refcontent>
        </reference>

        <reference anchor="Li03">
          <front>
            <title>Linear Network Coding</title> network coding</title>
            <author initials="S.-Y.R." surname="Li"/> initials="S.-Y." surname="Li" fullname="S.-Y.R. Li"/>
            <author initials="R.W." initials="R." surname="Yeung" fullname="Raymond W. Yeung"/>
            <author initials="N." surname="Cai" fullname="Ning Cai"/>
            <date year="2003"/> year="2003" month="February"/>
          </front>
	  <seriesInfo name="IEEE name="DOI" value="10.1109/TIT.2002.807285"/>
	  <refcontent>IEEE Transactions on Information Theory" value=""/> Theory</refcontent>
        </reference>
      </references>
    </references>
    <!-- <section anchor="app-additional" numbered="true" toc="default">
      <name>Additional Stuff</name>
      <t/>
    </section> -->
    <!-- Change Log  -->
    <section numbered="false" toc="include" removeInRFC="false">
      <name slugifiedName="name-acknowledgments">Acknowledgments</name>
      <t>
        The authors would like to thank the NWCRG chairs, Vincent Roca <contact fullname="Vincent Roca"/> (our shepherd) and Marie-Jose Montpetit;
        and <contact fullname="Marie-Jose Montpetit"/>, as well as
        all those who provided comments -- comments, namely (in alphabetical order), Emmanuel Lochin, David Oran, and Colin Perkins. <contact fullname="Emmanuel Lochin"/>, <contact fullname="David Oran"/>, and <contact fullname="Colin Perkins"/>.
    </t>
    </section>
  </back>
</rfc>