Data Link Layer

The job of the data link layer is to

make the communication on the
physical link reliable and efficient
1
Recall Data Link Layer
Definition
Data Link Layer - Provides for the reliable
transfer of information across the physical
link; sends blocks of data (frames) with
necessary synchronization, error control,
and flow control
Examples HDLC, PPP

2
Data Link Layer
It then manages how the flow process of the
bit stream takes place to include the
following:
Creates and recognizes frame boundaries
Checks received messages for integrity
Manages channel access and flow control
Ensures correct sequence and transmitted data
Detects and possibly corrects errors that occur in
the Physical Layer without using the functions of
the upper layers
Provides flow-control techniques to ensure that
link buffer capacity is not exceeded 3
Data Link Layer Issues
Link Configuration Addressing
Control Framing
Link Discipline Synchronization
Control Error Control
Link Management - Flow Control
bringing link up and
down

4
Link Configuration Control
Link Configuration Control refers to the
following:
Link Topology
Link Duplexity

5
Link Topology
The topology of a communication link
refers to the physical arrangement of the
connection between the devices. In its
fundamental form the topology of a data
link between two devices could be:
Direct Link
Indirect Link

6
Direct Link - Subtypes
There are two possibilities with a direct
link:
Multipoint Link
Point to Point Link

7
Link Duplexity
Duplexity refers to the fact that either one
station can transmit at a time (half duplex)
or both can transmit simultaneously (full
duplex).

8
Link Discipline with Point to
Point Links
Simple
One device may
send an ENQ
message to see if
the other is ready
On receiving an ACK
the DATA frame may
be sent
Vertical Time
Sequence Diagram

9
Framing
Framing refers to the fact that the
beginning and the end of data are marked
so to be recognized and help in
synchronization.
A frame is a quantum of data usually at
layer two of the OSI reference model.
The size of a frame is measured in bits.
The size of a frame could range from a few
bits (5 to 8) to few hundred or even
thousand bits.
10
Synchronization
Synchronization refers to the fact the
receiver must know when the data begins
and when it ends and also the receiver
should be able to distinguish between each
bit in the frame of data.
Concerned with timing issues
Small timing difference become more
significant over time if no synchronization
takes place between sender and receiver
Synchronization occurs on the data link
layer 11
Synchronous Synchronization
Large blocks of bits (frames) are
transmitted without start or stop bits after
every 5 or 8 bits
The beginning of a frame is marked by a
preamble - flag
End is marked by a postamble - flag
Bit-stuffing is used to prevent occurrence
of flag in the data - provides data
transparency
12
Synchronous Synchronization
Flag is usually a bit pattern 01111110
For sizable blocks of data synchronous
transmission is far more efficient
e.g. HDLC with 1000 bit frame size and 48
control bits is only 4.8% overhead.
Two types:
bit oriented
Character oriented

13
Flag Fields
Delimit frame at both ends
01111110
May close one frame and open another
Receiver hunts for flag sequence to synchronize
Bit stuffing used to avoid confusion with data
containing 01111110
0 inserted after every sequence of five 1s
If receiver detects five 1s it checks next bit
If 0, it is deleted
If 1 and seventh bit is 0, accept as flag
If sixth and seventh bits 1, sender is indicating
abort
14
Bit
Stuffing
Example
with
possible
errors

15
Flow Control
Flow Control refers to mechanisms that
make sure that the sending station cannot
overwhelm the receiving station with data.
Preventing buffer overflow
Transmission time
Time taken to emit all bits into medium
Propagation time
Time for a bit to traverse the link

16
Stop-and-Wait Flow Control
The simplest form of flow control is Stop
and Wait Flow Control.
Stop and Wait Flow Control works like this:
The sending station sends a frame of data
and then waits for an acknowledgement
from the other station before sending
further data
The other party can stop the flow of data by
simply withholding an acknowledgement
17
Stop-and-Wait Flow Control
Source may not send new frame until
receiver acknowledges the frame already
sent
Very inefficient, especially when a single
message is broken into separate frames

18
Stop-and-Wait Flow Control
Stop and Wait Flow control works great if
data are sent as a few large frames.
However large frames are undesirable for
the following reasons:
Large frame means one station occupies the
link for a longer time (undesirable on a
multipoint link)
There is more chance of error in a large frame
resulting in more lost data and more
retransmission
19
Utilization under SW Flow
Control
Utilization = U = frame time / total time
U = 1/1+2a
a = Propagation Time / Transmission Time
a = Medium length in bits / Frame length
in bits

20
Sliding-Window Flow Control
Allows multiple frames to be in transit
Receiver sends acknowledgement with
sequence number of anticipated frame
Sender maintains list of sequence numbers
it can send, receiver maintains list of
sequence numbers it can receive
ACK (acknowledgement) supplemented
with RNR (receiver not ready)

21
Error Detection
Error detection refers to the techniques
used to send extra information that can
help in indicating to the receiver if the data
might have been changed during the
course of travelling through the medium.
Parity error detection and CRC error
detection are two techniques that will be
discussed for error detection.

22
Cyclic Redundancy Check
For a Message block of k bits (called M)
transmitter generates n bit sequence
(Called Frame Check Sequence or F)
Transmit k+n bits which is exactly divisible
by some number called P which is n+1 bits
long
Receive divides frame by that number
If no remainder, assume no error

23
CRC
Example

24
Address Resolution
Protocol - ARP
IP over Ethernet

25
 Address Resolution
(continued)
 A resolves protocol address for B for protocol messages from an
application on A sent to an application on B
 A does not resolve a protocol address for F
 Through the internet layer, A delivers to F by routing through R1 and
R2
 A resolves R1 hardware address
 Network layer on A passes packet containing destination protocol
address F for delivery to R1
Host A Host C Host E

Network 1 Router 1 Network 2 Router 2 Network 3

Host B Host D Host F

26
 Address Resolution
Techniques
Association between a protocol address and a
hardware address is called a binding. Three
techniques:
Table lookup - Bindings stored in memory with
protocol address as key - data link layer looks up
protocol address to find hardware address
Closed-form computation - Protocol address
based on hardware address - Data link layer derives
hardware address from protocol address
Dynamic - Network messages used for "just-in-
time" resolution - Data link layer sends message
requesting hardware address; destination responds
27
ARP Message Format

28
ARP Message Contents
HARDWARE ADDRESS TYPE = 1 for Ethernet
PROTOCOL ADDRESS TYPE = 0x0800 for IP
OPERATION = 1 for request, 2 for response
Contains both target and sender mappings
from protocol address to hardware address
Request sets hardware address of target to 0
Target can extract hardware address of
sender (saving an ARP request)
Target exchanges sender/target in response29
30
ARP, Bridging and Routing
 ARP is transparent to bridging, since bridging will
propagate ARP broadcasts like any other Ethernet
broadcast, and will transparently bridge the replies.
 A router does not propagate Ethernet broadcasts,
because the router is a Network Level device, and
Ethernet is a Data Link Level protocol. Therefore, an
Internet host must use its routing protocols to select
an appropriate router, that can be reached via
Ethernet ARPs.
 After ARPing for the IP address of the router, the
packet (targeted at some other Destination Address) is
transmitted to the Ethernet address of the router. 31
 Proxy ARP
 Proxy ARP is a technique that is can be used by routers to
handle traffic between hosts that don't expect to use a
router as described above. Probably the most common case
of its use would be the gradual subnetting of a larger
network. Those hosts not yet converted to the new system
would expect to transmit directly to hosts now placed
behind a router.
 A router using Proxy ARP recognizes ARP requests for hosts
on the "other side" of the router that can't reply for
themselves. The router answers for those addresses with
an ARP reply matching the remote IP address with the
router's Ethernet address (in essence, a lie).

32
 Proxy ARP - Problems
Proxy ARP is best thought of as a temporary
transition mechanism, and its use should not be
encouraged as part of a stable solution. There are
a number of potential problems with its use,
including the inability of hosts to fall back on
alternate routers if a network component fails,
and the possibility of race conditions and bizarre
traffic patterns if the bridged and routed network
segments are not clearly delineated.

33
Reverse ARP - RARP
 Sometimes, it is also necessary to find out the IP-address
associated with a given Ethernet address. This happens
when a diskless machine wants to boot from a server on
the network, which is quite a common situation on local
area networks.
 A diskless client, however, has virtually no information
about itself-- except for its Ethernet address! So what it
basically does is broadcast a message containing a plea for
boot servers to tell it its IP-address.
 There's another protocol for this, named Reverse Address
Resolution Protocol, or RARP. Along with the BOOTP
protocol, it serves to define a procedure for bootstrapping
diskless clients over the network.
34