They say the the greatest trick the devil ever pulled was making people belive he didn't exist. But I don't think that's right. I think his greatest trick was to make people belive he was god.
The following is homework:
Go-Back-N
The Go-Back-N protocol is one of several Sliding-Window protocols. A Sliding- Window protocol is essentially a compromise between the stop-and-wait protocol and the unrestricted protocol. The stop-and-wait protocol allows only for one frame to be sent at a time. No new frame can be sent before an acknowledgement is received. The unrestricted protocol on the other hand, allows a sender to pass on everything it wants to, and assumes that the receiver is able to receive it all without problems. With a Sliding-Window protocol, a middle ground is taken: The sender stores it's sent frames in a local buffer and resend them if acknowledgements are not received within the expected time. When acknowledgement does arrive, the sender's buffer is emptied up to and including the frame that is acknowledged. That is, if the receiver acknowledges frame m, and the sender has stored frames k, l, m, n, and o in the buffer, it assumes that the receiver got frames all the way up to m, and so it purges k, l, and m from it's buffer. The two standard versions of the Sliding-Window protocol are Go-Back-N, and Selective Repeat. Go-Back-N is considered the simpler of the two, as it only accepts frames that come in order, and ignores all others. This is the protocol I have implemented in this assignment.
My implementation of Go-Back-N is completely contained in the Data Link Layer. A Linked List defines the window. This simplifies several aspects of the algorithm: I don't have to keep a record of the size of the window, as the list maintains such a record itself. The first position in the window is simply the first entry in the list, and purging the buffer is simply a matter of removing entries in order of insertion. I have also defined three internal classes: The TimedFrame, the AckTimerTask, and the FrameTimerTask. The timertasks are called such to separate them from the timers that are used to schedule these two inner classes.
The AckTimerTask is a simple class that, when ran, notifies the Data Link Layer that the Acknowledgement Timer has expired by putting a predefined Event on the EventQueue.
The FrameTimerTask completely mirrors the AckTimerTask, except that the event it puts on the queue when ran, notifies the Data Link that a Frame Timer has expired. One frame-timer is associated with each data-frame that is sent. TimedFrame is a bigger class. This inner class contains an instance of the supplied Frame class in a addition to a number of methods. The constructor takes the same arguments as that of the Frame constructer. When constructed, TimedFrame creates a new Frame, a new Timer and a new FrameTimerTask. It then uses the Timer to schedule the FrameTimerTask to execute if it is not cancelled in time. TimedFrame also contains methods to stop or restart its timer, in addition to basic accessors. The stopTimer() method calls the cancel() methods of the FrameTimerTask and the Timer. The restart() method stops the two timers just like stopTimer(), and then constructs new timers, and finally uses the new Timer to schedule the new FrameTimerTask.
The protocol itself works an infinite loop. During each pass, the data link layer looks at the EventQueue for one of six separate events. These events are: 1) Packet from Patron and the window is not at its maximum size. In this case a new frame is constructed using the packet as data. The frame is number one above last frame modulo max frame number (in this implementation no frame is numbered above 5, so if last frame sent was number five, the new frame is numbered 0) and contains an acknowledgement number equal to the last frame that was received through the physical layer. This frame is then sent off, and the acknowledgement timer is stopped, since an acknowledgement is piggybacked with this frame.
2) Packet from Patron, but the window is at its maximum size. In this case the packet is ignored and the event is put back on the queue. This is so the buffer does not overrun and the packet is not lost.
3) Acknowledgement timer expired. This happens if no frame has been sent lately, so the other end hasn't had any frames acknowledged. To deal with this a special frame is constructed that contains no data, only an acknowledgement number. This frame is put on the physical layer and the acknowledgement timer is stopped.
4) Frame timer expired. This happens when a frame has been sent, but no acknowledgement has been received for it. Since the buffer only contains outstanding frames, the entire window is sent through the physical layer. The frames are modified however: The acknowledgement piggybacked is not the one the frame was constructed with. Instead each old frame is sent with the current acknowledgement number. Finally each frame's frame timer is restarted so they are not forgotten all about.
5) Frame arrives through physical layer, but the frame is damaged. When a frame arrives, its CRC is addressed. If this check fails the frame is damaged and a NAK frame is constructed and sent.
6) Frame arrives through physical layer, and the CRC succeeds. Now many things may happen, but the first is always that the buffer is purged. The frame that arrived will always have an acknowledgement number. This number is consulted and every frame in the buffer, from the oldest frame up to and including the frame with the same frame-number as the ack-number, is removed and their frame-timers are stopped. Next the frame type is checked. Any frame can be one of four types: Ack, Nak, data in sequence, and data out of sequence. If it is an ack-frame no further action is needed. If it is a Nak-frame, this means that something was wrong with data already sent, and the proper reaction is to resend everything that is still in the buffer. If the frame contains data in sequence, that is the frame contains data and the frame-number is the one expected, the packet contained in the frame is passed on to the patron. The expected frame number is incremented modulo maximum frame-number and the acknowledgement timer is restarted if it's not already active. Finally, if the frame is a data-frame, but it is out of sequence, it is simply ignored and a Nak-frame is passed through the physical layer.