[Udpcast] Reliable multicast protocol

Saikrishna Dasari sai_thesis at yahoo.com
Sun Dec 18 17:43:54 CET 2005


Guofu,
  Following is what I got from  Alain long time ago.  Hope this helps.
   
  Thanks,
  Sai
   
  *****************************************************************
  There are no format documents yet about the protocol. The protocol is
not based on an RFC, but is homegrown specifically for udpcast.

Updcast uses two UDP port numbers, 9000 and 9001.

The receiver listens on 9000 (portbase), the sender on 9001 
(portbase+1)

The protocol runs as follows:

1. When the sender starts up, it broadcast a CMD_HELLO message to the
local network broadcast address

2. When the receiver starts up, or whenever it receives a CMD_HELLO
message, it sends a CMD_CONNECT_REQ address. If the CMD_CONNECT_REQ is
sent at startup, it is broadcast; else it is sent to the server's
address (as deducted from the CMD_HELLO message).

This allows the rendez-vous to be established no matter whether the
client or the server first starts up. Additionnally, the server can be
set up to periodically send its CMD_HELLO message (interesting for
asynchronous mode, see below).


3. The server replies to each CMD_CONNECT_REQ with a CMD_CONNECT_REPLY
(unicasted to the client who sent the CMD_CONNECT_REQ). The connect
reply contains the client number that the server assigned to that
client (clNr), the block size (size of packed), a bitmask of
capabilities, and the multicast address to be used for the actual data
transfer transfer.

At this stage, server and client know about each other, and are ready
to start the transfer. For convenience, the transfer may either be
started at the server, or at any participating client.

4. If transfer start is initiated by a client, it sends the server a
CMD_GO message.

5. If the transfer start is initiated by the server (or, after
reception of the CMD_GO message from a client), the server starts
transfering data by sending CMD_DATA packets. The reception of the
first CMD_DATA packet is a signal to all clients that now the
rendez-vous phase is over, and that the transfer has started.

The data is subdivided into slices, which are themselves subdivided
into stripes (only in FEC mode), which are subdivided in network
packets, which are made up of bytes.

A CMD_DATA packet contains the slice number (sliceNo), the block
number within that slice (blockNo), and the total number of bytes in
the slice, and then the data itself.

After each slice has been transmitted, lost packets are handled.

In FEC mode, lost packets are recovered by the client by using the
error correction packets included in each slice.

A CMD_FEC packet contains the number of stripes in the slice, the
slice number, the block number, and the number of bytes.


In non-FEC mode, the server asks each client to acknowledge at the end
of the slice (CMD_REQACK). The CMD_REQACK contains the identifier of
the slice to be acknowleged (sliceNo), the number of bytes in that
slice (bytes), and a retransmission counter. The clients reply to the
CMD_REQACK either with a CMD_OK (if they received everything) or with
a CMD_RETRANSMIT (if packets were missed). Both the CMD_OK and
CMD_RETRANSMIT message contain the sliceNo. The CMD_RETRANSMIT message
contains also a bitmap of the missed packets, and the retransmit id.

In response the CMD_RETRANSMIT messages, the server will retransmit
packets that have been missed by at least one client, increments the
rxmit counter and then send another CMD_REQACK. The rxmit counter is
used to discard late CMD_RETRANSMIT messages: indeed, after a round of
retransmission, CMD_RETRANSMIT messages from the previous round should
be ignored, or else the server may resend packets that have been
received in this round.

Clients may leave a transmission by sending a CMD_DISCONNECT. Sending
the CMD_DISCONNECT is important, or else the server will needlessly
wait for the acknowledgments of these clients. However, if a client
crashes without sending a CMD_DISCONNECT, the server has a timeout to
detect this situation, and continue with the other clients ("The
client #n has been dropped by the server").

When all clients have received all packets (i.e. all clients have send
a CMD_OK for that slice), the sender moves on to the next slice, until
end of file is reached. The server signals end of transfer by sending
a slice of zero bytes.

Including slice size in every packet, and number of stripes in every
FEC packet may seem redundant. However, this is needed in order to
make the protocol robust in cases of packet loss: if the number of
bytes was only in the first or in the last packet, then the loss of
that packet would make it hard to recover, because not only the data
was lost, but also the meta-data needed to reconstruct that
slice. This is especially relevant in FEC mode.

FEC mode is intended for unidirectional (asynchronous mode). In this
mode, there are no acknowledgments, and no retransmissions. This is
intended for situations where no receiver-to-sender communication is
possible, or where the latency of such a communication would be
prohibitively high, such as multicast over satellite.

The server sends (one or several) CMD_HELLO which includes the
multicast address it intends to use, and then starts with the
data. Each slice not only contains the data, but also a configurable
number of redundant "error correction" packets.

FEC mode uses an algorithm based on Vandermonde matrices to
recalculate the contents of any lost packets. The algorithm is chosen
such that all k data packets may be restored as long as the receiver
has gotten at least k packets (be it data or FEC). For example, with
k-3 data packets, and 3 FEC packets, all k data packets may be
reconstructed. K is a parameter of the algorithm, and the higher the
value for k, the more computation intensive the algorithm
is. Moreover, values of k greater than 128 are not supported. For that
reason, each slice (which may be up to 1024 packets) is subdivided in
several stripes (of at most 128 packets), which are interleaved
(i.e. first comes 1st packet of 1st stripe, than 1st packet of 2nd
stripe, ..., then 1st packet of last stripe, than 2nd packet of 1st
stripe, etc.) That way a burst loss of packets (for instance, 6
packets in a row) won't overly impact one stripe but will rather be
spread out among several. Indeed, if udp-sender has been set up to
include l redundant packets per stripe, it must be avoided at all cost
that more than l packets are lost per stripe, or otherwise the loss in
uncrecoverable.

Additional complications in the protocol arise from the fact that a
first version of the protocol used the native byte ordering from Intel
processors, rather than use the network byte order. This made udpcast
unportable to non-PC architectures. This was changed two years ago;
however in order to stay compatible with older versions, the receiver
and sender are able to detect that packets with the "wrong" byte order
have been received, and are able to correct for that: if the message
code (CMD_*) doesn't make sense in network byte order, udpcast tries
to interpret it in Intel byte order, and if that matches a known code,
the packet is byte-swapped.


Regards,

Alain



__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lll.lgl.lu/pipermail/udpcast/attachments/20051218/62558b01/attachment.htm 


More information about the Udpcast mailing list