rfc9426.original.xml   rfc9426.xml 
<?xml version='1.0' encoding='utf-8'?> <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE rfc [ <!DOCTYPE rfc [
<!ENTITY nbsp "&#160;"> <!ENTITY nbsp "&#160;">
<!ENTITY zwsp "&#8203;"> <!ENTITY zwsp "&#8203;">
<!ENTITY nbhy "&#8209;"> <!ENTITY nbhy "&#8209;">
<!ENTITY wj "&#8288;"> <!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" category="info" docName="draft-i
rtf-nwcrg-bats-07" ipr="trust200902" obsoletes="" updates="" submissionType="IET
F" xml:lang="en" tocInclude="true" tocDepth="4" symRefs="true" sortRefs="true" v
ersion="3">
<!-- xml2rfc v2v3 conversion 3.9.0 -->
<!-- category values: std, bcp, info, exp, and historic
ipr values: trust200902, noModificationTrust200902, noDerivativesTrust200
902,
or pre5378Trust200902
you can add the attributes updates="NNNN" and obsoletes="NNNN"
they will automatically be output with "(if approved)" -->
<!-- ***** FRONT MATTER ***** -->
<front> <rfc xmlns:xi="http://www.w3.org/2001/XInclude" submissionType="IRTF" category="
<!-- The abbreviated title is used in the page header - it is only necessary info" consensus="true" docName="draft-irtf-nwcrg-bats-07" number="9426" ipr="tru
if the st200902" obsoletes="" updates="" xml:lang="en" tocInclude="true" tocDepth="4" s
full title is longer than 39 characters --> ymRefs="true" sortRefs="true" version="3">
<title abbrev="BATS Code">BATS Coding Scheme for Multi-hop Data Transport</t <!-- xml2rfc v2v3 conversion 3.9.0 -->
itle>
<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 -->
<front>
<title abbrev="BATS Code">BATched Sparse (BATS) Coding Scheme for Multi-hop
Data Transport</title>
<seriesInfo name="RFC" value="9426"/>
<author fullname="Shenghao Yang" initials="S" surname="Yang"> <author fullname="Shenghao Yang" initials="S" surname="Yang">
<organization>CUHK(SZ)</organization> <organization>CUHK(SZ) &amp; n-hop technologies</organization>
<address> <address>
<postal> <postal>
<street/> <street/>
<!-- Reorder these if your country does things differently -->
<city>Shenzhen</city> <city>Shenzhen</city>
<region>Guangdong</region> <region>Guangdong</region>
<code/> <code/>
<country>China</country> <country>China</country>
</postal> </postal>
<phone>+86 755 8427 3827</phone> <phone>+86 755 8427 3827</phone>
<email>shyang@cuhk.edu.cn</email> <email>shyang@cuhk.edu.cn</email>
<!-- uri and facsimile elements may also be added -->
</address> </address>
</author> </author>
<author fullname="Xuan Huang" initials="X" surname="Huang"> <author fullname="Xuan Huang" initials="X" surname="Huang">
<organization>CUHK</organization> <organization>CUHK</organization>
<address> <address>
<postal> <postal>
<street/> <street/>
<!-- Reorder these if your country does things differently -->
<city>Hong Kong</city> <city>Hong Kong</city>
<region>Hong Kong SAR</region> <region>Hong Kong SAR</region>
<code/> <code/>
<country>China</country> <country>China</country>
</postal> </postal>
<phone>+852 3943 8375</phone> <phone>+852 3943 8375</phone>
<email>1155136647@link.cuhk.edu.hk</email> <email>1155136647@link.cuhk.edu.hk</email>
<!-- uri and facsimile elements may also be added -->
</address> </address>
</author> </author>
<author surname="R.W. Yeung" fullname="Raymond W. Yeung"> <author fullname="Raymond W. Yeung" initials="R" surname="Yeung">
<organization>CUHK</organization> <organization>CUHK &amp; n-hop technologies</organization>
<address> <address>
<postal> <postal>
<street/> <street/>
<!-- Reorder these if your country does things differently -->
<city>Hong Kong</city> <city>Hong Kong</city>
<region>Hong Kong SAR</region> <region>Hong Kong SAR</region>
<code/> <code/>
<country>China</country> <country>China</country>
</postal> </postal>
<phone>+852 3943 8375</phone> <phone>+852 3943 8375</phone>
<email>whyeung@ie.cuhk.edu.hk</email> <email>whyeung@ie.cuhk.edu.hk</email>
<!-- uri and facsimile elements may also be added -->
</address> </address>
</author> </author>
<author fullname="John K. Zao" surname="J.K. Zao"> <author fullname="John K. Zao" surname="Zao" initials="J.">
<!--organization>National Chiao Tung University</organization--> <organization>CUHK</organization>
<organization>NCTU</organization>
<address> <address>
<postal> <postal>
<street/> <street/>
<!-- Reorder these if your country does things differently --> <city>Hong Kong</city>
<city>Hsinchu</city> <region>Hong Kong SAR</region>
<region>Taiwan</region>
<code/> <code/>
<country>China</country> <country>China</country>
</postal> </postal>
<phone/> <phone>+852 3943 8346</phone>
<email>jkzao@ieee.org</email> <email>johnzao@ie.cuhk.edu.hk</email>
<!-- uri and facsimile elements may also be added -->
</address> </address>
</author> </author>
<date year="2023" month="January" day="4"/> <date year="2023" month="July"/>
<!-- If the month and year are both specified and are the current ones, xml2 <workgroup>Coding for Efficient Network Communications</workgroup>
rfc will fill
in the current day for you. If only the current year is specified, xml2
rfc will fill
in the current day and month for you. If the year is not the current on
e, it is
necessary to specify at least a month (xml2rfc assumes day="1" if not s
pecified for the
purpose of calculating the expiry date). With drafts it is normally su
fficient 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. --
>
<keyword>BATS code</keyword> <keyword>BATS code</keyword>
<keyword>multi-hop</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> <abstract>
<t>Linear network coding can in general improve the network communication performance in terms of throughput, latency and reliability. BATched Sparse (BAT S) code is a class of efficient linear network coding scheme with a matrix gener alization of fountain codes as the outer code, and batch-based linear network co ding as the inner code. This document describes a baseline BATS coding scheme fo r communication through multi-hop networks, and discusses the related research i ssues towards a more sophisticated BATS coding scheme. This document is a produc t of the Coding for Efficient Network Communications Research Group (NWCRG).</t> <t>In general, linear network coding can improve the network communication performance in terms of throughput, latency, and reliability. BATched Sparse (B ATS) code is a class of efficient linear network coding scheme with a matrix gen eralization of fountain codes as the outer code and batch-based linear network c oding as the inner code. This document describes a baseline BATS coding scheme f or communication through multi-hop networks and discusses the related research i ssues towards a more sophisticated BATS coding scheme. This document is a produc t of the Coding for Efficient Network Communications Research Group (NWCRG).</t>
</abstract> </abstract>
</front> </front>
<middle> <middle>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Introduction</name> <name>Introduction</name>
<t>This document specifies a baseline <xref target="Yang14" format="defaul <t>This document specifies a baseline <xref target="Yang14" format="defaul
t">BATched Sparse (BATS) code</xref> scheme for data delivery in multi-hop netwo t">BATched Sparse (BATS) code</xref> scheme for data delivery in multi-hop netwo
rks, and discusses the related research issues towards a more sophisticated sche rks and discusses the related research issues towards a more sophisticated schem
me. The BATS code described here includes an outer code and an inner code. The o e. The BATS code described here includes an outer code and an inner code. The ou
uter code is a matrix generalization of fountain codes (see also the RapterQ cod ter code is a matrix generalization of fountain codes (see also the RaptorQ code
e described in <xref target="RFC6330" format="default">RFC&nbsp;6330</xref>), wh described in <xref target="RFC6330" format="default"/>), which inherits the adv
ich inherits the advantages of reliability and efficiency and possesses the extr antages of reliability and efficiency and possesses the extra desirable property
a desirable property of being network coding compatible. The inner code, also ca of being compatible with network coding. The inner code, also called recoding,
lled recoding, is formed by linear network coding for combating packet loss, imp is formed by linear network coding for combating packet loss, improving the mult
roving the multicast efficiency, etc. A detailed design and analysis of BATS cod icast efficiency, etc. A detailed design and analysis of BATS codes are provided
es are provided in the <xref target="Yang17" format="default">BATS monograph</xr in the <xref target="Yang17" format="default">BATS monograph</xref>.</t>
ef>.</t> <t>A BATS coding scheme can be applied in multi-hop networks formed by wir
<t>A BATS coding scheme can be applied in multi-hop networks formed by wir eless communication links, which are inherently unreliable due to interference,
eless communication links, which are inherently unreliable due to interference, fading, multipath, etc. Existing transport protocols like TCP use end-to-end re
fading, multipath, etc. Existing transport protocols like TCP use end-to-end re transmission, while network protocols such as IP might enable store-and-forward
transmission, while network protocols such as IP might enable store-and-forward at the relays so that packet loss would accumulate along the way.</t>
at the relays, so that packet loss would accumulate along the way.</t> <t>A BATS coding scheme can be used for various data delivery applications
<t>A BATS coding scheme can be used for various data delivery applications , like file transmission, video streaming over wireless multi-hop networks, etc.
like file transmission, video streaming over wireless multi-hop networks, etc. Different from the forward error correction (FEC) schemes that are applied eith
Different from traditional forward error correcting (FEC) schemes that are appli er hop-by-hop or end-to-end, the BATS coding scheme combines the end-to-end codi
ed either hop-by-hop or end-to-end, the BATS coding scheme combines the end-to-e ng (the outer code) with certain hop-by-hop coding (the inner code) and hence ca
nd coding (the outer code) with certain hop-by-hop coding (the inner code), and n potentially achieve better performance.</t>
hence can potentially achieve better performance.</t> <t>The baseline coding scheme described here considers a network with mult
<t>The baseline coding scheme described here considers a network with mult iple communication flows. For each flow, the source node encodes the data for tr
iple communication flows. For each flow, the source node encodes the data for tr ansmission separately. However, inside the network, it is possible to mix the pa
ansmission separately. Inside the network, however, it is possible to mix the pa ckets from different flows for recoding. In this document, we describe a simple
ckets 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/d
case where recoding is performed within each flow. Note that the same encoding/d ecoding scheme described here can be used with different recoding schemes as lon
ecoding scheme described here can be used with different recoding schemes as lon g as they follow the principle we illustrate in this document.</t>
g 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 dest ination node. Communicating the same data to multiple destination nodes is calle d multicast. Refer to <xref target="research" format="default"/> for the further discussion of multicast. </t> <t>In this document, we focus on the case that each flow has only one dest ination node. Communicating the same data to multiple destination nodes is calle d 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 pr ovides researchers and engineers a starting point for developing network communi cation applications/protocols based on BATS codes. Second, it helps to make the research issues clearer towards a sophisticated BATS code based network protocol . Important research directions include the security issues, congestion control and routing algorithms for BATS codes, etc. </t> <t>The purpose of the baseline BATS coding scheme is twofold. First, it pr ovides researchers and engineers a starting point for developing network communi cation applications/protocols based on BATS codes. Second, it helps to make the research issues clearer towards a sophisticated network protocol based on BATS c odes. Important research directions include the security issues, congestion cont rol, routing algorithms for BATS codes, etc. </t>
<t> This document is a product of and represents the collaborative work an d consensus of the Coding for Efficient Network Communications Research Group (N WCRG). It is not an IETF product and is not an IETF standard.</t> <t> This document is a product of and represents the collaborative work an d consensus of the Coding for Efficient Network Communications Research Group (N WCRG). It is not an IETF product and is not an IETF standard.</t>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Requirements Language</name> <name>Requirements Language</name>
<t>The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", <t>
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this The key words "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>", "<bcp14>REQU
document are to be interpreted as described in <xref target="RFC2119" fo IRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL
rmat="default">RFC 2119</xref>.</t> NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>", "<bcp14>
RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
"<bcp14>MAY</bcp14>", and "<bcp14>OPTIONAL</bcp14>" in this document are to
be interpreted as
described in BCP&nbsp;14 <xref target="RFC2119"/> <xref target="RFC8174"/>
when, and only when, they appear in all capitals, as shown here.
</t>
</section> </section>
<!--Requirements Language-->
</section> </section>
<!--Introduction-->
<section anchor="procedures" numbered="true" toc="default"> <section anchor="procedures" numbered="true" toc="default">
<name>A Use Case of BATS Coding Scheme</name> <name>A Use Case of the BATS Coding Scheme</name>
<t>The BATS coding scheme described in this document can be used, for exam <t>The BATS coding scheme described in this document can be used, for exam
ple, by a Data Delivery Protocol (DDP). Though this document is not about a DDP, ple, by a Data Delivery Protocol (DDP). Though this document is not about a DDP,
we briefly illustrate in this section how a BATS coding scheme is employed by a in this section, we briefly illustrate how a BATS coding scheme is employed by
DDP to make the role of the coding scheme clear. Some terms that will be used i a DDP to make the role of the coding scheme clear. Some terms that will be used
n this section are summarized here:</t> in this section are summarized here:</t>
<ul spacing="normal"> <dl newline="false" spacing="normal">
<li>DDP: data delivery protocol.</li> <dt>DDP:</dt> <dd>Data Delivery Protocol</dd>
<li>DDP packet: the packet formed by a DDP employing a BATS coding sch <dt>DDP packet:</dt> <dd>the packet formed by a DDP employing a BATS c
eme.</li> oding scheme</dd>
<li>source packet: the packet formed by the data for delivery.</li> <dt>source packet:</dt> <dd>the packet formed by the data for delivery
<li>outer encoder: the outer code encoder of a BATS code.</li> </dd>
<li>recoder: the inner code encoder of a BATS code.</li> <dt>outer encoder:</dt> <dd>the outer code encoder of a BATS code</dd>
<li>outer decoder: the outer code decoder of a BATS code.</li> <dt>recoder:</dt> <dd>the inner code encoder of a BATS code</dd>
<li>coded packet: the packet generated by the outer code encoder or a <dt>outer decoder:</dt> <dd>the outer code decoder of a BATS code</dd>
recoder.</li> <dt>coded packet:</dt> <dd>the packet generated by the outer code enco
<li>batch: a set of coded packets generated by a BATS coding scheme fr der or a recoder</dd>
om the same subset of the source packets.</li> <dt>batch:</dt> <dd>a set of coded packets generated by a BATS coding
<li>recoded packet: a coded packet generated by a recoder.</li> scheme from the same subset of the source packets</dd>
<li>degree: the number of source packets used to generate a batch by t <dt>recoded packet:</dt> <dd>a coded packet generated by a recoder</dd
he outer encoder. The degree can be different for different batch.</li> >
</ul> <dt>degree:</dt> <dd>the number of source packets used to generate a b
<t>Other common terms can be found in <xref target="RFC8406" format="def atch by the outer encoder. (The degree can be different for a different batch.)<
ault">RFC 8406</xref>.</t> /dd>
</dl>
<t>Other common terms can be found in <xref target="RFC8406" format="def
ault"/>.</t>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Introduction</name> <name>Introduction</name>
<t>We describe a data delivery process that involves one source node, on e destination node, and multiple intermediate nodes in between. A BATS coding sc heme includes an outer code encoder (also called outer encoder), an inner code e ncoder (also called recoder), and an outer decoder which decodes the outer code and the inner code jointly as illustrated in <xref target="network_model" format ="default"/>. The functions of the outer encoder, recoder and outer decoder are described below: </t> <t>We describe a DDP that involves one source node, one destination node , and multiple intermediate nodes in between. A BATS coding scheme includes an o uter code encoder (also called outer encoder), an inner code encoder (also calle d recoder), and an outer decoder that decodes the outer code and the inner code jointly, as illustrated in <xref target="network_model" format="default"/>. The functions of the outer encoder, recoder, and outer decoder are described below: </t>
<figure anchor="network_model"> <figure anchor="network_model">
<name>A network model for data delivery.</name> <name>A Network Model for Data Delivery</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <artwork name="" type="" align="center" alt=""><![CDATA[
| |
| {set of source packets} | {set of source packets}
v v
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| outer encoder | | outer encoder |
| v | source node | v | source node
| recoder | | recoder |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| |
| {set of DDP packets} | {set of DDP packets}
v v
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| | | |
| recoder | intermediate node | recoder | intermediate node
| | | |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| |
| {set of DDP packets} | {set of DDP packets}
v v
... ...
| |
| {set of DDP packets} | {set of DDP packets}
v v
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| | | |
| outer decoder | destination node | outer decoder | destination node
| | | |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| |
| {set of source packets} | {set of source packets}
v v
]]></artwork> ]]></artwork>
</figure> </figure>
<t>At the source node, the DDP first processes the data to be delivered into a number of source packets each of the same number of bits (see details in <xref target="ddp_padding" format="default" />), and then provides all the sourc e packets to the outer encoder. The outer encoder will further generate a sequen ce of batches, each consisting of a fixed number of coded packets (see the descr iption in <xref target="ddp_encoder" format="default" />).</t> <t>At the source node, the DDP first processes the data to be delivered into a number of source packets, each of the same number of bits (see details in <xref target="ddp_padding" format="default" />), and then provides all the sour ce packets to the outer encoder. The outer encoder will further generate a seque nce of batches, each consisting of a fixed number of coded packets (see the desc ription in <xref target="ddp_encoder" format="default" />).</t>
<t>Each batch generated at the source node is further processed by the r ecoder 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="dd p_recoder" format="default" />). After processed by the recoder, the DDP forms a nd transmits the DDP packets using the coded packets, together with the correspo nding batch information.</t> <t>Each batch generated at the source node is further processed by the r ecoder 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="dd p_recoder" format="default" />). After it is processed by the recoder, The DDP f orms and transmits the DDP packets using the coded packets, together with the co rresponding batch information.</t>
<t>We assume that a DDP packet is either correctly received or completel y erased during the communication. The DDP extracts the coded packets and the co rresponding batch information from its received DDP packets. A recoder is employ ed at an intermediate node that does not need the data, and generates recoded pa ckets 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>We assume that a DDP packet is either correctly received or completel y erased during the communication. The DDP extracts the coded packets and the co rresponding batch information from its received DDP packets. A recoder is employ ed at an intermediate node that does not need the data and generates recoded pac kets for each batch (see the description in <xref target="ddp_recoder" format="d efault" />). The DDP forms and transmits DDP packets using the recoded packets a nd 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 transmitt ed data using the received batches (see the description in <xref target="ddp_dec oder" format="default" />). The DDP sends the decoded data to the application th at needs the data.</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 transmitt ed data using the received batches (see the description in <xref target="ddp_dec oder" format="default" />). The DDP sends the decoded data to the application th at needs the data.</t>
</section> </section>
<!--Introduction-->
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Data Delivery Procedures</name> <name>DDP Procedures</name>
<t>Suppose that the DDP has F octets of data for transmission. We descri <t>Suppose that the DDP has F octets of data for transmission. We descri
be the procedures of one BATS session for transmitting the F octets. There is a be 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, 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 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 discussed in this a single BATS session depends on the coding parameters that are discussed in th
section, and will be calculated at the end of <xref target="packetformat" />.</t is section and the calculations described at the end of <xref target="packetform
> at" />.</t>
<section anchor="ddp_padding" numbered="true" toc="default"> <section anchor="ddp_padding" numbered="true" toc="default">
<name>Source Node Data Partitioning and Padding</name> <name>Source Node Data Partitioning and Padding</name>
<t> <t>
The DDP first determines the following parameters: The DDP first determines the following parameters:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>Batch size (M): the number of coded packets in a batch generated <li>batch size (M): the number of coded packets in a batch generated
by the outer encoder.</li> by the outer encoder</li>
<li>Recoding field size (q): the number of elements in the finite fi <li>recoding field size (q): the number of elements in the finite fi
eld for recoding. q is 2 or 2^8</li> eld for recoding, i.e., q is 2 or 2<sup>8</sup></li>
<li>BATS payload size (TO): the number of payload octets in a BATS p <li>BATS payload size (TO): the number of payload octets in a BATS p
acket, including the coded data and the coefficient vector.</li> acket, including the coded data and the coefficient vector</li>
</ul> </ul>
<t> Based on the above parameters, the parameters T, CO and K are calc ulated as follows: <t> Based on the above parameters, the parameters T, CO, and K are cal culated as follows:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>CO: the number of octets of a coefficient vector, calculated as <li>CO: the number of octets of a coefficient vector, calculated as
CO = ceil(M*log2(q)/8), which is also called the coefficient vector overhead.</l CO = ceil(M * log2(q) / 8), which is also called the coefficient vector overhead
i> </li>
<li>T: the number of data octets of a coded packet, calculated as T <li>T: the number of data octets of a coded packet, calculated as T
= TO - CO.</li> = TO - CO</li>
<li>K: number of source packets, calculated as K = floor(F/T)+1. </l <li>K: number of source packets, calculated as K = floor(F / T) + 1<
i> /li>
</ul> </ul>
<t> <t>
The data MUST be padded to have T*K octets, which will be partiti The data <bcp14>MUST</bcp14> be padded to have T*K octets, which
oned into K source packets b[0], ..., b[K-1], each of T octets. will be partitioned into K source packets b[0], ..., b[K - 1], each of T octets.
In our padding scheme, b[0], ..., b[K-2] are filled with data oct In our padding scheme, b[0], ..., b[K - 2] are filled with data o
ets, and b[K-1] is filled with the remaining data octets and padding octets. ctets, and b[K - 1] is filled with the remaining data octets and padding octets.
Let P = K*T-F denote the number of padding octets. We use b[K-1, 0] Let P = K * T - F denote the number of padding octets. We use b[K -
, ..., b[K-1, T-P-1] to denote the T-P source octets and b[K-1, T-P], ..., b[K-1 1, 0], ..., b[K - 1, T - P - 1] to denote the T - P source octets and b[K - 1,
, T-1] to denote the P padding octets in b[K-1], respectively. The padding inser T - P], ..., b[K - 1, T - 1] to denote the P padding octets in b[K - 1], respect
tion process is shown in <xref target="data_padding" format="default"/>.</t> ively. The padding insertion process is shown in <xref target="data_padding" for
mat="default"/>.</t>
<figure anchor="data_padding"> <figure anchor="data_padding">
<name>Data Padding Insertion Process</name> <name>Data Padding Insertion Process</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <sourcecode type="pseudocode"><![CDATA[
Z = T - P Z = T - P
j = 1 j = 1
v = 1 v = 1
Let bl be the last source packet b[K-1] Let bl be the last source packet b[K - 1]
for i = Z, Z+1, ..., T-1 do for i = Z, Z + 1, ..., T - 1 do
bl[i] = j bl[i] = j
if i+1 >= v+Z do if i + 1 >= v + Z do
j += 1 j += 1
v += j v += j
]]></artwork> ]]></sourcecode>
</figure> </figure>
</section> </section>
<!--Padding-->
<section anchor="ddp_encoder" numbered="true" toc="default"> <section anchor="ddp_encoder" numbered="true" toc="default">
<name>Source Node Outer Code Encoding Procedure</name> <name>Source Node Outer Code Encoding Procedure</name>
<t> <t>
The DDP provides the BATS encoder with the following information: The DDP provides the BATS encoder with the following information:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>Batch size (M): the number of coded packets in a batch.</li> <li>batch size (M): the number of coded packets in a batch</li>
<li>Recoding field size (q): the number of elements in the finite fi <li>recoding field size (q): the number of elements in the finite fi
eld for recoding.</li> eld for recoding</li>
<li>Maximum degree (MAX_DEG): a positive integer that specifies the <li>maximum degree (MAX_DEG): a positive integer that specifies the
largest degree can be used.</li> largest degree can be used</li>
<li>Degree distribution (DD): an unsigned integer array of size MAX_ <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, w DEG+1. The i-th entry DD[i] is the probability that i is chosen as the degree, w
here i is between 0 and MAX_DEG.</li> here i is between 0 and MAX_DEG.</li>
<li>A sequence of batch IDs (BID) (j, j = 0, 1, ...).</li> <li>a sequence of batch IDs (BIDs) (j, j = 0, 1, ...)</li>
<li>Number of source packets (K).</li> <li>number of source packets (K)</li>
<li>Packet size (T): the number of octets in a source packet.</li> <li>packet size (T): the number of octets in a source packet</li>
<li>Source packets (b[i], i = 0, 1, ..., K-1).</li> <li>source packets (b[i], i = 0, 1, ..., K - 1)</li>
</ul> </ul>
<t> <t>
Using this information, the outer encoder generates M coded packets fo r each batch ID using the following steps to be described in details at <xref ta rget="encoder" format="default"/>:</t> Using this information, the outer encoder generates M coded packets fo r each BID using the following steps that are described in detail in <xref targe t="encoder" format="default"/>:</t>
<ul spacing="normal"> <ul spacing="normal">
<li> Obtain a degree d by sampling DD. Roughly, the value d is chose n with probability DD[d].</li> <li> Obtain a degree d by sampling DD. Roughly, the value d is chose n with probability DD[d].</li>
<li> Choose d source packets uniformly at random from all the K sour ce packets. It is allowed that a source packet is used by mutiple batches.</li> <li> Choose d source packets uniformly at random from all the K sour ce packets. It is allowed that a source packet is used by multiple batches.</li>
<li> Generate M coded packets using the d source packets.</li> <li> Generate M coded packets using the d source packets.</li>
</ul> </ul>
<t>The DDP receives from the outer encoder a sequence of batches, wher e the batch with ID j has <t>From the outer encoder, the DDP receives a sequence of batches, whe re the batch with ID j has M coded packets (x[j,i], i =0, 1, ..., M - 1), each c ontaining TO octets.
</t> </t>
<ul spacing="normal">
<!--li>a degree d[j], and</li-->
<li>M coded packets (x[j,i], i =0, 1, ..., M-1), each containing TO
octets.</li>
</ul>
<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 deliver with eac h coded packet with its batch ID, which will be further used by both recoder and decoder. The DDP will use the batches to form DDP packets to be transmitted to other network nodes towards the destination nodes. The DDP <bcp14>MUST</bcp14> d eliver each coded packet with its batch ID, which will be further used by both t he recoder and decoder.
</t> </t>
<t>The DDP <bcp14>MUST</bcp14> deliver some of the information us
<t>The DDP MUST deliver some of the information used by the encod ed by the encoder to each of the recoders and the decoder, either embedded in th
er to each recoder and the decoder, either embedded in the DDP packets or transm e DDP packets or transmitted using separated protocol messages.
itted using separated protocol messages: For recoders, the DDP <bcp14>MUST</bcp14> deliver the following inform
For recoders, the DDP MUST deliver the following information to each r ation to each recoder:
ecoder:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>M: batch size</li> <li>M: batch size</li>
<li>q: recoding field size.</li> <li>q: recoding field size</li>
</ul> </ul>
<t> <t>
For the decoder, the DDP MUST deliver the following information to the decoder: For the decoder, the DDP <bcp14>MUST</bcp14> deliver the following inf ormation to the decoder:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>M: batch size</li> <li>M: batch size</li>
<li>q: recoding field size</li> <li>q: recoding field size</li>
<li>K: the number of source packets</li> <li>K: the number of source packets</li>
<li>T: the number of octets in a source packet</li> <li>T: the number of octets in a source packet</li>
<li>DD: the degree distribution.</li> <li>DD: the degree distribution</li>
</ul> </ul>
<t> <t>
The BID is used by both recoders and decoders. We will illustrate in < xref target="parameters" /> that 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 <xref target="Yang17" /> about how to design a good degree distribution. On ce designed, the degree distribution can be shared between the source node and t he destination node by the DDP, which is not further discussed here. The BID is used by both recoders and decoders. In <xref target="parame ters"/>, we illustrate how to embed BID, M, q, and K into DDP packets. The degre e distribution DD does not need to be changed frequently. See Section 6 of <xref target="Yang17" /> about how to design a good degree distribution. Once designe d, the degree distribution can be shared between the source node and the destina tion node by the DDP, which is not further discussed here.
</t> </t>
</section> </section>
<section anchor="ddp_recoder" numbered="true" toc="default"> <section anchor="ddp_recoder" numbered="true" toc="default">
<name>Recoding Procedures</name> <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 b atches from the outer code encoding procedure. At an intermediate node, the DDP receives the DDP packets from the other network nodes. <t>Both the source node and the intermediate nodes perform recoding on the batches before transmission. At the source node, the recoder receives the b atches 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 not to recode, it just forwards the DDP packets it received. If the DDP 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. Otherwise, the DDP should be able to extract coded packets and the corresponding batch information from these packets.
</t> </t>
<t> <t>
For a received batch, the DDP determines a positive integer Mr, the number of recoded packets to be transmitted for the batch, and provides the reco der with the following information: For a received batch, the DDP determines a positive integer (Mr) and the number of recoded packets to be transmitted for the batch, and DDP provides the recoder with the following information:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>the batch size M,</li> <li>M: batch size</li>
<li>the recoding field size q,</li> <li>q: recoding field size</li>
<li>a number of received coded packets of the same batch, each conta <li>a number of received coded packets of the same batch, each conta
ining TO octets, and</li> ining TO octets</li>
<li>the number of recoded packets to be generated (Mr).</li> <li>Mr: the number of recoded packets to be generated</li>
</ul> </ul>
<t> <t>
The recoder uses the information provided by the DDP to generate Mr recoded packets, each containing TO octets, to be described in <xref target="re coder" format="default"/>. The DDP uses the Mr recoded packets to form the DDP p ackets for transmitting. The recoder uses the information provided by the DDP to generate Mr recoded packets, each containing TO octets, which are described in <xref target ="recoder" format="default"/>. The DDP uses the Mr recoded packets to form the D DP packets for transmitting.
</t> </t>
</section> </section>
<section anchor="ddp_decoder" numbered="true" toc="default"> <section anchor="ddp_decoder" numbered="true" toc="default">
<name>Destination Node Procedures</name> <name>Destination Node Procedures</name>
<t> <t>
At the destination node, the DDP receives DDP packets from an intermed iate network node, and should be able to extract coded packets and the correspon ding batch information from these packets. The DDP then employs an outer decoder to recover the data transmitted by the source node. At the destination node, the DDP receives DDP packets from an intermed iate network node and should be able to extract coded packets and the correspond ing batch information from these packets. The DDP then employs an outer decoder to recover the data transmitted by the source node.
</t> </t>
<t> <t>
The DDP provides the outer decoder (to be described in <xref target="d ecoder" format="default"/>) with the following information: The DDP provides the outer decoder (to be described in <xref target="d ecoder" format="default"/>) with the following information:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<!-- <t>F: number of octets in the data,</t> --> <li>M: batch size</li>
<li>M: batch size,</li> <li>q: recoding field size</li>
<li>q: recoding field size,</li>
<li>K: the number of source packets</li> <li>K: the number of source packets</li>
<li>T: the number of octets of a source packet</li> <li>T: the number of octets of a source packet</li>
<li>A sequence of batches, each of which is formed by a number of co ded packets belonging to the same batch, with their corresponding BIDs.</li> <li>a sequence of batches, each of which is formed by a number of co ded packets belonging to the same batch, with their corresponding BIDs</li>
</ul> </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 targe t="decoder" />). If successful, the decoder returns the recovered K source packe ts to the DDP, which will use the K source packets to form the F octets data. Th e recommended padding deletion process is shown as follows:</t> <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 targe t="decoder" />). If successful, the decoder returns the recovered K source packe ts to the DDP, which will use the K source packets to form the F octets data. Th e recommended padding deletion process is shown as follows:</t>
<figure anchor="data_depadding"> <figure anchor="data_depadding">
<name>Data Padding Deletion Process</name> <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 // this procedure returns the number P of padding octets
// at the end of b[K-1] // at the end of b[K - 1]
Let bl be the last decoded source packet b[K-1] Let bl be the last decoded source packet b[K - 1]
PL = bl[T-1] PL = bl[T - 1]
if PL == 1 do if PL == 1 do
return P = 1 return P = 1
WI = T - 1 WI = T - 1
while bl[WI] == PL do while bl[WI] == PL do
WI = WI - 1 WI = WI - 1
return P = (1 + bl[WI]) * bl[WI] + T - WI - 1 return P = (1 + bl[WI]) * bl[WI] + T - WI - 1
]]></artwork> ]]></sourcecode>
</figure> </figure>
</section> </section>
</section> </section>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Recommendation for the Parameters</name> <name>Recommendation for the Parameters</name>
<t> <t>
The recommendation for the parameters M and q is shown as follows: The recommendation for the parameters M and q is shown as follows:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>When q=2, M=16,32,64,128</li> <li>when q = 2, M = 16, 32, 64, 128</li>
<li>When q=256, M=4,8,16,32</li> <li>when q = 256, M = 4, 8, 16, 32</li>
</ul> </ul>
<t> <t>
It is RECOMMENDED that K is at least 128. The encoder/decoder SHALL supp ort an arbitrary positive integer value less than 2^16. However, the BATS coding scheme to be described is not optimized for small K. It is <bcp14>RECOMMENDED</bcp14> that K is at least 128. The encoder/dec oder <bcp14>SHALL</bcp14> support an arbitrary positive integer value less than 2<sup>16</sup>. However, the BATS coding scheme to be described is not optimized for small K.
</t> </t>
</section> </section>
<!--Recommendation for the Parameters-->
<section anchor="parameters" numbered="true" toc="default"> <section anchor="parameters" numbered="true" toc="default">
<name>Coding Parameters in DDP Packets</name> <name>Coding Parameters in DDP Packets</name>
<t>Here we provide an example of embedding the aforementioned BATS codin <t>Here, we provide an example of embedding the aforementioned BATS codi
g parameters into the DDP packets which will be used for recoding and decoding. ng parameters into the DDP packets that will be used for recoding and decoding.
A DDP can form a DDP packet using a coded packet by adding necessary information A DDP can form a DDP packet using a coded packet by adding necessary info
that can help to deliver the DPP packet to the next node, e.g., the DDP protoco rmation that can help to deliver the DDP packet to the next node (e.g., the vers
l version, addresses and session identifiers. We will not go into the details of ion of the DDP, addresses, and session identifiers). We will not go into the det
formatting these fields in a DDP packet, but focus on how to format the coding ails of formatting these fields in a DDP packet, but we focus on how to format t
parameters and the coded packet in a DDP packet.</t> he coding parameters and the coded packet in a DDP packet.</t>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Coding Parameter Format</name> <name>Coding Parameter Format</name>
<t> Here we provide an example of using 32 bits (4 octets) to embed th e parameters K, M, q, and BID. The 32 bits are separated into three subfields, d enoted as K, Mq and BID, respectively, as illustrated in <xref target="packet_he ader"/>.</t> <t>Here, we provide an example of using 32 bits (4 octets) to embed th e parameters K, M, q, and BID. The 32 bits are separated into three subfields, d enoted as K, Mq, and BID, respectively, as illustrated in <xref target="packet_h eader"/>.</t>
<figure anchor="packet_header"> <figure anchor="packet_header">
<name>Coding parameter field format.</name> <name>Coding Parameter Field Format</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <artwork name="" type="" align="center" alt=""><![CDATA[
0 1 2 3 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 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 | | K | Mq | BID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork> ]]></artwork>
</figure> </figure>
<ul spacing="normal"> <dl newline="false" spacing="normal">
<li>K: 16-bit unsigned integer, specifying the number of source pack <dt>K:</dt> <dd>16-bit unsigned integer, specifying the number of so
ets of the BATS session.</li> urce packets of the BATS session</dd>
<li>Mq: 3-bit unsigned integer to specify the value of M and q as <x <dt>Mq:</dt> <dd>3-bit unsigned integer, specifying the value of M a
ref target="Mq_value" format="default"/>.</li> nd q, as shown in <xref target="Mq_value" format="default"/></dd>
<li>BID: 13-bit unsigned integer, specifying the batch ID of the bat <dt>BID:</dt> <dd>13-bit unsigned integer, specifying the batch ID o
ch the packet belongs to.</li> f the batch the packet belongs to</dd>
<!--li>d: 8-bit unsigned integer, specifying the batch degree of the </dl>
batch the packet belongs to.</li-->
</ul>
<table anchor="Mq_value" align="center"> <table anchor="Mq_value" align="center">
<name>Values of Mq field</name> <name>Values of the Mq Field</name>
<thead> <thead>
<tr> <tr>
<th align="left">Mq</th> <th align="left">Mq</th>
<th align="left">M</th> <th align="left">M</th>
<th align="left">q</th> <th align="left">q</th>
<!-- <th align="left">O</th> -->
</tr> </tr>
</thead> </thead>
<tbody> <tbody>
<tr> <tr>
<td align="left">000</td> <td align="left">000</td>
<td align="left">16</td> <td align="left">16</td>
<td align="left">2</td> <td align="left">2</td>
<!-- <td align="left">2</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">010</td> <td align="left">010</td>
<td align="left">32</td> <td align="left">32</td>
<td align="left">2</td> <td align="left">2</td>
<!-- <td align="left">2</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">100</td> <td align="left">100</td>
<td align="left">64</td> <td align="left">64</td>
<td align="left">2</td> <td align="left">2</td>
<!-- <td align="left">4</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">110</td> <td align="left">110</td>
<td align="left">128</td> <td align="left">128</td>
<td align="left">2</td> <td align="left">2</td>
<!-- <td align="left">8</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">001</td> <td align="left">001</td>
<td align="left">4</td> <td align="left">4</td>
<td align="left">256</td> <td align="left">256</td>
<!-- <td align="left">8</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">011</td> <td align="left">011</td>
<td align="left">8</td> <td align="left">8</td>
<td align="left">256</td> <td align="left">256</td>
<!-- <td align="left">16</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">101</td> <td align="left">101</td>
<td align="left">16</td> <td align="left">16</td>
<td align="left">256</td> <td align="left">256</td>
<!-- <td align="left">32</td> -->
</tr> </tr>
<tr> <tr>
<td align="left">111</td> <td align="left">111</td>
<td align="left">32</td> <td align="left">32</td>
<td align="left">256</td> <td align="left">256</td>
<!-- <td align="left">64</td> -->
</tr> </tr>
</tbody> </tbody>
</table> </table>
<t>The choice of the coding parameters depends on the computation cost, the network conditions and the expected end-to-end coding performance. Usually, a larger batch size M will have a better coding performance, but higher computa tion cost for encoding, recoding and decoding. The field size q affects the coef ficient vector overhead, and also the computation cost for recoding. Within a BA TS session, the BID field should be different for all batches, and hence the max imum number of batches can be generated for the outer encoder is 2^13. For diffe rent BATS sessions, batches can use the same BID.</t> <t>The choice of the coding parameters depends on the computation cost, the network conditions, and the expected end-to-end coding performance. Usually , a larger batch size M will have a better coding performance but higher computa tion cost for encoding, recoding, and decoding. The field size q affects the coe fficient vector overhead and also the computation cost for recoding. Within a BA TS session, the BID field should be different for all batches, and hence, the ma ximum number of batches that can be generated for the outer encoder is 2<sup>13< /sup>. For different BATS sessions, batches can use the same BID.</t>
</section> </section>
<section anchor="packetformat" numbered="true" toc="default"> <section anchor="packetformat" numbered="true" toc="default">
<name>Coded Packet Format</name> <name>Coded Packet Format</name>
<figure anchor="packet_payload"> <figure anchor="packet_payload">
<name>Code packet format in a DDP packet.</name> <name>Code Packet Format in a DDP Packet</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <artwork name="" type="" align="center" alt=""><![CDATA[
CO T CO T
+-----------------------+-------------------------------+ +-----------------------+-------------------------------+
| coefficient vector | coded data | | coefficient vector | coded data |
+-----------------------+-------------------------------+ +-----------------------+-------------------------------+
]]></artwork> ]]></artwork>
</figure> </figure>
<t> <t>
A coded packet has TO=T+CO octets, where the first CO octets contain t he coefficient vector and the remaining T octets contain the coded data. A coded packet has TO=T+CO octets, where the first CO octets contain t he coefficient vector and the remaining T octets contain the coded data.
<!-- Information in both fields MAY be encoded in JSON (ASCII) or prot obuf (binary) formats -->
</t> </t>
<ul spacing="normal"> <dl newline="false" spacing="normal">
<li>coefficient vector: CO = M*log2(q)/8 octets. For the values of M <dt>coefficient vector:</dt> <dd>CO = M * log2(q) / 8 octets. For th
and q in <xref target="Mq_value" format="default"/>, CO is at most 32 octets wh e values of M and q in <xref target="Mq_value" format="default"/>, CO is at most
en q is 256 and 6 octets when q is 2. </li> 32 octets when q is 256 and 6 octets when q is 2. </dd>
<li>coded data: T octets. T should be chosen so that the whole DDP p <dt>coded data:</dt> <dd>T octets. T should be chosen so that the wh
acket is at most PMTU.</li> ole DDP packet is at most Path MTU (PMTU).</dd>
</ul> </dl>
<t>Using the above formation, we can calculate the largest file size F for different parameters. For example, when q=2 and M=128, we have CO = 6 octets . Counting the 4 octets for embedding the coding parameters, we can choose T = P MTU-H-10, where H is the header length of a DDP packet. As K can be at most 2^16 -1, F can be at most (PMTU-H-10)(2^16-1) octets. In this case, K/M is about 2^9 and the BID field allows transmitting 2^4*K/M batches. </t> <t>Using the above formation, we can calculate the largest file size (F ) for different parameters. For example, when q = 2 and M = 128, we have CO = 6 octets. Counting the 4 octets for embedding the coding parameters, we can choose T = PMTU - H - 10, where H is the header length of a DDP packet. As K can be at most 2<sup>16</sup> - 1, F can be at most (PMTU - H - 10)(2<sup>16</sup> - 1) o ctets. In this case, K / M is about 2<sup>9</sup> and the BID field allows trans mitting 2<sup>4</sup> * K / M batches. </t>
</section> </section>
<!-- <section title="Packet Footer">
<figure anchor="packet_footer" title="BATS packet footer format."><artwo
rk><![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 prev
ent pollution attack.</t>
<t>parity check: 1 octet. A parity check field used to verity the co
rrectness of the packet.</t>
</list>
</t>
</section> -->
</section> </section>
</section> </section>
<section anchor="specification" numbered="true" toc="default"> <section anchor="specification" numbered="true" toc="default">
<name>BATS Code Specification</name> <name>BATS Code Specification</name>
<section anchor="common" numbered="true" toc="default"> <section anchor="common" numbered="true" toc="default">
<name>Common Parts</name> <name>Common Parts</name>
<t> <t>
The T octets of a source packets are treated as a column vector of T e lements in GF(256). The CO octets of coefficient vector are treated as a column vector of CO elements in GF(q), where q=2 or q=256. Linear algebra and matrix op erations over finite fields are assumed in this section. The T octets of a source packet are treated as a column vector of T el ements 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 or q&nbsp;=&nbsp;256. Linear algebr a and matrix operations over finite fields are assumed in this section.
</t> </t>
<t> <t>
For the two elements of GF(2), their multiplication corresponds to a lo gical AND operation and their addition is a logical XOR operation. For the two elements of GF(2), their multiplication corresponds to a lo gical AND operation, and their addition is a logical XOR operation.
An element of the field GF(256) can be represented by a polynomial wit h binary coefficients and degree lower or equal to 7. The addition between two e lements of GF(256) is defined as the addition of the two binary polynomials. An element of the field GF(256) can be represented by a polynomial wit h binary coefficients and degree lower or equal to 7. The addition between two e lements of GF(256) is defined as the addition of the two binary polynomials.
The multiplication between two elements of GF(256) is the multiplicati on of the two binary polynomials modulo a certain irreducible polynomial of degr ee 8, called a primitive polynomial. One example of such a primitive polynomial for GF(256) is: The multiplication between two elements of GF(256) is the multiplicati on of the two binary polynomials modulo a certain irreducible polynomial of degr ee 8, called a primitive polynomial. One example of such a primitive polynomial for GF(256) is:
</t> </t>
<ul empty="true" spacing="normal" bare="false"> <t indent="3">x<sup>8</sup> + x<sup>4</sup> + x<sup>3</sup> + x<sup>
<li>x<sup>8</sup> + x<sup>4</sup> + x<sup>3</sup> + x<sup>2</sup> + 2</sup> + 1 </t>
1 </li>
</ul>
<t> <t>
A common primitive polynomial MUST 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. A common primitive polynomial <bcp14>MUST</bcp14> be specified for all t he finite field multiplications over GF(256). Note that a binary polynomial of d egree less than 8 can be represented by a binary sequence of 8 bits, i.e., an oc tet.
</t> </t>
<t> Suppose that a pseudorandom number generator Rand() which generates <t> Suppose that a pseudorandom number generator, Rand(), which generate
an unsigned integer of 32 bits is shared by both encoding and decoding. The pseu s an unsigned integer of 32 bits, is shared by both encoding and decoding. The p
dorandom generator can be initialized by Rand_Init(S) with seed S. When S is not seudorandom generator can be initialized by Rand_Init(S) with seed S. When S is
provided, the pseudorandom generator is initialized arbitrarily. One example of not provided, the pseudorandom generator is initialized arbitrarily. One example
such a pseudorandom generator is defined in <xref target="RFC8682" format="defa of such a pseudorandom generator is defined in <xref target="RFC8682" format="d
ult">RFC&nbsp;8682</xref>.</t> efault"/>.</t>
<t>A function called BatchSampler is used in both encoding and decoding. <t>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 The function takes two integers, j and d, as input and generates an array idx o
d integers and a d x M matrix G. The function first initializes the pseudorand f d integers and a d x M matrix G. The function first initializes the pseudoran
om generator with j, sample d distinct integers from 0 to K-1 as idx, and sample dom generator with j, sample d distinct integers from 0 to K-1 as idx, and sampl
d*M integers from 0 to 255 as G. See the pseudocode in <xref target="batch_samp e d*M integers from 0 to 255 as G. See the pseudocode in <xref target="batch_sam
ler" format="default"/>. </t> pler" format="default"/>. </t>
<figure anchor="batch_sampler"> <figure anchor="batch_sampler">
<name>Batch Sampler Function</name> <name>Batch Sampler Function</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <sourcecode type="pseudocode"><![CDATA[
function BatchSampler(j,d) function BatchSampler(j, d)
// initialize the pseudorandom generator by seed j. // initialize the pseudorandom generator by seed j.
Rand_Init(j) Rand_Init(j)
// sample d distinct integers between 0 and K-1. // sample d distinct integers between 0 and K - 1.
for k = 0, ..., d-1 do for k = 0, ..., d - 1 do
r = Rand() % K r = Rand() % K
while r already exists in idx do while r already exists in idx do
r = Rand() % K r = Rand() % K
idx[k] = r idx[k] = r
// sample d x M matrix // sample d x M matrix
for r = 0, ..., d-1 do for r = 0, ..., d - 1 do
for c = 0,...,M-1 do for c = 0, ..., M - 1 do
G[r,c] = Rand() % 256 G[r, c] = Rand() % 256
return idx, G return idx, G
]]></artwork> ]]></sourcecode>
</figure> </figure>
</section> </section>
<section anchor="encoder" numbered="true" toc="default"> <section anchor="encoder" numbered="true" toc="default">
<name>Outer Code Encoder</name> <name>Outer Code Encoder</name>
<t>Define a function called DegreeSampler that returns an integer d usin g the degree distribution DD. We expect that the empirical distribution of the r eturning d converges to DD(d) when d &lt; K. One design of DegreeSampler is illu strated in <xref target="degree_sampler" format="default"/>. Note that when K &l t; MAX_DEG, the degree value returned by DegreeSampler does not exactly follow t he distribution DD, which however would not affect the practical decoding perfor mance for the outer decoder to be described in <xref target="decoder" />. <t>Define a function called DegreeSampler that returns an integer d usin g the degree distribution DD. We expect that the empirical distribution of the r eturning d converges to DD(d) when d &lt; K. One design of DegreeSampler is illu strated in <xref target="degree_sampler" format="default"/>. Note that when K &l t; MAX_DEG, the degree value returned by DegreeSampler does not exactly follow t he distribution DD, which however would not affect the practical decoding perfor mance for the outer decoder to be described in <xref target="decoder" />.
</t> </t>
<figure anchor="degree_sampler"> <figure anchor="degree_sampler">
<name>Degree Sampler Function.</name> <name>Degree Sampler Function</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <sourcecode type="pseudocode"><![CDATA[
function DegreeSampler(j, DD) function DegreeSampler(j, DD)
Let CDF be an array Let CDF be an array
CDF[0] = 0 CDF[0] = 0
for i = 1, ..., MAX_DEG do for i = 1, ..., MAX_DEG do
CDF[i] = CDF[i-1] + DD[i] CDF[i] = CDF[i - 1] + DD[i]
Rand_Init(j) Rand_Init(j)
r = Rand() % CDF[MAX_DEG] r = Rand() % CDF[MAX_DEG]
for d = 1, ..., MAX_DEG do for d = 1, ..., MAX_DEG do
if r >= CDF[d] do if r >= CDF[d] do
return min(d,K) return min(d, K)
return min(MAX_DEG,K) return min(MAX_DEG, K)
]]></artwork> ]]></sourcecode>
</figure> </figure>
<t> <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. 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> </t>
<ul spacing="normal"> <ul spacing="normal">
<li>Obtain a degree d by calling DegreeSampler with input j. <li>Obtain a degree d by calling DegreeSampler with input j.
</li> </li>
<li>Obtain idx and G[j] by calling BatchSampler with input j and d. <li>Obtain idx and G[j] by calling BatchSampler with input j and d.
</li> </li>
<li>Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d-1]]). Form the batc h X[j] = B[j]*G[j], whose dimension is T x M. <li>Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d - 1]]). Form the ba tch X[j] = B[j] * G[j], whose dimension is T x M.
</li> </li>
<li>Form the TO x M matrix Xr[j], where the first CO rows of Xr[j] for m the M x M identity matrix I with entries in GF(q), and the last T rows of Xr[j ] is X[j]. <li>Form the TO x M matrix Xr[j], where the first CO rows of Xr[j] for m the M x M identity matrix I with entries in GF(q) and the last T rows of Xr[j] is X[j].
</li> </li>
</ul> </ul>
<t>See the pseudocode of the batch generating process in <xref target="g en_batch" format="default"/>.</t> <t>See the pseudocode of the batch generating process in <xref target="g en_batch" format="default"/>.</t>
<figure anchor="gen_batch"> <figure anchor="gen_batch">
<name>Batch Generation Function.</name> <name>Batch Generation Function</name>
<artwork name="" type="" align="left" alt=""><![CDATA[ <sourcecode type="pseudocode"><![CDATA[
function GenBatch(j) function GenBatch(j)
d = DegreeSampler(j) d = DegreeSampler(j)
(idx, G) = BatchSampler(j,d) (idx, G) = BatchSampler(j, d)
B = (b[idx[0]], b[idx[i]], ..., b[idx[d-1]]) B = (b[idx[0]], b[idx[i]], ..., b[idx[d - 1]])
X = B * G X = B * G
Xr = [I; X] Xr = [I; X]
return Xr return Xr
]]></artwork> ]]></sourcecode>
</figure> </figure>
</section> </section>
<section anchor="recoder" numbered="true" toc="default"> <section anchor="recoder" numbered="true" toc="default">
<name>Inner Code Encoder (Recoder)</name> <name>Inner Code Encoder (Recoder)</name>
<t> <t>
In general, the inner code of a BATS code comprises (random) linear ne twork coding applied on the coded packets belonging to the same batch. The recod ed 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 M r recoded packets are supposed to be generated. Following traditional random lin ear network coding, a recoded packet can be generated by random linear combinati on: (randomly) choose a sequence of coefficients c[i], i = 0, 1, ..., r-1 from G F(q), and generate c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet. Th is recoding approach, called random linear recoding, achieves good network codin g performance for multicast when the batch size is sufficiently large.</t> In general, the inner code of a BATS code comprises (random) linear ne twork coding applied on the coded packets belonging to the same batch. The recod ed 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 random linear network coding, a recoded packet can be generated by a random linear combination: (rand omly) choose a sequence of coefficients c[i], i = 0, 1, ..., r - 1 from GF(q) an d 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 cod ing performance for multicast when the batch size is sufficiently large.</t>
<t> <t>
For unicast communications in a single path as illustrated in <xref targ et="network_model" format="default"/>, it is not necessary to generate all the M r 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 optim al network coding performance as random linear recoding in more complicated comm unication scenarios that include multiple paths and multiple destination nodes. For unicast communications in a single path, as illustrated in <xref tar get="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 are directly used as recoded packets, and max(Mr - r, 0) recoded pack ets are generated using linear combinations. Compared with random linear recodin g, this recoding approach, called systematic recoding, can reduce both the compu tation cost and the recoding latency that accumulates linearly with the number o f nodes. Note that the use of systematic recoding may not always achieve the opt imal network coding performance as random linear recoding in more complicated co mmunication scenarios that include multiple paths and multiple destination nodes .
</t> </t>
</section> </section>
<section anchor="decoder" numbered="true" toc="default"> <section anchor="decoder" numbered="true" toc="default">
<name>Outer Decoder</name> <name>Outer Decoder</name>
<t> 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 th e last T rows of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; whe n 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 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 th at the total rank of all the batches is at least K.</t>
<t> The same degree distribution DD used for the outer encoder is suppos ed to be known by the outer decoder. By calling DegreeSampler and BatchSampler w ith input j, we obtain d[j], idx[j] and G[j]. According to the encoding and reco ding processes described in <xref target="encoder" format="default"/> and <xref target="recoder" format="default"/>, 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. <t> The same degree distribution DD used for the outer encoder is suppos ed to be known by the outer decoder. By calling DegreeSampler and BatchSampler w ith input j, we obtain d[j], idx[j], and G[j]. According to the encoding and rec oding processes described in Sections <xref target="encoder" format="counter"/> and <xref target="recoder" format="counter"/>, we have the system of linear equa tions 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.
</t> </t>
<t> We first describe a belief propagation (BP) decoder that can efficie ntly solve the source packets when a sufficient number of batches have been rece ived. A batch j is said to be decodable if rank(G[j]H[j]) = d[j] (i.e., the syst em 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 iter ation is formed by the following steps: <t> We first describe a belief propagation (BP) decoder that can efficie ntly solve the source packets when a sufficient number of batches have been rece ived. A batch j is said to be decodable if rank(G[j]H[j]) = d[j] (i.e., the syst em 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 iter ation is formed by the following steps:
</t> </t>
<ul spacing="normal"> <ul spacing="normal">
<li> Decoding step: Find a batch j that is decodable. Solve the corres <li> Decoding Step: Find a batch j that is decodable. Solve the corres
ponding system of linear equations Y[j] = B[j]G[j]H[j] and decode B[j].</li> ponding system of linear equations Y[j] = B[j]G[j]H[j] and decode B[j].</li>
<li> Substitution step: Substitute the decoded source packets into und <li> Substitution Step: Substitute the decoded source packets into und
ecodable batches. Suppose that a decoded source packet b[k] is used in generatin ecodable batches. Suppose that a decoded source packet b[k] is used in generatin
g an undecodable Y[j]. The substitution involves 1) removing the entry in idx[j] g 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) r corresponding to k, 2) removing the row in G[j] corresponding to b[k], and 3) r
educing d[j] by 1. </li> educing d[j] by 1. </li>
</ul> </ul>
<t> <t>
The BP decoder repeats the above steps until no batches are decodable du ring the decoding step. The BP decoder repeats the above steps until no batches are decodable du ring the decoding step.
</t> </t>
<t>When the degree distribution DD in the outer code encoder (see <xref t arget="encoder" format="default"/>) is properly designed, the BP decoder guarant ees a high probability for the recovery of a given fraction of the source packet s when K is large. To recover all the source packets, a precode can be applied t o 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 w ith a high probability when K is relatively small, it is possible to continue wi th inactivation decoding, where certain source packets are treated inactive so t hat a similar belief propagation process can be resumed. The reader is referred to <xref target="RFC6330" format="default">RFC&nbsp;6330</xref> for the design o f a precode with a good inactivation decoding performance. </t> <t>When the degree distribution DD in the outer code encoder (see <xref t arget="encoder" format="default"/>) is properly designed, the BP decoder guarant ees a high probability for the recovery of a given fraction of the source packet s when K is large. To recover all the source packets, a precode can be applied t o 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 w ith inactivation decoding, where certain source packets are treated as inactive so that a similar belief propagation process can be resumed. The reader is refer red to <xref target="RFC6330" format="default"/> for the design of a precode wit h a good inactivation decoding performance. </t>
</section> </section>
</section> </section>
<section anchor="research" numbered="true" toc="default"> <section anchor="research" numbered="true" toc="default">
<name>Research Issues</name> <name>Research Issues</name>
<t>The baseline BATS coding scheme described in <xref target="procedures" format="default"/> and <xref target="specification" format="default"/> needs var ious refinement and complement towards becoming a more sophisticated network com munication application. Various related research issues are discussed in this se ction, but the security related issues are left to <xref target="Security" forma t="default"/>. </t> <t>The baseline BATS coding scheme described in Sections <xref target="pro cedures" format="counter"/> and <xref target="specification" format="counter"/> needs various refinements and complements towards becoming a more sophisticated network communication application. Various related research issues are discussed in this section, but the security-related issues are left to <xref target="Secu rity" format="default"/>. </t>
<section anchor="coding" numbered="true" toc="default"> <section anchor="coding" numbered="true" toc="default">
<name>Coding Design Issues</name> <name>Coding Design Issues</name>
<t>When the number of batches is sufficiently large, the BATS code speci <t>When the number of batches is sufficiently large, the BATS code speci
fication in <xref target="specification" format="default"/> has nearly optimal p fication in <xref target="specification" format="default"/> has nearly optimal p
erformance in the sense that the decoding can be successful with a high probabil erformance in the sense that the decoding can be successful with a high probabil
ity when the total rank of all the batches used for decoding is just slightly la ity when the total rank of all the batches used for decoding is just slightly la
rger than the number of source packet K. But when K is small, the degree sampler rger than the number of source packet K. But when K is small, the DegreeSampler
function in <xref target="degree_sampler" format="default"/> and the BatchSampl function in <xref target="degree_sampler" format="default"/> and the BatchSample
er function in <xref target="batch_sampler" format="default"/> based on a pseudo r function in <xref target="batch_sampler" format="default"/> based on a pseudor
random generator may not sample all the source packets evenly, so that some of t andom generator may not sample all the source packets evenly so that some of the
he source packets are not well protected. One approach to solve this issue is to source packets are not well protected. One approach to solve this issue is to g
generate a deterministic degree sequence when the number of batches is relative enerate a deterministic degree sequence when the number of batches is relatively
ly small, and design a special pseudorandom generator that has a good sampling p small and design a special pseudorandom generator that has a good sampling perf
erformance when K is small.</t> ormance when K is small.</t>
<t>There are research issues related to recoding discussed in <xref targ <t>There are research issues related to recoding discussed in <xref targ
et="recoder" format="default"/>. One question is how many recoded packets to gen et="recoder" format="default"/>. One question is how many recoded packets to gen
erate for each batch. Though it is asymptotically optimal when using the same nu erate for each batch. Though it is asymptotically optimal when using the same nu
mber of recoded packets for all batches, it has been shown that transmitting a d mber of recoded packets for all batches, it has been shown that transmitting a d
ifferent number of recoded packets for different batches can improve the recodin ifferent number of recoded packets for different batches can improve the recodin
g efficiency. The intuition is that for a batch with a lower rank, a smaller num g efficiency. For a batch with a lower rank, the intuition is that a smaller num
ber of recoded packets need to be transmitted. This kind of recoding scheme is c ber of recoded packets need to be transmitted. This kind of recoding scheme is c
alled <xref target="Yin19" format="default">adaptive recoding</xref>.</t> alled <xref target="Yin19" format="default">adaptive recoding</xref>.</t>
<t>Packet loss in network communication is usually bursty, which may har m the recoding performance. One way to resolve this issue is to transmit the pac kets of different batches in a mixed order, which is also called <xref target="Y in20" format="default">batch interleaving</xref>. How to efficiently interleave batches without increasing end-to-end latency too much is a research issue.</t> <t>Packet loss in network communication is usually bursty, which may har m the recoding performance. One way to resolve this issue is to transmit the pac kets of different batches in a mixed order, which is also called <xref target="Y in20" 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 a nd destination nodes. To benefit from multiple source nodes, we would need diffe rent source nodes to generate statistically independent batches. It is well-know n that <xref target="Li03" format="default">linear network coding</xref> achieve s the multicast capacity. BATS codes can benefit from network coding due to its inner code. For multicast, each destination node performs independently the same operations as described in this document, but the inner code should be improved to taking multiple destination node into consideration. How to efficiently impl ement multicast needs further research.</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 a nd destination nodes. To benefit from multiple source nodes, we would need diffe rent source nodes to generate statistically independent batches. It is well-know n that <xref target="Li03" format="default">linear network coding</xref> achieve s the multicast capacity. BATS codes can benefit from network coding due to its inner code. For multicast, each destination node independently performs the same operations as described in this document, but the inner code should be improved to take multiple destination nodes into consideration. How to efficiently imple ment multicast needs further research.</t>
</section> </section>
<section anchor="protocol" numbered="true" toc="default"> <section anchor="protocol" numbered="true" toc="default">
<name>Protocol Design Issues</name> <name>Protocol Design Issues</name>
<t>The baseline scheme in this document focuses on reliable communicatio <t>The baseline scheme in this document focuses on reliable communicatio
n. There are other issues to be considered towards designing a fully functional n. 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 issue DDP based on a BATS coding scheme. Here, we discuss some network management issu
s that are closely related to a BATS coding scheme: routing, congestion control es that are closely related to a BATS coding scheme: routing, congestion control
and media access control.</t> , and media access control.</t>
<t>The outer code of a BATS code can be regarded as a channel code for t <t>The outer code of a BATS code can be regarded as a channel code for t
he channel induced by the inner code, and hence the network management algorithm he channel induced by the inner code, and hence, the network management algorith
s should try to maximize the capacity of the channel induced by the inner code. ms should try to maximize the capacity of the channel induced by the inner code.
A <xref target="Dong20" format="default">network utility maximization problem</x A <xref target="Dong20" format="default">network utility maximization problem</
ref> for BATS coding can be applied to study routing, congestion control and med xref> for BATS coding can be applied to study routing, congestion control, and m
ia access control jointly. Compared with the network utility maximization for In edia access control jointly. Compared with the network utility maximization for
ternet, there are two major differences. First, the network flow rate is not mea the Internet, there are two major differences. First, the network flow rate is n
sured by the rate of the raw packets. Instead, a rank based measurement induced ot measured by the rate of the raw packets. Instead, a rank-based measurement in
by the inner code is applied for BATS coding schemes. Second, due to recoding, t duced by the inner code is applied for BATS coding schemes. Second, due to recod
he raw packet rate may not be the same for different links of a flow, i.e., no f ing, the raw packet rate may not be the same for different links of a flow, i.e.
low conservation for BATS coding schemes. These differences affect both the obje , no flow conservation for BATS coding schemes. These differences affect both th
ctive and the constraints of the utility maximization problem. </t> e objective and the constraints of the utility maximization problem. </t>
<t>Practical congestion control, routing and media access control algori <t>Practical congestion control, routing, and media access control algor
thms for BATS coding schemes deserve more research efforts. The rate of transmit ithms for BATS coding schemes deserve more research efforts. The rate of transmi
ting batches can be controlled end-to-end. Due to the recoding operation, howeve tting batches can be controlled end-to-end. Due to the recoding operation, howev
r, congestion control cannot be only performed end-to-end. The number of recoded er, congestion control cannot be only performed end-to-end. The number of recode
packets generated for a batch must be controlled at the intermediate nodes, whi d packets generated for a batch must be controlled at the intermediate nodes, wh
ch introduces new research issues for congestion control. A BATS coding scheme i ich introduces new research issues for congestion control. A BATS coding scheme
s an extension of forward erasure correction coding. See <xref target="RFC9265" is an extension of forward erasure correction coding. See <xref target="RFC9265"
format="default">RFC&nbsp;9265</xref> for more discussion of forward erasure cor format="default"/> for more discussion of forward erasure correction coding and
rection coding and congestion control.</t> congestion control.</t>
<t>For routing, the BATS coding scheme is flexible for implementing data <t>For routing, the BATS coding scheme is flexible for implementing data
transmission on multiple paths simultaneously. For unicast, it is optimal to tra transmission on multiple paths simultaneously. For unicast, it is optimal to tra
nsmit all the packets of a batch on the same path between the source node and th nsmit all the packets of a batch on the same path between the source node and th
e destination node, and for multicast, network coding gain can be obtained by tr e destination node, and for multicast, network coding gain can be obtained by tr
ansmitting packets of the same batch on different paths <xref target="Yang17" fo ansmitting packets of the same batch on different paths <xref target="Yang17" fo
rmat="default"/>. Last, under the scenario of BATS coding schemes, media access rmat="default"/>. Lastly, under the scenario of BATS coding schemes, media acces
control can have some different considerations: Retransmission is not necessary, s control can have some different considerations: Retransmission is not necessar
and a reasonably high packet loss rate can be tolerated. </t> y, and a reasonably high packet loss rate can be tolerated. </t>
</section> </section>
<section anchor="application" numbered="true" toc="default"> <section anchor="application" numbered="true" toc="default">
<name>Usage Scenario Considerations</name> <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 b road range of network communication scenarios. In general, a BATS coding scheme is suitable for data delivery in networks with multiple hops and unreliable link s.</t> <t>There are more research issues pertaining to various usage scenarios. The reliable communication technique provided by BATS codes can be used for a b road range of network communication scenarios. In general, a BATS coding scheme is suitable for data delivery in networks with multiple hops and unreliable link s.</t>
<t>One class of typical usage scenario is <xref target="Toh02" format="d <t>One class of typical usage scenario is <xref target="Toh02" format="d
efault">wireless mesh and ad hoc networks</xref>, including vehicular networks, efault">wireless mesh and ad hoc networks</xref>, including vehicular networks,
wireless sensor networks, smart lamppost networks, etc. These networks are chara wireless sensor networks, smart lamppost networks, etc. These networks are chara
cterized by a large number of network devices connected wirelessly with each oth cterized by a large number of network devices connected wirelessly with each oth
er without a centralized network infrastructure. A BATS coding scheme is suitabl er without a centralized network infrastructure.
e for high data load delivery in such networks without the requirement that the A BATS coding scheme is suitable for high data load delivery in such networks wi
point-to-point/one-hop communication is highly reliable. Therefore, employing a thout the requirement that the point-to-point or one-hop communication is highly
BATS coding scheme can provide more freedom for media access control, including reliable. Therefore, employing a BATS coding scheme can provide more freedom fo
power control, and physical-layer design so that the overall network throughput r media access control, including power control, and physical-layer design so th
can be improved. </t> at the overall network throughput can be improved. </t>
<t>Another typical usage scenario of BATS coding schemes is <xref target <t>Another typical usage scenario of BATS coding schemes is <xref target
="Sprea19" format="default">underwater acoustic networks</xref>, where the propa ="Sprea19" format="default">underwater acoustic networks</xref>, where the propa
gation delay of acoustic waves in underwater can be as long as several seconds. gation delay of acoustic waves underwater can be as long as several seconds. Due
Due to the long delay, feedback based mechanisms become inefficient. Moreover, p to the long delay, feedback-based mechanisms become inefficient. Moreover, poin
oint-to-point/one-hop underwater acoustic communication (for both the forward an t-to-point/one-hop underwater acoustic communication (for both the forward and r
d reverse directions) is highly unreliable. Due to these reasons, traditional ne everse directions) is highly unreliable. Due to these reasons, the networking te
tworking techniques developed for radio and wireline networks cannot be directly chniques developed for radio and wireline networks cannot be directly applied to
applied to underwater networks. As a BATS coding scheme does not rely on the fe underwater networks. As a BATS coding scheme does not rely on the feedback for
edback for reliability communication and can tolerate highly unreliable links, i reliability communication and can tolerate highly unreliable links, it makes a g
t makes a good candidate for developing data delivery protocols for underwater a ood candidate for developing data delivery protocols for underwater acoustic net
coustic networks.</t> works.</t>
<t>Last but not least, due to its capability of performing multi-source <t>Last but not least, due to its capability of performing multi-source,
multi-destination communications, a BATS coding scheme can be applied in various multi-destination communications, a BATS coding scheme can be applied in variou
content distribution scenarios. For example, a BATS coding scheme can be a cand s content distribution scenarios. For example, a BATS coding scheme can be a can
idate for the erasure code used in the <xref target="Byers20" format="default">l didate for the erasure code used in the <xref target="Byers20" format="default">
iquid data networking framework</xref> of CCN (content centric networking), and liquid data networking framework</xref> of content-centric networking (CCN) and
provides the extra <xref target="Zhang16" format="default">benefit of network co provides the extra <xref target="Zhang16" format="default">benefit of network co
ding</xref>. </t> ding</xref>. </t>
</section> </section>
</section> </section>
<!-- This PI places the pagebreak correctly (before the section title) in th
e text output. -->
<section anchor="IANA" numbered="true" toc="default"> <section anchor="IANA" numbered="true" toc="default">
<name>IANA Considerations</name> <name>IANA Considerations</name>
<t>This memo includes no request to IANA.</t> <t>This document has no IANA actions.</t>
</section> </section>
<section anchor="Security" numbered="true" toc="default"> <section anchor="Security" numbered="true" toc="default">
<name>Security Considerations</name> <name>Security Considerations</name>
<t> <t>
Subsuming both random linear network codes (RLNC) and fountain codes, BA TS codes naturally inherit both their desirable security capability of preventin g eavesdropping, as well as their vulnerability towards pollution attacks. In th is section, we discuss some related research issues. Subsuming both random linear network codes (RLNCs) and fountain codes, B ATS codes naturally inherit both their desirable security capability of preventi ng eavesdropping as well as their vulnerability towards pollution attacks. In th is section, we discuss some related research issues.
</t> </t>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Preventing Eavesdropping</name> <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 bat ch does not have a unique solution, and the probability that the eavesdropper ca n guess the d source packets used for encoding the batch correctly is 2^(-(d-M)T )&#60;=2^(-T), where T is the number of octets of a source packet (see also <xre f target="Bhattad07" format="default"/>). When inactivation decoding is applied, we can design the degree distribution DD so that the smallest degree is M+1, an d hence prevent the eavesdropper from decoding source packets from individual ba tches.</t> <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 bat ch does not have a unique solution, and the probability that the eavesdropper ca n guess the d source packets used for encoding the batch correctly is 2<sup>(-(d -M)T)</sup>&lt;=2<sup>(-T)</sup>, where T is the number of octets of a source pa cket (see also <xref target="Bhattad07" format="default"/>). When inactivation d ecoding is applied, we can design the degree distribution DD so that the smalles t degree is M+1 and hence prevent the eavesdropper from decoding source packets from individual batches.</t>
<t> <t>
If we allow the eavesdropper to collect multiple batches and use inac tivation 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. Therefor e, if the DDP can manage to restrict the eavesdropper from collecting a sufficie nt number of coded packets, the native security of BATS code is effective when T is sufficiently large. Here by native security, we mean the security protection provided by the BATS coding scheme without extra enhancement. If we allow the eavesdropper to collect multiple batches and use inac tivation 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. Therefor e, if the DDP can manage to restrict the eavesdropper from collecting a sufficie nt number of coded packets, the security of BATS code is effective when T is suf ficiently large. Here, by "intrinsic security", we mean the security protection provided by the BATS coding scheme without extra enhancement.
</t> </t>
<t> <t>
If the eavesdropper can collect a sufficient number of coded packets fo r correctly decoding, the native security of BATS code is ineffective. One solut ion 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 d ata encryption solution. This is a research issue that depends on specific BATS code schemes, and will not be further discussed here. If the eavesdropper can collect a sufficient number of coded packets fo r correctly decoding, the intrinsic security of BATS code is ineffective. One so lution in this case is to encrypt the whole data before using the BATS code sche me. Better schemes are desired towards reducing the computation cost of the whol e data encryption solution. This is a research issue that depends on specific BA TS code schemes and will not be further discussed here.
</t> </t>
<t> <t>
The threat exists for eavesdropping on the initial encoding process, w hich 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, info rmation isolation between the encoding process and all other user processes runn ing on the source node MUST be assured. The threat exists for eavesdropping on the initial encoding process, w hich 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, info rmation isolation between the encoding process and all other user processes runn ing on the source node <bcp14>MUST</bcp14> be assured.
</t> </t>
<t> <t>
In addition, the authenticity and trustworthiness of the encoding, rec oding and decoding program running on all the nodes MUST be attested by a truste d authority. Such a measure is also necessary in countering pollution attacks. In addition, the authenticity and trustworthiness of the encoding, rec oding, and decoding program running on all the nodes <bcp14>MUST</bcp14> be atte sted by a trusted authority. Such a measure is also necessary in countering poll ution attacks.
</t> </t>
</section> </section>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Privacy-Preserving against Traffic Analysis</name> <name>Privacy Preservation against Traffic Analysis</name>
<t> A security issue closely related to eavesdropping is traffic analysi <t> A security issue closely related to eavesdropping is traffic analysi
s. Even when eavesdropping is prevented, tracking the traffic flow patterns can s. Even when eavesdropping is prevented, tracking the traffic flow patterns can
help an attacker to know a certain information about the communication. Preventi help an attacker to know certain information about the communication. Preventing
ng traffic analysis is critical for communications that need to be anonymous. In traffic analysis is critical for communications that need to be anonymous. In <
<xref target="Fan09" format="default"/>, a homomorphic encryption based approac xref target="Fan09" format="default"/>, an approach based on homomorphic encryp
h is proposed for network coding to prevent traffic analysis. However, homomorph tion is proposed for network coding to prevent traffic analysis. However, homomo
ic encryption could be too computationally expensive for practical applications rphic encryption could be too computationally expensive for practical applicatio
and cannot help with the traffic analysis by monitoring the frequency and timing ns and cannot help with the traffic analysis by monitoring the frequency and tim
of network traffic. </t> ing of network traffic. </t>
<t> The network traffic using network coding does not necessarily satis fy the flow conservation property, and hence network coding can be used as a too l 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 multi path communication <xref target="Yang15" format="default"/>, and network coding makes multiple-path communication more flexible and efficient. Therefore, using network coding brings new research issues for both traffic analysis and its coun termeasure. <t> The network traffic using network coding does not necessarily satis fy the flow conservation property, and hence, network coding can be used as a to ol 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 mult ipath communication <xref target="Yang15" format="default"/>, and network coding makes multipath communication more flexible and efficient. Therefore, using net work coding brings new research issues for both traffic analysis and its counter measure.
</t> </t>
</section> </section>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Countermeasures against Pollution Attacks</name> <name>Countermeasures against Pollution Attacks</name>
<t>Like all network codes, BATS codes are vulnerable to pollution attack s. In these attacks, one or more compromised coding node(s) can pollute the code d messages by injecting forged packets into the network and thus prevent the re ceivers from recovering the transported data correctly. Moreover, a small number of polluted packets can infect a large number of packets by recoding and decodi ng <xref target="Zhao07" format="default"/>. <t>Like all network codes, BATS codes are vulnerable to pollution attack s. In these attacks, one or more compromised coding node(s) can pollute the code d messages by injecting forged packets into the network and thus prevent the re ceivers from recovering the transported data correctly. Moreover, a small number of polluted packets can infect a large number of packets by recoding and decodi ng <xref target="Zhao07" format="default"/>.
</t> </t>
<t>The research community has long been investigating the use of homomor <t>The research community has long been investigating the use of homomor
phic signatures to identify the forged packets and stall the attacks (see <xref phic signatures to identify the forged packets and stall the attacks (see <xref
target="Zhao07" format="default"/>, <xref target="Yu08" format="default"/>, <xre target="Zhao07" format="default"/>, <xref target="Yu08" format="default"/>, and
f target="Agrawal09" format="default"/>). In these schemes, the source node atta <xref target="Agrawal09" format="default"/>). In these schemes, the source node
ches a signature to each packet to transmit, and the signature is allowed to be attaches a signature to each packet to transmit, and the signature is allowed to
processed by network coding same as the payload. All the intermediate nodes and be processed by network coding in the same way as the payload. All the intermed
the destination node can verify the signature attached to a received packet. How iate nodes and the destination node can verify the signature attached to a recei
ever, these countermeasures are regarded as being too computationally expensive ved packet. However, these countermeasures are regarded as being too computation
to be employed in broadband communications. </t> ally expensive to be employed in broadband communications. </t>
<t>A system-level approach based on <xref target="TC-Wikipedia" format=" <t>A system-level approach based on <xref target="TC-Wikipedia" format="
default">trusted computing</xref> can provide an alternative to protect BATS cod default">trusted computing</xref> can provide an alternative to protect BATS cod
es against pollution attacks. Trusted computing consists of software and hardwar es against pollution attacks. Trusted computing consists of software and hardwar
e technologies so that a computer behaves as expected. Suppose that all the netw e technologies so that a computer behaves as expected. Suppose that all the netw
ork nodes employ trusted computing. Two nodes will first gain trust with each ot ork nodes employ trusted computing. Two nodes will first gain trust with each ot
her, and then negotiate an authentication method for exchanging the coded packet her and then negotiate an authentication method for exchanging the coded packets
s of the BATS coding scheme. A network node would not use any packets received f of the BATS coding scheme. A network node would not use any packets received fr
rom other nodes without trust to avoid the pollution attack. om other nodes without trust to avoid the pollution attack.
</t> </t>
</section> </section>
</section> </section>
<!--section anchor="Acknowledgements" title="Acknowledgements">
<t></t>
</section-->
<!-- Possibly a 'Contributors' section ... -->
</middle> </middle>
<!-- *****BACK MATTER ***** -->
<back> <back>
<!-- References split into informative and normative -->
<!-- There are 2 ways to insert reference entries from the citation librar
ies:
1. define an ENTITY at the top, and use "ampersand character"RFC2629; h
ere (as shown)
2. simply use a PI "less than character"?rfc include="reference.RFC.211
9.xml"?> here
(for I-Ds: include="reference.I-D.narten-iana-considerations-rfc2434
bis.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 include
d files in the same
directory as the including file. You can also define the XML_LIBRARY en
vironment variable
with a value containing a set of directories to search. These can be e
ither in the local
filing system or remote ones accessed by http (http://domain/dir/... ).
-->
<references> <references>
<name>References</name> <name>References</name>
<references> <references>
<name>Normative References</name> <name>Normative References</name>
<!--?rfc include="http://xml.resource.org/public/rfc/bibxml/reference.RF <xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.2
C.2119.xml"?--> 119.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R <xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.81
FC.2119.xml"/> 74.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R <xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.8
FC.8682.xml"/> 682.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R <xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.8
FC.8406.xml"/> 406.xml"/>
</references> </references>
<references> <references>
<name>Informative References</name> <name>Informative References</name>
<!-- Here we use entities that we defined at the beginning. --> <xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.6
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R 330.xml"/>
FC.6330.xml"/> <xi:include href="https://bib.ietf.org/public/rfc/bibxml/reference.RFC.92
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RF 65.xml"/>
C.9265.xml"/>
<!-- A reference written by by an organization not a person. -->
<reference anchor="Yang14"> <reference anchor="Yang14">
<front> <front>
<title>Batched Sparse Codes</title> <title>Batched Sparse Codes</title>
<author initials="S." surname="Yang" fullname="Shenghao Yang"> <author initials="S." surname="Yang" fullname="Shenghao Yang">
</author> </author>
<author initials="R.W." surname="Yeung" fullname="Raymond W. Yeung"> <author initials="R." surname="Yeung" fullname="Raymond W. Yeung">
</author> </author>
<date year="2014"/> <date year="2014" month="September"/>
</front> </front>
<seriesInfo name="IEEE Transactions on Information Theory" value="60(9 <seriesInfo name="DOI" value="10.1109/TIT.2014.2334315"/>
), 5322-5346"/> <refcontent>IEEE Transactions on Information Theory, Vol. 60, Issue 9,
pgs. 5322-5346</refcontent>
</reference> </reference>
<reference anchor="Yang17"> <reference anchor="Yang17">
<front> <front>
<title>BATS Codes: Theory and Practice</title> <title>BATS Codes: Theory and Practice</title>
<author initials="S." surname="Yang" fullname="Shenghao Yang"> <author initials="S." surname="Yang" fullname="Shenghao Yang">
</author> </author>
<author initials="R.W." surname="Yeung" fullname="Raymond W. Yeung"> <author initials="R." surname="Yeung" fullname="Raymond W. Yeung">
</author> </author>
<date year="2017"/> <date year="2017" month="September"/>
</front> </front>
<seriesInfo name="Morgan &amp; Claypool Publishers" value=""/> <refcontent>Morgan &amp; Claypool Publishers</refcontent>
</reference> </reference>
<reference anchor="Yin19"> <reference anchor="Yin19">
<front> <front>
<title>A Unified Adaptive Recoding Framework for Batched Network Cod ing</title> <title>A Unified Adaptive Recoding Framework for Batched Network Cod ing</title>
<author initials="H.H.F." surname="Yin" fullname="Hoover H.F. Yin"/> <author initials="H." surname="Yin" fullname="Hoover H.F. Yin"/>
<author initials="B." surname="Tang" fullname="Bin Tang"/> <author initials="B." surname="Tang" fullname="Bin Tang"/>
<author initials="K.H." surname="Ng" fullname="Ka Hei Ng"/> <author initials="K." surname="Ng" fullname="Ka Hei Ng"/>
<author initials="S." surname="Yang" fullname="Shenghao Yang"> <author initials="S." surname="Yang" fullname="Shenghao Yang"/>
</author> <author initials="X." surname="Wang" fullname="Xishi Wang"/>
<author initials="X." surname="Wang" fullname="Xishi Wang"> <author initials="Q." surname="Zhou" fullname="Qiaoqiao Zhou"/>
</author> <date year="2019" month="July"/>
<author initials="Q." surname="Zhou" fullname="Qiaoqiao Zhou">
</author>
<date year="2019"/>
</front> </front>
<seriesInfo name="ISIT" value=""/> <seriesInfo name="DOI" value="10.1109/ISIT.2019.8849277"/>
<refcontent>2019 IEEE International Symposium on Information Theory (IS
IT)</refcontent>
</reference> </reference>
<reference anchor="Yin20"> <reference anchor="Yin20">
<front> <front>
<title>A Protocol Design Paradigm for Batched Sparse Codes</title> <title>A Protocol Design Paradigm for Batched Sparse Codes</title>
<author initials="H.H.F." surname="Yin" fullname="Hoover H.F. Yin"/> <author initials="H." surname="Yin" fullname="Hoover H.F. Yin"/>
<author initials="R.W." surname="Yeung" fullname="Raymond W. Yeung"> <author initials="R." surname="Yeung" fullname="Raymond W. Yeung"/>
</author> <author initials="S." surname="Yang" fullname="Shenghao Yang"/>
<author initials="S." surname="Yang" fullname="Shenghao Yang"> <date year="2020" month="July"/>
</author>
<date year="2020"/>
</front> </front>
<seriesInfo name="Entroy" value=""/> <seriesInfo name="DOI" value="10.3390/e22070790"/>
<refcontent>Entropy</refcontent>
</reference> </reference>
<reference anchor="Dong20"> <reference anchor="Dong20">
<front> <front>
<title>Network Utility Maximization for BATS Code enabled Multihop W ireless Networks</title> <title>Network Utility Maximization for BATS Code Enabled Multihop W ireless Networks</title>
<author initials="Y." surname="Dong" fullname="Yanyan Dong"/> <author initials="Y." surname="Dong" fullname="Yanyan Dong"/>
<author initials="S." surname="Jin" fullname="Shengh Jin"> <author initials="S." surname="Jin" fullname="Shengh Jin"/>
</author> <author initials="S." surname="Yang" fullname="Shenghao Yang"/>
<author initials="S." surname="Yang" fullname="Shenghao Yang"> <author initials="H." surname="Yin" fullname="Hoover H.F. Yin"/>
</author> <date year="2020" month="June"/>
<author initials="H.H.F." surname="Yin" fullname="Hoover H.F. Yin"/>
<date year="2020"/>
</front> </front>
<seriesInfo name="ICC" value=""/> <seriesInfo name="DOI" value="10.1109/ICC40277.2020.9148834"/>
<refcontent>ICC 2020 - 2020 IEEE International Conference on Communicat
ions (ICC)</refcontent>
</reference> </reference>
<reference anchor="Fan09"> <reference anchor="Fan09">
<front> <front>
<title>Weakly Secure Network Coding</title> <title>An Efficient Privacy-Preserving Scheme against Traffic Analys is Attacks in Network Coding</title>
<author initials="Y." surname="Yanfei" fullname="Yanfei Fan"/> <author initials="Y." surname="Yanfei" fullname="Yanfei Fan"/>
<author initials="Y." surname="Yixin" fullname="Yixin Jiang"/> <author initials="Y." surname="Yixin" fullname="Yixin Jiang"/>
<author initials="H." surname="Haojin" fullname="Haojin Zhu"/> <author initials="H." surname="Haojin" fullname="Haojin Zhu"/>
<author initials="X." surname="Sherman" fullname="Xuemin (Sherman) Sh en"/> <author initials="X." surname="Sherman" fullname="Xuemin (Sherman) Sh en"/>
<date year="2009"/> <date year="2009" month="April"/>
</front> </front>
<seriesInfo name="INFOCOM" value=""/> <seriesInfo name="DOI" value="10.1109/INFCOM.2009.5062146"/>
<refcontent>IEEE INFOCOM 2009</refcontent>
</reference> </reference>
<reference anchor="Yang15"> <reference anchor="Yang15">
<front> <front>
<title>mTor: A multipath Tor routing beyond bandwidth throttling</tit le> <title>mTor: A multipath Tor routing beyond bandwidth throttling</tit le>
<author initials="L." surname="Yang" fullname="Lei Yang"/> <author initials="L." surname="Yang" fullname="Lei Yang"/>
<author initials="F." surname="Fengjun" fullname="Fengjun Li"/> <author initials="F." surname="Fengjun" fullname="Fengjun Li"/>
<date year="2015"/> <date year="2015" month="September"/>
</front> </front>
<seriesInfo name="NCS" value=""/> <seriesInfo name="DOI" value="10.1109/CNS.2015.7346860"/>
<refcontent>2015 IEEE Conference on Communications and Network Security
(CNS)</refcontent>
</reference> </reference>
<reference anchor="Bhattad07"> <reference anchor="Bhattad07">
<front> <front>
<title>An efficient privacy-preserving scheme against traffic analys is attacks in network coding</title> <title>Weakly Secure Network Coding</title>
<author initials="K." surname="Bhattad" fullname="Kapil Bhattad"/> <author initials="K." surname="Bhattad" fullname="Kapil Bhattad"/>
<author initials="K.R." surname="Narayanan" fullname="Krishna R. Nar <author initials="K." surname="Narayanan" fullname="Krishna R. Naray
ayanan"/> anan"/>
<date year="2007"/> <date year="2005" month="April"/>
</front> </front>
<seriesInfo name="ISIT" value=""/>
</reference> </reference>
<reference anchor="Zhao07"> <reference anchor="Zhao07">
<front> <front>
<title>Signatures for content distribution with network coding</titl e> <title>Signatures for content distribution with network coding</titl e>
<author initials="F." surname="Zhao" fullname="Fang Zhao"/> <author initials="F." surname="Zhao" fullname="Fang Zhao"/>
<author initials="T." surname="Kalker"/> <author initials="T." surname="Kalker" fullname="Ton Kalker"/>
<author initials="M." surname="Medard"/> <author initials="M." surname="Medard" fullname="Muriel Medard"/>
<author initials="K.J." surname="Han"/> <author initials="K." surname="Han" fullname="Keesook J. Han"/>
<date year="2007"/> <date year="2007" month="June"/>
</front> </front>
<seriesInfo name="ISIT" value=""/> <seriesInfo name="DOI" value="10.1109/ISIT.2007.4557283"/>
<refcontent>2007 IEEE International Symposium on Information Theory</re
fcontent>
</reference> </reference>
<reference anchor="Byers20"> <reference anchor="Byers20">
<front> <front>
<title>Liquid Data Networking</title> <title>Liquid Data Networking</title>
<author initials="J.W." surname="Byers" fullname="John W. Byers"/> <author initials="J." surname="Byers" fullname="John W. Byers"/>
<author initials="M." surname="Luby" fullname="Michael Luby"/> <author initials="M." surname="Luby" fullname="Michael Luby"/>
<date year="2020"/> <date year="2020" month="September"/>
</front> </front>
<seriesInfo name="ICN" value=""/> <seriesInfo name="DOI" value="10.1145/3405656.3418710"/>
<refcontent>Proceedings of the 7th ACM Conference on Information-Centri
c Networking</refcontent>
</reference> </reference>
<reference anchor="Yu08"> <reference anchor="Yu08">
<front> <front>
<title>An Efficient Signature-Based Scheme for Securing Network Codi ng Against Pollution Attacks</title> <title>An Efficient Signature-Based Scheme for Securing Network Codi ng Against Pollution Attacks</title>
<author initials="Z." surname="Yu"/> <author initials="Z." surname="Yu"/>
<author initials="Y." surname="Wei"/> <author initials="Y." surname="Wei"/>
<author initials="B." surname="Ramkumar"/> <author initials="B." surname="Ramkumar"/>
<author initials="Y." surname="Guan"/> <author initials="Y." surname="Guan"/>
<date year="2008"/> <date year="2008" month="April"/>
</front> </front>
<seriesInfo name="INFOCOM" value=""/> <seriesInfo name="DOI" value="10.1109/INFOCOM.2008.199"/>
<refcontent>IEEE INFOCOM 2008 - The 27th Conference on Computer Communi
cations</refcontent>
</reference> </reference>
<reference anchor="Agrawal09"> <reference anchor="Agrawal09">
<front> <front>
<title>Homomorphic MACs: MAC-based integrity for network coding</tit le> <title>Homomorphic MACs: MAC-Based Integrity for Network Coding</tit le>
<author initials="S." surname="Agrawal" fullname="Shweta Agrawal"/> <author initials="S." surname="Agrawal" fullname="Shweta Agrawal"/>
<author initials="D." surname="Boneh" fullname="Dan Boneh"/> <author initials="D." surname="Boneh" fullname="Dan Boneh"/>
<date year="2009"/> <date year="2009" month="May"/>
</front> </front>
<seriesInfo name="International Conference on Applied Cryptography and <seriesInfo name="DOI" value="10.1007/978-3-642-01957-9_18"/>
Network Security" value=""/> <refcontent>International Conference on Applied Cryptography and Networ
k Security</refcontent>
</reference> </reference>
<reference anchor="TC-Wikipedia">
<reference anchor="TC-Wikipedia" target="https://en.wikipedia.org/w/inde
x.php?title=Trusted_Computing&amp;oldid=1151565594">
<front> <front>
<title>Trusted Computing</title> <title>Trusted Computing</title>
<author/> <author>
<date year=""/> <organization>Wikipedia</organization>
</author>
<date year="2023" month="April"/>
</front> </front>
<seriesInfo name="Wikipedia" value="https://en.wikipedia.org/wiki/Trus ted_Computing"/>
</reference> </reference>
<reference anchor="Sprea19"> <reference anchor="Sprea19">
<front> <front>
<title>BATS Coding for Underwater Acoustic Communication Networks</t itle> <title>BATS Coding for Underwater Acoustic Communication Networks</t itle>
<author initials="N." surname="Sprea" fullname="Nicolò Sprea"/> <author initials="N." surname="Sprea" fullname="Nicolò Sprea"/>
<author initials="M." surname="Bashir" fullname="Murwan Bashir"/> <author initials="M." surname="Bashir" fullname="Murwan Bashir"/>
<author initials="D." surname="Truhachev" fullname="Dmitri Truhachev "/> <author initials="D." surname="Truhachev" fullname="Dmitri Truhachev "/>
<author initials="K.V." surname="Srinivas"/> <author initials="K." surname="Srinivas" fullname="K. V. Srinivas"/>
<author initials="C." surname="Schlegel"/> <author initials="C." surname="Schlegel" fullname="Christian Schlege
<author initials="C." surname="Claudio Sacchi"/> l"/>
<date year="2019"/> <author initials="C." surname="Sacchi" fullname="Claudio Sacchi"/>
<date year="2019" month="June"/>
</front> </front>
<seriesInfo name="OCEANS" value=""/> <seriesInfo name="DOI" value="10.1109/OCEANSE.2019.8867299"/>
<refcontent>OCEANS 2019 - Marseille</refcontent>
</reference> </reference>
<reference anchor="Toh02"> <reference anchor="Toh02">
<front> <front>
<title>Ad Hoc Mobile Wireless Networks</title> <title>Ad Hoc Mobile Wireless Networks</title>
<author initials="C.K." surname="Toh" fullname="Chai Keong Toh"/> <author initials="C." surname="Toh" fullname="Chai Keong Toh"/>
<date year="2002"/> <date year="2001" month="December"/>
</front> </front>
<seriesInfo name="Prentice Hall Publishers" value=""/> <refcontent>Prentice Hall Publishers</refcontent>
</reference> </reference>
<reference anchor="Zhang16"> <reference anchor="Zhang16">
<front> <front>
<title>Combing CCN with network coding: An architectural perspective </title> <title>Combing CCN with network coding: An architectural perspective </title>
<author initials="G." surname="Zhang" fullname="Guoqiang Zhang"/> <author initials="G." surname="Zhang" fullname="Guoqiang Zhang"/>
<author initials="Z." surname="Xu" fullname="Ziqu Xu"/> <author initials="Z." surname="Xu" fullname="Ziqu Xu"/>
<date year="2016"/> <date year="2016" month="January"/>
</front> </front>
<seriesInfo name="Computer Networks" value=""/> <seriesInfo name="DOI" value="10.1016/j.comnet.2015.11.008"/>
<refcontent>Computer Networks</refcontent>
</reference> </reference>
<reference anchor="Li03"> <reference anchor="Li03">
<front> <front>
<title>Linear Network Coding</title> <title>Linear network coding</title>
<author initials="S.-Y.R." surname="Li"/> <author initials="S.-Y." surname="Li" fullname="S.-Y.R. Li"/>
<author initials="R.W." surname="Yeung" fullname="Raymond W. Yeung"/ <author initials="R." surname="Yeung" fullname="Raymond W. Yeung"/>
>
<author initials="N." surname="Cai" fullname="Ning Cai"/> <author initials="N." surname="Cai" fullname="Ning Cai"/>
<date year="2003"/> <date year="2003" month="February"/>
</front> </front>
<seriesInfo name="IEEE Transactions on Information Theory" value=""/> <seriesInfo name="DOI" value="10.1109/TIT.2002.807285"/>
<refcontent>IEEE Transactions on Information Theory</refcontent>
</reference> </reference>
</references> </references>
</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"> <section numbered="false" toc="include" removeInRFC="false">
<name slugifiedName="name-acknowledgments">Acknowledgments</name> <name slugifiedName="name-acknowledgments">Acknowledgments</name>
<t> <t>
The authors would like to thank the NWCRG chairs, Vincent Roca (our shep The authors would like to thank the NWCRG chairs, <contact fullname="Vin
herd) and Marie-Jose Montpetit; cent Roca"/> (our shepherd) and <contact fullname="Marie-Jose Montpetit"/>, as w
and all those who provided comments -- namely (in alphabetical order), E ell as
mmanuel Lochin, David Oran, and Colin Perkins. all those who provided comments, namely (in alphabetical order), <contac
t fullname="Emmanuel Lochin"/>, <contact fullname="David Oran"/>, and <contact f
ullname="Colin Perkins"/>.
</t> </t>
</section> </section>
</back>
</back>
</rfc> </rfc>
 End of changes. 190 change blocks. 
667 lines changed or deleted 542 lines changed or added

This html diff was produced by rfcdiff 1.48.