Transcript Chp. 4, Part III - comp

Chapter 4: Internetworking
(IP Routing)
Dr. Rocky K. C. Chang
16 March 2004
1
The routing problem
• Problem: How does a router construct its
routing table for IP forwarding?
• Forwarding vs routing
– Routing is the process by which forwarding tables
are built.
• Forwarding table vs routing table
– A routing table is built by routing protocols as a
precursor to building the forwarding table.
– A forwarding table consists of detail enough
information to speed up datagram forwarding.
2
Internet topology
• See http://www.cybergeography.org/atlas/topology.html for
more Internet topologies.
Large corporation
“Consumer ” ISP
Peering
point
Backbone service provider
“ Consumer” ISP
Large corporation
Peering
point
“Consumer”ISP
Small
corporation
3
Internet topology
• Major components in the Internet topology:
– Autonomous system (AS), e.g., polyu.edu.hk,
ibm.com, etc.
– Internet service providers (ISPs): Local ISPs,
regional ISPs, National ISPs, Backbone ISPs.
– Exchange networks: For local traffic interchange,
e.g., HKIX.
– Some special networks, like Harnet in Hong Kong.
– Routers (plus other networks) are usually used to
connect these components together.
4
An example
• u5x-174.comp.polyu.edu.hkwww.stanford.edu
– polyu.edu.hk (158.132.0.0) Harnet
(192.245.196.0)
– Harnet Scramento.cw.net (166.49.0.0)
– Scramento.cw.net SanFrancisco.cw.net
(204.70.0.0)
– SanFrancisco.cw.net  bbnplanet.net
– bbn.planet.net stanford.edu (171.64.0.0)
5
Not all routers are equal
• Interior routers: Only know how to route
datagrams to destinations within the same AS.
• Border routers: Interface between its AS and
other AS:
– A nonbackbone router usually has a “default route”
to another “more knowledgeable” router for
“unknown destinations.”
– A backbone router is supposed to know every IP
network in the Internet.
• Intradomain routing vs Interdomain routing
6
Intradomain routing
• Two main approaches: Distance vector and link
state.
– Both are implemented as distributed protocols
(centralization is the enemy of scalability).
– In the distance vector approach, each router talks
only to its directly connected neighbors, but it tells
them everything it has learned.
– In the link state approach, each router talks to all
other routers in the network, but it tells them only
what it knows for sure (only the states of its directly
connected links).
7
Distance vector routing protocols
• Each node does two things:
– It constructs a one-dimensional array (a vector)
containing the “distances” (costs) to all other nodes.
– It distributes the vector to its immediate neighbors.
• Each node’s vector initially consists of
– a distance of 0 for reaching itself, and
– a distance of infinity for reaching other nodes.
• When the algorithm converges, each node
knows for each destination node
– (1) the next node closer to the destination, and
– (2) the associated cost for this path.
8
An example
B
C
A
D
E
F
G
9
An example
• Node A’s routing table (using hop count as the
cost)
1. Initially
Destination
A
Cost
0
Next hop
A
3. After convergence
Destination
A
B
2. After talking with its neighbors
C
D
Destination Cost
Next hop
E
A
0
A
F
B
1
B
G
C
1
C
E
1
E
F
1
F
Cost
0
1
1
2
1
1
2
Next hop
A
B
C
C
E
F
F
10
Dynamic routing
• Each node periodically sends its distance vector
to its neighbor (periodic updates).
• If link A-C fails,
–
–
–
–
The cost in A’s entry to C becomes infinity.
B will advertise to A a path to C with cost 1.
F will advertise to A a path to C with cost 2.
Therefore, A’ entry to C is updated to: Next hop = B
and cost = 2.
11
Dynamic routing
• Each node may send an updated distance vector
to its neighbor, triggered by external events
(triggered updates).
• If link A-C fails,
– The cost in A’s entry to C becomes infinity.
– A will immediately send its updated vector to B, E,
F.
– This update does not affect B’s routing table.
– However, E will update its entry to C from 2 to
infinity, and then from infinity to 3; and similarly
for F.
12
Routing loops
• If the link A-E fails,
– The corresponding entry in A is updated.
– A triggered update from A, and periodic updates
from B, C, and F.
– Possible timing (>: earlier than):
• Case 1: A > B and A > C and A > F
• Case 2: A > B and A > C but A < F
• Case 3: A > B and A > F, but A < C
– In case 1, all nodes will eventually conclude that E
is unreachable.
– In case 2, a routing loop between A and F forms.
13
Routing loops
– In case 3, a routing loop between A and C forms.
• In both cases 2 and 3, the cost to E keeps on increasing.
– One solution to this problem is to declare the link
unusable when the cost reaches, say, 16 (count to
infinity).
• Split horizon is another solution to solving 2node routing loop.
– A node will not advertise a route back to another
node that serves as the next hop for that route.
– For example, B, C, F will not advertise their routes to
E back to A.
14
Routing information protocol (RIP)
• RIP implements the distance vector approach.
• A hop count of 16 is interpreted as infinity.
• Each RIP router broadcasts its distance vectors
to its neighbors every 30 seconds.
• RIP is implemented at the application level.
– Common daemons used on the Unix systems are the
programs routed and gated.
– RIP packets are carried over UDP and IP.
15
Link state routing protocols
• In this approach, every nodes maintains the
network topology information in a link state
database.
• Thus, this approach relies on two mechanisms:
– A reliable flooding for dissemination of link-state
information, and
– a shortest-path algorithm for computing routes.
16
An example
B
C
A
D
E
F
G
17
An example
• Link state database:
From
A
A
A
A
A
A
B
B
B
B
B
B
:
:
To
B
C
D
E
F
G
A
C
D
E
F
G
:
:
Metric
1
1
1
1
1
1
1
1
1
1
1
1
:
:
Seq. Number
1
1
1
1
1
1
1
1
1
1
1
1
:
:
18
Link state updates
• The link state can be based on any metric,
including hop count, latency, throughput,
monetary cost, etc.
• When a link state is changed, say from 1 to 2
for AE, A will send this update to all other
nodes through a reliable flooding scheme.
– A sends the update to B, C, F.
– A ensures the reliable transmission of the update
through positive acknowledgment and
retransmission.
19
Link state updates
– B, C, F, upon receiving the update, compare the
sequence number of the update and that in their
databases.
• If the sequence number in the update is higher, update the
link state in the database, and forward it to other interfaces
other than the one where the update is received.
• Otherwise, drop the update and no change in the database.
– Although C receives two copies of the update, it
forwards only one copy to D and the other is
discarded.
– The new link state database becomes
20
Link state updates
From
A
A
A
A
A
A
B
B
B
B
B
B
:
:
To
B
C
D
E
F
G
A
C
D
E
F
G
:
:
Metric
1
1
1
2
1
1
1
1
1
1
1
1
:
:
Seq. Number
1
1
1
2
1
1
1
1
1
1
1
1
:
:
21
Computing optimal paths
• Given a link state database for the network
topology, each node can apply any shortest-path
algorithms to find optimal paths from itself to
other nodes in the network.
• For example, using the hop count as the metric,
we have for node A:
22
Computing optimal paths
B
C
D
A
E
F
G
23
Open shortest path first (OSPF) protocol
• OSPF implements a link state approach.
• OSPF supports different type-of-service routing
by having different sets of metric for route
computation.
• OSPF supports equal-cost routes to a
destination.
• OSPF reduces the amount of routing update
messages as compared with RIP.
• OSPF provides fast and loopless convergence.
24
Interdomain routing
• Interdomain routing is especially important for
backbone routers.
• While intradomain routing is based on a
measurable quantity, interdomain routing is
based on trust and policy.
– The metric used in one domain may not be
meaningful in another domain.
• Therefore, the objective of interdomain routing
is reachability, not optimality.
– An interdomain routing protocol must be able to
find a loopless path to reach another AS.
25
Border gateway protocol (BGP)
• The primary goal of BGP is to provide efficient
and robust interdomain routing with rapid
convergence and loop detection.
– This goal is accomplished by the concept of path
vector.
• Two BGP speakers establish a BGP connection
by exchanging “open” messages.
– The connection is maintained by periodic exchanges
of “keepalive” messages.
– Routing information updates are sent in “update”
messages.
26
An example
Customer P
(AS 4)
128.96.0.0
192.4.153.0
Customer Q
(AS 5)
192.4.32.0
192.4.3.0
Customer R
(AS 6)
192.12.69.0
Customer S
(AS 7)
192.4.54.0
192.4.23.0
Regional provider A
(AS 2)
Backbone network
(AS 1)
Regional provider B
(AS 3)
27
An example
• The BGP speakers of AS4-7 advertise
reachability information to their regional
providers.
• AS2’s BGP speaker advertises reachability of
128.96.0.0, 192.4.153.0 with (AS2, AS4), and
192.4.32.0, and 192.4.3.0 with (AS2, AS5) to
AS1.
• AS1 will in turn advertise this reachability
information to AS3 with (AS1, AS2, AS4) and
(AS1, AS2, AS5), respectively.
28
Another example
Customer P
(AS 4)
128.96.0.0
192.4.153.0
Customer Q
(AS 5)
192.4.32.0
192.4.3.0
Customer R
(AS 6)
192.12.69.0
Customer S
(AS 7)
192.4.54.0
192.4.23.0
Regional provider A
(AS 2)
Backbone network
(AS 1)
Regional provider B
(AS 3)
29
Another example
• AS3 now receives two sets of reachability
information for 128.96.0.0, 192.4.153.0:
– One from AS1 with (AS1, AS2, AS4), and
– another from AS2 with (AS2, AS4).
– Now, AS3 could decide based on the minimal
number of AS traversal.
• The route (AS3, AS2, AS4) may return back to
AS2 via AS1.
– AS2 will refuse to use this route when it finds its
AS number in the advertisement.
30