Transcript Routing IP





Each router is assigned two or more IP addresses
• one address for each network to which the router attaches
To understand why, recall two facts:
• A router has connections to multiple physical networks
• Each IP address contains a prefix that specifies a physical
network
A single IP address does not suffice for a router
• because each router connects to multiple networks
• and each network has a unique prefix
The IP scheme can be explained by a principle:
• An IP address does not identify a specific computer
• each address identifies a connection between a computer and a
network
• A computer with multiple network connections (e.g., a router)
must be assigned one IP address for each connection
1
Multi-homed Hosts: Routers and the IP
Addressing Principle
2


Provides control messaging among the routers to monitor
the operation of the Internet
Messages are encapsulated in IP packets
 DESTINATION UNREACHABLE
 TIME EXCEEDED
 PARAMETER PROBLEM
 SOURCE QUENCH (reduce speed)
 REDIRECT
 ECHO REQUEST
 ECHO REPLY
 TIMESTAMP REQUEST
 TIMESTAMP REPLY
3
The principal ICMP message types.
5-61
4
A
packet does not know how to get to its
destination
 Must rely on the routers to send it in the
right direction
 So how do the routers do that?
A
router can't possibly know where
everything in the world is: it is only
connected to a handful of neighbour
routers
 How can a router in Izmir know that to
send a packet to Tokyo it might have to
forward it to America first?
 Routers exchange information with
each other to find the best possible
route to a destination
 Two
types of routing structures
• Autonomous System (AS): Local routing within
an organisation (requiring an interior gateway
protocol)
• Global (non-local) routing between organisations
(AS’s) (requiring an exterior gateway protocol)
Interior Gateway Protocols
 Requires static route added by hand, e.g.,
the route command
route add default gw 213.121.147.69
adds a default route to a gateway with IP
address 213.121.147.69
 Routing tables on most non-routers are
trivial and set up manually by the operating
system at boot time
ICMP Redirect
 Sometimes
routing tables are not perfectly
set up
 H1 wants to send to H2 but H1's routing table
tells it to route via R2
 When
the packet reaches R2, it sees it
should be routed out on the interface it
came in on: so R2 knows H1's table need
improving
 R2 forwards the packet and send an ICMP
redirect to H1
 H1
gets the redirect and uses it to update
its routing table. Next time H1 will be able
to route directly to R1
 ICMP
redirects are OK for small fixes, but
in general routers need something more
substantial
 Could let administrators to set up the
tables?
 Better to get the routers to do it themselves
 Dynamic routing is the passing of routing
information between routers
 Several
•
•
•
•
protocols are used
Routing Information Protocol (RIP)
Open Shortest Path First (OSPF)
Border Gateway Protocol (BGP)
Many more
 Each
protocol is suited to a certain
purpose, no single protocol fits all
 Internet
is managed as a collection of
Autonomous Systems (AS), each
administered by a single entity, e.g., a
University or company
 Each AS chooses a routing protocol to
direct packets within the AS: these are
interior gateway protocols (IGP), e.g., RIP
or OSPF
 Between ASs run exterior gateway
protocols (EGP), e.g., BGP
Distance-Vector and Link-State
 Routers can collect all kinds of information
about who is connected to whom and in
what manner: this must be condensed
down to something that can be put in a
routing table
 Two main algorithms are used:
• distance-vector protocols
• link-state protocols
 Distance-vector
gathers collections
(vectors) of hop counts (distances) from its
neighbouring routers to selected
destinations. From this it computes its own
vector of distances. RIP is an example
 Link-state gathers maps of connectivity
from all the routers in the AS (or some
subset) and uses this to compute its own
map. OSPF is an example
Distance-Vector vs Link-State
 Distance-vector is simple, but has
problems
 Link-state is more complex, but has
advantages
 When
a router starts it broadcasts a RIP
request on all its interfaces with address
family 0 and metric 16: this is a “send me
all your routes” request
 A router receiving such a request replies
with its vector of distances
 Otherwise
a request is for a route to a
particular address or addresses
 A reply is a metric for a route, or 16 to
indicate infinity or “no route”
 Given a reply we can update our routing
table: our metric is the received metric
plus 1 for the hop to the router that replied
 If
a new route with a smaller metric than an
existing route we can update our table to
use the new route: RIP always deems
shorter paths to be better
 RIP also sends a chunk of the routing table
every 30 seconds to its neighbours: routes
are timed out if they are not confirmed
within x minutes
A
timed-out route is set to metric 16, but
not deleted for 60 seconds: this ensures the
invalidation is propagated
 R3
knows a route to H with metric 1
 R3 sends a RIP message to R2, R2 learns a
route to H via R3 with metric 2
 R2 sends a message to R1, R1 learns a
route to H via R2 with metric 3
 Note
that R2 sends a message to R3, too, so
R3 learns there is a route to H via R2 with
metric 3
 But R3 can ignore this as it already knows a
better route
Updating of Vector
Distance tables
 RIP
has problems, in particular the long
time (several minutes) it takes to readjust
after a route is added or removed
somewhere: the slow convergence, or
count to infinity problem
Link up Propagation
A is initially down and comes up. The good news spreads relatively quickly.
A is down
The count-to-infinity problem: Link Down Propagation
A is up
Bad news spread slowly.
 Another
problem is that RIP is not suitable
for use between ASs as it is ignorant of
subnetting and possibly discloses too
much about the internal structure of the AS
 As RIP uses broadcast a router only gets
information from its immediate neighbours
and this makes getting a global view of the
network difficult
 The
metric limit of 15 is not big enough for
larger networks: making it bigger only
makes the count to infinity worse
 The only criterion for choice of route is the
metric: this is much too simplistic. Other
considerations including network speed,
bandwidth and cost should be taken into
account
 The
Open Shortest Path First protocol is
mainly based on the Dijkstra's shortest path
first Algorithm
 This
is a method for finding best paths
through a network, where “best” means
“shortest” or “lowest cost” or whatever you
want to measure
 It is used in several routing protocols
 We
want to find the shortest/cheapest path
between V and Z, where costs are as given
 We make a table of paths, containing a
predecessor to a node and a cost to get to
that node. Also mark each node
determined or undetermined
1.Initialise all costs to ∞, predecessors to blank
and all nodes undetermined
2.Initialise the cost of the starting node V to 0
3.While there are any undetermined nodes:
a) pick an undetermined node of lowest cost; call it C
b) mark C determined
c) for each undetermined neighbour N of C
if cost to C + cost N to C < cost to N we have found a shorter
path to N via C; make the cost of N be cost to C + cost N to
C and the predecessor of N to be C
 Determined
nodes are those for which we
definitely know the best route;
 Undetermined nodes are those for which
we need to find a better (shorter/cheaper)
route
 Pick
V
0
-
W
2
V
X
4
V
Y
∞
-
Z
7
V
det
undet
undet
undet
undet
cheapest undetermined node: V
 Make it determined and consider its
neighbours W, X and Z
 All have infinite cost, so make their
predecessors V and adjust their costs
 Pick
V
W
X
Y
Z
0
-
2
V
3
W
3
W
7
V
det
det
undet
undet
undet
cheapest undetermined node: W
 Make it determined, and consider its
undetermined neighbours X and Y
 Cost to X via W is 2+1<4, so revalue X; cost
to Y via W is 2+1<∞, so revalue Y
 Pick
V
0
-
W
2
V
X
3
W
Y
3
W
Z
5
X
det
det
det
undet
undet
cheapest undetermined node: X (or Y)
 Make it determined and consider its
undetermined neighbour Z
 Cost to Z via X is 3+2<7 so revalue Z
 Pick
V
0
-
W
2
V
X
3
W
Y
3
W
Z
5
X
det
det
det
det
undet
cheapest undetermined node: Y
 Make it determined and consider its
undetermined neighbour Z
 Cost to Z via Y is 3+3>5 so don't revalue Z
 Pick
V
0
-
W
2
V
X
3
W
Y
3
W
Z
5
X
det
det
det
det
det
cheapest undetermined node: Z
 Make it determined. It has no
undetermined neighbours so we are done
Final costs:
 So
V
W
X
Y
Z
0
2
3
3
5
-
V
W
W
X
cheapest path from V to Z is of cost 5
 Also have computed cheapest paths from V
to every other node
 Software
responsible for deciding which
output line an incoming packet should be
transmitted on
 Datagram
• Routing decision at every node
 VC
• Routing decision at the setup phase
Computer Networks 1
TANENBAUM
43










The Optimality Principle
Shortest Path Routing
Flooding
Distance Vector Routing
Link State Routing
Hierarchical Routing
Broadcast Routing
Multicast Routing
Routing for Mobile Hosts
Routing in Ad Hoc Networks
Computer Networks 1
TANENBAUM
44
 Correctness
 Simplicity
 Robustness
• What happens if the topology changes?
 Stability
• Must converge to an equilibrium
 Fairness
 Optimality
• Minimize mean packet delay
• Maximize total network throughput
Computer Networks 1
TANENBAUM
45
 Nonadaptive
algorithms
• Route is computed in advance and stored in the
router
• This is called static routing
 Adaptive
algorithms
• Base their decision on current measurement of
traffic and topology
Computer Networks 1
TANENBAUM
46
 Treat
routers as nodes
 Assign weights to links
• E.g.
 Fix all weight to 1 to minimize the number of hops
crossed
 Use distance in kilometers as weight to minimize
delay
 Use
Dijkstra’s algorithm to determine the
shortest path
Computer Networks 1
TANENBAUM
47
Computer Networks 1
TANENBAUM
48
 Initialize
• T = {s} set of nodes incorporated (s source)
• L(n)=w(i,j) for ns initial path costs to neighbors
 Get
next node
• Add the neighbor x not in T that has least cost L(x) to
s.
• Add the edge from this neighbor to old T that
contributes to the path

Update least cost paths
• For all nT, update costs by
L(n)=min[L(n),L(x)+w(x,n)]
Computer Networks 1
TANENBAUM
49
5-8 top
Computer Networks 1
TANENBAUM
50
5-8
bottom
Computer Networks 1
TANENBAUM
51
 Every
incoming packet is sent out on every
outgoing line except the one it arrived on
 Generates vast number of duplicate packets
 Solutions
• Put a hop counter to every packet
• Avoid flooding the same packet second time
 Needs packet sequence numbers
• Use selective flooding
 Do not put the packet to every outgoing line, instead
put the packet to certain outgoing lines
 Used
in military applications and
measurements
Computer Networks 1
TANENBAUM
52
 Takes
load into account
 Needs
• Topology
• Load on the lines
• Capacity of the lines
 Given
the load and capacity, delay of the
line can be computed via queueing
theory
• T = 1 / (C - ) where
 1/ is mean packet size in bits
 C is line capacity in bps
  mean flow in packets per second
Computer Networks 1
TANENBAUM
53
 Distance
vector routing
• Did not take line bandwidth into account
• Took too long to converge
 Link
state routing: Each router
• Discover its neighbors, learn their network address.
• Measure the delay or cost to each of its neighbors.
• Construct a packet telling all it has just learned.
• Send this packet to all other routers.
• Compute the shortest path to every other router.
Computer Networks 1
TANENBAUM
54
 When
a rooter is booted, it sends HELLO
packet to all of its neighbors
 Neighbors reply by sending their
globally unique names
 Modeling LANs need extra mechanisms
• In the next slide an artificial node N is added to
represent the LAN
 From A to C, the path is represented as ANC
Computer Networks 1
TANENBAUM
55
 Each
router should know an estimate of delay
to each of its neighbors
 To estimate the delay, a router can send an
echo packet to its neighbor and measure the
time when it receives it back
 While measuring time, it is possible to include
or exclude the time the echo packet spends on
the queues which corresponds to consider load
on the line
 Including load may cause oscillations in the
algorithm
Computer Networks 1
TANENBAUM
56
A subnet in which the East and West parts
are connected by two lines.
Computer Networks 1
TANENBAUM
57
 Packets
•
•
•
•
contain
Identity of the sender
Sequence number
Age
List of neighbors and delays
 Packets
canbe issued
• Periodically or
• When a significant event occurs
Computer Networks 1
TANENBAUM
58
(a) A subnet. (b) The link state packets
for this subnet.
Computer Networks 1
TANENBAUM
59
 Flooding
is used
 Packet sequence numbers are used to discard
duplicates or old packets by holding packets
for a short while before flooding them
 32-bit sequence numbers are used to prevent
wrap-arounds
 For each packet, in addition to sequence
number, age is used and decremented every
second to solve
• Router crash problem
• Corrupted sequence number problem
Computer Networks 1
TANENBAUM
60
The packet buffer for router B in the
previous slide (Fig. 5-13).
Computer Networks 1
TANENBAUM
61
 When
a router accumulates a full set of link
state packets, it can construct the entire
network graph
 It then runs Dijkstra’s algorithm to construct
shortest paths to all possible destinations
 Even for a large subnet, the memory
requirements are reasonable
 Malfunctioning routers may cause problems
 Protocols using link state routing
• OSPF and IS-IS
Computer Networks 1
TANENBAUM
62