Routing

wangth (2018-2021, CC BY-SA)

? (2009-2017)
國立陽明交通大學資工系資訊中心
Computer Center of Department of Computer Science, NYCU
1
Why dynamic route ? (1)
● Static route is ok only when
○ Network is small
○ There is a single connection point to other network
○ No redundant route

只有單一網路連結， X 公司 網際網路
不需要路徑選擇更新

A
192.34.56.0
點對點電路 B
交換的連接 A B C

支幹 (Stub)網路 10.1.0.0

2
Why dynamic route ? (2)
● Dynamic Routing
○ Routers update their routing table with the information of adjacent
routers
○ Dynamic routing need a routing protocol for such communication
○ Advantage
■ They can react and adapt to changing network condition

A B

D C

3
Routing Protocol
● Used to change the routing table according to various routing
information
○ Specify detail of communication between routers
○ Specify information changed in each communication
■ Network reachability
■ Network state
■ Metric
● Metric
○ A measure of how good a particular route
■ Hop count, bandwidth, delay, load, reliability, …
● Each routing protocol may use different metric and exchange different
information
4
Autonomous System
● Autonomous System (AS)
○ Internet is organized into a collection of autonomous system
○ An AS is a collection of networks with same routing policy
■ Single routing protocol
■ Normally administered by a single entity
● Corporation or university campus
■ All depend on how you want to manage routing
Peering

AS 100
AS 100 AS 101

AS 102

5
Category of Routing Protocols – by AS
● AS-AS communication
○ Communications between routers in different AS
○ Interdomain routing protocols
○ Exterior gateway protocols (EGP)
○ Ex:
■ BGP (Border Gateway Protocol)
● Inside AS communication
○ Communication between routers in the same AS
○ Intradomain routing protocols Peering

○ Interior gateway protocols (IGP)

AS 100 AS 101
○ Ex:
■ RIP (Routing Information Protocol)
■ IGRP (Interior Gateway Routing Protocol)
AS 102
■ OSPF (Open Shortest Path First Protocol)
6
Intra-AS and Inter-AS routing
Inter-AS routing
C.b between A and B

B.a Host
b A.a h2
A.c
a c
C
a b
a B
c
d
Host A
h1 b

Intra-AS routing
within AS A Intra-AS Intra-AS network layer
routing routing
algorithm algorithm
Inter-AS, Intra- link layer
AS routing in ROUTING
physical layer
gateway A.c TABLE

DL DL DL
to/from A.b to/from B.a
PHY PHY PHY
to/from A.d
7
Category of Routing Protocols –
by information changed (1)
● Distance-Vector Protocol
○ Message contains a vector of distances, which is the cost to other
network
○ Each router updates its routing table based on these messages
received from neighbors
○ Protocols W X Y Z

■ RIP
A B C
■ IGRP
■ BGP Routing Table of A Routing Table of B Routing Table of C

W ← 0 X ← 0 Y ← 0

X → 0 Y → 0 Z → 0

Y → 1 Z → 1 W ← 1

Z → 2 W ← 1 W ← 1
8
Category of Routing Protocols –
by information changed (2)
● Link-State Protocol
○ Broadcast their link state to neighbors and build a complete network
map at each router using Dijkstra algorithm
○ Protocol
■ OSPF W X Y Z

A B C

Routing Table of A Routing Table of B Routing Table of C

W ← 0 X ← 0 Y ← 0

X → 0 Y → 0 Z → 0

SPF 結構樹 SPF 結構樹 SPF 結構樹

9
Difference between
Distance-Vector and Link-State
● Difference
Distance-Vector Link-State
Update Updates neighbor Update all nodes
(propagate new info.)
Convergence Propagation delay Fast convergence
cause slow convergence
Complexity Simple Complex
更新此路由
● Information update sequence 表的程序

更新此路由 更新此路由
表的程序 表的程序 B 更新此路由
表的程序
鍊結狀態更新
中的拓樸改變
A 路由器送出此 B
B 更新過的路由表 A 更新此路由
表的程序

拓樸改變導致
Distance-Vector 路由表更新 Link-State B
10
Routing Protocols
RIP IGP,DV
IGRP IGP,DV
OSPF IGP,LS
BGP EGP
國立陽明交通大學資工系資訊中心
Computer Center of Department of Computer Science, NYCU
11
RIP
● RIP
○ Routing Information Protocol
● Category
○ Interior routing protocol
○ Distance-vector routing protocol
■ Using “hop-count” as the cost metric
● Example of how RIP advertisements work
Destination Next router # of hops to Destination Next router # of hops to Destination Next router # of hops to
network destination network destination network destination

1 A 2 30 C 4 1 A 2
20 B 2 1 -- 1 20 B 2
30 B 7 10 -- 1 30 A 5
Routing table in router before Advertisement from router A Routing table after
Receiving advertisement receiving advertisement 12
RIP - Example
● Another Example

N2 = 1 hop

N1

ends up with a route to N3

through R2 with hop count to 2 R1
N3 = 1 hop

N2

N2 = 1 hop ends up with a route to N1

R1 through R1 with hop count to 2

N3

N2 = 1 hop

13
RIP – Message Format
● RIP message is carried in UDP datagram
○ Command: 1 for request and 2 for reply
○ Version: 1 or 2 (RIP-2)
0 15 16 31
command (1-6) version (1) (must be zero)

address family (2) (must be zero) 20 bytes per

route entry
32-bit IP address

(must be zero) 20
bytes
(must be zero)

metric (1-16)

(up to 24 more routes, with same format as previous 20 bytes)

14
RIP – Operation
● routed – RIP routing daemon
○ Operated in UDP port 520
● Operation
○ Initialization
■ Probe each interface
■ send a request packet out each interface, asking for other router’s complete routing table
○ Request received
■ Send the entire routing table to the requestor
○ Response received
■ Add, modify, delete to update routing table
○ Regular routing updates
■ Router sends out their routing table to every neighbor every 30 seconds
○ Triggered updates
■ Whenever a route entry’s metric change, send out those changed part routing table
15
RIP – Problems of RIP
● Issues
○ 15 hop-count limits
○ Take long time to stabilize after the failure of a router or link
○ No CIDR
0 15 16 3
● RIP-2 command (1-6) version (2) routering domain
1
○ EGP support
address family (2) route tag
■ AS number
○ CIDR support 32-bit IP address

32-bit subnet mask 20

bytes
32-bit next-hop IP address

metric (1-16)

(up to 24 more routes, with same format as previous 20 bytes)

16
IGRP (1)
● IGRP – Interior Gateway Routing Protocol
● Similar to RIP
○ Interior routing protocol
○ Distance-vector routing protocol
● Difference between RIP
○ Complex cost metric other than hop count
■ delay time, bandwidth, load, reliability
■ The formula

○ Use TCP to communicate routing information

○ Cisco System’s proprietary routing protocol 17
IGRP (2)
● Advantage over RIP
○ Control over metrics
● Disadvantage
○ Still classful and has propagation delay

18
OSPF (1)
● OSPF
○ Open Shortest Path First
● Category
○ Interior routing protocol
○ Link-State protocol
● Each interface is associated with a cost
○ Generally assigned manually
○ The sum of all costs along a path is the metric for that path
● Neighbor information is broadcast to all routers
○ Each router will construct a map of network topology
○ Each router run Dijkstra algorithm to construct the shortest path tree to
each routers
19
OSPF – Dijkstra Algorithm
● Single Source Shortest Path Problem
○ Dijkstra algorithm use “greedy” strategy
○ Ex: t x t x t x
1 1 1
8
8

8
10 14
10 10 10
9 9 9
s 0 2 3 4 6 s 0 2 3 4 6 s 0 2 3 4 6
7 7 7
5 5 5
5 5 7

8
8

2 2 2
y z y z y z
(a) (b) (c)

t x t x t x
1 1 1
8 13 8 9 8 9
10 10 10
9 9 9
0 2 3 4 6 0 2 3 4 6 0 2 3 4 6
7 7 7
5 5 5
5 7 5 7 5 7
2 2 2
y z y z y z
(d) (e) (f) 20
OSPF – Routing table update example (1)

21
OSPF – Routing table update example (2)

22
OSPF – Summary
● Advantage
○ Fast convergence
○ CIDR support
○ Multiple routing table entries for single destination, each for one
type-of-service
■ Load balancing when cost are equal among several routes
● Disadvantage
○ Large computation

23
BGP
● BGP
○ Border Gateway Protocol
● Exterior routing protocol
○ Now BGP-4
○ Exchange network reachability information with other BGP systems
● Routing information exchange
○ Message:
■ Full path of autonomous systems that traffic must transit to reach destination
■ Can maintain multiple route for a single destination
○ Exchange method
■ Using TCP
■ Initial: entire routing table
■ Subsequent update: only sent when necessary
■ Advertise only optimal path
● Route selection
○ Shortest AS path
24
BGP – Operation Example
● How BGP work
○ The whole Internet is a graph of autonomous systems
○ X ＝> Z
■ Original: X ＝> A ＝> B ＝> C ＝> Z
■ X advertise this best path to his neighbor W
○ W ＝> Z
■ W ＝> X ＝> A ＝> B ＝> C ＝> Z

A B C A B C
X Z

25
Routing Protocols Comparison

RIP IGRP OSPF BGP4

DV or LS DV DV LS Path Vec

TCP/UDP & Port U-520 IP-9 T-89 T-179

Classless No No Yes Yes

Updates Per. Per. Both Trig.

Load Balance No Yes Yes No

Internal / External Int. Int. Int. Ext.

Metric Hop Count Load Errors Delay Sum of Int. Cost Short. AS Path
Bandwidth

26
routed

國立陽明交通大學資工系資訊中心
Computer Center of Department of Computer Science, NYCU
27
routed
● Routing daemon
○ Speak RIP (v1 and v2)
○ Supplied with most every version of UNIX
○ Two modes
■ Server mode (-s) & Quiet mode (-q)
■ Both listen for broadcast, but server will distribute their information
○ routed will add its discovered routes to kernel’s routing table
○ Support configuration file - /etc/gateways
■ Provide static information for initial routing table

28