Packet Loss Detection Protocol (PLDP) is a light network protocol that adds packet loss detection and recovery to otherwise unreliable datagram protocols such as UDP or IP.

PLDP was designed as a lowest common denominator of protocols that need to natively deal with the packet loss and network congestion. It is particularly useful for quick prototyping of loss- and congestion- aware protocols of both reliable and unreliable nature.

The main feature of PLDP is its simplicity. It defines only 6 messages, two of which are an equivalent of ICMP ping and the remaining four implement simple and flexible traffic flow model.

Customization

While the syntax of PLDP messages is fully defined, their semantics are defined only partially. This is what allows adapting PLDP to the needs of a wide variety of higher level protocols and quickly building such protocols on top of PLDP.

Practically, this translates to PLDP library delegating certain operational decisions to the external code via callbacks.

For example, when the packet loss is reported by a receiver, PLDP may be used either to retransmit lost packets or to decline such retransmission. What to do exactly is left to the application to decide.

Another example is that the very definition of the packet loss is provided by the application. PLDP merely informs the application that it did not receive the packet that was due, and the application may call it a loss or it may, for example, wait and see if it was a case of a packet re-ordering.

Defaults

There are several variable parts of PLDP that are customizable by the application, and PLDP provides reasonable defaults for all of them. This makes PLDP library usable out of the box and allows for incremental customization.

In its default configuration PLDP is a NACK protocol from a "gap detection" family.

Translated, this means that the receiving end of the data transmission proactively notifies the sender on any interruptions (gaps) in the incoming sequence of numbered packets.

Usage

With a varying degree of effort PLDP can be used to implement:

• unreliable congestion-aware protocols
• reliable out-of-order delivery protocols (along the lines of TCP with SACK)
• TCP clones including Reno and Vegas flavors
• bandwidth estimation protocols
• simple ping and its more elaborate variations

Protocol

PLDP defines six messages - DATA, NACK, SKIP, NREQ, PING and PONG.

1. DATA message

As its name implies this message carries the actual data payload. All data messages are tagged with a monotonically increasing sequence number, one sequence per direction. These are the only PLDP messages that are tracked for the loss.

2. NACK message

Message is sent by the receiver of DATA messages when it decides to notify the sender on a perceived packet loss. The message contains the sequence number of the first packet that was expected by was not received as well as the list of other "lost" packets.

The following diagram illustrates a case of a single packet loss and subsequent recovery from the loss via retransmission:
3. SKIP message

Instead of retransmitting the DATA #3 packet in the above diagram, the sender had an option of sending SKIP message to tell the receiver that it won't retransmit the DATA.

This message is especially useful when the NACK reports a multi-packet loss and the application protocol can tolerate the loss. A VoIP data protocol would be a good example.

4. NREQ message

This message is sent by the DATA sender to solicit the NACK from the receiver. If there were no packet loss detected by the receiver, it responds with an empty NACK, otherwise it sends a regular NACK message.

NREQ is effectively a way to solicit an ACK from the other side. In a simple case it may be included with every DATA message and it will turn PLDP into an ACK protocol similar to TCP. If in addition to this the receiving side is configured to ignore the data loss, then PLDP will implement exact TCP semantics.

5. PING message

PING is sent to request a response from the peer in a form of a PONG message. The PING message includes arbitrary context data that is blindly copied by the peer into a PONG message.

6. PONG message

In addition to the context data from PING, the PONG message carries a processing delay value. This value is a number of microseconds that the PONG sender spent processing the message.

The processing delay may not be trivial if the pong is not dispatched immediately after the ping is received. In fact, pings may be accumulated and replied to only once every few seconds, in which case multiple pong messages are sent back at once, each with its own processing delay value.

Batching

PLDP allows multiple messages to be packed together and put on a wire as a single datagram. With an exception of multiple PONG message, there can be no more than one instance of every message type per PLDP wire datagram. Also due to the syntax of the DATA message, it must always come last when it is present.

Semantics

PLDP peer that is sending DATA messages is referred to as the sender, and its remote party is referred to as the receiver.

A peer can act as the sender and the receiver at the same time. In this case there are effectively two independent PLDP flows, one in each direction.

DATA at the receiver

The receiver keeps track of received packet sequence numbers and it discards duplicate packets.

NACK at the sender

Upon receiving NACK message the sender must either respond with the SKIP message or it must start retransmitting the DATA packets specified in NACK message. Only when it sends out or skips all missing packets should it resume sending new DATA messages.

NACK at the receiver

The receiver maintains a missing packets map that holds sequence numbers of the packets that are currently presumed to be missing. The map is initially empty.

The map is populated by the application when it determines that a specific packet should be considered missing. Map entries are removed by the PLDP upon receiving respective DATA or SKIP messages.

NACK timer

Once the first packet is added to the missing packet map, the receiver sends out NACK message and sets up a NACK retransmission timer. Timer interval defaults to a 2*RTT value, and it can be modified by the application.

The RTT value is updated through PING/PONG exchange using averaging method similar to the one used by TCP. Default RTT is set to a conservative value of 250 ms.

NACK timer is stopped under two conditions.

• The missing packet map becomes empty.
• The first packet (the packet with lowest sequence number) in a missing packet map is received. This reception implies that the sender received the NACK and started retransmitting the packets.

NACK timer is not stopped in direct response to receiving a SKIP message.

NACK details

NACKs are sent strictly by the timer. They do not piggyback on other messages that may be going in sender's direction.

Every NACK is paired with a PING message to facilitate RTT updates. This can be changed by the application.

Sender

As a sender the application has a control over:

• DATA transmission rate.
• Which lost packets are retransmitted and which are not.

Receiver

As a receiver the application has a control over:

• Determining what constitutes the packet loss.
  Whenever PLDP detects the first gap in a DATA packet sequence it notifies the application. It is then up to the application either to immediately respond with the NACK, to send the NACK after a delay or to completely ignore the loss. If the loss is ignored, the lost packet map is not updated. Otherwise the map is updated to record the packet sequence number.
  The default behavior is to send the NACK immediately.
• The NACK timer interval.
  The interval defaults to 2*RTT, and it may be changed by the application at will.

Ping and RTT

The application in either role also has control over the process of RTT estimation:

• The application can initiate an RTT update by sending a PING message. PLDP sends PING messages only with NACKs, so that is the only condition under which the update of RTT occurs in default configuration.
  The application may also choose to be notified when PONGs are received and then update the RTT using whatever logic it sees feasible. By default RTT is updated using standard TCP formula:
  RTT_current = (9*RTT_current + RTT_new) / 10
  
• The application decides when PONGs are sent out. When the PING is received, the PONG may be sent out immediately, sent later or not sent at all.
  PLDP keeps track of all delayed PONGs and sends them all at once when the application finally decides to dispatch them.