Model Description

The is used for reliable data transfer. Please refer to a good textbook in networking (e.g. [#!jim_book!#]) for details. In this protocol, packets to be transmitted from A to B are numbered sequentially. This sequence number (SN) is sent in the packet header and it is checked by the receiver.

Our model is a simple version of the go-back-n protocol. It consists of a Sender object that transmits packets to another object and receives acknowledgments for packets correctly received. A Receiver object accepts packets from the Sender object and transmits acknowledgments for packets that are received correctly.

In order to simplify our model, we assume that the round trip time (RTT) measured from the time the sender transmitted a packet until it gets an acknowledgment back (assuming the packet was correctly received by the receiver and also that the acknowledgment was received correctly by the transmitter) is included in the ``Channel'' object. This assumption is useful to maintain the cardinality of the state space under reasonable size. (The user is encouraged to relax this assumption and see what happens.) We also assume that the ACK packets are small enough so that the its transmission delay is negligible. Therefore only the propagation delays are included in the channel object. Furthermore, no sender timeout is modeled, and when the sender transmits all packets in a window it ``goes back'' and retransmits from the beginning of the window. In order to obtain a Markov model, all random variables are assumed to be exponentially distributed.

In the first model we present we assume that both packets and acknowledgments may be lost. However, the receiver only sends ACK packets back to the transmitter when it accepts a packet. The Sender object has two state variables: one, Win_begin, indicates the beginning of the transmitter window, and the other, SN, points to the sequence number of the next packet to be transmitted. The Receiver object has only one state variable RN that indicates the sequence number the receiver is expecting. That is, a packet with sequence number equal to RN is accepted, if received correctly. The Channel object has two variables. The first ACK_RN indicates the serial number of the last ACK that was sent to the receiver. (Note that this last ACK could have been lost.) The second variable N_acks indicates the number of ACK packets that are in transit in the channel. The model is shown in Figure .

Figure: The Go Back N Model.

The TANGRAM-II description of the objects is shown in Figures , and .

Figure: The Sender object (Go Back N Model) Model 1.

Figure: The Channel object (Go Back N Model). Model 1

Figure: The Receiver object (Go Back N Model) Model 1.

We encourage the user to first try the model using p_losing_ack=0, that is, no ACK packets are lost. This model has 18 states, considering the transmission window equal to $2$ as in the figures. (WARNING: the transmission window must be identical in all objects since their specification uses this parameter.)

The in the Channel object marks the transitions that represent a packet accepted by the receiver (in this model, this event happens when an ACK is sent to the channel). Using the marked transitions and the steady state results, the user can easily compute the system throughput.

Now lets change p_losing_ack to the value in Figure , and solve it again. The model now has 36 states. However, the Markov chain generated is not ergodic. Why? Because we assumed the sender only sends ACKs back whenever it accepts a packet. Since ACK packets can be lost, the sender may never receive an ACK for packets it sent. The user should verify the following set of states: $\{14, 20\}, \{28, 33\}$ and $\{34, 36\}$. Once the model reaches any of these states, it remains in the corresponding set. You should also try the interactive simulation and observe that the model reaches a deadlock state!

The tool, in this present version, does not check for ergodicity, and so the user must be careful when specifying a model. Also some of the solvers cannot be used when the model is not ergodic. For instance, the solver will not produce the correct result. However, the Power method can be used. You should verify the results with the Power method, allowing sufficient iterations until convergence is reached.

In order to obtain a correct working protocol, the receiver must send ACK packets whenever it receives a packet, not only when it accepts a packet. In our model, we also modify the Channel object so that: (a) a duplicate ACK is discarded when the channel has still ACKs to deliver and; (b) a duplicate ACK is not discarded if all ACK packets have been delivered.

Following the new specification, the message attribute of the Receiver object is changed to:

msg_rec = PKT_PORT
action ={ 
            int s;
            s = RN;
            if (msg_data == RN)
            {
                s = (RN + 1) % (TRANS_WIN+1);
                msg(ACK_PORT,all,s);    
                set_st("RN",s);
            }
            else 
            {
                msg(ACK_PORT,all,s);
            }
        }:prob = 1 - P_LOSING_PKT;
        {
            /*do nothing*/
            ;
        }:prob = P_LOSING_PKT;

The message attribute of the Channel object is changed to:

msg_rec = RECV_ACK_PORT
action={ 
           int n_acks; /* number of acks stored in channel */
           int ack_rn; /* serial number of the last ack transmitted from channel.
                       Note that this last ack may have been lost */
           int module;
           int sn_last_ack; /* serial number of the last ack in channel to be 
                            or last ack sent if n_acks=0 */
        
           module = TRANS_WIN + 1;
           n_acks = N_Acks;
           ack_rn = Ack_RN;
           sn_last_ack = (ack_rn + n_acks)%module;
           if (msg_data == (sn_last_ack+1)%module)
           /* this is a new ack that is entering the channel */
           {
               n_acks = N_Acks + 1;
           }
           else
           /* this is a duplicate ack */
           {
               if (n_acks == 0)
               /* acks in channel have been lost, so send this duplicate ack */
               {
                   n_acks = N_Acks + 1;
                   /* ack_rn = ack_rn - 1, in Module */
                   ack_rn = (ack_rn + TRANS_WIN)%module;
               }
           }
           set_st("N_Acks",n_acks);
           set_st("Ack_RN",ack_rn);
       };

One final observation: note that the attribute in this last model marks all the transitions corresponding to an ACK packet being received, and no distinction is made between a duplicate ACK or an ACK for a new packet accepted by the receiver. The user is encouraged to find out how to calculate the system throughput in this new model.