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

 Page 1


Net w ork La y er F orm ula Sheet
Net w ork La y er Resp onsibilities
• F unctions : Logical addressing, routing, pac k et forw arding, fragmen tation/reassem bly .
• P ac k et Deliv ery : End-to-end deliv ery , T
deliv ery
=
?
(T
prop
i
+T
transi
+T
queue
i
) .
• Throughput : S =
L
data
T
total
, where L
data
is pa yload size, T
total
includes propagation, transmission,
and queueing dela ys.
IP A ddressing
• IPv4 A ddress : 32 bits, 2
32
˜ 4.3 billion addresses.
• Class A :
– Range: 1.0.0.0 to 126.255.255.255.
– Net w ork Bits: 8, Host Bits: 24, N
hosts
= 2
24
-2 .
– Subnet Mask: 255.0.0.0 (/8).
• Classful A ddressing : Classes A, B, C, D, E; N
net w orks
= 2
net w ork-bits
, N
hosts
= 2
host-bits
-2 .
• CIDR (Classless In terdomain Routing) :
– Mask: /n , N
hosts
= 2
32-n
-2 .
– Subnet Size: S
subnet
= 2
32-n
.
• IP F ragmen tation :
– F ragmen t Size: L
fragmen t
=MTU , where MTU is maxim um transmission unit.
– Num b er of F ragmen ts: N
fragmen ts
=?
L
pac k et
-H
IP
MTU-H IP
? , where H
IP
= 20 b ytes (I Pv4).
– Offset: O
i
= (i-1)·
MTU-H IP
8
, in 8-b yte units.
A d dress Resolution Proto col (ARP)
• Mapping : IP address (32 b its) to MA C address (48 bits).
• Cac he Hit Time : T
ARP-hit
˜O(1) .
• Cac he Miss Time : T
ARP-miss
=T
broadcast
+T
resp onse
+T
pro c
, t ypically T
ARP-miss
˜ 1-10 ms.
• Cac he Size : S
ARP-cac he
=N
en tries
·(S
IP
+S
MA C
+S
metadata
) .
Dynamic Host Configuration Proto col (DHCP)
• Lease Time : T
lease
, t ypically hours to da ys.
• DHCP T ransaction Time : T
DHCP
=T
DISCO VER
+T
OFFER
+T
REQUEST
+T
A CK
˜ 4·RTT .
• A ddress P o ol Size : N
addresses
= 2
32-n
-N
reserv ed
, where n is subnet mask bits.
In ternet Con trol Message Proto col (ICMP)
• Ping Round-T rip Time : RTT =T
request
+T
resp onse
= 2·T
prop
+T
pro c
.
• Error Rep orting Ov erhead : T
ICMP
=T
generate
+T
trans
, where T
trans
=
L
ICMP
R
, L
ICMP
is ICMP
pac k et size.
• Time-to-Liv e (TTL) : Decremen ts b y 1 p er hop, TTL
max
= 255 .
1
Page 2


Net w ork La y er F orm ula Sheet
Net w ork La y er Resp onsibilities
• F unctions : Logical addressing, routing, pac k et forw arding, fragmen tation/reassem bly .
• P ac k et Deliv ery : End-to-end deliv ery , T
deliv ery
=
?
(T
prop
i
+T
transi
+T
queue
i
) .
• Throughput : S =
L
data
T
total
, where L
data
is pa yload size, T
total
includes propagation, transmission,
and queueing dela ys.
IP A ddressing
• IPv4 A ddress : 32 bits, 2
32
˜ 4.3 billion addresses.
• Class A :
– Range: 1.0.0.0 to 126.255.255.255.
– Net w ork Bits: 8, Host Bits: 24, N
hosts
= 2
24
-2 .
– Subnet Mask: 255.0.0.0 (/8).
• Classful A ddressing : Classes A, B, C, D, E; N
net w orks
= 2
net w ork-bits
, N
hosts
= 2
host-bits
-2 .
• CIDR (Classless In terdomain Routing) :
– Mask: /n , N
hosts
= 2
32-n
-2 .
– Subnet Size: S
subnet
= 2
32-n
.
• IP F ragmen tation :
– F ragmen t Size: L
fragmen t
=MTU , where MTU is maxim um transmission unit.
– Num b er of F ragmen ts: N
fragmen ts
=?
L
pac k et
-H
IP
MTU-H IP
? , where H
IP
= 20 b ytes (I Pv4).
– Offset: O
i
= (i-1)·
MTU-H IP
8
, in 8-b yte units.
A d dress Resolution Proto col (ARP)
• Mapping : IP address (32 b its) to MA C address (48 bits).
• Cac he Hit Time : T
ARP-hit
˜O(1) .
• Cac he Miss Time : T
ARP-miss
=T
broadcast
+T
resp onse
+T
pro c
, t ypically T
ARP-miss
˜ 1-10 ms.
• Cac he Size : S
ARP-cac he
=N
en tries
·(S
IP
+S
MA C
+S
metadata
) .
Dynamic Host Configuration Proto col (DHCP)
• Lease Time : T
lease
, t ypically hours to da ys.
• DHCP T ransaction Time : T
DHCP
=T
DISCO VER
+T
OFFER
+T
REQUEST
+T
A CK
˜ 4·RTT .
• A ddress P o ol Size : N
addresses
= 2
32-n
-N
reserv ed
, where n is subnet mask bits.
In ternet Con trol Message Proto col (ICMP)
• Ping Round-T rip Time : RTT =T
request
+T
resp onse
= 2·T
prop
+T
pro c
.
• Error Rep orting Ov erhead : T
ICMP
=T
generate
+T
trans
, where T
trans
=
L
ICMP
R
, L
ICMP
is ICMP
pac k et size.
• Time-to-Liv e (TTL) : Decremen ts b y 1 p er hop, TTL
max
= 255 .
1
Routing Proto cols (e.g., OSPF)
• OSPF (Op en Shortest P ath First) :
– Link-State Cost: C
link
?
1
Bandwidth
, e.g., C =
10
8
Bandwidth (bps)
.
– Shortest P ath Computation (Dijkstra’s): O(V
2
) or O(E +V logV) , where V is n um b er of
routers, E is n um b er of links.
– Con v ergence Time: T
con v erge
=T
flo o d
+T
compute
, t ypically T
con v erge
˜ 1-10 s.
• Routing T able Size : S
table
=N
routes
·(S
destination
+S
next-hop
+S
metadata
) .
• P ath Length : L
path
=
?
C
linki
, where C
linki
is cost of link i .
P ac k et F orw arding
• F orw arding Dela y : T
forw ard
=T
lo okup
+T
queue
+T
trans
, where T
lo o kup
˜O(logN
routes
) .
• Queueing Dela y : T
queue
=
Q size
µ
, where Q
size
is queue length, µ is service rate (pac k ets/s).
• T ransmission Dela y : T
trans
=
L
pac k et
R
, where R is link bandwidth.
P erformance Metrics
• Round-T rip Time (R TT) : RTT = 2·T
prop
+T
trans
+T
queue
+T
pro c
.
• Throughput : S =
L
effectiv e
T
total
, where L
effectiv e
excludes headers.
• P ac k et Loss Probabilit y : P
loss
= 1-(1-P
link-loss
)
N
hops
, where P
link-loss
is p er-link loss proba-
bilit y .
• Latency : T
latency
=
?
N
i=1
(T
prop
i
+T
transi
+T
queue
i
+T
pro c
i
) , where N is n um b er of hops.
• Jitter : s
dela y
=
v
1
n
?
n
i=1
(d
i
-d)
2
, where d
i
is pac k et dela y , d is mean dela y .
2