Transcript CSC 335 Data Communications and Networking I

CSC 581
Communication Networks II
Chapter 7b: Network Routing
Dr. Cheer-Sun Yang
Routing Algorithm
Classifications
• Static vs. dynamic(adaptive)
• Centralized vs. distributed
2
Types of Routing Protocols
• Centralized vs. Distributed protocols
• Static vs. Adaptive
• Link State(adaptive) vs. Distance
Vector(Static)
• Interior vs. Exterior routing protocols
3
Centralized vs. Distributed
• Centralized – All interconnection information is
generated and maintained at a single central
location. See Partial Routing Tables in Figure 7.4
and Routing Matrix in Figure 7.5
• Distributed – There is no central control. Each
node must maintain and determine its routing
information independently. See Figure 7.6
4
Static vs. Adaptive
• Static– Once a node determines its routing table,
the node does not change it unless the network
configuration is changed, e.g., a node is added or
deleted. Distance Vector algorithm is the base of
static routing protocols.
• Adaptive – The routing table will be modified as
network conditions (link status, congestion status,
configuration) change. Any pitfalls? (See Figure
7.6 again.) Link State routing protocols are
adaptive protocols.
• Can you compare these two techniques?
5
Link State vs. Distance Vector
• Link State – adaptive; based on link status
information and Dijkstra’s Algorithm
• Distance Vector – static; based on hop count
and Bellman-Ford Algorithm
6
Interior vs. Exterior
• Interior – only used within a domain
• Exterior – between two domains via
gateways, e.g., hierarchical routing
architecture
7
Routing Tables
• Each network node
stores information
about the network.
• When a packet arrives,
it uses the destination
address and the
routing table to decide
the routine.
8
1
3
6
A
4
B
Host
2
5
Switch or router
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
9
Figure 7.23
1
A
1
2
3
5
7
3
1
4
8
6
B
5
2
4
3
C
2
6
5
5
2
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
D
10
Figure 7.24
Node 3
Node 1
Incoming
node VC
A 1
A 5
3
2
3
3
Outgoing
node VC
3
2
3
3
A 1
A 5
Incoming
node VC
1
2
1
3
4
2
6
7
6
1
4
4
Outgoing
node VC
6
7
4
4
6
1
1
2
4
2
1
3
Node 6
Incoming
node VC
3
7
3
1
B
5
B
8
Outgoing
node VC
B
8
B 5
3
1
3
7
Node 4
Node 2
Incoming
node VC
C
6
4
3
Outgoing
node VC
4
3
C 6
Incoming
node VC
2
3
3
4
3
2
5
5
Outgoing
node VC
3
2
5
5
2
3
3
4
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
Node 5
Incoming
node VC
4
5
D
2
Outgoing
node VC
D
2
4
5
11
Figure 7.25
Link State vs. Distance Vector
• Link State: uses propagation delay, transmission
speed, etc., as cost factors; a central node collects
the “cost” of all links and broadcast the
information to all nodes; every node maintains the
“whole picture” of the network and computes the
shortest distance.
• Distance Vector: uses hop count as a cost factor;
every node only maintains the cost to its
neighbors.
12
(a)
0000
0001
0010
0011
1
0100
0101
0110
0111
4
3
R2
R1
5
2
1000
1001
1010
1011
00
01
10
11
1
3
2
3
00
01
10
11
1100
1101
1110
1111
3
4
3
5
(b)
0000
0111
1010
1101
1
0001
0100
1011
1110
4
3
R1
R2
5
2
0011
0110
1001
1100
0001 4
0000 1
0100 4
0111 1
1011 4
1010 1
… …
…
…
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
0011
0101
1000
1111
13
Figure 7.27
Examples
• Routing Information Protocol – an interior
protocol; based on hop count (an example of
distance vector).
• Open Shortest Path First (OSPF) – an interior
protocol; based on length, bit rate, delay, or dollar
cost (examples of link state).
• Border Gateway Protocol – an exterior protocol
(an example of hierarchical routing).
14
15
Bellman-Ford Algorithm
• Also called backward search algorithm
• The theory on which Distance Vector
routing protocols are based.
16
Bellman-Ford Algorithm
B
A
C
E
D
Cost (A,Z) = smallest of the cost of link from A to
K + cost of cheapest route from K to Z (  K
such that A to K has a link).
17
1
2
1
3
6
5
2
3
4
1
2
3
2
4
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
18
Figure 7.28
1
2
1
3
6
2
1
2
4
2
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
19
Figure 7.29
2
1
3
X
6
5
2
3
4
1
2
3
2
4
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
20
Figure 7.30
Bellman-Ford Algorithm
A
2
D
7
1
2
E
B
2
C
4
Network for Bellman-Ford Algorithm
21
Destination
22
23
(c) Third Iteration
24
Bellman-Ford Routing
25
Problems with Bellman-Ford
Algorithm
• Sometimes, a node may update its routing
information slowly.
• It reacts rapidly to good news, but leisurely
to bad news.
26
Count-to-Infinity Problem
A
B
C D
E
  
1   
1
2  
1 2 3 
1
2
3
4
A is down initially.
Then, A comes back up.
A
B
C D
E
1
2
3
4
3
3
2
4
3
3
5
5
7
4
6
6
8
5
5
7
7
…
4
4
4
7
6
6
8
   
The link between A and B is cut.27
(a)
1
2
1
3
1
4
1
(b)
1
2
1
3
X
4
1
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
28
Figure 7.31
Split Horizon
1. Initially, all nodes are up.
2. Then, A goes down.
3. One the first change, B knows
that A is down;C knows that C
cannot reach A either.
3. C reports the distance to A as
infinity.
The distance to X is not reported
backward to nodes incident with
the link where packets
sent to X must pass. In C, the
distance to A is always reported
to B as infinity.
A
B
1
C D
2
3

 
  
E
4
…
   
29
ARPANET Routing Strategies(1)
• First Generation (1957, 1962)
– Uses Bellman-Ford Algorithm (a distributed version)
• Second Generation (1979)
–
–
–
–
–
Uses delay as performance criterion
Delay measured directly
Uses Dijkstra’s algorithm
Good under light and medium loads
Under heavy loads, little correlation between reported
delays and those experienced
30
ARPANET Routing Strategies(2)
• Third Generation (1987)
– Link cost calculations changed
– Measure average delay over last 10 seconds
– Normalize based on current value and previous
results
– Link State Routing
– Hierarchical Routing
31
Link State Algorithms
• A node gathers information on the status of each
link to each neighbor.
• A node builds a link state packet for each link.
• A node receiving link state packets forwards them
to all of its neighbors except the one from which it
receives the packet.
• As link state packets are exchanged, each node
eventually learns about the network topology, the
cost, and the status of each link.
32
Dijkstra’s Algorithm – A Link
State Algorithm
• Finding a shortest path from a node.
• A centralized static algorithm
• Link state routing approaches are based on
Dijkstra’s Algorithm.
33
1
2
1
3
6
2
3
4
2
2
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
34
Figure 7.32
Hierarchical Routing
• All nodes are divided into groups called domains.
• Routes between two nodes in a common domain
are determined using the domain’s protocols.
• Each domain has one or more specifically
designated nodes called routers or gateways that
determine routes between domains.
• A domain can consist of subdomains.
35
36
Hierarchical Routing
• Purpose: reduce the size of routing tables for
routing in a large networking environment
37
Node 1
Destination
Next node
2
2
3
3
4
4
5
2
6
3
Node 2
Destination
Next node
1
1
3
1
4
4
5
5
6
5
Node 3
Destination
Next node
1
2
4
5
6
Destination
1
2
3
5
6
1
4
4
6
6
Node 4
Next node
1
2
3
5
3
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
Node 6
Destination
Next node
1
3
2
5
3
3
4
3
5
5
Destination
1
2
3
4
6
Node 5
Next node
4
2
4
4
6
38
Figure 7.26
39
40
Autonomous Systems (AS)
•
•
•
•
Group of routers
Exchange information
Common routing protocol
Set of routers and networks managed by
single organization
• A connected network
– There is at least one route between any pair of
nodes
41
Routing Information Protocol
• Routing Information
– About topology and delays in the internet
• Routing Algorithm
– Used to make routing decisions based on
information
42
43
Open Shortest Path First (1)
•
•
•
•
OSPF
IGP of Internet
Replaced Routing Information Protocol (RIP)
Uses Link State Routing Algorithm
–
–
–
–
Each router keeps list of state of local links to network
Transmits update state info
Little traffic as messages are small and not sent often
RFC 2328
• Route computed on least cost based on user cost
metric
44
Open Shortest Path First (2)
• Topology stored as directed graph
• Vertices or nodes
– Router
– Network
• Transit
• Stub
• Edges
– Graph edge
• Connect two router
• Connect router to network
45
Operation
• Dijkstra’s algorithm used to find least cost
path to all other networks
• Next hop used in routing packets
46
Border Gateway Protocol (BGP)
• For use with TCP/IP internets
• Preferred EGP of the Internet
• Messages sent over TCP connections
–
–
–
–
Open
Update
Keep alive
Notification
• Procedures
– Neighbor acquisition
– Neighbor reachability
– Network reachability
47
Other Routing Approaches
• Flooding
• Deflection Routing
• Source Routing
48
(a)
1
3
6
4
2
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
49
Figure 7.33 - Part 1 of 3
(b)
1
3
6
4
2
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
50
Figure 7.33 - Part 2 of 3
(c)
1
3
6
4
2
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
51
Figure 7.33 - Part 3 of 3
Deflection Routing
• Also known as hot potato routing
• The network maintains multiple paths to a
destination.
• It tries all paths one at a time.
• Advantage: a switch can be bufferless since
packets do not have to wait for a specific
port to become available.
52
0,0
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
3,0
3,1
3,2
3,3
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
53
Figure 7.34
busy
0,0
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
3,0
3,1
3,2
3,3
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
54
Figure 7.35
Source Routing
• Source hosts maintain the big picture
55
3,6,B
6,B
1,3,6,B
1
3
6
B
A
4
B
Source host
2
5
Copyright 2000 McGraw-Hill LeonGarcia and Widjaja Communicaiton
Destination host
56
Figure 7.36
Required Reading
• Chapter 7: section 7.4, 7.5, 7.6
57