Datalink Layer - Computer Networks Theory
The data link layer transforms the physical layer, a raw transmission facility, to a reliable link and is responsible for node-to-node delivery
Hop to Hop/Node to Node delivery
Data Link works within a network => Communication between 2 or more person within a LAN
Responsible for sending message to next Router/Node/Hop
Framing/Packeting
Need to pack each bits into Frames, so that each Frames is distinguishable from another
Fixed-Size Framing
Variable-Size Framing
Types
Byte/Character Stuffing
Character-oriented Protocol => FlagDataFlag
To send Flag as data => FlagAEscFlagCFlag
Bit Stuffing
Flow Control
Set of procedures used to restrict the amount of data that sender can send before waiting for acknowledgement => With too many messages Router will need to control the Flow at every Node
Methods/Algorithms
Simplest => For noiseless channel (Ideal condition)
Stop and Wait
Sends a Frame and Waits till conformation is received, then sends next Frame
Window Size = 1 => Can send/receive only 1 message at a time
Sequence Number (SN) = 2 (010101...) => Represented by 0 & 1 in this case, Used to differentiate each Frames, Sender will send the SN of Frame that it is sending and Receiver will respond with the SN of next expecting Frame, If SN doesn't match then message is sent again
Available SN = Window Size of Sender + Window Size of Receiver
Time-out => Waiting time in case of no Frame/Conformation received, The same Frame/Conformation is resend
Efficiency = TT/(TT + RTT) => Round Trip Time (RTT) = 2*PD, TT = L/R
Go back N
Window Size = N => Sender = 2m - 1, Receiver = 1, where "m" is the total no. of bits required to represent SN
Sender sends no. of Frames less than its Window Size at a time and Receiver receives it one by one
Doesn't accept out of order Packets, Only in sequence
Selective Repeat
Window Size => Sender & Receiver = 2m-1
Sender sends no. of Frames equal to its Window Size at a time
Accepts out of order Packets
Receiver can also send negative acknowledgement
Error Control
Theory
Detecting error in this Layer instead of Destination is more efficient
Redundancy => Adding extra bits for detecting errors at the destination
Types
Single bit error
Burst error
Length of error => Lents from 1 bit change to last
Total no. of bits changed = Bandwidth * Time Duration of Error
Error Detection (Based on Redundancy)
Simple Parity (Even/Odd)
Size = m (Message Bits) + 1
Least expensive
Even Parity => No. of 1 should be even
Can detect all single bit error
Can detect all odd no. of error
Minimum Hamming Distance = n => It can detect (n-1) bit error
Hamming Distance = No. of 1 after XOR operation of 2 codes
2D Parity Check
Checksum (Transport Layer)
Cyclic Redundancy Check (CRC)
Based on Binary division
Total Bits = m (Message) + r (Redundant)
Can detect all odd errors, Single bit, Burst error of length equal to polynomial degree
Redundant 0 bits = Degree of Polynomial = No. of Divisor bits - 1
Find divisor by taking the coefficient of Polynomial
Do XOR operation starting from 1st 1 and find the Remainder
Replace the Redundant bits with the Remainder counting from LSB and send the message
Receiver will also perform same division and if remainder is 0 then message is correct
Error Correction
When an error is discovered, the receiver can have the sender retransmit the entire data unit
Hamming Code
Parity Bits are at positions 2n , rest Data bits
Calculate Pi by doing XOR operation between first starting from ith bit then taking next 2i bits and leaving next 2i bits
Send the message
Receiver will perform the same operation to find error
If error then redundant bits will give the position of error
Connections
Point to Point
Devices are connected through a dedicated link
Eg = PPP
Sub-layers of Data Link Layer
Logical Link Control (LLC)
Multiple Access Protocols (MAC)
Logical Link Control (LLC)
To control link when sending data from sender to receiver => To synchronize frames, To detect error & correct, Flow control, data transmit
Multiple/Media Access Protocols (MAC)
The link between the devices are shared => Not in case of Point to Point
Makes sure that only 1 sends message and others receive at a time => Control collision
Types
Random Access
Controlled Access
Channelization Protocols
Random Access
Priority is random, Anyone can send data anytime, Any amount of Data can be send
Types
Aloha => Pure & Slotted => Vulnerable Time, Throughput
CSMA => Vulnerable Time, Efficiency, Transmission Time, Propagation Time
CSMA/CD (Ethernet) => Collision Detection
CSMA/CA => Collision Avoidance
Controlled Access
Controlled Authority (Station)
Types
Polling => Efficiency, Throughput
Token Passing => Token Ring
Channelization Protocols
Using proper channel
Types
FDMA => Diving frequency band in fix channel
TDMA => Diving based on time
Pure Aloha
Any station can start transmission at any time => Collision possible
Acknowledgement there => If collision occurs than no response is sent by the receiver, then retransmission
Backoff Method => To reduce collision during retransmission
LAN based
Only transmission time (fixed), No propagation time
Vulnerable Time = 2 x TT
Time when no other station can send message to avoid collision
Transmission Time = Message/Bandwidth
Efficiency (η) = G x e-2G
G is the number of station that want to transmit the data during TT
η highest when G = 1/2
ηmax = 18.4%
Slotted Aloha
Time is divided into slots, slot size is equal to TT
Transmission will start from the beginning of the slot
Collision possible when more than 1 station start transmission at the beginning of the slot
Vulnerable Time = TT
As no other transmission can start from the slot from any other place, if one is already started from the beginning
Efficiency (η) = G x e-G
η highest when G = 1
ηmax = 36.8%
Carrier Sensor Multiple Access (CSMA)
Senses the carrier before sending the data => Transmitter will check the medium/sense if already some data is moving
Transmitter will only check the point connecting it to medium, not the entire medium
Used in Ethernet
Types
1-persistent
0-persistent
p-persistent
1-persistent
Continuously senses/checks till it gets idle and sends the data
In worst case all will send the data immediately medium becomes idle leading to collision
0-persistent
Checks after a random amount of time till it gets idle and sends the data
Collision less but in waiting period more as the medium may get idle during waiting time
p-persistent
Continuously senses/checks till it gets idle and sends the data based on some probability value
Carrier Sensor Multiple Access/Collision Detection (CSMA/CD)
No acknowledgement system
First the transmitter loads bits on the channel, them signal moves/propagate and goes the every address, required address will accept the signal
If the transmitter receives collision signal while it is transmitting then it gets to know that collision happened
Ideally energy received by the transmitter tells about collision but energy gets reduced over time
To be able to judge collision, Worst case => Transmission Time (TT) ≥ 2 x Propagation Delay (PD)
L ≥ 2 x PD x BD
ɳ = 1/1 + 6.44a, where a = PD/TT
Carrier Sensor Multiple Access/Collision Avoidance (CSMA/CA)
Used in Wireless LAN (WLAN), Wi-fi, IEE 802.11
Inter Frame Space (IFS)
Distributed Coordination Function (DCF)
Ready to Send (RTS) Signal
Clear to Send (CTS) Signal
Ethernet Frame Format (IEEE 802.3)
Based on LAN
Uses CSME/CD
Types
10 Base 2 => Thin
10 Base 5 => Thick
10 Base T
100 Base Fix => Fast
10G Base T => Gigabit
Topology => Bus, Star
Bit Rate => 1 Mb/sec - 400 Gb/sec
Frame Format
PREAMBLE & SFD bits in 1010....10 format, Added by Physical layer, For alerting the receiver
Destination Address (DA) => MAC => Contains physical address of the next node, known by ARP packet
Source Address (SA) => Contains physical address of the source node
DATA => Pure data should be of at least 46 B, maximum 1500 B
Cyclic Redundancy Check (CRC)
Token Ring (IEEE 802.5)
Ring topology is used
Access control method used is token passing => Transmitter will catch token before sending data and release it after process is done
Early token release => Token released after data is sent
Delayed token release => Token released after data is received after going through full circle
Token ring is unidirectional
Data rate used is 4 Mbps & 16 Mbps
Piggybacking acknowledgement is used
Acknowledgement sent with data
Differential Manchester encoding is used
Variable size framing
Monitor station is used
To remove frames that is corrupted
Frame Format for Data
Start Delimiter (SD) => Used for alert/synchronization
Access Control (AC) => Used for priority/result bit/token present
Frame Control (FC) => Frame sent is data or control frame
Destination Address (DA)
Source Address (SA)
DATA => Minimum size can be 0, maximum depends on Token Holding Time (THT)
Cyclic Redundancy Check (CRC)
End Delimiter (SD)
Frame Status (FS)
Frame Format for Token
Start Delimiter (SD)
Access Control (AC)
End Delimiter (SD)
Physical Address (MAC) - Addressing
