The Internet has changed a long time ago. One of the main protocols of the Internet - UDP is used by applications not only to deliver datagrams and broadcasts, but also to provide "peer-to-peer" connections between network nodes. Due to its simple design, this protocol has many previously unplanned uses, however, the shortcomings of the protocol, such as the lack of guaranteed delivery, have not disappeared anywhere. This article describes the implementation of the guaranteed delivery protocol over UDP.
Contents:
Entry
The original architecture of the Internet assumed a homogeneous address space in which each node had a global and unique IP address and could communicate directly with other nodes. Now the Internet, in fact, has a different architecture - one area of global IP addresses and many areas with private addresses hidden behind NAT devices.In this architecture, only devices in the global address space can easily communicate with anyone on the network because they have a unique, globally routable IP address. A node on a private network can connect to other nodes on the same network, and can also connect to other well-known nodes in the global address space. This interaction is achieved largely due to the network address translation mechanism. NAT devices, such as Wi-Fi routers, create special translation table entries for outgoing connections and modify IP addresses and port numbers in packets. This allows outgoing connections from the private network to hosts in the global address space. But at the same time, NAT devices usually block all incoming traffic unless separate rules for incoming connections are set.
This architecture of the Internet is correct enough for client-server communication, where clients can be in private networks, and servers have a global address. But it creates difficulties for the direct connection of two nodes between different private networks. A direct connection between two nodes is important for peer-to-peer applications such as voice transmission (Skype), gaining remote access to a computer (TeamViewer), or online gaming.
One of the most effective methods for establishing a peer-to-peer connection between devices on different private networks is called hole punching. This technique is most commonly used with applications based on the UDP protocol.
But if your application needs guaranteed delivery of data, for example, you transfer files between computers, then using UDP will have many difficulties due to the fact that UDP is not a guaranteed delivery protocol and does not provide packet delivery in order, unlike the TCP protocol.
In this case, to ensure guaranteed packet delivery, it is required to implement an application layer protocol that provides the necessary functionality and works over UDP.
I want to note right away that there is a TCP hole punching technique for establishing TCP connections between nodes in different private networks, but due to the lack of support for it by many NAT devices, it is usually not considered as the main way to connect such nodes.
For the remainder of this article, I will focus only on the implementation of the guaranteed delivery protocol. The implementation of the UDP hole punching technique will be described in the following articles.
Protocol Requirements
- Reliable packet delivery implemented through a positive feedback mechanism (the so-called positive acknowledgment )
- The need for efficient transfer of big data, i.e. the protocol should avoid unnecessary packet relays
- It should be possible to cancel the delivery confirmation mechanism (the ability to function as a "pure" UDP protocol)
- Ability to implement command mode, with confirmation of each message
- The basic unit of data transfer over the protocol must be a message
These requirements largely coincide with the Reliable Data Protocol requirements described in и , and I relied on those standards when developing this protocol.
To understand these requirements, let's look at the timing of data transfer between two network nodes using the TCP and UDP protocols. Let in both cases we will have one packet lost.
Transfer of non-interactive data over TCP:
As you can see from the diagram, in case of packet loss, TCP will detect the lost packet and report it to the sender by asking for the number of the lost segment.
Data transfer via UDP protocol:
UDP does not take any loss detection steps. Control of transmission errors in the UDP protocol is entirely the responsibility of the application.
Error detection in the TCP protocol is achieved by establishing a connection with an end node, storing the state of that connection, indicating the number of bytes sent in each packet header, and notifying receipts using an acknowledgment number.
Additionally, to improve performance (i.e. sending more than one segment without receiving an acknowledgment), the TCP protocol uses the so-called transmission window - the number of bytes of data that the sender of the segment expects to receive.
For more information about the TCP protocol, see , from UDP to where, in fact, they are defined.
From the above, it is clear that in order to create a reliable message delivery protocol over UDP (hereinafter referred to as Reliable UDP), it is required to implement data transfer mechanisms similar to TCP. Namely:
- save connection state
- use segment numbering
- use special confirmation packages
- use a simplified windowing mechanism to increase protocol throughput
Additionally, you need:
- signal the start of a message, to allocate resources for the connection
- signal the end of a message, to pass the received message to the upstream application and release protocol resources
- allow the connection-specific protocol to disable the delivery confirmation mechanism to function as "pure" UDP
Reliable UDP header
Recall that a UDP datagram is encapsulated in an IP datagram. The Reliable UDP packet is appropriately "wrapped" into a UDP datagram.
Reliable UDP header encapsulation:
The structure of the Reliable UDP header is quite simple:
- Flags - package control flags
- MessageType - message type used by upstream applications to subscribe to specific messages
- TransmissionId - the number of the transmission, together with the address and port of the recipient, uniquely identifies the connection
- PacketNumber - packet number
- Options - additional protocol options. In the case of the first packet, it is used to indicate the size of the message
Flags are as follows:
- FirstPacket - the first packet of the message
- NoAsk - the message does not require an acknowledgment mechanism to be enabled
- LastPacket - the last packet of the message
- RequestForPacket - confirmation packet or request for a lost packet
General principles of the protocol
Since Reliable UDP is focused on guaranteed message transmission between two nodes, it must be able to establish a connection with the other side. To establish a connection, the sender sends a packet with the FirstPacket flag, the response to which will mean the connection is established. All response packets, or, in other words, acknowledgment packets, always set the value of the PacketNumber field to one more than the largest PacketNumber value of successfully received packets. The Options field for the first packet sent is the size of the message.
A similar mechanism is used to terminate a connection. The LastPacket flag is set on the last packet of the message. In the response packet, the number of the last packet + 1 is indicated, which for the receiving side means successful delivery of the message.
Connection establishment and termination diagram:
When the connection is established, data transfer begins. Data is transmitted in blocks of packets. Each block, except the last one, contains a fixed number of packets. It is equal to the receive/transmit window size. The last block of data may have fewer packets. After sending each block, the sending side waits for a delivery confirmation or a request to re-deliver lost packets, leaving the receive/transmit window open to receive responses. After receiving confirmation of block delivery, the receive/transmit window shifts and the next block of data is sent.
The receiving side receives the packets. Each packet is checked to see if it falls within the transmission window. Packets and duplicates that do not fall into the window are filtered out. Because If the size of the window is fixed and the same for the recipient and the sender, then in the case of a block of packets being delivered without loss, the window is shifted to receive packets of the next block of data and a delivery confirmation is sent. If the window does not fill up within the period set by the work timer, then a check will be started on which packets have not been delivered and requests for redelivery will be sent.
Retransmission Diagram:
Timeouts and protocol timers
There are several reasons why a connection cannot be established. For example, if the receiving party is offline. In this case, when trying to establish a connection, the connection will be closed by timeout. The Reliable UDP implementation uses two timers to set timeouts. The first, the working timer, is used to wait for a response from the remote host. If it fires on the sender side, then the last sent packet is resent. If the timer expires at the recipient, then a check for lost packets is performed and requests for redelivery are sent.
The second timer is needed to close the connection in case of a lack of communication between the nodes. For the sender side, it starts immediately after the working timer expires, and waits for a response from the remote node. If there is no response within the specified period, the connection is terminated and resources are released. For the receiving side, the connection close timer is started after the work timer expires twice. This is necessary to insure against the loss of the confirmation packet. When the timer expires, the connection is also terminated and resources are released.
Reliable UDP transmission state diagram
The principles of the protocol are implemented in a finite state machine, each state of which is responsible for a certain logic of packet processing.
Reliable UDP State Diagram:
Closed - is not really a state, it is a start and end point for the automaton. For state Closed a transmission control block is received, which, implementing an asynchronous UDP server, forwards packets to the appropriate connections and starts state processing.
FirstPacketSending – the initial state in which the outgoing connection is when the message is sent.
In this state, the first packet for normal messages is sent. For messages without send confirmation, this is the only state where the entire message is sent.
SendingCycle – ground state for the transmission of message packets.
Transition to it from the state FirstPacketSending carried out after the first packet of the message has been sent. It is in this state that all acknowledgments and requests for retransmissions come. Exit from it is possible in two cases - in case of successful delivery of the message or by timeout.
FirstPacketReceived – the initial state for the recipient of the message.
It checks the correctness of the beginning of the transmission, creates the necessary structures, and sends an acknowledgment of receipt of the first packet.
For a message that consists of a single packet and was sent without using proof of delivery, this is the only state. After processing such a message, the connection is closed.
assembly – basic state for receiving message packets.
It writes packets to temporary storage, checks for packet loss, sends acknowledgments for the delivery of a block of packets and the entire message, and sends requests for redelivery of lost packets. In case of successful receipt of the entire message, the connection goes into the state Completed, otherwise, a timeout exits.
Completed – closing the connection in case of successful receipt of the entire message.
This state is necessary for the assembly of the message and for the case when the delivery confirmation of the message was lost on the way to the sender. This state is exited by a timeout, but the connection is considered successfully closed.
Deeper into the code. transmission control unit
One of the key elements of Reliable UDP is the transmission control block. The task of this block is to store current connections and auxiliary elements, distribute incoming packets to the corresponding connections, provide an interface for sending packets to a connection, and implement the protocol API. The transmission control block receives packets from the UDP layer and forwards them to the state machine for processing. To receive packets, it implements an asynchronous UDP server.
Some members of the ReliableUdpConnectionControlBlock class:
internal class ReliableUdpConnectionControlBlock : IDisposable
{
// массив байт для указанного ключа. Используется для сборки входящих сообщений
public ConcurrentDictionary<Tuple<EndPoint, Int32>, byte[]> IncomingStreams { get; private set;}
// массив байт для указанного ключа. Используется для отправки исходящих сообщений.
public ConcurrentDictionary<Tuple<EndPoint, Int32>, byte[]> OutcomingStreams { get; private set; }
// connection record для указанного ключа.
private readonly ConcurrentDictionary<Tuple<EndPoint, Int32>, ReliableUdpConnectionRecord> m_listOfHandlers;
// список подписчиков на сообщения.
private readonly List<ReliableUdpSubscribeObject> m_subscribers;
// локальный сокет
private Socket m_socketIn;
// порт для входящих сообщений
private int m_port;
// локальный IP адрес
private IPAddress m_ipAddress;
// локальная конечная точка
public IPEndPoint LocalEndpoint { get; private set; }
// коллекция предварительно инициализированных
// состояний конечного автомата
public StatesCollection States { get; private set; }
// генератор случайных чисел. Используется для создания TransmissionId
private readonly RNGCryptoServiceProvider m_randomCrypto;
//...
}
Implementation of asynchronous UDP server:
private void Receive()
{
EndPoint connectedClient = new IPEndPoint(IPAddress.Any, 0);
// создаем новый буфер, для каждого socket.BeginReceiveFrom
byte[] buffer = new byte[DefaultMaxPacketSize + ReliableUdpHeader.Length];
// передаем буфер в качестве параметра для асинхронного метода
this.m_socketIn.BeginReceiveFrom(buffer, 0, buffer.Length, SocketFlags.None, ref connectedClient, EndReceive, buffer);
}
private void EndReceive(IAsyncResult ar)
{
EndPoint connectedClient = new IPEndPoint(IPAddress.Any, 0);
int bytesRead = this.m_socketIn.EndReceiveFrom(ar, ref connectedClient);
//пакет получен, готовы принимать следующий
Receive();
// т.к. простейший способ решить вопрос с буфером - получить ссылку на него
// из IAsyncResult.AsyncState
byte[] bytes = ((byte[]) ar.AsyncState).Slice(0, bytesRead);
// получаем заголовок пакета
ReliableUdpHeader header;
if (!ReliableUdpStateTools.ReadReliableUdpHeader(bytes, out header))
{
// пришел некорректный пакет - отбрасываем его
return;
}
// конструируем ключ для определения connection record’а для пакета
Tuple<EndPoint, Int32> key = new Tuple<EndPoint, Int32>(connectedClient, header.TransmissionId);
// получаем существующую connection record или создаем новую
ReliableUdpConnectionRecord record = m_listOfHandlers.GetOrAdd(key, new ReliableUdpConnectionRecord(key, this, header.ReliableUdpMessageType));
// запускаем пакет в обработку в конечный автомат
record.State.ReceivePacket(record, header, bytes);
}
For each message transfer, a structure is created that contains information about the connection. Such a structure is called connection record.
Some members of the ReliableUdpConnectionRecord class:
internal class ReliableUdpConnectionRecord : IDisposable
{
// массив байт с сообщением
public byte[] IncomingStream { get; set; }
// ссылка на состояние конечного автомата
public ReliableUdpState State { get; set; }
// пара, однозначно определяющая connection record
// в блоке управления передачей
public Tuple<EndPoint, Int32> Key { get; private set;}
// нижняя граница приемного окна
public int WindowLowerBound;
// размер окна передачи
public readonly int WindowSize;
// номер пакета для отправки
public int SndNext;
// количество пакетов для отправки
public int NumberOfPackets;
// номер передачи (именно он и есть вторая часть Tuple)
// для каждого сообщения свой
public readonly Int32 TransmissionId;
// удаленный IP endpoint – собственно получатель сообщения
public readonly IPEndPoint RemoteClient;
// размер пакета, во избежание фрагментации на IP уровне
// не должен превышать MTU – (IP.Header + UDP.Header + RelaibleUDP.Header)
public readonly int BufferSize;
// блок управления передачей
public readonly ReliableUdpConnectionControlBlock Tcb;
// инкапсулирует результаты асинхронной операции для BeginSendMessage/EndSendMessage
public readonly AsyncResultSendMessage AsyncResult;
// не отправлять пакеты подтверждения
public bool IsNoAnswerNeeded;
// последний корректно полученный пакет (всегда устанавливается в наибольший номер)
public int RcvCurrent;
// массив с номерами потерянных пакетов
public int[] LostPackets { get; private set; }
// пришел ли последний пакет. Используется как bool.
public int IsLastPacketReceived = 0;
//...
}
Deeper into the code. states
States implement the state machine of the Reliable UDP protocol, where the main processing of packets takes place. The abstract class ReliableUdpState provides an interface for the state:
The entire logic of the protocol is implemented by the classes presented above, together with an auxiliary class that provides static methods, such as, for example, constructing the ReliableUdp header from the connection record.
Next, we will consider in detail the implementation of the interface methods that determine the basic algorithms of the protocol.
DisposeByTimeout Method
The DisposeByTimeout method is responsible for releasing connection resources after a timeout and for signaling successful/unsuccessful message delivery.
ReliableUdpState.DisposeByTimeout:
protected virtual void DisposeByTimeout(object record)
{
ReliableUdpConnectionRecord connectionRecord = (ReliableUdpConnectionRecord) record;
if (record.AsyncResult != null)
{
connectionRecord.AsyncResult.SetAsCompleted(false);
}
connectionRecord.Dispose();
}
It's only overridden in the state Completed.
Completed.DisposeByTimeout:
protected override void DisposeByTimeout(object record)
{
ReliableUdpConnectionRecord connectionRecord = (ReliableUdpConnectionRecord) record;
// сообщаем об успешном получении сообщения
SetAsCompleted(connectionRecord);
}
ProcessPackets Method
The ProcessPackets method is responsible for additional processing of a package or packages. Called directly or via a packet wait timer.
In condition assembly the method is overridden and is responsible for checking for lost packets and transitioning to the state Completed, in case of receiving the last packet and passing a successful check
Assembling.ProcessPackets:
public override void ProcessPackets(ReliableUdpConnectionRecord connectionRecord)
{
if (connectionRecord.IsDone != 0)
return;
if (!ReliableUdpStateTools.CheckForNoPacketLoss(connectionRecord, connectionRecord.IsLastPacketReceived != 0))
{
// есть потерянные пакеты, отсылаем запросы на них
foreach (int seqNum in connectionRecord.LostPackets)
{
if (seqNum != 0)
{
ReliableUdpStateTools.SendAskForLostPacket(connectionRecord, seqNum);
}
}
// устанавливаем таймер во второй раз, для повторной попытки передачи
if (!connectionRecord.TimerSecondTry)
{
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
connectionRecord.TimerSecondTry = true;
return;
}
// если после двух попыток срабатываний WaitForPacketTimer
// не удалось получить пакеты - запускаем таймер завершения соединения
StartCloseWaitTimer(connectionRecord);
}
else if (connectionRecord.IsLastPacketReceived != 0)
// успешная проверка
{
// высылаем подтверждение о получении блока данных
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
connectionRecord.State = connectionRecord.Tcb.States.Completed;
connectionRecord.State.ProcessPackets(connectionRecord);
// вместо моментальной реализации ресурсов
// запускаем таймер, на случай, если
// если последний ack не дойдет до отправителя и он запросит его снова.
// по срабатыванию таймера - реализуем ресурсы
// в состоянии Completed метод таймера переопределен
StartCloseWaitTimer(connectionRecord);
}
// это случай, когда ack на блок пакетов был потерян
else
{
if (!connectionRecord.TimerSecondTry)
{
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
connectionRecord.TimerSecondTry = true;
return;
}
// запускаем таймер завершения соединения
StartCloseWaitTimer(connectionRecord);
}
}
In condition SendingCycle this method is called only on a timer, and is responsible for resending the last message, as well as enabling the connection close timer.
SendingCycle.ProcessPackets:
public override void ProcessPackets(ReliableUdpConnectionRecord connectionRecord)
{
if (connectionRecord.IsDone != 0)
return;
// отправляем повторно последний пакет
// ( в случае восстановления соединения узел-приемник заново отправит запросы, которые до него не дошли)
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.RetransmissionCreateUdpPayload(connectionRecord, connectionRecord.SndNext - 1));
// включаем таймер CloseWait – для ожидания восстановления соединения или его завершения
StartCloseWaitTimer(connectionRecord);
}
In condition Completed the method stops the running timer and sends the message to the subscribers.
Completed.ProcessPackets:
public override void ProcessPackets(ReliableUdpConnectionRecord connectionRecord)
{
if (connectionRecord.WaitForPacketsTimer != null)
connectionRecord.WaitForPacketsTimer.Dispose();
// собираем сообщение и передаем его подписчикам
ReliableUdpStateTools.CreateMessageFromMemoryStream(connectionRecord);
}
ReceivePacket method
In condition FirstPacketReceived the main task of the method is to determine whether the first message packet actually arrived at the interface, and also to collect a message consisting of a single packet.
FirstPacketReceived.ReceivePacket:
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
if (!header.Flags.HasFlag(ReliableUdpHeaderFlags.FirstPacket))
// отбрасываем пакет
return;
// комбинация двух флагов - FirstPacket и LastPacket - говорит что у нас единственное сообщение
if (header.Flags.HasFlag(ReliableUdpHeaderFlags.FirstPacket) &
header.Flags.HasFlag(ReliableUdpHeaderFlags.LastPacket))
{
ReliableUdpStateTools.CreateMessageFromSinglePacket(connectionRecord, header, payload.Slice(ReliableUdpHeader.Length, payload.Length));
if (!header.Flags.HasFlag(ReliableUdpHeaderFlags.NoAsk))
{
// отправляем пакет подтверждение
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
}
SetAsCompleted(connectionRecord);
return;
}
// by design все packet numbers начинаются с 0;
if (header.PacketNumber != 0)
return;
ReliableUdpStateTools.InitIncomingBytesStorage(connectionRecord, header);
ReliableUdpStateTools.WritePacketData(connectionRecord, header, payload);
// считаем кол-во пакетов, которые должны прийти
connectionRecord.NumberOfPackets = (int)Math.Ceiling((double) ((double) connectionRecord.IncomingStream.Length/(double) connectionRecord.BufferSize));
// записываем номер последнего полученного пакета (0)
connectionRecord.RcvCurrent = header.PacketNumber;
// после сдвинули окно приема на 1
connectionRecord.WindowLowerBound++;
// переключаем состояние
connectionRecord.State = connectionRecord.Tcb.States.Assembling;
// если не требуется механизм подтверждение
// запускаем таймер который высвободит все структуры
if (header.Flags.HasFlag(ReliableUdpHeaderFlags.NoAsk))
{
connectionRecord.CloseWaitTimer = new Timer(DisposeByTimeout, connectionRecord, connectionRecord.ShortTimerPeriod, -1);
}
else
{
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
connectionRecord.WaitForPacketsTimer = new Timer(CheckByTimer, connectionRecord, connectionRecord.ShortTimerPeriod, -1);
}
}
In condition SendingCycle this method is overridden to accept delivery acknowledgments and retransmission requests.
SendingCycle.ReceivePacket:
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
if (connectionRecord.IsDone != 0)
return;
if (!header.Flags.HasFlag(ReliableUdpHeaderFlags.RequestForPacket))
return;
// расчет конечной границы окна
// берется граница окна + 1, для получения подтверждений доставки
int windowHighestBound = Math.Min((connectionRecord.WindowLowerBound + connectionRecord.WindowSize), (connectionRecord.NumberOfPackets));
// проверка на попадание в окно
if (header.PacketNumber < connectionRecord.WindowLowerBound || header.PacketNumber > windowHighestBound)
return;
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
if (connectionRecord.CloseWaitTimer != null)
connectionRecord.CloseWaitTimer.Change(-1, -1);
// проверить на последний пакет:
if (header.PacketNumber == connectionRecord.NumberOfPackets)
{
// передача завершена
Interlocked.Increment(ref connectionRecord.IsDone);
SetAsCompleted(connectionRecord);
return;
}
// это ответ на первый пакет c подтверждением
if ((header.Flags.HasFlag(ReliableUdpHeaderFlags.FirstPacket) && header.PacketNumber == 1))
{
// без сдвига окна
SendPacket(connectionRecord);
}
// пришло подтверждение о получении блока данных
else if (header.PacketNumber == windowHighestBound)
{
// сдвигаем окно прием/передачи
connectionRecord.WindowLowerBound += connectionRecord.WindowSize;
// обнуляем массив контроля передачи
connectionRecord.WindowControlArray.Nullify();
// отправляем блок пакетов
SendPacket(connectionRecord);
}
// это запрос на повторную передачу – отправляем требуемый пакет
else
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.RetransmissionCreateUdpPayload(connectionRecord, header.PacketNumber));
}
In condition assembly in the ReceivePacket method, the main work of assembling a message from incoming packets takes place.
Assembling.ReceivePacket:
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
if (connectionRecord.IsDone != 0)
return;
// обработка пакетов с отключенным механизмом подтверждения доставки
if (header.Flags.HasFlag(ReliableUdpHeaderFlags.NoAsk))
{
// сбрасываем таймер
connectionRecord.CloseWaitTimer.Change(connectionRecord.LongTimerPeriod, -1);
// записываем данные
ReliableUdpStateTools.WritePacketData(connectionRecord, header, payload);
// если получили пакет с последним флагом - делаем завершаем
if (header.Flags.HasFlag(ReliableUdpHeaderFlags.LastPacket))
{
connectionRecord.State = connectionRecord.Tcb.States.Completed;
connectionRecord.State.ProcessPackets(connectionRecord);
}
return;
}
// расчет конечной границы окна
int windowHighestBound = Math.Min((connectionRecord.WindowLowerBound + connectionRecord.WindowSize - 1), (connectionRecord.NumberOfPackets - 1));
// отбрасываем не попадающие в окно пакеты
if (header.PacketNumber < connectionRecord.WindowLowerBound || header.PacketNumber > (windowHighestBound))
return;
// отбрасываем дубликаты
if (connectionRecord.WindowControlArray.Contains(header.PacketNumber))
return;
// записываем данные
ReliableUdpStateTools.WritePacketData(connectionRecord, header, payload);
// увеличиваем счетчик пакетов
connectionRecord.PacketCounter++;
// записываем в массив управления окном текущий номер пакета
connectionRecord.WindowControlArray[header.PacketNumber - connectionRecord.WindowLowerBound] = header.PacketNumber;
// устанавливаем наибольший пришедший пакет
if (header.PacketNumber > connectionRecord.RcvCurrent)
connectionRecord.RcvCurrent = header.PacketNumber;
// перезапускам таймеры
connectionRecord.TimerSecondTry = false;
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
if (connectionRecord.CloseWaitTimer != null)
connectionRecord.CloseWaitTimer.Change(-1, -1);
// если пришел последний пакет
if (header.Flags.HasFlag(ReliableUdpHeaderFlags.LastPacket))
{
Interlocked.Increment(ref connectionRecord.IsLastPacketReceived);
}
// если нам пришли все пакеты окна, то сбрасываем счетчик
// и высылаем пакет подтверждение
else if (connectionRecord.PacketCounter == connectionRecord.WindowSize)
{
// сбрасываем счетчик.
connectionRecord.PacketCounter = 0;
// сдвинули окно передачи
connectionRecord.WindowLowerBound += connectionRecord.WindowSize;
// обнуление массива управления передачей
connectionRecord.WindowControlArray.Nullify();
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
}
// если последний пакет уже имеется
if (Thread.VolatileRead(ref connectionRecord.IsLastPacketReceived) != 0)
{
// проверяем пакеты
ProcessPackets(connectionRecord);
}
}
In condition Completed the only task of the method is to send a re-acknowledgment of the successful delivery of the message.
Completed.ReceivePacket:
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
// повторная отправка последнего пакета в связи с тем,
// что последний ack не дошел до отправителя
if (header.Flags.HasFlag(ReliableUdpHeaderFlags.LastPacket))
{
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
}
}
Send Packet Method
In condition FirstPacketSending this method sends the first packet of data, or, if the message does not require delivery confirmation, the entire message.
FirstPacketSending.SendPacket:
public override void SendPacket(ReliableUdpConnectionRecord connectionRecord)
{
connectionRecord.PacketCounter = 0;
connectionRecord.SndNext = 0;
connectionRecord.WindowLowerBound = 0;
// если подтверждения не требуется - отправляем все пакеты
// и высвобождаем ресурсы
if (connectionRecord.IsNoAnswerNeeded)
{
// Здесь происходит отправка As Is
do
{
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.CreateUdpPayload(connectionRecord, ReliableUdpStateTools. CreateReliableUdpHeader(connectionRecord)));
connectionRecord.SndNext++;
} while (connectionRecord.SndNext < connectionRecord.NumberOfPackets);
SetAsCompleted(connectionRecord);
return;
}
// создаем заголовок пакета и отправляем его
ReliableUdpHeader header = ReliableUdpStateTools.CreateReliableUdpHeader(connectionRecord);
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.CreateUdpPayload(connectionRecord, header));
// увеличиваем счетчик
connectionRecord.SndNext++;
// сдвигаем окно
connectionRecord.WindowLowerBound++;
connectionRecord.State = connectionRecord.Tcb.States.SendingCycle;
// Запускаем таймер
connectionRecord.WaitForPacketsTimer = new Timer(CheckByTimer, connectionRecord, connectionRecord.ShortTimerPeriod, -1);
}
In condition SendingCycle in this method, a block of packets is sent.
SendingCycle.SendPacket:
public override void SendPacket(ReliableUdpConnectionRecord connectionRecord)
{
// отправляем блок пакетов
for (connectionRecord.PacketCounter = 0;
connectionRecord.PacketCounter < connectionRecord.WindowSize &&
connectionRecord.SndNext < connectionRecord.NumberOfPackets;
connectionRecord.PacketCounter++)
{
ReliableUdpHeader header = ReliableUdpStateTools.CreateReliableUdpHeader(connectionRecord);
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.CreateUdpPayload(connectionRecord, header));
connectionRecord.SndNext++;
}
// на случай большого окна передачи, перезапускаем таймер после отправки
connectionRecord.WaitForPacketsTimer.Change( connectionRecord.ShortTimerPeriod, -1 );
if ( connectionRecord.CloseWaitTimer != null )
{
connectionRecord.CloseWaitTimer.Change( -1, -1 );
}
}
Deeper into the code. Creating and Establishing Connections
Now that we've seen the basic states and the methods used to handle states, let's break down a few examples of how the protocol works in a bit more detail.
Data transmission diagram under normal conditions:
Consider in detail the creation connection record to connect and send the first packet. The transfer is always initiated by the application that calls the send message API. Next, the StartTransmission method of the transmission control block is invoked, which starts the transmission of data for the new message.
Creating an outgoing connection:
private void StartTransmission(ReliableUdpMessage reliableUdpMessage, EndPoint endPoint, AsyncResultSendMessage asyncResult)
{
if (m_isListenerStarted == 0)
{
if (this.LocalEndpoint == null)
{
throw new ArgumentNullException( "", "You must use constructor with parameters or start listener before sending message" );
}
// запускаем обработку входящих пакетов
StartListener(LocalEndpoint);
}
// создаем ключ для словаря, на основе EndPoint и ReliableUdpHeader.TransmissionId
byte[] transmissionId = new byte[4];
// создаем случайный номер transmissionId
m_randomCrypto.GetBytes(transmissionId);
Tuple<EndPoint, Int32> key = new Tuple<EndPoint, Int32>(endPoint, BitConverter.ToInt32(transmissionId, 0));
// создаем новую запись для соединения и проверяем,
// существует ли уже такой номер в наших словарях
if (!m_listOfHandlers.TryAdd(key, new ReliableUdpConnectionRecord(key, this, reliableUdpMessage, asyncResult)))
{
// если существует – то повторно генерируем случайный номер
m_randomCrypto.GetBytes(transmissionId);
key = new Tuple<EndPoint, Int32>(endPoint, BitConverter.ToInt32(transmissionId, 0));
if (!m_listOfHandlers.TryAdd(key, new ReliableUdpConnectionRecord(key, this, reliableUdpMessage, asyncResult)))
// если снова не удалось – генерируем исключение
throw new ArgumentException("Pair TransmissionId & EndPoint is already exists in the dictionary");
}
// запустили состояние в обработку
m_listOfHandlers[key].State.SendPacket(m_listOfHandlers[key]);
}
Sending the first packet (FirstPacketSending state):
public override void SendPacket(ReliableUdpConnectionRecord connectionRecord)
{
connectionRecord.PacketCounter = 0;
connectionRecord.SndNext = 0;
connectionRecord.WindowLowerBound = 0;
// ...
// создаем заголовок пакета и отправляем его
ReliableUdpHeader header = ReliableUdpStateTools.CreateReliableUdpHeader(connectionRecord);
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.CreateUdpPayload(connectionRecord, header));
// увеличиваем счетчик
connectionRecord.SndNext++;
// сдвигаем окно
connectionRecord.WindowLowerBound++;
// переходим в состояние SendingCycle
connectionRecord.State = connectionRecord.Tcb.States.SendingCycle;
// Запускаем таймер
connectionRecord.WaitForPacketsTimer = new Timer(CheckByTimer, connectionRecord, connectionRecord.ShortTimerPeriod, -1);
}
After sending the first packet, the sender enters the state SendingCycle – wait for confirmation of package delivery.
The receiving side, using the EndReceive method, receives the sent packet, creates a new connection record and passes this packet, with a pre-parsed header, to the ReceivePacket method of the state for processing FirstPacketReceived
Creating a connection on the receiving side:
private void EndReceive(IAsyncResult ar)
{
// ...
// пакет получен
// парсим заголовок пакета
ReliableUdpHeader header;
if (!ReliableUdpStateTools.ReadReliableUdpHeader(bytes, out header))
{
// пришел некорректный пакет - отбрасываем его
return;
}
// конструируем ключ для определения connection record’а для пакета
Tuple<EndPoint, Int32> key = new Tuple<EndPoint, Int32>(connectedClient, header.TransmissionId);
// получаем существующую connection record или создаем новую
ReliableUdpConnectionRecord record = m_listOfHandlers.GetOrAdd(key, new ReliableUdpConnectionRecord(key, this, header. ReliableUdpMessageType));
// запускаем пакет в обработку в конечный автомат
record.State.ReceivePacket(record, header, bytes);
}
Receiving the first packet and sending an acknowledgment (FirstPacketReceived state):
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
if (!header.Flags.HasFlag(ReliableUdpHeaderFlags.FirstPacket))
// отбрасываем пакет
return;
// ...
// by design все packet numbers начинаются с 0;
if (header.PacketNumber != 0)
return;
// инициализируем массив для хранения частей сообщения
ReliableUdpStateTools.InitIncomingBytesStorage(connectionRecord, header);
// записываем данные пакет в массив
ReliableUdpStateTools.WritePacketData(connectionRecord, header, payload);
// считаем кол-во пакетов, которые должны прийти
connectionRecord.NumberOfPackets = (int)Math.Ceiling((double) ((double) connectionRecord.IncomingStream.Length/(double) connectionRecord.BufferSize));
// записываем номер последнего полученного пакета (0)
connectionRecord.RcvCurrent = header.PacketNumber;
// после сдвинули окно приема на 1
connectionRecord.WindowLowerBound++;
// переключаем состояние
connectionRecord.State = connectionRecord.Tcb.States.Assembling;
if (/*если не требуется механизм подтверждение*/)
// ...
else
{
// отправляем подтверждение
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
connectionRecord.WaitForPacketsTimer = new Timer(CheckByTimer, connectionRecord, connectionRecord.ShortTimerPeriod, -1);
}
}
Deeper into the code. Closing the connection on timeout
Timeout handling is an important part of Reliable UDP. Consider an example in which an intermediate node failed and data delivery in both directions became impossible.
Diagram for closing a connection by timeout:
As can be seen from the diagram, the sender's work timer starts immediately after sending a block of packets. This happens in the SendPacket method of the state SendingCycle.
Enabling the work timer (SendingCycle state):
public override void SendPacket(ReliableUdpConnectionRecord connectionRecord)
{
// отправляем блок пакетов
// ...
// перезапускаем таймер после отправки
connectionRecord.WaitForPacketsTimer.Change( connectionRecord.ShortTimerPeriod, -1 );
if ( connectionRecord.CloseWaitTimer != null )
connectionRecord.CloseWaitTimer.Change( -1, -1 );
}
The timer periods are set when the connection is created. The default ShortTimerPeriod is 5 seconds. In the example, it is set to 1,5 seconds.
For an incoming connection, the timer starts after receiving the last incoming data packet, this happens in the ReceivePacket method of the state assembly
Enabling the work timer (Assembling state):
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
// ...
// перезапускаем таймеры
connectionRecord.TimerSecondTry = false;
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
if (connectionRecord.CloseWaitTimer != null)
connectionRecord.CloseWaitTimer.Change(-1, -1);
// ...
}
No more packets arrived on the incoming connection while waiting for the working timer. The timer went off and called the ProcessPackets method, where the lost packets were found and redelivery requests were sent for the first time.
Sending redelivery requests (Assembling state):
public override void ProcessPackets(ReliableUdpConnectionRecord connectionRecord)
{
// ...
if (/*проверка на потерянные пакеты */)
{
// отправляем запросы на повторную доставку
// устанавливаем таймер во второй раз, для повторной попытки передачи
if (!connectionRecord.TimerSecondTry)
{
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
connectionRecord.TimerSecondTry = true;
return;
}
// если после двух попыток срабатываний WaitForPacketTimer
// не удалось получить пакеты - запускаем таймер завершения соединения
StartCloseWaitTimer(connectionRecord);
}
else if (/*пришел последний пакет и успешная проверка */)
{
// ...
StartCloseWaitTimer(connectionRecord);
}
// если ack на блок пакетов был потерян
else
{
if (!connectionRecord.TimerSecondTry)
{
// повторно отсылаем ack
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
connectionRecord.TimerSecondTry = true;
return;
}
// запускаем таймер завершения соединения
StartCloseWaitTimer(connectionRecord);
}
}
The TimerSecondTry variable is set to true. This variable is responsible for restarting the working timer.
On the sender's side, the working timer is also triggered and the last sent packet is resent.
Enabling connection close timer (SendingCycle state):
public override void ProcessPackets(ReliableUdpConnectionRecord connectionRecord)
{
// ...
// отправляем повторно последний пакет
// ...
// включаем таймер CloseWait – для ожидания восстановления соединения или его завершения
StartCloseWaitTimer(connectionRecord);
}
After that, the connection close timer starts in the outgoing connection.
ReliableUdpState.StartCloseWaitTimer:
protected void StartCloseWaitTimer(ReliableUdpConnectionRecord connectionRecord)
{
if (connectionRecord.CloseWaitTimer != null)
connectionRecord.CloseWaitTimer.Change(connectionRecord.LongTimerPeriod, -1);
else
connectionRecord.CloseWaitTimer = new Timer(DisposeByTimeout, connectionRecord, connectionRecord.LongTimerPeriod, -1);
}
The connection close timer timeout period is 30 seconds by default.
After a short time, the working timer on the recipient's side fires again, requests are sent again, after which the connection close timer starts for the incoming connection
When the close timers fire, all resources of both connection records are released. The sender reports the delivery failure to the upstream application (see Reliable UDP API).
Releasing connection record resources:
public void Dispose()
{
try
{
System.Threading.Monitor.Enter(this.LockerReceive);
}
finally
{
Interlocked.Increment(ref this.IsDone);
if (WaitForPacketsTimer != null)
{
WaitForPacketsTimer.Dispose();
}
if (CloseWaitTimer != null)
{
CloseWaitTimer.Dispose();
}
byte[] stream;
Tcb.IncomingStreams.TryRemove(Key, out stream);
stream = null;
Tcb.OutcomingStreams.TryRemove(Key, out stream);
stream = null;
System.Threading.Monitor.Exit(this.LockerReceive);
}
}
Deeper into the code. Restoring data transfer
Data transmission recovery diagram in case of packet loss:
As already discussed in closing the connection on timeout, when the working timer expires, the receiver will check for lost packets. In case of packet loss, a list of the number of packets that did not reach the recipient will be compiled. These numbers are entered into the LostPackets array of a specific connection, and requests for redelivery are sent.
Sending requests to redeliver packages (Assembling state):
public override void ProcessPackets(ReliableUdpConnectionRecord connectionRecord)
{
//...
if (!ReliableUdpStateTools.CheckForNoPacketLoss(connectionRecord, connectionRecord.IsLastPacketReceived != 0))
{
// есть потерянные пакеты, отсылаем запросы на них
foreach (int seqNum in connectionRecord.LostPackets)
{
if (seqNum != 0)
{
ReliableUdpStateTools.SendAskForLostPacket(connectionRecord, seqNum);
}
}
// ...
}
}
The sender will accept the redelivery request and send the missing packets. It is worth noting that at this moment the sender has already started the connection close timer and, when a request is received, it is reset.
Resending lost packets (SendingCycle state):
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
// ...
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
// сброс таймера закрытия соединения
if (connectionRecord.CloseWaitTimer != null)
connectionRecord.CloseWaitTimer.Change(-1, -1);
// ...
// это запрос на повторную передачу – отправляем требуемый пакет
else
ReliableUdpStateTools.SendPacket(connectionRecord, ReliableUdpStateTools.RetransmissionCreateUdpPayload(connectionRecord, header.PacketNumber));
}
The resent packet (packet #3 in the diagram) is received by the incoming connection. A check is made to see if the receive window is full and normal data transmission is restored.
Checking for hits in the receive window (Assembling state):
public override void ReceivePacket(ReliableUdpConnectionRecord connectionRecord, ReliableUdpHeader header, byte[] payload)
{
// ...
// увеличиваем счетчик пакетов
connectionRecord.PacketCounter++;
// записываем в массив управления окном текущий номер пакета
connectionRecord.WindowControlArray[header.PacketNumber - connectionRecord.WindowLowerBound] = header.PacketNumber;
// устанавливаем наибольший пришедший пакет
if (header.PacketNumber > connectionRecord.RcvCurrent)
connectionRecord.RcvCurrent = header.PacketNumber;
// перезапускам таймеры
connectionRecord.TimerSecondTry = false;
connectionRecord.WaitForPacketsTimer.Change(connectionRecord.ShortTimerPeriod, -1);
if (connectionRecord.CloseWaitTimer != null)
connectionRecord.CloseWaitTimer.Change(-1, -1);
// ...
// если нам пришли все пакеты окна, то сбрасываем счетчик
// и высылаем пакет подтверждение
else if (connectionRecord.PacketCounter == connectionRecord.WindowSize)
{
// сбрасываем счетчик.
connectionRecord.PacketCounter = 0;
// сдвинули окно передачи
connectionRecord.WindowLowerBound += connectionRecord.WindowSize;
// обнуление массива управления передачей
connectionRecord.WindowControlArray.Nullify();
ReliableUdpStateTools.SendAcknowledgePacket(connectionRecord);
}
// ...
}
Reliable UDP API
To interact with the data transfer protocol, there is an open Reliable Udp class, which is a wrapper over the transfer control block. Here are the most important members of the class:
public sealed class ReliableUdp : IDisposable
{
// получает локальную конечную точку
public IPEndPoint LocalEndpoint
// создает экземпляр ReliableUdp и запускает
// прослушивание входящих пакетов на указанном IP адресе
// и порту. Значение 0 для порта означает использование
// динамически выделенного порта
public ReliableUdp(IPAddress localAddress, int port = 0)
// подписка на получение входящих сообщений
public ReliableUdpSubscribeObject SubscribeOnMessages(ReliableUdpMessageCallback callback, ReliableUdpMessageTypes messageType = ReliableUdpMessageTypes.Any, IPEndPoint ipEndPoint = null)
// отписка от получения сообщений
public void Unsubscribe(ReliableUdpSubscribeObject subscribeObject)
// асинхронно отправить сообщение
// Примечание: совместимость с XP и Server 2003 не теряется, т.к. используется .NET Framework 4.0
public Task<bool> SendMessageAsync(ReliableUdpMessage reliableUdpMessage, IPEndPoint remoteEndPoint, CancellationToken cToken)
// начать асинхронную отправку сообщения
public IAsyncResult BeginSendMessage(ReliableUdpMessage reliableUdpMessage, IPEndPoint remoteEndPoint, AsyncCallback asyncCallback, Object state)
// получить результат асинхронной отправки
public bool EndSendMessage(IAsyncResult asyncResult)
// очистить ресурсы
public void Dispose()
}
Messages are received by subscription. Delegate signature for callback method:
public delegate void ReliableUdpMessageCallback( ReliableUdpMessage reliableUdpMessage, IPEndPoint remoteClient );Message:
public class ReliableUdpMessage
{
// тип сообщения, простое перечисление
public ReliableUdpMessageTypes Type { get; private set; }
// данные сообщения
public byte[] Body { get; private set; }
// если установлено в true – механизм подтверждения доставки будет отключен
// для передачи конкретного сообщения
public bool NoAsk { get; private set; }
}
To subscribe to a specific message type and/or a specific sender, two optional parameters are used: ReliableUdpMessageTypes messageType and IPEndPoint ipEndPoint.
Message types:
public enum ReliableUdpMessageTypes : short
{
// Любое
Any = 0,
// Запрос к STUN server
StunRequest = 1,
// Ответ от STUN server
StunResponse = 2,
// Передача файла
FileTransfer =3,
// ...
}
The message is sent asynchronously; for this, the protocol implements an asynchronous programming model:
public IAsyncResult BeginSendMessage(ReliableUdpMessage reliableUdpMessage, IPEndPoint remoteEndPoint, AsyncCallback asyncCallback, Object state)
The result of sending a message will be true - if the message successfully reached the recipient and false - if the connection was closed by timeout:
public bool EndSendMessage(IAsyncResult asyncResult)
Conclusion
Much has not been described in this article. Thread matching mechanisms, exception and error handling, implementation of asynchronous message sending methods. But the core of the protocol, the description of the logic for processing packets, establishing a connection, and handling timeouts, should be clear to you.
The demonstrated version of the reliable delivery protocol is robust and flexible enough to meet the previously defined requirements. But I want to add that the described implementation can be improved. For example, to increase throughput and dynamically change timer periods, mechanisms such as sliding window and RTT can be added to the protocol, it will also be useful to implement a mechanism for determining MTU between connection nodes (but only if large messages are sent).
Thank you for your attention, I look forward to your comments and comments.
PS For those who are interested in the details or just want to test the protocol, the link to the project on GitHube:
Useful links and articles
- TCP protocol specification: и
- UDP protocol specification: и
- Discussion of the RUDP protocol:
- Reliable Data Protocol: и
- A simple implementation of delivery confirmation over UDP:
- Article describing NAT traversal mechanisms:
- Implementation of the asynchronous programming model: и
- Porting the asynchronous programming model to the task-based asynchronous pattern (APM in TAP):
Update: Thank you и for the idea of adding a task to the interface. The compatibility of the library with old operating systems is not violated, because The 4th framework supports both XP and 2003 server.
Source: habr.com