NDNLP Implementation of�Best-Effort Link-Layer Reliability

Eric Newberry

Klaus Schneider

The University of Arizona

Background

• Based upon “Hop-By-Hop Best Effort Link Layer Reliability in Named Data Networking” by S. Vusirikala, et al.
• A Practical Congestion Control Scheme for NDN
• Modifications in Redmine issue #3823
• No packet number transmitted, only frame number
• RTO timeout uses traditional TCP RTO equation (SRTT + 4 * RTTVAR)
• After maximum retx reached or a loss, a notification will be sent to the strategy layer.
• The sender sends notifications to strategy layer based upon network-layer packets, not fragmented link-layer packets.
• Sequence numbers are required for all packets when BELRP enabled.

Terminology and Definitions

• This protocol is designed to form part of the NDN link protocol (NDNLPv2) system, as such it has some special terminology:
• A link-layer frame is called an LpPacket.
• The sequence number of a frame is called a Sequence (note the capitalization).
• A NetPkt is a network-layer packet (Data or Interest).
• The NFD Face system is composed of *Transport* and LinkService modules.
• The Transport module handles the transmission of LpPackets on the link and is protocol-specific.
• The LinkService module handles features common to every Transport, such as Sequence assignment and fragmentation.
• This protocol is designed to be part of the LinkService.

Packet Format

• The following headers fields need to be added to NDNLP:
• Ack (64-bit unsigned integer)
• This field may be repeated within the same packet, containing different values. For example:
• LpPacket ::� Ack :: 123� Ack :: 456� Ack :: 789
• TxSequence (64-bit unsigned integer)

Sender - onOutgoingNetworkLayerPacket()

Store LpPacket in TransmitCache

Assign sequence numbers to fragments

Start RTO timer

Send/Retx LpPacket to Transport for transmission

Increment retx[seq]

Call onGiveUp()

retx[seq] >= maxRetx

No

Fragment NetPkt into LpPackets

For each fragment

Create mapping of all fragments in NetPkt

Yes

Cancel all RTO timers for this NetPkt

Delete all LpPackets of NetPkt from TransmitCache

onOutOfOrderAck()

On RTO timer expire

Call onLoss()

Assign next sequential TxSequence and map TxSequence to seq num

Sender - onReceiveLpPacket()

Extract ACKs

Cancel fragment’s RTO timeout timer

Remove ACK’d fragments from TransmitCache

For each received ACK

Receive LpPacket

from Transport

Are there any unacknowledged frame numbers < ACK frame num?

Cancel fragment’s RTO timer and call onOutOfOrderAck()

If yes,

For each frame num < ACK

Reassembly

Map TxSequence to sequence number

Increment number of ACKs w/ greater TxSequences

Is number of greater TxSequences >= MAXGREATER (default: 3)

Yes

Receiver - onReceiveLpPacket()

Reassembly

Receive LpPacket

from Transport

Extract TxSequence from LpPacket

Insert Ack for TxSequence into AckQueue

Send as many Acks in AckQueue as can fit in an IDLE packet

For every Ack in AckQueue

Every 5ms (configurable)

Receiver - Send Subsystem

Search AckCache for pending Acks for frame’s nexthop

Receive network layer packet for transmission

Piggyback as many Acks as possible

Fragmentation

Send frame to Transport for transmission

RTO Calculation

• RTO is calculated using the standard TCP RTO formula (SRTT + 4 * RTTVAR).
• RTT is measured as the difference between the time the fragment was transmitted and the time an ACK was received for it.
• Fragments with one or more retransmissions are not taken into account when calculating the RTO.