Final Project : JAVA Applet Programming
THE GBN PROTOCOL
COURSE NO. EEE 459/591
PREPARED BY:
SHAMIUL AZOM. ASU ID: 993456298
2
1. CONCEPT ILLUSTRATED BY APPLET
I demonstrated the GBN protocol in my applet programming. The GBN protocol was covered extensively
in our class. It demonstrates principles of reliable data transfer.
In a Go-Back-N (GBN) protocol, the sender is allowed to transmit multiple packets (when available)
without waiting for an acknowledgment, but is constrained to have no more than some maximum
allowable number, N, of unacknowledged packets in the pipeline. Figure 1 shows the sender's view of the
range of sequence numbers in a GBN protocol. If we define base to be the sequence number of the
oldest unacknowledged packet and nextseqnum to be the smallest unused sequence number (that is, the
sequence number of the next packet to be sent), then four intervals in the range of sequence numbers
can be identified. Sequence numbers in the interval [0,base-1] correspond to packets that have already
been transmitted and acknowledged. The interval [base,nextseqnum-1] corresponds to packets that have
been sent but not yet acknowledged. Sequence numbers in the interval [nextseqnum,base+N-1] can be
used for packets that can be sent immediately, should data arrive from the upper layer. Finally, sequence
numbers greater than or equal to base+N cannot be used until an unacknowledged packet currently in the
pipeline has been acknowledged.
Figure1: Sender's view of sequence numbers in Go-Back-N
As illustrated in Figure 1, the range of permissible sequence numbers for transmitted but not-yet-
acknowledged packets can be viewed as a "window" of size N over the range of sequence numbers. As
3
the protocol operates, this window slides forward over the sequence number space. For this reason, N is
often referred to as the window size and the GBN protocol itself as a sliding-window protocol.
In practice, a packet's sequence number is carried in a fixed-length field in the packet header. If k is the
number of bits in the packet sequence number field, the range of sequence numbers is thus [0,2k - 1].
With a finite range of sequence numbers, all arithmetic involving sequence numbers must then be done
using modulo 2k arithmetic. (That is, the sequence number space can be thought of as a ring of size 2k,
where sequence number 2k - 1 is immediately followed by sequence number 0.)
Figures 2 and 3 give an extended-FSM description of the sender and receiver sides of an ACK-based,
NAK-free, GBN protocol. This FSM description is described as an extended FSM since there are added
variables (similar to programming language variables) for base and nextseqnum and also added
operations on these variables and conditional actions involving these variables.
Figure 2: Extended FSM description of GBN sender
4
Figure 3: Extended FSM description of GBN receiver
The GBN sender must respond to three types of events:
Invocation from above. When rdt_send() is called from above, the sender first checks to see if the
window is full, that is, whether there are N outstanding, unacknowledged packets. If the window is not full,
a packet is created and sent, and variables are appropriately updated. If the window is full, the sender
simply returns the data back to the upper layer, an implicit indication that the window is full. The upper
layer would presumably then have to try again later. In a real implementation, the sender would more
likely have either buffered (but not immediately sent) this data, or would have a synchronization
mechanism (for example, a semaphore or a flag) that would allow the upper layer to call rdt_send() only
when the window is not full.
Receipt of an ACK. In GBN protocol, an acknowledgment for packet with sequence number n is be taken
to be a cumulative acknowledgment, indicating that all packets with a sequence number up to and
including n have been correctly received at the receiver.
A timeout event. The protocol's name, "Go-Back-N," is derived from the sender's behavior in the
presence of lost or overly delayed packets. As in the stop-and-wait protocol, a timer will again be used to
recover from lost data or acknowledgment packets. If a timeout occurs, the sender resends all packets
that have been previously sent but that have not yet been acknowledged. The sender in Figure 2 uses
only a single timer, which can be thought of as a timer for the oldest transmitted-but-not-yet-
acknowledged packet. If an ACK is received but there are still additional transmitted-but-yet-to-be-
acknowledged packets, the timer is restarted. If there are no outstanding unacknowledged packets, the
timer is stopped.
The receiver's actions in GBN are also simple. If a packet with sequence number n is received correctly,
and is in order (that is, the data last delivered to the upper layer came from a packet with sequence
number n - 1), the receiver sends an ACK for packet n, and delivers the data portion of the packet to the
upper layer. In all other cases, the receiver discards the packet and resends an ACK for the most recently
received in-order packet. Since packets are delivered one-at-a-time to the upper layer, if packet k has
been received and delivered, then all packets with a sequence number lower than k have also been
delivered. Thus, the use of cumulative acknowledgments is a natural choice for GBN.
In GBN protocol, the receiver discards out-of-order packets. The receiver must deliver data, in order, to
the upper layer. Now, when, say, packet n is expected, packet n + 1 arrives instead. Since data must be
delivered in order, the receiver could buffer (save) packet n + 1 and then deliver this packet to the upper
layer after it had later received and delivered packet n. However, if packet n is lost, both it and packet n +
1, will eventually be retransmitted as a result of the GBN retransmission rule at the sender. Thus, the
5
receiver can simply discard packet n + 1. The advantage of this approach is the simplicity of receiver
buffering--the receiver need not buffer any out-of-order packets. Thus, while the sender must maintain the
upper and lower bounds of its window and the position of nextseqnum within this window, the only piece
of information the receiver need maintain is the sequence number of the next in-order packet. This value
is held in the variable expectedseqnum, shown in the receiver FSM in Figure 3. Of course, the
disadvantage of throwing away a correctly received packet is that the subsequent retransmission of that
packet might be lost or garbled and thus even more retransmissions would be required.
Figure 4 shows the operation of the GBN protocol for the case of a window size of four packets. Because
of this window size limitation, the sender sends packets 0 through 3 but then must wait for one or more of
these packets to be acknowledged before proceeding. As each successive ACK (for example, ACK0 and
ACK1) is received, the window slides forward and the sender can transmit one new packet (pkt4 and
pkt5, respectively). On the receiver side, packet 2 is lost and thus packets 3, 4, and 5 are found to be out-
of-order and are discarded.
Figure4: Go-Back-N in operation
It is worth noting that an implementation of this protocol in a protocol stack would likely be structured
similar to that of the extended FSM in Figure 2. The implementation would also likely be in the form of
various procedures that implement the actions to be taken in response to the various events that can
occur. In such event-based programming, the various procedures are called (invoked) either by other
procedures in the protocol stack, or as the result of an interrupt. In the sender, these events would be (1)
a call from the upper-layer entity to invoke rdt_send(), (2) a timer interrupt, and (3) a call from the lower
layer to invoke rdt_rcv() when a packet arrives.
The GBN protocol incorporates almost all of the techniques that are in the reliable data-transfer
components of TCP. These techniques include the use of sequence numbers, cumulative
acknowledgments, checksums, and a time-out/retransmit operation. In this sense, TCP has a number of
- 1
- 2
前往页