A Preliminary Specification Of A Data Link Protocol

This data link protocol provides a reliable connection between two hosts. The hosts are identified by an IP and port number (i.e., this protocol uses the UDP protocol to deliver the frames). A protocol is specified by the services it provides and the messages that are exchanged by the two entities that implement the protocol. The messages are specified by their format, and how they are exchanged (i.e., the receipt of message A implies replying with message B). Additionally, the important state of the software that implements the protocol can also be part of its specification.

This protocol is specified by first describing the services it provides and the interface to those services. The main state elements maintained by the protocol entity is then discussed, followed by a description of the messages (frames) that are exchanged to implement the services.

Data Link Services

The main service provided is guaranteed data deliver. The ability to reset the link is also provided to handle initialization of the link and error recover.

The interface is currently not specified, however you are free to come up with your own.

Data Link State

The main state of a link is given by two variables, one that keeps track of the sequence number of the next outgoing data frame, and the second the keeps track of the expected sequence number of the next incoming data frame. These variables are referred to as the NextOutgoingFrame and the NextFrameExpected. In order for the link state to be meaningful, the protocol entities handling the connection must exist. When the entities are created, the NextOutgoingFrame and NextFrameExpected are initially set to 0.

The entity that implements the protocol can also be in a VALID or INVALID state. The entity is in a VALID state when it is first created, and remains in the VALID state as long as no errors occur. An error occurs when an attempt to reset the link fails or an attempt to transfer data fails. The entity's state is changed to VALID if an attempt to reset the link succeeds. When the entity is in the INVALID state, only the reset link service request is honoured.

The protocol entities will also maintain additional state, but that state is only relevant to the implementation and not the specification.

Frame Format

Byte Offset	Field Name	Description
0	Destination	the IP number and port number of the destination host
6	Source	the IP number and port number of the source host
12	Flag	a byte indicate the contents of the frame, see below
13	SequenceNo	an 8-bit sequence number for the current frame
14	AcknowledgementNo	an 8-bit acknowledgement number
15	DataLen	the data length in bytes is given by a 16-bit unsigned integer
16	Data	0 to 1024 bytes of payload data

The following sections expand on the format and description of a data link frame.

Destination

The destination address is given by a 4 byte IP number in network byte order, followed by a 2 byte port number in network byte order. Since the frame is sent by a UDP service, including the source address is redundant. However it provides the ability to first sent the frame to a different host, that then forwards the frame to its destination. The intermediary host can be used to trace the exchange of frames.

Source

The source address is given by a 4 byte IP number in network byte order, followed by a 2 byte port number in network byte order. The source, while normally redundant is provided to allow for an intermediary host.

Flag

The format and description of the flag byte is given in the following table:

Bit Offset Flag Bit Name Description

0 RESET When set to 1, that state of the connection must be reset.

1 DATA_VALID Indicates that the frame contains data when set to 1.

2 ACK_VALID Indicates that the frame's acknowledgment field is valid when set to 1. If the RESET bit is also set, then the frame is acknowledging a reset of the link.

Bit Offset	Flag Bit Name	Description
0	RESET	When set to 1, that state of the connection must be reset.
1	DATA_VALID	Indicates that the frame contains data when set to 1.
2	ACK_VALID	Indicates that the frame's acknowledgment field is valid when set to 1. If the RESET bit is also set, then the frame is acknowledging a reset of the link.

SequenceNo

To allow for the detection of duplicate frames, each outgoing frame is given a sequence number. An 8-bit field for the sequence number allows a range of 0 to 255. The sequence number after 255 is 0. If the RESET flag bit is set then the sequence number must be zero.

AcknowledgementNo

An 8-bit field that contains an acknowledgement number in the range of 0 to 255. If the ACK_VALID bit is set to 1, then the receiving host knows that the AcknowledgementNo field is valid and should be used in the acknowledgement of the indicated outgoing frames.

DataLen

This is a 16-bit field representing an 16-bit integer in the range of 0 to 65536. The first byte is the most significant (i.e., the first byte is multiplied by 256). Although the maximum value is 65536, the actual length is restricted to being less than or equal to 1024.

Data

This field contains from 0 to 1024 bytes of payload data. There is no restriction on the contents.

Protocol Behaviour

The frame format gives the syntax of the messages that implement the data link protocol. The semantic (protocol behaviour) is specified by describing the resulting behaviour given a service request, the occurrence of a time out event, and the arrival of a frame. The following subsections describe the actions caused by service requests, time outs, and message arrivals.

Reset Link Service Request

The state variables NextOutgoingFrame and NextFrameExpected must be set to 0. A frame with the RESET flag set should be sent to the peer. The peer is the protocol entity at the other end of the link. The DATA_VALID and ACK_VALID flags should be cleared (set to 0). The SequenceNo, AcknowledgeNo, DataLen fields should be 0. A timer should be started to resend the above "RESET" frame unless a frame is received containing the RESET and ACK_VALID flags set to 1. The timer should be set to 1 second. Any "DATA" frames sent waiting for acknowledgement are discarded and the associated timers are cancelled.

If the timer expires before receipt of the "RESET ACK" frame, the "RESET" frame is retransmitted and the timer restarted. A "RESET" frame should only be resent three times. After four attempts the entity's state is set to INVALID.

Arrival of a "RESET" frame

The arrival of a frame with the RESET flag set and the ACK_VALID flag cleared should set the NextOutgoingFrame and NextFrameExpected variables to 0. Any "DATA" frames waiting for acknowledgement are discarded and the associated timers are cancelled. A "RESET ACK" frame is sent. The RESET and ACK_VALID flags of the "RESET ACK" frame are set to 1. The SequenceNo, AcknowledgeNo, DataLen fields should be 0.

Arrival of a "RESET ACK" frame

On receipt of an "RESET ACK", if the receiving entity is expected an "RESET ACK" frame, then the associated timer is cancelled. The arrival is ignored if the entity was not expecting the "RESET ACK" frame.

Data Send Service Request

This service request results in the transmission of a "DATA" frame. The client's data is placed in the Data field, the DataLen field is set to the data length. The NextOutgoingFrame variable is used to set to SequenceNo field and then incremented modulo 256. The DATA_VALID flag is set to 1. A copy of this frame is saved for retransmission. A 1 second timer is started and the frame sent.

If the timer expires before the receipt of an "ACK" frame, the "DATA" frame is resent, and the 1 second timer restarted. A "DATA" frame can only be resent a maximum of 3 times. After four attempts the entity's state is set to INVALID, and the copied frame is freed.

Arrival of a "DATA" frame

On receipt of a "DATA" frame, its SequenceNo is checked against the value of the NextFrameExpected variable, and if they match the data frame is accepted, passed onward, and the NextFrameExpected variable is incremented modulo 256. An "ACK" frame is sent. This frame has its ACK_VALID bit set to 1 and its Acknowledgement field set to value of the incoming SequenceNo field. Its SequenceNo field is set to the sequence number the value of the NextOutgoingFrame variable. Note the NextOutgoingFrame variable is not incremented. The "ACK" frame is sent on receipt of any "DATA" frame. This handles the case when a duplicate "DATA" frame has been sent because of an early timeout or lose of the corresponding "ACK" frame.

Arrival of an "ACK" frame

On receipt of a frame with the ACK_VALID flag set, a search is made to see if there are any outgoing data frames waiting for acknowledgement. The saved copies of any unacknowledged outgoing frames with a sequence number less than or equal to the AcknowledgementNo are freed, and the associated timer is cancelled. No action occurs if no matching frames are found.

Message Exchanges Examples

This section provides example traces of messages exchanged between to peer entities in accomplishing a series of service requests.

The following table shows the messages exchanges for host A resetting the link and then requesting three data transfers to host B.

Service Request Direction Dest Source Flag SeqNo AckNo DataLen

A: reset link A -> B B:2000 A:2200 R-- 0 0 0

B -> A A:2200 B:2000 R-A 0 0 0

A: send data A -> B B:2000 A:2200 -D- 0 0 47

B -> A A:2200 B:2000 --A 0 0 0

A: send data A -> B B:2000 A:2200 -D- 1 0 49

B -> A A:2200 B:2000 --A 0 1 0

A: send data A -> B B:2000 A:2200 -D- 2 0 43

B -> A A:2200 B:2000 --A 0 2 0

Service Request	Direction	Dest	Source	Flag	SeqNo	DataLen
A: reset link	A -> B	B:2000	A:2200	`R--`	0	0
B -> A	A:2200	B:2000	`R-A`	0	0
A: send data	A -> B	B:2000	A:2200	`-D-`	0	47
B -> A	A:2200	B:2000	`--A`	0	0
A: send data	A -> B	B:2000	A:2200	`-D-`	1	49
B -> A	A:2200	B:2000	`--A`	0	1
A: send data	A -> B	B:2000	A:2200	`-D-`	2	43
B -> A	A:2200	B:2000	`--A`	0	2

The next exchange shows the result of B resetting the link, A sending data, B sending data twice, and lastly A sending data.

Service Request Direction Dest Source Flag SeqNo AckNo DataLen

B: reset link B -> A A:2200 B:2000 R-- 0 0 0

A -> B B:2000 A:2200 R-A 0 0 0

A: send data A -> B B:2000 A:2200 -D- 0 0 47

B -> A A:2200 B:2000 --A 0 0 0

B: send data B -> A A:2200 B:2000 -D- 0 0 49

A -> B B:2000 A:2200 --A 1 0 0

B: send data B -> A A:2200 B:2000 -D- 1 0 43

A -> B B:2000 A:2200 --A 1 1 0

A: send data A -> B B:2000 A:2200 -D- 1 1 43

B -> A A:2200 B:2000 --A 2 1 0

Service Request	Direction	Dest	Source	Flag	SeqNo	AckNo	DataLen
B: reset link	B -> A	A:2200	B:2000	`R--`	0	0	0
A -> B	B:2000	A:2200	`R-A`	0	0	0
A: send data	A -> B	B:2000	A:2200	`-D-`	0	0	47
B -> A	A:2200	B:2000	`--A`	0	0	0
B: send data	B -> A	A:2200	B:2000	`-D-`	0	0	49
A -> B	B:2000	A:2200	`--A`	1	0	0
B: send data	B -> A	A:2200	B:2000	`-D-`	1	0	43
A -> B	B:2000	A:2200	`--A`	1	1	0
A: send data	A -> B	B:2000	A:2200	`-D-`	1	1	43
B -> A	A:2200	B:2000	`--A`	2	1	0

The following table depicts the exchange in the which a data frame is lost, and retransmitted, then a successful data transmission and finally a transmission involving the lost of an acknowledgement frame.

Service Request Direction Dest Source Flag SeqNo AckNo DataLen

A: send data
data lost
resent A -> B B:2000 A:2200 --D 89 34 19

A -> B B:2000 A:2200 --D 89 34 19

B -> A A:2200 B:2000 --A 34 89 0

A: send data A -> B B:2000 A:2200 -D- 90 34 174

B -> A A:2200 B:2000 --A 34 90 0

A: send data
lost ack
resent A -> B B:2000 A:2200 -D- 91 34 49

B -> A A:2200 B:2000 --A 34 91 0

A -> B B:2000 A:2200 -D- 91 34 49

B -> A A:2200 B:2000 --A 34 91 0

Service Request	Direction	Dest	Source	Flag	SeqNo	AckNo	DataLen
A: send data data lost resent	A -> B	B:2000	A:2200	`--D`	89	34	19
	A -> B	B:2000	A:2200	`--D`	89	34	19
	B -> A	A:2200	B:2000	`--A`	34	89	0
A: send data	A -> B	B:2000	A:2200	`-D-`	90	34	174
A: send data	B -> A	A:2200	B:2000	`--A`	34	90	0
A: send data lost ack resent	A -> B	B:2000	A:2200	`-D-`	91	34	49
	B -> A	A:2200	B:2000	`--A`	34	91	0
	A -> B	B:2000	A:2200	`-D-`	91	34	49
	B -> A	A:2200	B:2000	`--A`	34	91	0