[ Home | Plans | Meetings | Members | Search | Papers | Links | CyberWear | LocoSoft]
1. Description of algorithm used
2. Packet formats and header fields
3. Establishing a connection link
4. Data transfer and link maintenance
5. Terminating a connection
Description Of The Algorithm Used
The transmission algorithm uses a simple stop-and-wait algorithm to ensure reliable delivery of packets. Additionally, the use of checksum fields in the header helps determine whether the packet obtained on the receiver side has not been corrupted whilst in transit. Timeouts are used in the protocol program to determine whether a certain length of time has elapsed without an event happening. If the receiver receives data and is not happy with it for any reason, such as incorrect checksum, incorrect preamble (see later - data transfer), incorrect sequence number or length, the packet will be discarded. Such an occurrence will result in the sender not receiving an acknowledgement for that packet before the timeout expires. Hence, the packet will be retransmitted.
Since the Footbridge link used for this protocol is only half-duplex, the protocol has to emulate full-duplex for the over-lying layers. Although we can't send two messages at the same time, we can interleave their packets - effectively time-slicing the link. With the simple S&W algorithm, the sender waits an acknowledgement for its last data packet. The protocol used puts the acknoledgement either in a small system sized packet or inside the header of a data packet being sent from the other side (the receiver). Therefore, if the receiver has data to send in the middle of a transmission from the sender, it may both acknowledge the sender's data and send its data at the same time, giving the impresseion of a full-duplex link with minimal latency.
N.B. This timeline has time running down the page
The picture above shows the example progress of a three-packet message attempting transmission. The vertical red arrows on the sender side indicate the timeout period, which may be set to any length e.g. 200 ms. The timeout starts counting as soon as the packet is transmitted - if the correct acknowledgement is not received within the set time, the sender will timeout and retransmit the packet.
The example show both a data packet being received with incorrect checksum/sequence number and hence no acknowledgement, a data packet being lost in transit and a data packet acknowledgement being lost in transit. The stop-and-wait algorithm handles all these events.
As is discussed in the "Establishing a connection link" section, to ensure only one device may talk at a time once the link has been negotiated (for a half duplex line), the two devices are either labelled "primary" or "secondary".
Packet Formats & Header Fields
The following section describes in detail the format of the packets that can be transmitted by the protocol. Firstly, there are two types of packets that are used:
1. Data packets - Used to transmit data contained within the packet payload
2. System packets - Used by the protocol to implement operations and actions
Both types of packet have fixed length, set in the protocol source code. Data packets have length set to PACKET_SIZE bytes, and system packets have a length of SYS_PACKET_SIZE bytes. System packets are just the standard header, without any payload part, which contains all the information required for the receiver to decide what to do. Note one data length packet doubles up as a data acknowledgement packet.
The layout of both types of packets are shown below along with a key for the field names:
|Field:||Description:||Current Size in Bytes: (constant name in brackets)|
|FUNC||- Packet function (see later for possibilities)||1 (FUNC_LEN)|
|DLEN||- Useful data length in packet payload (zero for non data packets)||1 (DLEN_LEN)|
|Source ID||- ID of packet sender||8 (ID_LEN)|
|Seq Num||- Sequence number of packet (position in message for data packets)||1 (SEQNUM_LEN)|
|Seq Ack||- Sequence number of packet to be Acknowledged (if any)||1 (SEQACK_LEN)|
|Tot Num||- Total number of packets in message (only for data packets)||3 (TOTNUM_LEN)|
|CS1||- 1st Checksum value for packet||1 (CS1_LEN)|
|CS2||- Second checksum value||1 (CS2_LEN)|
|Payload||- The data is contained within this field (omitted for non-data packets)||83 (DATA_SIZE)|
The FUNC field is used by the receiver to establish what type the incoming packet is
according to the below type:
|DATA_PACKET||This packet is just contains data for the current incoming message|
|DATA_ACK_COMING||This packet contains data as well as an acknowledgement for the last data packet received|
|DATA_ACK||This is just an acknowledgement for the last data packet received|
|SYS_POLL||A system poll message used to test the connection status|
|SYS_POLL_ACK||The acknowledgement to a SYS_POLL packet|
The FUNC type also dictates to the receiver what size the incoming
packet is i.e. PACKET_SIZE for the packets with data payloads, and SYS_PACKET_SIZE for the
The DLEN field is used in data packets only to tell the receiver how much of the payload is useful data - for full payloads this value will equal the maximum data payload size DATA_SIZE. Normally the final packet of a message will not be completely filled, only partly used.
For data packets, it is necessary to store the sequence number of the packet so to avoid packet duplication on the receiving end. This number only currently occupies 1 byte and is simply the current packet number "mod" with 255. The receiving end can therefore check whether a packet is the one expected or not. The next field "SEQACK" is used for data acknowledgements, and contains the same value as the last received packet so the packet sender can proceed sending the next one. For one packet messages, the sequence number simply can not be 1. This is because a lost acknowledgement (but received packet) will mean the packet will be retransmitted and the receiver cannot distinguish between them. To cure this, the protocol uses a sequence byte that is toggled between 0 and 1 on consecutive one-packet messages. Hence, the sequence number field may contain 0 occasionally instead of using the sequence number counter. The total number of packets is still set to 1 however.
The TOTNUM field has currently three bytes representing the total number of packets in the message giving a maximum packet range of approx 256 to the power of 3.
The checksum fields give a reliable means of detetcting data corruption.
From the above field sizes in their respective headers, the packet sizes can be calculated thus:
|Size In Bytes: (constant name in brackets)|
|Data Packets||100 (PACKET_SIZE)|
|Other packets (system)||17 (SYS_PACKET_SIZE)|
N.B. It is worth stating now that the byte value 255 is reserved for the networking protocol and should not be permitted in either a system packet or a data packet - data payloads should be already encoded with base64 to ensure no NULLS etc. But DLEN will never be longer than DATA_SIZE (around 100 bytes), checksums of 255 are automatically changed to 244, sequence number and total packet number fields have a maximum value of 244 before wrapping to zero. The ID must also not contain bytes of 255 - 0->254 are permitted like any other header field.
Establishing a connection link
Initially, no viable connection exists between two devices. However,
certain devices will be able to actively seek out another device by sending SYS_POLL
message into the void and listening for a SYS_POLL_ACK reply - when one is received the
device knows another device is now within range and ready to talk to it. It does not
matter whether both devices are sending out SYS_POLL message over a half-duplex link,
since they both operate random timeouts and so one will always get through after a couple
of tries before the receiver has a chance to send its poll message.
Certain devices will be set to actively seek another device - the decision will be simply based on available power. CyberJackets have much more power than a commonly used handheld display for instance - so CyberJackets will send out poll messages, whereas handheld display and other small peripherals will only listen for them - of course on receipt of a SYS_POLL message the passive device will reply with a SYS_POLL_ACK.
With the fact that the initial poll messages have been exchanged and the two devices in the link know who the other is from the ID in the system packet header, both sides can make a set of decisions. The link must establish which one of the devices is to become the primary and which the secondary. This is done by examining the ID number both sent over from the other device and its own ID. These unique identifiers also represent which type of device the device is - say a CyberJacket, or a handheld, or an InfoPost etc. Again using the power issue and also considering the major flow direction of data:
|A Device:||Has Higher "Value" Than A:|
Since a device will know what kind of device the other
is, a device can set itself to be a primary or secondary depending on whether it has a
higher "value" or not. If two CyberJackets are trying to connect, both are equal
devices - in this instance, the one with the higher ID number becomes primary.
Whenever a link fails, both sides of the link will reinitialise itself to its original settings and carry on either listening or polling.
With the link established, the overlying protocol layer
(in our case the Footbridge Manager) is informed that a link has been established and so
the relevant services may kick in and the data transfer may begin - if no data is
currently available to be transmitted, the primary device will send a SYS_POLL message
instead to keep the secondary device informed that the link is still up as explained in
the next section.
Data transfer and link maintenance
With the communication link established, it is up to the network layer to determine the link status at any point in time and keep the Footbridge manager layer above it informed. If one side of the communication receives data, it knows the link is still usable and resets its internal timer record as to when the last contact was made. During data transfer, for instance, the sender will retry a set number of times to transmit a packet successfully before giving up knowing no acknowledgement has been received. However, when there is no data to transmit i.e. when the link is idle, how does the protocol establish whether the link is still viable? The answer is that when the primary device in the link is in the READY state, it will send every so often a SYS_POLL message to the secondary device. The secondary device, on receiving this system packet correctly will reset its internal "link-down" timeout to zero and transmit a SYS_POLL_ACK packet back to the primary device. Now, the primary device knows the secondary is still in range and waiting transmission. If the secondary device wants to send data to the primary at any point, it must wait for the SYS_POLL message to come to it, whereupon it may send data packets to the primary device in place of a SYS_POLL_ACK, since all the primary wants to hear is data still coming from the other side.
When a device has any data to send across the Footbridge link (this
includes system packets), it first sends a preamble DATA_COMING. This is simply a reserved
byte value of 255 - hence no data in the packet itself may have this value (see Packet
format section above). Immediately after this, the sender proceeds to send the actual
packet. The receiver, who is polling its communication port will detect the preamble,
check it is the preamble expected, and then read in the packet. If the initial data coming
in does not constitute a valid preamble, the receiver has no choice but to completely
ignore the rest of the incoming data. An example of such an event would by burst noise or
the initial part of a packet being lost/destroyed, so the receiver can easily establish
whether was it has got is valid.
Below is a diagrammatic representation of the sequence of data transmissions for a data/acknowledgement event:
The protocol will ignore any data coming in without the DATA_COMING preamble preceding it, and it will read any data after the preamble assuming it to be viable.
Terminating a connection
The protocol has ways of detected whether the communication link has gone down or out of range - a primary device who is either sending SYS_POLL or data packets will simply not receive any acknowledgements back from the secondary device - if the acknowledgement packets do arrive but are scrambled and corrupted, a device will simply throw them away and not use them to decide if the link is still up. A secondary device will not hear any SYS_POLL message come from the primary or, if it was transmitting, not receive a valid acknowledgement. Hence, both sides will either attempt to retransmit the packet or wait another length of time listening for a valid packet. If none are received after RETRY_NUM attempts (around 8 say), the link is declared DOWN and the devices must destroy their out/in message table and return to either polling or listening for a link. If a valid packet is received within the RETRY_NUM attempts the link is still UP and the device may proceed as normal with its timeout counter set back to zero.
The material displayed is provided 'as is' and is subject to use restrictions.
For problems or questions regarding this web contact Cliff Randell.
Last updated: January 14, 2000.
ęCopyright Hewlett-Packard 1997-2000.