March 2024 - This site, and Kamaelia are being updated. There is significant work needed, and PRs are welcome.

Protocol: Simple Reliable Multicast

This page describes a simple protocol overlaid on top of multicast to give a thin layer of reliability. It is notintended to replace existing reliable multicast protocols, but to show how they can be developed and integrated into a Kamaelia based system. For the basis of this discussion it is referred to here generally as SRM - simply short for "Simple Reliable Multicast".

Background

Multicast is an unreliable protocol. It is also rarely implemented over the wide area internet, despite its age and only slightly more often inside company networks. However where it is available - such as the BBC's trial multicast peering system used for the 2004 Olympics and others - it provides the benefit that broadcast television can be made available over the internet. (Note: multicast is not broadcast - the "multi" part denotes that anyone may send and receive, not just one source)

As well as a lack of deployment multicast has a number of specific characteristics that cause problems for any protocol you wish to send over multicast:

As a result we need a system that can essentially perform a "as good as it can" attempt at cleaning up the resulting "mess" we are left with. This might seem strong words, but even over a wireless link inside the home sending multicast data from one room to another can result in all 3 of these issues interfering heavily with any higher level protocol.

Example Setup

Take Example 4 - a simple multicast system for example. This contains a system version with the following two pipelines:

Server:

pipeline(

)

Client:

pipeline(

)

(I've removed the calls to these pipelines' .activate() and .run() methods)

Running these together on a single host (eg via the MulticastStreamingSystem.py script provided) results in the single file being transmitted, and recieved and played back. However if we split this across two scripts, run one on a server machine, one on a client and place an unreliable network in between (such as an 802.11b network), then we instantly hit audio problems due to out of order delivery and data loss.

Protocol Design

The protocol does the following:

The protocol will not dothe following:

Usage

The directory containing Example 4 now also contains an SRM based version called MulticastStreamingSystem_SRM.py. The client and server pipelines now looks like this: (additions in bold blue)

Client:

pipeline(

)

Server:

pipeline(

)

Underlying Approach

The underlying appraoch is as follows:

On the way out from the server:

Annotate the chunks of data to send with a sequence number

Create frames containing the data, sequence numbers and lengths

Provide a means of resynchronisingthe data stream by adding in restart markers. The data between these markers generally form chunks.

Limit the resulting data's sizein terms of actual data blocks sent, to reduce the likelihood that they will get thrown away by the multicast layer (this is done outside the actual SRM components because the SRM components don't know where the data they create is being sent).

On the way into the client:

Details

Unsuprisingly this all maps to a collection of components, and it's simplest to show the 2 pipelines from the code:

Sending:

def SRM_Sender():

return pipeline(

)

Receiving:

def SRM_Receiver():

return pipeline(

)

For those interested a full test suite for framing and data chunking can be found in Kamaelia.Protocol.test , and also Kamaelia.Data.Escape (along with tests). A frame is created as follows:

Note that this allows for a variable length header terminated by a carriage return, with the header consisting of two numbers - one is a sequence number, the other is a length. Both are expressed as strings and are expected to be parsed. The data is passed through unchanged by the Framer.

Chunking is essentially the same process. The chunker simply takes data (usually frames, but it doesn't not require frames), does the following:

Inserts a restart marker - defaulting to "XXXXXXXXXXXXXXXXXXXXXXXX" (24 'X' characters) into the data stream. The marker is considered to precede a data chunk, hence for a specific data stream it will start with this marker, but not terminate with it.

The contents of chunks (ie the original data stream) is escaped such that the restart marker cannot exist accidentally. The approach taken is as follows:

Escape any % charcter as %25 before performing any other escaping

For every character in the restart marker

Unescaping follows the same approach, but in reverse order.

Implementation

Initial implementation was by Tom Gibson, a vacation trainee at BBC R&D during the Summer of 2005. The robustness of the algorithm was subsequently increased by Michael, up to the limits described above.

The implementation can be found in the following files & components:

Kamaelia.Protocol.SimpleReliableMulticast:

Annotator

RecoverOrder

Two component factories:

Kamaelia.Protocol.Framing:

Kamaelia.Data.Escape - contains two functions used by DataChunker& DataDeChunker:

Boundary Issues

Relationship to Other Reliable Multicast Work

Making multicast reliable is not a new idea. This protocol is simply designed to be "the simplest thing that can possibly work", and that's it. Essentially it's provided to allow a basis for testing other reliable multicast delivery systems, and to show how they can be layered into existing pipelines with relative ease. It is of course immediately useful in it's own right.