Transcript RoutingAtTheNetworkL.. - University of Delaware

Homework due?
Next lecture is in 311 Pearson
Hall (Studio A). Give me or the
TA a sheet of paper with your
name (attendance)
University of Delaware CPEG 419
1
Connection vs. connectionless
issue
Packet switching
Virtual-circuit
Setup
Not needed
needed
addressing
Each packet has full address
Just VC number (label)
State information
Nothing about the flow is
needed
Each VC requires a some
information
Routing
Each packet routing
independently
Route is chosen at setup.
Effect of router failure
Perhaps little, a few packets lost
until a new route is found.
All VC that pass through router
have to be re-setup
Quality of Service
Difficult
Easy to implement, but hard to
plan efficiently.
Congestion control
Difficult
Easy to implement, but difficult
to plan efficiently.
University of Delaware CPEG 419
2
We mostly look at connectionless routing.
But connection-oriented is becoming more
and more important (maybe).
University of Delaware CPEG 419
3
Overview of Routing in the
Global Internet Today
The problem of scalability
Each router must know where to send a
packet next.
IP address
Next hop (interface
#)
128.132.4.123
1
128.125.5.123
2
125.35.124.24
3
27.34.43.43
2
34.39.23.1
3
64.34.56.111
2
72.119.12.34
1
University oftable
Delaware
419
The forwarding
areCPEG
huge!!!
4
Subnetting
Divide and conquer
AS (e.g. ATT)
A
128.120.XXX.XXX
1
2
A3
MCI
128.132.1XX.XXX
24.124.123.XXX
1
4
IP address
mask
#
128.132.0.0
255.255.128.0
2
128.120.0.0
255.255.0.0
1
24.124.123.0
255.255.255.0
3
72.111.19.0
255.255.?.0
3
116.24.0.0
255.255.0.0
3
2
B
B
3
GE
72.111.19X.XXX
116.24.XXX.XXX
Must carefully distribute addresses
IP address
mask
#
128.0.0.0
255.0.0.0
1
24.124.123.0
255.255.255.0
2
72.111.19.0
255.255.?.0
4
116.24.0.0
255.255.0.0
3
University of Delaware CPEG 419
5
Hierarchical Routing
Must distribute address carefully
Then there are two problems
How to route between subnets (interdomain routing)
BGP
How to route in a subnet (intradomain routing)
Distance Vector (RIP)
Link State (OSPF)
University of Delaware CPEG 419
6
Routing
 Based on knowledge of network topology, choose appropriate paths
from source to destination.
 Goals
 Correctness
 Simplicity (funny, aren’t we smart enough to make complicated things?)
 Robustness – when a router or link goes down, the network must
remain up.
 Stability – some routing algorithms never converge or take a very long
time to converge after a small change. A small change in one part of
the network should not lead to a large change. Currently, BGP does not
meet this criteria.
 Fairness
 Optimality
University of Delaware CPEG 419
7
Fairness and optimality
3
5
1
8
7
2
4
6
Total flow is maximized by just sending from 1->2, 3->4 and 5->6, but not so fair to 7->8
University of Delaware CPEG 419
8
Adaptive and Non-adaptive
Routing
Non-adaptive routing:
Fixed routing, static routing.
Do not take current state of the network (e.g., load,
topology).
Routes are computed in advance, off-line, and
downloaded to routers when booted.
Adaptive routing:
Routes change dynamically as function of current
state of network.
Algorithms vary on how they get routing information,
metrics used, and when they change routes.
University of Delaware CPEG 419
9
Hot potato routing
Just send the packet somewhere.
IP address
mask
#
128.132.0.0
255.255.128.0
2
128.120.0.0
255.255.0.0
1
24.124.123.0
255.255.255.0
3
72.111.19.0
255.255.?.0
3
116.24.0.0
255.255.0.0
3
University of Delaware CPEG 419
10
Flooding
 Every packet is sent to every neighboring router except the one it
came on.
 In order to stop the packet from traveling forever, a counter of the
number of hops is decremented at every hop. Once the counter hits
zero, the packet is dropped.
 Use sequence numbers so that if a router sees a packet twice, it will
drop it. But then each router need to keep a list of packets it has seen
so far.
 Each packet could contain a list to routers visited so far. Then…
 Selective flooding
 Flood to those neighbors that are in the general right direction.
 As we shall see, flooding is used (but not for data). It was used in
link layer routing.
University of Delaware CPEG 419
11
Shortest Path Routing
Shortest with respect to some metric
Example:
Number of hops.
Delay.
Bandwidth.
Cost.
University of Delaware CPEG 419
12
Bellman Optimality
Principle
General statement about optimal routes
(topology, routing algorithm independent).
If router J is on optimal path between I and K,
then the optimal path from J to K also falls
along the same route.
Proof by contradiction.
Corollary:
Set of optimal routes from all sources to destination
form a tree rooted at destination.
Sink tree.
University of Delaware CPEG 419
13
Distance Vector Routing –
Dynamic Programming
 Limited state information. Just the next hop and cost.
A
A
D
F
C
B
G
H
address
Next
hop
cost
address
Next
hop
cost
A
A
0
A
A
1
B
B
1
B
B
1
C
C
1
C
A
2
D
D
1
D
D
0
E
E
2
E
B
2
F
D
2
F
F
1
G
B
2
G
B
2
H
B
3
H
B
3
D
E
University of Delaware CPEG 419
14
Distance Vector Routing –
Dynamic Programming
 Suppose a new node comes on line.
I
I
A
D
F
C
B
G
E
address
Next
hop
Cos
t
A
?

B
?

C
?

D
?

E
?

F
?

G
?

H
?

I
I
0
H
University of Delaware CPEG 419
15
Distance Vector Routing –
Dynamic Programming
 Suppose a new node comes on line.
 Suppose I first talks to A.
A
I
A
D
F
C
B
G
E
address
Next
hop
cost
address
Next
hop
cost
A
A
0
A
A
1
B
B
1
B
A
2
C
C
1
C
A
2
D
D
1
D
A
2
E
E
2
E
A
3
F
D
2
F
A
3
G
B
2
G
A
2
H
B
3
H
A
2
I
I
0
I
H
University of Delaware CPEG 419
16
Distance Vector Routing –
Dynamic Programming
 Suppose a new node comes on line.
 Suppose I first talks to A.
 Next I talks to D.
D
I
A
D
F
C
B
G
E
address
Next
hop
cost
1
A
A
1
B
1
B
A
2
C
A
2
C
A
2
D
D
0
D
D
1
E
B
2
E
A
3
F
F
1
F
D
2
G
B
2
G
A
2
H
B
3
H
A
2
I
I
0
address
Next
hop
cost
A
A
B
I
H
University of Delaware CPEG 419
17
Distance Vector Algorithm
Start with all destinations with infinite distance,
except for the actual node, which is distance 0.
Every 30 seconds (RIP), or when a change
occurs in the table, send table to neighbors.
If the distance to a prefix advertised by a
neighbor is less plus the distance to the
neighbor is less than known distance, reduce
distance to prefix and route packets with that
destination prefix to that neighbor.
University of Delaware CPEG 419
18
Count to Infinity Problem
A
B
C
D
E




initial
1



1 iteration
1
2


2 iterations
1
2
3

3 iterations
1
2
3
4
4 iterations
A
B
C
D
E
1
2
3
4
initial
3
2
3
4
1 iteration
3
4
3
4
2 iterations
5
3
5
4
3 iterations
5
6
5
6
4 iterations
University of Delaware CPEG 419
19
Approaches to Mitigate
Count Infinity
Why is count to infinity a problem?
It generates tons of routing updates – too much traffic
The network should report that a route is unreachable.
Put upper bound an upper bound the the diameter of the network.
But what is the network grows (as it did).
Split horizon. A router does not report a distance to the neighbor it learned the distance
from.
Split horizon with poison reverse. If A advertises the best cost to E to B, then B
advertises a cost of infinity to E back to A.
This only works for loops that involve two nodes. With larger loops, the mitigation is
more difficult and these remedies reduce the rate of convergence.
The way to fix it is to use link state routing.
University of Delaware CPEG 419
20