hack hack reasearch facility

References:
1. "Computer Networks", 3rd Edition, Andrew S. Tanenbaum
2. "Computer Networks, A System Approach", 3rd Edition
Peterson, Davy, Kaufmann


1.1 Introduction

In this chapter we will discuss the services the datalink layer of the
networking stack is required to have and the various existing layer 2
protocols which cater to these requirements in different ways. The job of the
datalink layer to transfer the bits to the destination machine, which then can
be handed over to the network layer for processing. The data link layer in
itself receives a raw stream of bits for the physical layer, which itself could be
built on different technologies like cable, dsl, wireless, optical fiber to name a
few. The actual communication path between any two adjacent hosts can be shown as
below:


HOST 1 (SENDER) HOST 2 (RECEIVER)
------------- -------------
| | | |
|___________| |___________|
| | LAYER 4 | | TRANSPORT (TCP/UDP)
|___________| |___________|
| . | LAYER 3 | . | NETWORK (IP)
|_____|_____| |_____|_____|
| | | LAYER 2 | | | DATALINK (PPP)
|_____|_____| |_____|_____|
| | | LAYER 1 | | | PHYSICAL
|_____|_____| |_____|_____|
| |
\_______________________________________/


ACTUAL DATA PATH

Figure 1.1 Communication channel between two adjacent hosts

(NOTE: By adjacent we mean two hosts which are connected by a physical connection)

Shown above are the lower 4 layers of the OSI (Open Systems Interconnection) Reference
Model.

1.2 Design Issues

The datalink layer is designed to offer the following functionalities:

(A) Provide a well-defined service interface to the network layer (layer 3).
Depending on the efficiency and error rate of the underlying physical
layer, the datalink layer can be designed in any of the three ways:

(a) Unacknowledged connectionless service. This consists of the source host
sending independent frames to the destination host without any sort of
feedback/acknowledgment mechanism.There is no connection setup or release.
Frame recovery due to line noise is left to the network layer. This kind of
service is appropriate for high speed, low error communication channels
such as an optical fiber network.

(b) Acknowlegded connectionless service. Communication channels which are
more error prone and hence require more reliable communication implement
a feedback mechanism for each frame sent between two hosts. This enables
the sender to know if the frame has arrived correctly or not. This ack
sending mechanism is not a requirement but an optimization, because the
transport layer can always send a message and wait for it to be
acknowledged. However a message, (a unit of data in the transport layer)
consists of several frames, (unit of data in the datalink layer), so the
re-transmission of each faulty received message would bear a lot of
overhead. Such a mechanism is useful on wireless channels which are
inherently unreliable.

(c) Acknowledged connection-oriented service. This is the most
sophisticated service the datalink layer can provide to the network
layer. In this service the source and destination hosts establish a
connection before any transfer of data takes place. Each frame is
received in the same order it is sent in. The service also gaurantees
that each frame is received only once.Communication between two hosts
takes place in three phases. First phase is connection setup, during
which each side initalizes counters and variables to keep track of
frames. Second phase consists of actual frame transmission and the
third phase consists of connection release, freeing up the resources
and buffers when the transfer is done.

(B) Framing
The datalink layer receives a raw bit stream from the underlying physical
layer. This bit stream is not gusranteed to be error free. On a noisy
communication channel the received number of bits maybe less/more, and/or
different than the ones transmitted. In order to provide a reliable
transfer to the network layer the data link layer breaks the bit stream
into frames and computes the checksum for each frame. This checksum is
also transmitted along with the frame. The destination host on receiving a
frame, computes another checksum from its data and compares it to the one
transmitted. This enables the datalink layer of the destination host to
detect and possiblly correct frames, depending upon the method the checksum
is computed in. Some methods used for framing are:
- Character count: The number of characters in the frame are stored in a
field of the header attached to the frame.
- Starting and Ending characters with character stuffing.Each frame starts
with a known ASCII character sequence DLE STX and ends with the sequence
DLE ETX. (DLE IS Data Link Escape, STX is Start Of Text, ETX is End of
Text). A serious problem with this method is that the frame data itself
could contain any of these sequences.
- Starting and Ending characters with bit stuffing: This method solves the
above mentioned problem by stuffing an additional ASCII DLE for every DLE
character in the data.The data link layer of the destination host is then
responsible for removing these bit stuffings from the frame data before
assembling the frames.


(C) Error Control, Sequencing frames and sending control frames for feedback.
A bad communication channel can cause a variety of strange events during
communication, flipping of bits, losing bits from a frame, new bits in the
frame, frames completely disappearing, either host going down.
To communicate the receiving of a correct or incorrect frame the receiver
host sends postive or negative acknowledgements accordingly to the sender
host.This would cause the sender to hang forever waiting for an ack frame.
The sender can have a timeout to resend the frame again if it doesn't
receive an ack in a given time period. To prevent the recipient data link
layer from passing the same frame more than once to the network layer,each
outgoing frame is assigned a sequence number. This whole managing of
timers and frame sequencing is an integral part of data link layer design.


(D) Flowcontrol, control the rate of data transmission between two hosts.
This is another of the important issues in the design of the data link
layer, how to coordinate the rate of transmission between two hosts.
What if the sender is sending data at a much faster rate than the receiver
can process/accept, causing dropping of packets at the receiver end
which further causes the sender to timeout on the ack packets it is
expecting, causing restransmission, leading to a less efficient network.
The sender in such a case is usually throttled by using a feedback
mechanism. There are various ways in which the receiver communicates
to the sender using control frames about the number/rate of packets it
can accept comfortably.

1.3 Elementary Data Link Protocols

1.3.1 An unrestricted simplex protocol:
This is a simple data link protocol which makes certain assumption
which are far from true in the real world, but its sole purpose is
to explain the working of the data link layer and then incrementally
taking the assumptions off.
Assumption 1: Data is transmitted in only one direction
Assumption 2: At both ends the network layers are always ready
Assumption 3: Infinite buffer size of the sender, receiver
Assumption 4: There is no error on the communication channel

PSUDO CODE:


void sender(void)
{
frame f;
packet p;

while (TRUE)
{
get_packet_from_network(p);
packet_to_frame(p,f);
send_frame_to_physical_layer(f);
}
}

void receiver(void)
{
frame r;
packet p;
while(true) {
get_frame_from_physical_layer(r);
frame_to_packet(p,r);
send_packet_to_network(p);
}
}

1.3.2 A Simplex Protocol for a Noisy Channel
Consider Assumption 4 is no longer true, frames can be lost or
damaged. But damaged frames can be detected by the receiver.
Both these protocols suffer from a number of flaws, frames
submitted out of order, duplication of frames, if an ack frame
is lost the sender is kept waiting.
Protocols in which the sender waits for an acknowledgment before
sending the next frame are called ARQ (Automatic Repeat Request).
The protocols have a timeout for retransmission to deal with lost
frames. This still does not solve the problem of duplication which
requires for the frames to have sequence numbers.

1.3.3 Sliding Window Protocols
All the previously discussed protocols could possibly be used for
a unidirectional data transfer, in the real world we need
a bidirectional communication channel. One way of doin this would
be to have two seperate channels one from the data ( forward)
channel and one for its acknowledgments (reverse), but the reverse
channel would almost be entirely wasted. A big improvement over
this is using the same channel for transmitting data and control
frames. When a data frame arrives, instead of immediately sending
a control frame(ack), the data link layer waits for the network
layer to pass it a message, and the ack is sent along with the
data frame. This greatly reduces network traffic. This is known as
PIGGYBACKING.
In all sliding window protocols, each outbound frame
contains a sequence number from 0 to 2^n -1, so the first n-bits
are used for the seq. numbers. Both the sender and the receiver
maintain their own window, which could have different sizes. Some
protocols require a fixed size, while some can be changed as frames
are sent and received. The "Stop and Wait" protocol is a particular
Sliding Window protocol with n=1.
Until now we had made the assumption that the transmission time
required for a frame to arrive at the receiver plus the transmission
time for the acknowledgment to come back is negligible. Consider a
60 kbps satellite channel with a 600-msec round-trip propogation
delay. Let the frame size be 1200 bits, at t = 0, the sender starts
sending the first frame, at t = 20 msec, the frame has been completely
sent, now at t=320 msec the frame fully arrives at the receiver, while
the sender gets the ack back at t= 620 msec. The sender in this case
was blocking for over 90% of the time.
To overcome this problem, there is another class of sliding window
protocol called "Go Back N". In this the sender is allowed to transmit
upto 'w' frames before blocking. With the right choice of 'w', the
sender is able to continously transmit frames for a time equal to the
round trip time without filling up the window. This technique is called
PIPELINING. If the receiver has a window size of 1, then on receiving
an erroneous frame, the receiver stops sending acks to all the frames
received subsequently, the sender eventually times out and
retransmits the remaining frames again. A better solution is when the receiver
has a window size > 1, and it first collects all the correct frames and
sends acks for them to the sender, when the sender realizes it hasn't
received the acks for all the data frames it sent, it resends the one
with missing acks. This is known as "Selective Repeat".