Unicast Routing Protocols

Acute Communication Corp.

Edward Jin-Ru Chen
jzchen@[Link]

Edward Jin-Ru Chen Acute Unicast Routing

1
 Content

 Introduction
 Algorithms
Distance Vector, Link State and Hybrid
 Routing Protocols
RIP, OSPF, IGRP, EIGRP and BGP
 Testing Issue

Edward Jin-Ru Chen Acute Unicast Routing

2
 Roles in the Protocol Stack

 OSI seven layers

Physical, Data link, Network, Transport, Session,
Presentation and Application
 Network layer
Provides upper layers with independence from the data
transmission and switching technologies used to connect
systems
Performs switching and routing function
Such as Internet Protocol (IP)

Edward Jin-Ru Chen Acute Unicast Routing

3
 IP Version 4 Header
Format
Version Length TOS Total Length

Identification flag Fragment Offset

TTL Protocol Header Checksum

Source IP address

Destination IP address

Options… Padding…

Edward Jin-Ru Chen Acute Unicast Routing

4
 IP Address

 IPv4 defines a 32-bit address space

 Each host contains unique address
 Divide into network space and host space

Edward Jin-Ru Chen Acute Unicast Routing

5
 IP Subnet

 Divide the subnet into class A, B or C

 Using subnet mask to represent the network
portion of the IP address
 Can use classless subnet (only depend on the
subnet mask)

Edward Jin-Ru Chen Acute Unicast Routing

6
 Autonomous System (AS)

Edward Jin-Ru Chen Acute Unicast Routing

7
 AS (II)

 Each AS has unique 16-bit number

 Inside the autonomous system using the identical
interior or intra-domain routing protocol
Such as RIP, OSPF
 Outside the autonomous system, using the exterior
or inter-domain routing protocol
Such as BGP

Edward Jin-Ru Chen Acute Unicast Routing

8
 What Is Routing?

6
2
3
1
5

Edward Jin-Ru Chen Acute Unicast Routing

9
 Why Routing Protocol?

 Static Route VS Dynamic Route

 Find the way automatically

Edward Jin-Ru Chen Acute Unicast Routing

10
 Default Route

 Static route for unknown destination

 [Link] at RIP

Edward Jin-Ru Chen Acute Unicast Routing

11
 Switch VS Protocol

 Cooperation between protocol engine and

forwarding engine
 Protocol engine
Used to be real-time OS working over processor
 Forwarding engine
ASIC
FPGA
ASIC with embedded micro-processor

Edward Jin-Ru Chen Acute Unicast Routing

12
 Switch VS Protocol (II)

 Protocol engine decide the forwarding port and

tell the forwarding engine
 Forwarding engine just follow the known
information to forwarding the multicast packet
 Address search
Best match (or longest match)
Best match cooperate with cache (exactly match)
Exactly match

Edward Jin-Ru Chen Acute Unicast Routing

13
 Routing Algorithms

 Distance Vector
 Link State
 Combination of upper two classes

Edward Jin-Ru Chen Acute Unicast Routing

14
 Distance Vector

 Provide the route sign

 All propagated routing information are processed
after collected
 Keep and use the processed information
 Such as Routing Information Protocol

Edward Jin-Ru Chen Acute Unicast Routing

15
 Example of Distance Vector
A
Target Next Hop Metric Time
B Direct 1 1
C Direct 1 1
B C D B 2 2
E C 2 2 Target Next Hop Metric Time
B Direct 1 1
E Direct 1 1
D E Target Next Hop Metric Time
C E 2 2
A B 2 2
A Direct 1 1
C Direct 1 1
D Direct 1 1
E C 2 2

Edward Jin-Ru Chen Acute Unicast Routing

16
 Link State

 Provide the road map

 All propagated information are bare information
about the link status
 Keep the bare information and use the processed
information
 Such as Open Shortest Path First

Edward Jin-Ru Chen Acute Unicast Routing

17
 Example of Link State
B 3
C 5
A A
A 3
3 5 C 1 3 5
1 D 5
1
B C A 5 B C
B 1
5 1 E 1 5 1
2 B 5 2
D E D E
E 2
C 1
D 2
Edward Jin-Ru Chen Acute Unicast Routing
18
 Routing Information
Protocol
 Derived from XNS
 Novell IPX also uses RIP
 Distance Vector
 uses hop count as metric
 Router broadcasts table every 30 sec
 Maximum network diameter is 15 hops
 Does not support variable-length subnet masks
 subnet mask is not contained in routing updates
 Suitable for small networks

Edward Jin-Ru Chen Acute Unicast Routing

19
 RIP Version 2

 Enhancement to RIP Version 1

 RIP- 2 Messages now carry:
route tag – specifies origin of route information
subnet mask
authentication
next hop
 RIP- 2 can use IP Multicast to send updates
option to use 224.0.0. 9

Edward Jin-Ru Chen Acute Unicast Routing

20
 RIP Characteristics

 Bellman-Ford (Distance Vector) Algorithm

D(i, i) = 0, for all i
D(i, j) = min [d(i, k) + D(k, j)], otherwise
 Constrained by 16 hop counts
 Periodic exchange routing information
Routing information is similar to forwarding information

Edward Jin-Ru Chen Acute Unicast Routing

21
 Count to Infinity in RIP

1 A B C D
A B Time
B, 3 D, 2 B, 3 Dir, 1
1 1 B, 3 Break B, 3 Dir, 1
C, 4 C, 4 A, 4 Dir, 1
C 1 C, 5 C, 5 A, 5 Dir, 1
10 ... ... ... ...
D C, 11 C, 11 A, 11 Dir, 1
1 C, 12 C, 12 D, 11 Dir, 1
E C, 12 C, 12 D, 11 Dir, 1
Edward Jin-Ru Chen Acute Unicast Routing
22
 Improving the Robustness

 Split horizon
Simple split horizon
Split horizon with poison reverse
 Triggered update

Edward Jin-Ru Chen Acute Unicast Routing

23
 Split Horizon

 Simple split horizon

Instability may caused by neighbors engaged in a pattern
of mutual deception
It is never useful to claim reachability for a destination
network to the neighbor(s) from which the route was
learned
Omit routes learned from one neighbor in updates sent to
that neighbor

Edward Jin-Ru Chen Acute Unicast Routing

24
 Simple Split Horizon

Net A, Metric 3

Router

No Net A entry

Edward Jin-Ru Chen Acute Unicast Routing

25
 Split Horizon

 Split horizon with poisoned reverse

Advertising reverse routes with a metric of infinite (16)
If two routers have routes pointing at each other, poison
reverse will break the loop immediately.
Disadvantage is to increases the size of the routing
messages

Edward Jin-Ru Chen Acute Unicast Routing

26
 Split Horizon with Poison
Reverse

Net A, Metric 3

Router

Net A, Metric 16 (Infinite)

Edward Jin-Ru Chen Acute Unicast Routing

27
 Incompleteness of Split
Horizon

B C

Edward Jin-Ru Chen Acute Unicast Routing

28
 Triggered Update

 Whenever a router changes the metric for a route,

it is required to send update messages almost
immediately
 combines with the rules for computing new
metrics
The receiving router believes the new information, whether
the new metric is higher or lower than the old one.

Edward Jin-Ru Chen Acute Unicast Routing

29
 Triggered Update (II)

Transmit immediately

Net A, Metric n+1

Net A, Metric n Router Net A, Metric n+1

Net A, Metric n+1

Edward Jin-Ru Chen Acute Unicast Routing

30
 RIP Timers

 Period update timer (30 sec)

 Timeout timer (180 sec)
 Garbage-collection timer (120 sec)

Edward Jin-Ru Chen Acute Unicast Routing

31
 Open Shortest Path First
(OSPF)
 Link-state protocol
Shortest path first protocol
Distributed-database protocol
 Depending on the link information to construct
shortest path to each destination
 Use the area to reduce link-state database size
 Use the Designated Router to reduce routing
information traffic

Edward Jin-Ru Chen Acute Unicast Routing

32
 OSPF (II)

 Equal cost multi-path support

 TOS-based routing support
Separate SPF for each TOS value
 IP subnetting support
Attach an IP address mask to each advertised route

Edward Jin-Ru Chen Acute Unicast Routing

33
 OSPF Operation
N 13
N 12 N 14
8 8 8
3 1 1 8

N1
RT5 6
AS sample RT1 RT4
7

N3
6 6
1 8
3 1 RT3 RT6
N2

2 Ia 7
RT2
N4 N 12

N 11 6 2
N 15
3 RT7 9
Ib 5 1
1 R T10
RT9 1 2 3
N9

N8
10 1 1
R T 11 N6
S L IP R T 1 2
H1 2 1

RT84

N 10 N7

Edward Jin-Ru Chen Acute Unicast Routing

34
 OSPF Operation (II)

 RT12 advertisement
RT12  N9 : 1
RT12  N10 : 2
RT12  H1 : 10
 N9 advertisement
N9  RT9 : 0
N9  RT11 : 0
N9  RT12 : 0

Edward Jin-Ru Chen Acute Unicast Routing

35
 OSPF Operation (III)
From
RT1 RT2 RT3 RT4 RT5 RT6 RT7 RT8 RT9 RT10 RT11 RT12 N3 N6 N8 N9
RT1 0

Directed Graph RT2

RT3
RT4 8
6
0
0
0
RT5 8 6 6
RT6 8 7 5
RT7 6 0
RT8 0
RT9 0
RT10 7 0 0
RT11 0 0
RT12 0
N1 3
N2 3

To N3
N4
1 1 1
2
1

N5
N6 1 1 1
N7 4
N8 3 2
N9 1 1 1
N10 2
N11 3
N12 8 2
N13 8
N14 8
N15 9
H1 10

Edward Jin-Ru Chen Acute Unicast Routing

36
 OSPF Operation (IV)

The SPF tree for Router RT6

6
RT5 RT6 7 R T10 5 Ia
3
7 1
8 8 Ib N8
8

N6 RT7 9 N 15
6

N 12 N 13 N 14

2
RT3 1 N3
N7 4 RT8
R T11
2 N 12
N4
1

RT2 RT1 N9 RT12 10 H1

RT3
3 2
3

N 10
N2 N1 RT9 3 N 11

Edward Jin-Ru Chen Acute Unicast Routing

37
 OSPF Area

Edward Jin-Ru Chen Acute Unicast Routing

38
 OSPF Area (II)

 Divide Autonomous System into two levels

Area 0 (Backbone area)
Other areas transmit summarized information into
backbone area
 Link information stored in each router, which
belongs to the same area, is identical

Edward Jin-Ru Chen Acute Unicast Routing

39
 OSPF Area Operation
N 13
N 12 N 14
8 8 8
3 1 1 8
AS with Area

N1
RT1 RT4 RT5 6
7
sample

N3
A rea 1 6
1 8 6

3 1 RT3 RT6
N2
2 Ia 7
RT2
N4
N 12

N 11 6 2
Ib 5 N 15
3 R T10 RT7 9
1
1
RT9 1 2 3
N9

N8
10 1 1
RT11 N6
S L IP R T 1 2
H1 2 1

A rea 3 RT84
A rea 2
N 10 N7

Edward Jin-Ru Chen Acute Unicast Routing

40
 OSPF Area Operation (II)
From
RT1 RT2 RT3 RT4 RT5 RT7 N3
Area 1's RT1
RT2
0
0
Database RT3
RT4
0
0
RT5 14 8
RT7 20 14
N1 3
N2 3
N3 1 1 1 1
N4 2
To Ia, Ib 15 22
N6 16 15
N7 20 19
N8 18 18
N9-N11, 19 16
H1
N12 8 2
N13 8
N14 8
N15 9

Edward Jin-Ru Chen Acute Unicast Routing

41
 OSPF Area Operation (III)
From
RT3 RT4 RT5 RT6 RT7 RT10 RT11
RT3 6
Backbone's RT4 8
RT5 8 6 6
Database RT6 8 7 5
RT7 6
RT10 7 2
RT11 3
N1 4 4
N2 4 4
N3 1 1
To N4 2 3
Ia 5
Ib 7
N6 1 1 3
N7 5 5 7
N8 4 3 2
N9-N11, 1
H1
N12 8 2
N13 8
N14 8
N15 9
Edward Jin-Ru Chen Acute Unicast Routing
42
 OSPF Hello Protocol

 Periodic send the hello packet containing the

discovered neighbors
 Discover OSPF neighbors
May use multicast (AllSPFRouters) on broadcast or point-
to- point links or configuration may be required
 Elect the Designated router
DR only elected on broadcast and point- to- point links

Edward Jin-Ru Chen Acute Unicast Routing

43
 OSPF Hello Protocol (II)

 Establish Adjacencies between Neighboring

Routers
Only adjacent routers exchange routing table updates
Use to control the distribution of routing information

Edward Jin-Ru Chen Acute Unicast Routing

44
 OSPF Designated Router

 Elected through Hello Protocol

High priority first
High router ID first
 Originate network links advertisement on behalf
of the network
 Adjacent to all other routers on the network

Edward Jin-Ru Chen Acute Unicast Routing

45
 OSPF LSA

 Router links advertisements

 Network links advertisements
 Summary link advertisements
Advertise routes to networks
Advertise routes to AS boundary routers
 AS external link advertisements
Type 1 external metric equivalent to the link state metric
Type 2 external metric greater than any internal metric

Edward Jin-Ru Chen Acute Unicast Routing

46
 OSPF Routing

 Synchronize Link-State Databases

adjacent routers exchange database description packets
link- state request/ updates provide neighbors with most
recent LSA - flooded within area
 Calculate the routing table

Edward Jin-Ru Chen Acute Unicast Routing

47
 OSPF Extension

 Functions and Services provided by OSPF can be

easily extended
define new information and use LSA advertisements to
flood throughout routing domain
 OSPF Opaque LSA (RFC2370) designed to carry
new information
routers may use this information or other applications may
use OSPF to flood data

Edward Jin-Ru Chen Acute Unicast Routing

48
 OSPF Extension (II)

 Two New OSPF Services make use of the Opaque

LSA
Address Resolutions Advertisements (ARA)
Optimized Multipath (OMP)

Edward Jin-Ru Chen Acute Unicast Routing

49
 OSPF ARA

 Utilize fast and reliable OSPF topology updates to

propagate link- layer information (IP/ ATM
address mappings) to OSPF ATM- attached
routers
 Not subject to packet loss like NHRP and no need
to query address resolution server
 Supports point- to- point, point- to- multipoint
and multipoint- to- point connections

Edward Jin-Ru Chen Acute Unicast Routing

50
 OSPF ARA (II)

 Interoperate with existing mechanisms (MPOA,

NHRP)
 Associate group of routers into a single logical
network (VPN)
attached logical network ID value to ARA packets

Edward Jin-Ru Chen Acute Unicast Routing

51
 Multipath Forwarding

 More than one path of equal cost may exist

between two points in the network (termed Equal
Cost Multipath)
Routing protocols such as OSPF may support this
Multipath forwarding means that the router maintains
multiple next hop entries for a destination

Edward Jin-Ru Chen Acute Unicast Routing

52
 Multipath Forwarding (II)

 Forwarding can be done on a per-packet round-

robin basis
however different paths may exhibit different delay,
bandwidth and MTU characteristics
problematic for TCP sender and receiver
 possible to generate out-of-order transmission
 error loss retransmission may happen

Edward Jin-Ru Chen Acute Unicast Routing

53
 Multipath Forwarding (III)

 Another technique is to divide traffic equally

across multiple paths by applying next-hop
identifier (hash) to each source/destination
address pair
 Still no knowledge of load or capacity of equal cost
paths

Edward Jin-Ru Chen Acute Unicast Routing

54
 OSPF OMP (Optimized
Multipath)
 Use OSPF Opaque LSA to distribute loading
information for equal cost paths
LSA_ OMP_ LINK_ LOAD – measures load, capacity and
packets dropped from a particular link
LSA_ OMP_ PATH_ LOAD
 Adjust distribution of traffic across multiple paths
based on advertised OMP loading information

Edward Jin-Ru Chen Acute Unicast Routing

55
 OSPF OMP Forwarding

 Hash boundary (meaning percentage of traffic

flowing over equal cost paths) may move
depending on load information conveyed by OMP
updates

Edward Jin-Ru Chen Acute Unicast Routing

56
 Interior Gateway Routing
Protocol
 Proposed by Cisco Systems, Inc.
 Is a distance vector interior-gateway protocol
 Use a combination of metrics
Internetwork delay, bandwidth, reliability, and traffic load
Reliability and load can be ranged from 1 to 255
Bandwidth can be ranged from 1.2kbps to 10gbps
Delay can be ranged from 1 to 2 to 24th power

Edward Jin-Ru Chen Acute Unicast Routing

57
 IGRP (II)

 Permit multipath routing

 Dual equal-bandwidth lines may run in round-
robin fashion, with automatic switch over to other
when one line goes down
 Multipath can be used even with different metrics
(if bandwidth is 3:1, offered load set to be 3:1)

Edward Jin-Ru Chen Acute Unicast Routing

58
 IGRP Stability Features

 Hold-downs tell routers to hold down any changes

that might affect routs for some period of time to
avoid the update information “polluted” by
regular update
 Split Horizon
 Poison Reverse Updates

Edward Jin-Ru Chen Acute Unicast Routing

59
 IGRP Timers

 Update timer
The time to send the routing update message (90s)
 Invalid timer
The time to decide the route invalid without refreshed
information
 Hold-time period
 Flush timer
Time to flushed from the routing table

Edward Jin-Ru Chen Acute Unicast Routing

60
 Enhanced IGRP

 Combination of link state protocol and distance

vector protocol
 Using Diffusing Update Algorithm (DUAL)
Fast convergence
 Store all of its neighbors’ routing table
 If not appropriate route exists,queries its neighbor for an alternate
routes
Variable length subnet mask

Edward Jin-Ru Chen Acute Unicast Routing

61
 Enhanced IGRP (II)

Parital, bounded updates

 No periodic update
 Send partial updates only when the metric for a route changes
(Less bandwidth requirement)
Multiple network-layer support
 AppleTalk, IP, and Novell NetWare
 Redistribute routes learned from OSPF, RIP, IS-IS, EGP, or BGP.
Novell implementation redistributes routes learned from Novell
RIP or SAP

Edward Jin-Ru Chen Acute Unicast Routing

62
 Enhanced IGRP (III)

 Features four new technologies

Neighbor discovery/recovery
 Using hello packet
Reliable Transport Protocol
 For update and acknowledgement not for hello packet
DUAL finite state machine
Protocol-dependent modules

Edward Jin-Ru Chen Acute Unicast Routing

63
 Inter-Domain Routing

 Policy Routing - Deciding where to direct information

based on:
 Cost, Performance, Security, Availability and Reliability, Traffic Type
- Best Effort or Real- time, Others...

Edward Jin-Ru Chen Acute Unicast Routing

64
 Border Gateway Protocol

 Designed as a true inter- AS routing protocol for

TCP/ IP- based networks
 Uses concept of Path Vectors to represent path to
reachable destination
prevents loops
 Enables policy- based routing by affecting route
selection and controlling the distribution of
specific routes

Edward Jin-Ru Chen Acute Unicast Routing

65
 BGP (II)

 Uses TCP to reliably exchange routing information

 BGP4 supports route aggregation and variable length
subnet masking
 Inter- BGP Router relationships:
 Internal BGP – between two BGP routers within same AS
 External BGP – between two BGP routers in separate AS
 No restrictions on network topology
 RFC1771

Edward Jin-Ru Chen Acute Unicast Routing

66
 BGP Path Vector

Net A, Path: 1 AS 2 Net A, Path: 1,2

AS 1 AS 3
Net A
Net A, Path: 1,2,3 Not accept

 BGP routers advertise routing information which contains a

sequence AS numbers that a route has traversed. This is
referred to as a Path Vector
 A BGP router will not accept an update if it sees its own AS
number in the update
 This ensures loop free inter- domain routing
Edward Jin-Ru Chen Acute Unicast Routing
67
 BGP Routing Process

Edward Jin-Ru Chen Acute Unicast Routing

68
 BGP Routing Process

 Routing updates are received from other BGP routers

 Input policy engine filters routes and performs attribute
manipulation
 Decision process decides what routes BGP router will use
 Output policy engine filters routes and performs attribute
manipulation for routes to be advertised
 Routing updates are advertised to other BGP routers

Edward Jin-Ru Chen Acute Unicast Routing

69
 BGP Message Flow

 BGP peers establish a TCP connection with each other

 Initially the entire routing table is exchanged; after that
only changes in topology or policy are sent in UPDATE
messages
 BGP Updates can announce or withdraw a route
 BGP Updates also carry attributes which are used by the
policy engines and the decision process
 AS_ PATH, ORIGIN, NEXT_ HOP, MULTI_ EXIT_ DISC, LOCAL_
PREF, etc.

Edward Jin-Ru Chen Acute Unicast Routing

70
 Protocol Verification

 Packet Format
Lower protocol parameter setting
Entry field validity
 Timer
Preciseness of each timer
 Algorithm
Using entered packet to generate virtual environment to
trigger algorithm calculation

Edward Jin-Ru Chen Acute Unicast Routing

71
 Protocol Verification

 Input process
Check the processing result of different input packets
 Output process
Check the processing result when router generate packets

Edward Jin-Ru Chen Acute Unicast Routing

72
 Testing Example

 RIP timer verify

 Divide the RIP process into slots
Slots is separated by the periodic update
 Procedure
Transmit a response packet into DUT (Device Under Test)
Count the number of periodic updates contains the newly
added entry
Verify the time to become invalid and disappear

Edward Jin-Ru Chen Acute Unicast Routing

73
 Timer Verify

180 sec 120 sec

180 sec 120 sec

Response Triggered Periodic

Update Update
Edward Jin-Ru Chen Acute Unicast Routing
74
 Benchmarks

 Throughput (pps)
 Routing entry update delay

Edward Jin-Ru Chen Acute Unicast Routing

75