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

 Page 1


Routing F orm ula Sheet
Routing Ov erview
• F unction : Determines optimal path for pac k et deliv ery across net w orks.
• Routing T able Size : S
table
= N
routes
· (S
dest
+S
next-hop
+S
metric
) , where S
dest
is destination
address size (e.g., 4 b ytes for IPv4).
• P ath Cost : C
path
=
?
C
linki
, whereC
linki
is cost of linki (e.g., hop coun t, bandwidth-based).
• F orw arding Dela y : T
forw ard
=T
lo okup
+T
queue
+T
trans
, whereT
lo oku p
˜O(logN
routes
) .
Routing Infor mation Proto col (RIP)
• Distance V ector Proto col : Uses hop c oun t as metric,C
link
= 1 , max hops = 15.
• Up date In terv al : T
up date
= 30 s (default).
• Con v ergence Time : T
con v erge
˜O(N·T
up date
) , whereN is n um b er of routers.
• Message Size : S
RIP
= 4+N
en tries
·20 b ytes (RIP v2, up to 25 en tries).
• Coun t-to-Infinit y Problem : Mitigated b y split horizon, route p ois oning,T
timeout
= 180 s.
Op en Shor test P ath First (OSPF)
• Link-State Proto col : Uses Dijkstra’s algorithm for shortest path.
• Link Cost : C
link
=
10
8
Bandwidth (bps)
, adjustable b y net w ork admin.
• Shortest P ath Computation Time : O(V
2
) orO(E +V logV) , whereV 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 1-10 s .
• Link-State A dv ertisemen t (LSA) Size : S
LSA
˜ 20+S
link-info
, v aries b y LSA t yp e.
• Area Hierarc h y : Reduces routing o v erhead,N
routers
=
?
N
areai
.
Border Gatew a y Proto col (BGP)
• P ath V ector Proto col : Main tains path attributes (e.g., AS path).
• Up date Message Size : S
BGP
=S
header
+S
path-attributes
+S
NLRI
, t ypically 100-1000 b ytes.
• Con v ergence Time : T
con v erge
˜ O(M·N
AS
) , where M is n um b er of routes, N
AS
is n um b er of
autonomous systems.
• P ath Selection : Prefers shortest AS path,C
path
=N
AS-hops
, or lo cal preference.
• Keep-Aliv e In terv al : T
k eep-aliv e
= 60 s (default), hold time = 3·T
k eep-aliv e
.
Multicast Routing
• Distance V ector Multicast Routing Proto col (D VMRP) :
– Rev erse P ath F orw arding (RPF): A ccepts pac k et if incoming in terface is on shortest path to
source.
– Pruning Time: T
prune
?N
leaf-no des
, reduces unnecessary tra?ic.
– T ree Cost: C
tree
=
?
C
linki
for links in m ulticast tree.
• Proto col Indep enden t Multicast (PIM) :
– Dense Mo de: Flo o d-and-prune, similar to D VMRP ,T
flo o d
˜O(N
routers
) .
1
Page 2


Routing F orm ula Sheet
Routing Ov erview
• F unction : Determines optimal path for pac k et deliv ery across net w orks.
• Routing T able Size : S
table
= N
routes
· (S
dest
+S
next-hop
+S
metric
) , where S
dest
is destination
address size (e.g., 4 b ytes for IPv4).
• P ath Cost : C
path
=
?
C
linki
, whereC
linki
is cost of linki (e.g., hop coun t, bandwidth-based).
• F orw arding Dela y : T
forw ard
=T
lo okup
+T
queue
+T
trans
, whereT
lo oku p
˜O(logN
routes
) .
Routing Infor mation Proto col (RIP)
• Distance V ector Proto col : Uses hop c oun t as metric,C
link
= 1 , max hops = 15.
• Up date In terv al : T
up date
= 30 s (default).
• Con v ergence Time : T
con v erge
˜O(N·T
up date
) , whereN is n um b er of routers.
• Message Size : S
RIP
= 4+N
en tries
·20 b ytes (RIP v2, up to 25 en tries).
• Coun t-to-Infinit y Problem : Mitigated b y split horizon, route p ois oning,T
timeout
= 180 s.
Op en Shor test P ath First (OSPF)
• Link-State Proto col : Uses Dijkstra’s algorithm for shortest path.
• Link Cost : C
link
=
10
8
Bandwidth (bps)
, adjustable b y net w ork admin.
• Shortest P ath Computation Time : O(V
2
) orO(E +V logV) , whereV 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 1-10 s .
• Link-State A dv ertisemen t (LSA) Size : S
LSA
˜ 20+S
link-info
, v aries b y LSA t yp e.
• Area Hierarc h y : Reduces routing o v erhead,N
routers
=
?
N
areai
.
Border Gatew a y Proto col (BGP)
• P ath V ector Proto col : Main tains path attributes (e.g., AS path).
• Up date Message Size : S
BGP
=S
header
+S
path-attributes
+S
NLRI
, t ypically 100-1000 b ytes.
• Con v ergence Time : T
con v erge
˜ O(M·N
AS
) , where M is n um b er of routes, N
AS
is n um b er of
autonomous systems.
• P ath Selection : Prefers shortest AS path,C
path
=N
AS-hops
, or lo cal preference.
• Keep-Aliv e In terv al : T
k eep-aliv e
= 60 s (default), hold time = 3·T
k eep-aliv e
.
Multicast Routing
• Distance V ector Multicast Routing Proto col (D VMRP) :
– Rev erse P ath F orw arding (RPF): A ccepts pac k et if incoming in terface is on shortest path to
source.
– Pruning Time: T
prune
?N
leaf-no des
, reduces unnecessary tra?ic.
– T ree Cost: C
tree
=
?
C
linki
for links in m ulticast tree.
• Proto col Indep enden t Multicast (PIM) :
– Dense Mo de: Flo o d-and-prune, similar to D VMRP ,T
flo o d
˜O(N
routers
) .
1
– Sparse Mo de: Uses rendezv ous p oin t (RP),T
join
=T
RP-register
+T
tree-build
.
– Group Size: N
group
= 2
28
(m ulticast address range in IPv4).
• Multicast T ree Size : S
tree
=N
no des
·S
state
, whereS
state
is p er-group state (e.g., 100-500 b ytes).
IP Routing Metrics
• Hop Coun t : C
path
=N
hops
, used b y RIP .
• Bandwidth-Based Cost : C
link
=
K
Bandwidth
, whereK is constan t (e.g., 10
8
for OSPF).
• Dela y-Based Cost : C
link
=T
prop
+T
queue
, used in some dynamic routing.
• Load-Based Cost : C
link
?
Q curren t
Q max
, whereQ is queue length.
P ac k et F orw arding
• Lo okup Time : T
lo okup
˜O(logN
routes
) with trie orO(1) with TCAM.
• T ransmission Dela y : T
trans
=
L
pac k et
R
, whereR is link bandwidth.
• Queueing Dela y : T
queue
=
Q size
µ
, whereµ is service rate (pac k ets/s).
• T otal F orw arding Dela y : T
forw ard
=T
lo okup
+T
queue
+T
trans
.
IPv6 Routing
• A ddress Space : 2
128
addresses,N
prefixes
«N
IPv4-prefixes
due to aggre gation.
• Header Size : H
IPv6
= 40 b ytes (fixed).
• Routing T able E?iciency : S
IPv6-table
<S
IPv4-table
due to hierarc hical addressing.
• Next-Hop Resolution : Same as IPv4, uses Neigh b or Disco v ery Proto col (NDP),T
NDP
˜T
ARP
.
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
, whereL
effectiv e
excludes headers.
• P ac k et Loss Probabilit y : P
loss
= 1-(1-P
link-loss
)
N
hops
, whereP
link-loss
is p er-link loss proba-
bilit y .
• Jitter : s
dela y
=
v
1
n
?
n
i=1
(d
i
-d)
2
, whered
i
is pac k et dela y ,d is mean dela y .
• Con v ergence Dela y : T
con v erge
=T
detect
+T
propagate
+T
compute
, v aries b y proto col.
2