Formula Sheets: Data Link Layer | Computer Networks - Computer Science Engineering (CSE) PDF Download

 Page 1


Data Link La y er F orm ula Sheet
Link La y er Services
• F unctions : F raming, error detection/correction, flo w con trol, media access con trol (MA C).
• Sub-la y ers :
– Logical Link Con trol (LLC): Handles flo w con trol, error con trol, m ultiplexing.
– Media A ccess Con trol (MA C): Manages access to shared medium.
F raming
• Fixed-Length F rames : F rame size = L bits.
• V ariable-Length F rames :
– Bit Stu?ing: Insert 0 after fiv e consecutiv e 1s (e.g., HDLC).
– Byte Stu?ing: Use FLA G (0x7E), ESC (0x7D) for delimiting.
• F rame Ov erhead : O
frame
=
H
L+H
, where H is header size, L is pa yload size.
Flo w Con trol Proto cols
• Stop-and-W ait Proto col :
– Throughput: S =
L
RTT+T trans
, where L is frame size, RTT is round-trip time, T
trans
=
L
R
, R
is data rate.
– E?iciency: ? =
1-P error
1+2a
, where a =
T prop
T trans
, T
prop
is propagation dela y , P
error
is frame error
probabilit y .
• Sliding Windo w Proto col :
– Windo w Size: W = 2
n
- 1 (Selectiv e Rep eat), W = 2
n
(Go-Bac k-N), where n is sequence
n um b er bits.
– E?iciency (Go-Bac k-N): ? =
1-P error
1+2a·P error
.
– E?iciency (Selectiv e Rep eat): ? ˜ 1-P
error
(for large W ).
Error Detection and Correction
• P arit y Chec k : Detects single-bit errors, P
detect
= 1 for o dd n um b er of errors.
• Cyclic Redundancy Chec k (CR C) :
– Generator p olynomial degree k : Detects all burst errors of length =k .
– Detection Probabilit y: P
detect
= 1-
1
2
k
.
• Hamming Co de :
– P arit y Bits: r , where 2
r
=m+r +1 , m is data bits.
– Hamming Distance: d
min
= 3 (corrects 1-bit errors).
– Error Correction Capabilit y: t =?
d min-1
2
? .
• Chec ksum: 1’s complemen t sum of 16-bit w ords, P
detect
dep ends on error pattern.
1
Page 2


Data Link La y er F orm ula Sheet
Link La y er Services
• F unctions : F raming, error detection/correction, flo w con trol, media access con trol (MA C).
• Sub-la y ers :
– Logical Link Con trol (LLC): Handles flo w con trol, error con trol, m ultiplexing.
– Media A ccess Con trol (MA C): Manages access to shared medium.
F raming
• Fixed-Length F rames : F rame size = L bits.
• V ariable-Length F rames :
– Bit Stu?ing: Insert 0 after fiv e consecutiv e 1s (e.g., HDLC).
– Byte Stu?ing: Use FLA G (0x7E), ESC (0x7D) for delimiting.
• F rame Ov erhead : O
frame
=
H
L+H
, where H is header size, L is pa yload size.
Flo w Con trol Proto cols
• Stop-and-W ait Proto col :
– Throughput: S =
L
RTT+T trans
, where L is frame size, RTT is round-trip time, T
trans
=
L
R
, R
is data rate.
– E?iciency: ? =
1-P error
1+2a
, where a =
T prop
T trans
, T
prop
is propagation dela y , P
error
is frame error
probabilit y .
• Sliding Windo w Proto col :
– Windo w Size: W = 2
n
- 1 (Selectiv e Rep eat), W = 2
n
(Go-Bac k-N), where n is sequence
n um b er bits.
– E?iciency (Go-Bac k-N): ? =
1-P error
1+2a·P error
.
– E?iciency (Selectiv e Rep eat): ? ˜ 1-P
error
(for large W ).
Error Detection and Correction
• P arit y Chec k : Detects single-bit errors, P
detect
= 1 for o dd n um b er of errors.
• Cyclic Redundancy Chec k (CR C) :
– Generator p olynomial degree k : Detects all burst errors of length =k .
– Detection Probabilit y: P
detect
= 1-
1
2
k
.
• Hamming Co de :
– P arit y Bits: r , where 2
r
=m+r +1 , m is data bits.
– Hamming Distance: d
min
= 3 (corrects 1-bit errors).
– Error Correction Capabilit y: t =?
d min-1
2
? .
• Chec ksum: 1’s complemen t sum of 16-bit w ords, P
detect
dep ends on error pattern.
1
Media A ccess Con trol (MA C) Proto cols
• Pure Aloha :
– Throughput: S =Ge
-2G
, where G is offered load (frames p er frame time).
– Max Throughput: S
max
= 0.184 at G = 0.5 .
• Slotted Aloha :
– Throughput: S =Ge
-G
.
– Max Throughput: S
max
= 0.368 at G = 1 .
• CSMA/CD (Carrier Sense Multiple A ccess with Collision Det ection) :
– E?iciency: ? ˜
1
1+5a
, where a =
T prop
T trans
.
– Minim um F rame Size: L
min
= 2·T
prop
·R .
• CSMA/CA (Collision A v oidance) :
– Con ten tion Windo w: CW ? [CW
min
,CW
max
] , doubles after collision.
– Bac k off Time: T
bac k off
= random(0,CW)·T
slot
.
Ethernet (IEEE 802.3)
• F rame F ormat : Pream ble (7 b ytes) + SFD (1 b yte) + Dest MA C (6 b ytes) + Src MA C (6 b ytes)
+ T yp e (2 b ytes) + Data (46-1500 b ytes) + CR C (4 b ytes).
• Minim um F rame Size : 64 b ytes (ensures collision detection).
• Throughput : ? =
L
data
L
data
+L
o v erhead
+T
IFS
·R
, where T
IFS
is in terframe space.
• Binary Exp onen tial Bac k off : After k -th collision, w ait random time in [0,2
k
-1] slots, k = 10 .
Wireless LANs (IEEE 802.11)
• DCF (Distributed Co ordination F unction) : Uses CSMA/CA with R TS/CTS.
• Throughput : S =
L
data
T
data
+T
DIFS
+T
SIFS
+T
R TS
+T
CTS
+T
A CK
, where DIFS/SIFS are in terframe spaces.
• R TS/CTS Ov erhead : T
R TS/CTS
=T
R TS
+T
CTS
+2·T
SIFS
.
• Hidden T erminal Solution : R TS/CTS reduces collision probabilit y .
Switc hing and Bridging
• Learning Bridge : Up dates MA C table, T
learn
=O(1) p er frame.
• Spanning T ree Proto col (STP) :
– P ath Cost: C =
?
C
link
, in v ersely prop ortional to bandwidth.
– Con v ergence Time: T
STP
=T
listen
+T
learn
, t ypically 30-50s.
• F orw arding Dela y : T
forw ard
=T
queue
+T
switc h
.
P erformance Metrics
• Round-T rip Time (R TT) : RTT = 2·T
prop
+T
trans
+T
queue
.
• Throughput : S =
L
effectiv e
T
total
, where L
effectiv e
excludes o v erhead.
• F rame Error Rate (FER) :P
FER
= 1-(1-P
bit
)
L
, whereP
bit
is bit error rate,L is frame length.
• Latency : T
latency
=T
prop
+T
trans
+T
queue
+T
pro c
.
2