C-UDP

2. Cyclic User Datagram Protocol

2.1. Description

Continous media (audio and video) is embedded in everyone's life in our days. The networks are also used by everyone in all parts of the world. For this, efficient communication is needed. TCP is most widely used today for its safety and liveness. UDP is not so reliable as some packets are lost and never retrieved. However a new protocol, a hybrid between TCP and UDP was specified by Brian C. Smith ('94).

The media servers are usually built in a way that server clients in a round-robin or cyclic scheduling [SJ93, R93]. They read some data from the disk and then serve each client over the network. The next service time makes the server to read the next chunk of data and again serve the clients. The transmission of the first chunk must end before the next one starts. This is basically how UDP works. The user experiences then the loss of the network as annoying dropouts in video or "pops" in audio. In Mpeg encoding however, certain frames are encoded independent of other frames (I-frames) while other are encoded as differences from other frames (P-frames and B-frames). If one of these reference frames is lost the ones based on it cannot be decoded at all. So it would be nice that the transmission protocol has some type of prioritizing the different frames, making an I-frame for example more important than P-frames or B-frames. This is exactly what C-UDP does. Not only has this priority feature different from normal UDP, but has also guarantee of transmission, as does TCP. Details follow.

C-UDP priority feature makes every packet priority proportional to the probability of successful packet delivery. The C-UDP implements this feature as follows:

Every cycle the to-be-transmitted chunk of data is fragmented into packets, every packet is indexed with a header for sequencing and loss detection and then placed in a packetQueue. The priority feature lies in this queue. High-priority packets are placed at the front of the queue, whereas low-priority packets are placed at its rear. Every packet has a label of unsent while in the queue and the transfer process for the respective chunk has not yet begun. After the transfer proceeds, the Sender marks all packets in the packetQueue as sent. Then the Sender waits, T time, until sending the next chunk. This waiting time is calculated so that transmitted bandwidth matches the estimated network bandwidth.

T = numSent / estBW

where numSent is the number of bytes sent in the previous burst. The calculation of estBW is detailed in the paper on CUDP. If a packet is lost then the Receiver can infer this from the headers of all the other packets and automatically sends an ARQ (automatic repeat request) to the Sender , which then resens the missing packet. The ARQ contains the packetID and the burstID in which the packet should have been according to the headers of the other packets in that burst. When an ARQ reaches the Sender, it updated the packetQueue by marking the requested packets as unsent. So this way the Sender will send them in the next burst. So for each non-sequential packet which the Receiver gets it will trigger an ARQ, which will then be filtered out by its burstID. This way redundant ARQs will not be processed.

The next picture shows an overview of the transmission sequence :

To distinguish between a lost packet and the end of transmission a special packet called EOC (end-of-cycle) is used. These packets contain no data and are identified by the Receiver through a special bit in the header. An EOC is sent by the Receiver when all packets in the packetQueue have been marked with the sent flag, and after that, at intervals of 100 milliseconds. When the Receiver gets an EOC, it sends an ARQ with all packets missing in the last cycle. When for example the last packet in a burst is lost, an EOC packet makes it clear of that for the Receiver.

Figure 1 depicts a sample transmission consisting of 5 packets. The tables represent the packetQueue at the specified timesteps. Timesteps are also indicated in the transmission sequence above the tables. First it's easy to see that at T0 in the first burst b1, packet p1 is lost and then between T2 and T3 and ARQ about this is received. Again in the next timestep T1, packet p3 is lost and an ARQ requesting packet p3 is then received between T4 and T5. Th thirs burst arrives successfully as does the last one with the EOC packet. So normally if no loss would occur there would be just 3 bursts but because two packets were lost, summing to one burst (as a burst has 2 packets) then an additional burst is needed to complete the transmission. This is not the case for TCP, as the position of the packet in the burst would be critical in determining the number of packets to be resent.

As stated by the author:

"CUDP gives high priority media units a better chance of delivery because, in the event of packet loss, they get more chances for retransmission than units later in the queue. Assuming each packet has probability α< 1 of being lost, then the probability of a packet being lost after k delivery attempts is . Since k is approximately the cycle length divided by the round trip time, high priority packets can be given arbitrarily high probability of delivery by making the cycle lengths large."

There is also a method for estimating the bandwidth but is not relevant for this approach. For more information see the paper on C-UDP: [S94].

2.2. Implementation

The implementation is oriented on knowledge and belief and how visualising the transmission could help understand better the process behind it. So a lot of features are left out because they lack relevance for this approach. The same as in the Stulp & Verbrugge paper on visualising the TCP, an asynchronous communication is considered, where S and R perform actions when they are scheduled, as proposed by Halpern and Zuck. The model also deals with an alphabet consisting of letters of the Roman alphabet and has an infinite tape. The implementation just deals with reordering and loss, which can be modified from the interface. Mutation and insertion are not included but they will be discussed later. The algorithm in pseudo-code is given below:

Sender's algorithm

//this is the timer specified in C-UDP description paper representing the time between bursts
timer = 0

// sender then starts reading from the tape
while sender has not reached the end of the tape do

//store the time when the first packet is sent
if timer == 0
store current_time in timer;

//if T time has passed since last burst send next burst; current_time is the current system time, as above
if (timer + T < current_time)

//set the sent flag of the next burst_size packets as true

set sent_flag true

//call procedure; see below
send_next_burst

    //if an arq packet is received then get the content of the packet and set the sent flag as false
    if (arq received)

        set the sent_flag of the arq packet content as false

//this procedure loops through already send packets and checks if an arq packet was received for any of them, if yes it sends the packet, until burst_size //packets have been sent; also resets the timer when burst_size packets have been sent

procedure send_next_burst

    count = 0
    loop through already sent packets
        check if the sent_flag is set
        if no then
                send
                and increment count
        if count equals burst_size

timer = 0

break

----------------------------------------------------------------------------------------------------------------------------------------

Receiver's algorithm

//this is a timer for the receiver to know how much time it should wait after the first packet was received, for sending arqs
timer = 0;

//boolean var to store when a first packet from a burst has arrived
received_first = false;

//this is to hold supposedly the last index to be received in a burst ; supposedly because packets may rearrange on the way
current_end = burst_size;

//main loop
while true do

//if a packet is received and received_first is false it means it's a first packet from a burst; and so set the timer to current system time; also set received_first //true as a first packet just arrived

if received packet and received_first == false

timer = current_time

received_first = true

//wait T time after the first packet was received until starting sending arqs

while timer + T < current time

//reset the timer as we are starting sending now
timer = 0

//loop through received packets starting from 0, because even if an arq was sent before, maybe it was lost; so arqs will be sent until the packet is received

        loop through received packets from 0 to current_end
            if packet is null then send arq
        current_end = current_end + burst_size
        received_first = false

//there is also the case when no messages arrive anymore but arqs still need to be sent so periodically a trigger is set to send arqs until all packets arrive (not shown here)

As can be seen the implementation is quite simple and even though many features of the transmission have been left out, the property of prioritizing packets is embedded in the algorithm.

The protocol, I believe takes the sliding windows of TCP to the extremes, in the following sense : when an acknowledgement is received in TCP implies that every other packet with a smaller index was surely received; in CUDP it implies that every other packet, even with a bigger index was received, but obviously smaller than the current index of the sender. I think it is more intuitive for the Receiver to send the least packets possible, and this can be achieved in this way. If the number of packets lost would be bigger than the number of packets received then TCP would be probably more fit. But in the case where much more packets arrive then they are lost (and which I think is the normal case) CUDP is more efficient with resepect to the number of packets sent by the Receiver and implicitely by the Sender. Also the priority feature is of big importance for a communication protocol, a feature which TCP does not have.