Transcript Internal Routers

CMPT 371
Data Communications and Networking
Routing in the Internet
Internal Routing Protocols
0
© Janice Regan, CMPT 128, 2007-2012
Hierarchical Routing



So far when considering routing we have considered a “group of
routers” and seen how to develop routes between them, and forward
packets along those routes.
Both distance vector and link state routing have limitations when
scaling to very large networks. The amount of information
exchanged becomes prohibitive. (possible for your local network but
not for the entire Internet)
Each administrative entity wants autonomy to optimize and configure
their own networks for their own purposes. No one configuration will
satisfy everyone
 Need to allow each administrative entity the freedom to configure
and protect their network as they wish
 But we still need to be able to communicate between these
different networks
Janice Regan © Oct 2007
1
Autonomous Systems (AS)
 Group of routers and hosts controlled by a single
administrative authority
 Common routing protocol (interior routing protocol or
IRP) for all members of the group

Defines mechanisms for discovering, validating, and
maintaining routes within the autonomous system
 A connected network within the local group

There is at least one route between any pair of nodes
 Routing protocol for propagating subset of routing
information to other autonomous systems on the
internet (Exterior routing protocol or ERP)
Janice Regan © Oct 2007
2
Interior Router Protocol (IRP)
 Routers need complete information about the
local AS




IRP Passes routing information between routers within AS
Needs a detailed model

what information is sent between routers

formats of messages carrying this information

frequency of exchange of this information

Algorithms for routing (creating routing tables) and forwarding
(using routing tables). Are these algorithms distributed?
Local? Global? Etc.
Routing and forwarding algorithms may differ between ASs as
may other parts of the model (for example DV or LS)
Also called intra-autonomous system routing protocol
Janice Regan © Oct 2007
3
Some ASs
AS A
B1
IRP A
A
1
IRP B
A
2
AS B
B2
B3
B6
B4
Gateway
router
B5
A
3
A
4
IRP C
C1
C2
C5
AS C
Janice Regan © Oct 2007
C3
C4
4
Some ASs
 Only routers are shown in the previous diagrams, the
networks of hosts that communicate with the Internet
through each of the routers are shown as dotted lines
 A host is attached through one of these networks to its
default router. The router that attaches it the larger
internet
 The default router for the source host is called the
source router
 The default router for the destination host is the
destination router
Janice Regan © Oct 2007
5
Routing with ASs
 If both the source router and the destination router are in
the same AS then the IRP for that AS is used to route
the packet from the source to the receiver
 If the source router and the destination router are in
different ASs then



the IRP for the source AS is used to reach the gateway router
for the source AS
The gateway router uses another protocol (the ERP, more later)
to get the packet to the gateway router of the destination AS.
The gateway router of the destination AS uses the IRP of the
destination AS to send the packet to its destination with the
destination AS
Janice Regan © Oct 2007
6
Exterior Routing Protocol
 ERP is an External Routing Protocol
 Routers need some information about external
ASs


Use ERP to communicate outside AS
At least one routers in the AS must do external
routing
 When more than one router in the AS does external
routing must also consider finding the fastest path
between gateway routers in the local AS
 ERP supplies summary information on reachability of
group members to routers outside the AS
Janice Regan © Oct 2007
7
Application of IRP and ERP
Figure
Stallings
Janice19.5
Regan
© Oct(2003)
2007
8
Distance-vector Routing Approach

Each node exchanges information with neighbor nodes



Each node maintains vector of link costs for each directly attached
node and distance and next-hop values for each destination node in
the system
A node must transmit large amounts of information



Neighbors are both directly connected to same system
Distance vector to all neighbors, Containing estimated path cost to all
nodes in a configuration and next hop labels
Changes take long time to propagate (count to infinity)
Used by first generation routing algorithm for ARPANET and by
Routing Information Protocol (RIP, routed) RIP is an internal
gateway protocol (IGP) used between routers within an AS
Janice Regan © Oct 2007
9
Routing Information Protocol
 RIP, The simplest dynamic distance vector




routing protocol still in use, was built and adopted
before a formal standard was available (RFC
1058 RIPv1, 2453 RIPv2 )
Implemented in LINUX as the routed process.
Adequate only for small and stable ASs
based on the Bellman-Ford (or distance vector)
algorithm
helps control count to infinity problem by
specifying a maximum hop count of 15
Janice Regan © Oct 2007
10
Routing Information Protocol
 Uses a simple metric, hop count
 Not designed to deal with more complicated
dynamic metrics such as delay, reliability or
load (these can cause route oscillations)
 Helps control oscillation between equal cost
routes by retaining original route unless a route
with a lower cost is found.
 Helps prevent slow convergence (after changes
in the topology of the network) by sending update
messages immediately after updates have been
completed (triggered updates)
Janice Regan © Oct 2007
11
Updating and RIP
 Routing tables are updated or maintained

Each router will periodically (every 30 seconds)
broadcast its routing table
 If no update is received from a router for 180
seconds, that router is considered to no longer be
reachable
 Each router will process the received updates,
adding new entries, updating entries for which a
lower cost path has been located and updating
entries for directly connected nodes whose cost
changed
 If the routing information changes during the update
process the router will immediately broadcast the
modified tables to its neighbors (called a triggered
update)
Janice Regan © Oct 2007
12
Link-state Routing Approach
 When router initialized and at intervals thereafter, it




determines link cost on each interface (cost to each
directly connected node)
Advertises set of link costs to other nodes in topology
Each node constructs routing table containing
minimum cost paths to all attached nodes ( costs and
first hop to each router) using the data received from all
other nodes advertisements (information on nearest
neighbors only to reduce packet size).
Open shortest path first (OSPF) protocol uses link-state
routing. (a common IRP)
Second generation routing algorithm for ARPANET
Janice Regan © Oct 2007
13
Open Shortest Path First:
 OSPF is the preferred IGP of Internet
 Uses a Link State Routing Algorithm (RFC 2328) Each
router

keeps a database of information based on local costs and
received update packets from other routers in the AS




Each update includes cost information from one router to each of
its neighbors
Can build directed graph showing topology and path costs for
entire network from this information (for all routers)
Uses the database and Dykstra’s algorithm to determine least
cost paths
Advertises its locally determined routing table periodically and
when it changes (to all routers in the network)
Janice Regan © Oct 2007
14
Sample AS
Figure
19.7Regan
Stallings
Janice
© (2003)
Oct 2007
15
Directed Graph for OSPF
 Vertices or nodes are routers and networks
 Types of Network


Transit: data not originating in network can pass through the
network, more than one router is attached to the network
Stub: data not originating in network can enter only. One router
is attached to network
 Edges, associated costs at output of routers


Connect two routers with a pair of edges
Connect router to transit network with pair of edges (network to
router edge has a cost of 0), or to stub network with single
edge
Janice Regan © Oct 2007
16
Directed Graph of AS
Figure
19.8Regan
Stallings
Janice
© (2003)
Oct 2007
17
Dividing an AS into Areas






Many networks are large and complex it is often useful to divide them
into areas and deal with each smaller area separately
A large advantage of OSPF is that it includes mechanisms for
dealing with ASs partitioned into areas.
When an AS is divided into areas the areas are chosen so they can
be connected by a backbone of routers
Any router which is part of an area, but also communicates with other
areas, is also a part of the backbone area.
The backbone is a special area. The information passing between all
other areas travels through the backbone routers (dark ovals in
diagram)
Routers in each area run their own copy of the routing process and
have their own topological link-state data base. Routers in one area
have no detailed knowledge of routing in other areas.
Janice Regan © Oct 2007
18
Backbone routers
3,4,5,6,7,10,11
AS Boundary routers
5,7
Internal routers
1,2,5,6,8,9,12
Area Border routers
3,4,7,10,11
1
b
Includes
Router 4
2
b
2
3
b
Includes
Routers 7
and 11
From
notes
of©Lou
Janice
Regan
Oct Hafer,
2007 after RFC1131: AS divided into areas
19
Types of routers in an AS
 Internal Routers: all connected networks belong to
the same area or with only backbone interfaces
 Area Border Routers: not internal, run one copy of
routing algorithm for backbone, and one copy for
each attached area
 Backbone Routers: has at least one interface to
the backbone. Can be an internal router if all
interfaces are with the backbone. Otherwise it is an
area border router
 AS boundary routers: Part of the AS but also
communicates with routers outside the AS using
and EGP. Can be routers of an of the above types
Janice Regan © Oct 2007
20
Neighbor Routers
 Any pair of routers attached to the same single
network segment (single broadcast address)
can become neighbors
 To become neighbors they must agree that they
are neighbors
 The pair of routers negotiates this agreement
using and exchange of Hello packets (more
later) to assure a two way link is established
© Janice Regan, 2006
21
Adjacent routers
 Routers establish an adjacency if they will be
exchanging LSAs.(link state announcement
packets that carry routing information between
routers)
 A router on a particular physical segment will
not necessarily be adjacent to all other routers
on that segment
 A router with multiple interfaces may
simultaneously be adjacent to routers on more
than one network segment
© Janice Regan, 2006
22
OSPF messages


Encapsulated in IP datagrams
5 types of messages, all message types begin
with a common header
 Message types are
1.
2.
3.
4.
5.
Hello
Database description
Link status request,
Link status update
Link status acknowledgement
© Janice Regan, 2006
23
OSPF operation (1)
1.
Meet your neighbors


2.
Hello messages are used to establish and test neighbor
reachability
Two OSPF router may be neighbors if they are on the same
network segment
Make good friends:



Database description, link state request update and ack are
used for forming adjacencies (making friends)
Adjacencies are agreements to exchange Link State
Announcements. Adjacencies are not established with all
neighbors, just an optimal subset.
Database description, link state request, link state update and link
state ack messages are used to establish adjacency
© Janice Regan, 2006
24
OSPF operation (2)
3. Keeping in touch with friends
3. Send Hello messages periodically to verify that
neighbors are still neighbors
4. Break the neighbor (and adjacency relations) if you
do not hear from a neighbor (receive a hello) for 3
periods
5. Send update information about any changes in
routing to your adjacent neighbors when you have it
(send Link state announcements LSAs)
6. Update your routing database based on LSAs
received from your adjacent neighbors
© Janice Regan, 2007-2012
25
Flooding protocol: conditions
 A message(LSA) contains a database record. A
database record contains information about one
link between two routers in the graph discussed
earlier. (one link is in one direction)
 Each message contains a time stamp or
message number
 These message numbers are used by the
receiving node to determine age of the record
 Send means transmit through all attached
interfaces except the one on which the incoming
message arrived
© Janice Regan, 2006
26
Flooding protocol
 Receive message: Find the corresponding
record in the local database if it exists

If the record is not yet in the local database add the
record. Send the message
 If the record’s message number is larger than the
message number in the data base, replace the
message in the database with the new record. Send
the message.
 If the records message number is the same as the
message number in the database do nothing
 If the records message number is smaller than the
message number in the database, send the record in
the database back through the interface on which
the message arrived
© Janice Regan, 2006
27
link state advertisements (1)
 Router link advertisement
 Originated by all routers
 Flooded throughout a single area only
 Describes the states of the router’s interfaces to the
area
 Network link advertisement
 Originated by broadcast networks
 Flooded throughout a single area only
 Contains a list of routers connected to the network
© Janice Regan, 2006
28
Backbone routers
3,4,5,6,7,10,11
AS Boundary routers
5,7
Internal routers
1,2,5,6,8,9,12
Area Border routers
3,4,7,10,11
1
b
Includes
Router 4
2
b
2
3
b
Includes
Routers 7
and 11
From
notes
of©Lou
Janice
Regan
Oct Hafer,
2007 after RFC1131: AS divided into areas
29
link state advertisements (2)
 Summary link advertisement
 Originated by border area routers
 Flooded throughout a area and backbone
 Describes a route outside the local area but within
the AS
 AS external link advertisement
 Originated by AS boundary area routers
 Flooded throughout the AS
 Contains a route to a destination outside the AS in
another AS
© Janice Regan, 2006
30