Wednesday, 2 April 2008

Send send send

When sending messages that a larger than one TSDU in size multiple options start to appear, some options are tied to the network layer properties for optimum transmission efficiency, some more generic to simplify application development. The following chart lists the options:

The first and second option covers the basic simplified application layer high level function, pass one or a vector of application defined message buffers. OpenPGM will then segment those buffers to the TSDU size determined from the maximum TPDU and PGM header requirements.

A traditional scatter/gather IO vector can be used with the last call, pgm_transport_sendv3(), this provides a convenient mechanism to pass an application protocol header and payload separately without copy overhead.

The sendv2() pair provides an optimised mechanism of passing PGM payload size buffers which can be directly sent on the wire with pre-pended header.

Tuesday, 25 March 2008

Sudoku error correction

Forward error correction (FEC) is a method of adding extra information (redundancy) to a message so that if any part is lost the data can be reconstructed without re-requesting from the sender. In a network protocol this is advantageous when either there is a significant number of receivers, e.g. internet radio, or the communications link to the sender is slow or expensive, e.g. deep space probes.

As a terse example of FEC, if a message comprised of nine numbers 1-9, and we added eight redundant numbers we end up with something like a Sudoku board:

As per the rules of Sudoku, if some numbers were missing we could determine the lost numbers from the neighbours on the same line or box.

Reed-Solomon encoding creates a graph based on a polynomial function that each point matches a byte in the data stream, x is the location in the stream, y is the value. For example, in the polynomial graph below imagine every red point being a byte of information in a transmission group. The graph can be extended to include extra data points, here marked in green. These points are extra redundant information, called parity data. As the parity points follow the same line it is possible to use these points to re-construct the original graph polynomial function. Once this function is calculated any missing real data points can be recovered by substituting the x location values.

The benefit over convential selective "Automatic Repeat reQuest" (ARQ), is that one parity point can recover any one lost original data point. The disadvantage is the extra time to perform the calculations, however in hardware systems these calculations can be implemented directly in hardware using a slightly different form called BCH Code.

Both forms of code are popular in software projects, notable examples include Luigi Rizzo's RMDP, Peter Brian Clements PAR Parity Archives, and Phil Karn's DSP and FEC library (e.g. Linux software modems). However the results are in different forms, Vandermonde calculations produce vector space coefficients, and BCH's Linear Shift Feedback Register produces polynomial space coefficients. Microsoft's PGM implementation uses Rizzo's implementation, and so for initial compatibility OpenPGM will use a Vandermonde matrix calculation.

Friday, 11 January 2008

Network system testing

Testing is always helpful in development, large projects often undergo testing at different levels: unit testing, integration testing, and performance testing. With a multicast network protocol none of these cover actual testing of the protocol between hosts, so we create a new method: network system testing. We want to test the OpenPGM stack and the API it provides to the application developer as pictured below on the top right.

Some tests need an external source to drive functionality in the stack, the Simulator is used for this task. In order to verify the packets sent out by the stack are correct with have the Monitor.

In order to build an extensive set of tests that can be reliably re-run we want to use automated testing. This means some form of scripting of all three systems and synchronisation between how each is run. The Tester host runs a script that remotely controls and receives feedback from each of the three test systems. All communication is via stdin and stdout, including the monitor with is a glorified version of tcpdump but shows PGM packets in JSON form.

To make everything platform agnostic and to ease development all scripts are in Perl, modules can be used to SSH into remote hosts, perform high resolution timing, process JSON representation of PGM packets, etc.