Assignment for Datakom I:
Modelling of the Alternating Bit Protocol using SDL/SDT

Introduction

This assignment will introduce you to the specification and description language SDL and the design tool SDT.

Prerequisites

Before you start with the assignment you should have read the following:

Implementation

The assignment is to be done in groups of max. 2 students. We will assist you in the beginning of the assignment with special lab-times to assure a quick start. You can find a lot of on-line documentation for SDL and SDT on the Web.

Reports

Your report must include the SDL/GR-diagrams of the FSMs and MSCs showing the behaviour of your implementations for the test sequences described later on. You have to make an own subdirectory for this assignment and write the complete path on your report so we can check it!

Please hand in your reports right on time in and only in the mailbox of Jesper Jonsson (Building 1, 4. floor, box no. 95). The first page of your report must be the signed declaration .

Alternating Bit Protocol

Function

The alternating bit protocol consists of a Sender_ABP and a Receiver_ABP communicating via two channels with FIFO characteristic. The two channels are called Data_Medium and Ack_Medium, respectively. Both can loose messages. The purpose of the protocol is to transmit data from the sender to the receiver in the correct order, although the medium can lose data and/or acknowledgement messages. Distorted messages are handled like lost ones. The protocol works as follows:

The Sender_ABP takes a message which is ready to be sent to the Receiver_ABP. It transmits the message together with a sequence number via the Data_Medium to the Receiver_ABP. Then the Sender_ABP waits for an acknowledgement from the Receiver_ABP containing the same sequence number. If the appropriate acknowledgement arrives, the Sender_ABP performs the same procedure for the next waiting message, but this time with an inverted sequence number (i.e., 0->1, 1->0). If the appropriate acknowledgement does not arrive within a certain period of time, the Sender_ABP resends the same message. This time period is controlled by a Timer_ABP that is started as soon as the Sender_ABP has transmitted the message to the Receiver_ABP. The Timer_ABP is stopped as soon as the acknowledgement arrives.

The Receiver_ABP, when in the idle state, acknowledges all incoming messages. If the sequence number is wrong, it will discard the message and stay in the same state. After receiving a message with a correct sequence number, it will acknowledge only packages with the last correct sequence number until a Receive signal is received. After that, it will invert the sequence number, and go back to the idle state.

The channels Data_Medium and Ack_Medium transmit messages and acknowledgements, respectively. The loss of messages or acknowledgements is controlled via special signals by the environment (i.e., you).

The structure of the scenario is shown in the following picture which is not valid SDL/GR. This diagram shows the timer as a seperate block, check your SDL documentation how timers are realized and include them in your sender!

In addition, we want you to use parametrized signals and not two different signals for data or acknowledgements with different sequence numbers! I.e., d(0) denotes the signal d with the parameter 0, d(1) the signal d with the parameter 1. Do not use, e.g., d_0 and d_1, which would represent two different signals. The reason for this is, that the ABP is a very simple version of the more general concept of sequence numbers which can be more than just 0 and 1. Please stay as far as possible with the names and identifiers we are using throughout this introduction.

Description as Finite State Machines (FSM)

FSMs are often a very convenient and also more formal way of describing protocols. In the following we describe the FSMs of Sender_ABP, Receiver_ABP, Data_Medium and Ack_Medium. If you are in doubt of the functionality of the protocol after reading the above description, look at the following FSMs, they represent what you have to implement! You have to model all transitions explicitly and to state clearly if you use implicit mechanisms of SDL (e.g., the consumption of unexpected signals).

The semantics of the diagrams is as follows: circles denote states, arcs denote transitions between states. Transitions are described using the notation input_events; output_events. The meaning is as follws: if the FSM receives one of the input_events in a state at the beginning of an arc, it outputs all output_events and goes into the state the arc points to. Unexpected signals are ignored, but you have to state clearly via comments when you ignore what events!

Sender

Receiver

Data_Medium

Ack_Medium

Exercise

Model the ABP using SDL as specification language and SDT as design tool. You will have to use extended FSMs, model the main states as shown in the state diagrams above. Use the SDL TIMER construct in the sender with its SET and RESET commands. Messages and/or acknowledgements do not need to have any contents besides the sequence number.

Check your protocol description using the following test sequences and use MSCs for documentation!

Test Sequences

The test sequences shall show you (and us) that your protocol works (but it does not prove correctness!). You have to apply at least the following three sequences and hand the results in. Do not implement endless loops in the sender, but send the messages one after the other and perform all possible transactions every time you have sent a new message!

Slow Receiver

Bad connection

Slow Receiver and Lost Acknowledgement

And now have fun with the assignment!