Algorithms

This page will summarize some details about the algorithms used in lnphost.

Detecting and avoiding collisions

All transceivers within a room send on the same infrared carrier frequency. This makes it possible for collisions to occur: whenever two senders are active at the same time, their signals will interfere and the receiver is unable to distinguish between both signals. It is a major design goal to avoid collisions as good as possible by controlling access to the medium. Two simple rules describe this mechanism, they can also be found in the Ethernet specification where they form the base of the CSMA/CD collision detection/avoidance system.

No transceiver is allowed to send while another one is sending (collision avoidance).
Should two stations start to send at the same time, they must be able to detect this by listening to their own signal. If this condition occurs, both senders must interrupt the transmission and retry after a random pause. (collision detection).

BrickOS implements these rules inside its transmitter code.

If the RCX receives a byte, a timer is reset to its starting value from where it counts down towards zero. All transmissions are blocked as long as the timer has a non-zero value. The starting value is chosen large enough so that at least two bytes could be transmitting during the time the timer needs to reach zero. Transmissions from other stations are protected by this mechanism.
To detect collisions during a transmission the RCX must receive and verify the echo from every sent byte. After a complete byte has left the sender, brickOS should be able to read the just received byte which must be identical to the byte that was send just before. If they are not, no byte has been received at all or any other type of error has happened, it is likely that a collision has occurred. BrickOS will interrupt the transmission in this case and block the transceiver for a random amount of time. A practical side effect of this algorithm is that the echo of packages can reliably be removed from the incoming data stream.

The algorithms for collision detection and avoidance described above can only work if they have full control over the timing of the transceiver. Delays between sending a byte to the transceiver and the actual transmission and between reception of the infrared signal and the byte reaching the program must be low. The maximum duration is the time it takes to transmit a single byte. Much longer delays make it impossible for the algorithms to work reliably. In the RCX this is not a problem because no buffers are used between the brickOS and the serial port.

Almost every desktop PC has serial ports with enabled FIFOs that can cause delays up to 12 times the time it takes to send a byte which is by far too long to get collision avoidance to work. An incoming transmission might have started to fill the FIFO buffer before the application is able to see the first byte, making it believe that it is free to send. Echo removal is impossible because of similar problems. The application cannot construct a temporal relationship between sent and received bytes.

The consequence is that collision avoidance cannot be implemented on most platforms. lnpd tries to do it and fails. Under Linux it is possible to disable the serial port FIFOs by downgrading the driver to the 16450 using setserial. On other platforms this is impossible (Solaris) or requires kernel patches (BSD), so it is better not to use these algorithms at all. The higher communication layers can take care of the problems by realizing temporal access control and confirmations for received packets.

Heuristic packet recognition

All received bytes will be collected by lnphost inside a buffer until a valid packet has been assembled. The decision if a complete packet is located inside the buffer is done by the following algorithm.

The receiver continuously queries the tower for new bytes. If one has been received, it will be transfered to the buffer. If this is not the case within a fixed timeout, a previously started packet must be complete by now or will be rejected.
In both cases the packet detector takes over. It calls helper functions to decide if a valid packet is located at the beginning of the buffer (one function for every supported protocol). The functions will return YES, NO or MAYBE. The functions may use the information if a timeout has occurred as this means that no additional bytes will arrive.
If the function replies YES, the packet will be processed and removed from the buffer.
If the answer is NO, the first byte is deleted from the buffer and the test will be repeated with the remaining data.
In all other cases (MAYBE) the receiver must wait for further bytes or a timeout.

It is fairly easy to detect a correct brickOS packet. This is done by checking the header, the availability of the payload and the checksum at the end. Lego packets need more work, because their length is generally not known. But the fact, that every packet starts with 0x55, followed by byte/complement pairs, helps a lot in this case. The algorithm expects a lego packet to start with a valid header and adds byte pairs to it until an invalid pair is detected or the receiver times out. The last valid pair will be interpreted as a checksum and is used to verify the whole packet. The byte 0x55 will be used as a packet delimiter.

The detection heuristic will work fine in most cases, even in scenarios with mixed packet types. But it is not perfect, in some rare cases lego packets might not be detected correctly.