-------------------------------------------------
IP ROUTING
originally from Dr. Sidnie Feit.
--------------------------------------------------
Contents
--------------------------------------------------
Part 1. IP Routing Protocols
Part 2. RIP & RIP ver 2
Part 3. IGRP & EIGRP
Part 4. OSPF
Part 5. OSI & BGP
--------------------------------------------------
OPEN SHORTEST PATH FIRST
(Part 4 of 5)
In 1988, the internet Engineering Task Force (IETF) started
work on a new standard protocol to replace RIP. The result
was the Open Shortest Path First (OSPF) Interior Routing
Protocol, a routing protocol intended for use between
Autonomous System (AS) of all sizes. In 1990, OSPF was
recommended as a proposed standard. The protocol is
nonproprietary (public) technology.
Recall the link state router discovers paths by building a
map of a network and using a map to build a tree with the
router as its root. A metric value is computed for each
path or paths are selected for each IP Type of Service.
OSPF uses both link state paths and distance metrics. OSPF
is designed to scale well and to spread accurate routing
information quickly. In addition OSPF Support:
- Quick detection of topology and very rapiid establishment
of loop-free routes
- Low overhead, using updates that report cchanges rather
than all routes
- Traffic splitting accross multiple equivaalent paths.
- Routing based on Type of Service.
- Use of multicast on LANs.
- Mask and Subnetting and supernetting.
- Authentication.
In April of 1990, when the very large NASA Science internet
converted to OSPF, NASA routing traffic decreased
dramatically. After a change or disruption in the network,
globally correct routing information was established very
quickly -- typically within a few seconds, as compared to
minutes for some older protocol.
Version 2 of OSPF was published in mid-1991, and a revised
version 2 came out in March 1994. This was 216-page document
, so the description below should be considered a rough
outline of the protocol.
Autonomous System, Areas and Networks
In the OSPF standard, the term network means an IP network,
a subnet, or a CIDR supernet. Similary, a network mask
identifies a network, a subnet, or a CIDR supernet. An Area
is set of contiguous networks and hosts, along with any
routers any routers having interfaces to the networks.
An Autonomous System that uses OSPF is made up of one or
more areas. Each area has a number. Area 0 is a connected to
backbone that links to all of the other areas and glues the
Autonomous System alltogether.
__________________
( )
( area 0 )
( Backbone )
( )
(__________________)
/ \
______/__ __\_____
( ) ( )
( Area 1 ) ( Area 0 )
( ) ( )
(_________) (________)
OSPF backbone and areas.
Routing within an area is based on a complete link state map
for the area. OSPF scales well because a router needs to
know detailed metric and information only about an area that
it belongs to.
Every OSPF router in an area keeps an identical routing
database describing the topology and status of all of the
elements in the area. The database is used to construct an
area map. This database includes the state of every router,
each router's usable interface, is connected networks, and
its adjacent routers.
Whenever a change occurs (such as a link goes down), this
information propagated trough the area. This promotes
accurate routing and quick response to trouble. For example,
if OSPF routing were used in the network in figure below,
router A would quickly be informed that the link to B was
down and would realize immediatelly that there was no usable
route to network N.
________ _____ _____ _____ ________
|Router A|____| |__| |__| |--//--|Router B|
|________|\ |_____| |_____| |_____| link |________|
\ \ _____ _____ / / is
\ \_| |__| |_/ | down
\ |_____| |_____| |
\ _____ _____ __|__
\__| |__| |__| |
|_____| |_____| |_____|
A router that is initializing (just powered on or reset)
obtains a copy of the current database from an ajacent
neighbor. After that, only changes need to be communicated.
Changes get known quickly because OSPF uses an efficient
flooding algorithm to to spread information trough the area.
OSPF Area Shortest Paths
A router uses its area database to cunstruct a tree of
shortest paths with itself as the root. This tree is used to
build the routing table. If Type os Service (TOS) routing is
supported in the areas, a separate tree and set of routes is
built for each of Type of Service value.
The OSPF Backbone, Borders and Boundaries
Areas are glued together by the backbone. The backbone
contains all router that belong to multiple areas, as well
as any networks and routers and routers not assigned to any
other area. Recall that area are numbered and the backbone
is area 0.
A border router belongs to one or more areas and to the
backbone. If an Autonomous System is connected to the
outside world, boundary routers learn routes to networks
that are external to the autonomous system.
_____
.........................| G |......
: _____ Area 0 |_____| :
: | A |_ Backbone | :
: |_____| \ | :
: | \ \____________ | :
: | \______ \ | :
: | \ \ | :
: _____ _\___ \__|__ :
:.| B |.......| F |...| C |.....
..|_____|..... |_____|...|_____|....
: | : : \ / :
: __|_ : : \ ___/_ :
: | D | : : | E | :
: |____| : : |_____| :
: Area 1 : : Area 2 :
:............: :..................:
Routing and areas in Autonomous System
In figure above, backbone area 0 includes Router A, B, C,
F, G. Area 1 includes Routers B and D. Area 2 includes
Router C, E, and F. Routers B, C, and F are border routers.
Router G is a boundary router. Router B knows the full
topologies of area 1 and of the backbone. Similarly, Routers
C and F know the full topologies of area 2 and of the
backbone.
The Backbone must be contiguous. What happened if a
structuring of a network or an equipment failure causes the
backbone to be broken? Somtimes, virtual link can be used to
tie together pieces of the backbone.
A virtual link can be defined between two backbone router
that interfaces to the same area. The virtual link is
treated like unnumbered point-to-point link. The cost of
the virtual link. The cost of virtual link is the total path
costof the route between the two routers.
As shown in figur below, if link from A to F were lost,
Router F would no longer be connected to the other
backbone routers via a backbone link. The virtual link F-E-C
could be used t restore the connectedness of the backbone.
_____
.........................| G |......
: _____ Area 0 |_____| :
: | A |_ Backbone | :
: |_____| \ | :
: | : \____________ | :
: | :........... \ | :
: | (link down): \ | :
: __|__ __:__ \__|__ :
:.| B |.......| F |...| C |.....
..|_____|..... |_____|...|_____|....
: | : : \ / :
: __|_ : : \ ___/_ :
: | D | : : | E | :
: |____| : : |_____| :
: Area 1 : : Area 2 :
:............: :..................:
Defining a virtual link
Routing Across an OSPF Area Border
A border router knows the complete topology of each area to
which it connects. Recall that every border router belongs
to the backbone, and so it knows the full topology.
Using Summarized Information Inside an OSPF Area
Each border router summaries area information and tells the
other backbone router how far it is from networks within its
own area(s). This enables every border router to calculate
distance to destinations outside its own areas and then pass
that information into its own areas.
The summarized information includes a network, subnet, or
supernet identifier; a network mask; and at the distance
from the router to the external router.
For example, in figure below, suppose that the router E
wants to choose a path to a network M. Router E uses its
area database to find the distance dc and df to the network
routers C and F. Each of this, has reported its distance mc
and mf to network M. Router E can compare dc + mc with df +
mf and pick the shortest route.
_____
.........................| G |......
: _____ Area 0 |_____| :
: | A |_ Backbone | :
: |_____| \ | :
: | \ \____________ | :
: | \__________ \ | :
: | \ \ | :
: __|__ ___\_ \__|__ :
:.| B |.......| F |...| C |.....
..|_____|.... |_____|...|_____|....
: | : : \ / :
: __|_ : : \ ___/_ :
: | D | : : | E | :
: |____| : : |_____| :
: | : : | :
: |=========| : : |==========| :
: network M : : network N :
: : : :
: area 1 : : area 2 :
:.............: :..................:
Routing between areas
Note that the router B should not bother to pass summarized
distance information into area 1. There is only one path,
and so, no simple default entry suffices for all external
destinations.
Destinations Outside of OSPF AS
Many Autonomous system are connected to the internet or to
other Autonomous Systems. OSPF boundary routers provide
information about distances to the network outside of the
Autonomous System.
There are two types of OSPF extenal metrics. Type 1 is
equivalent to the local link state metric. Type two metrics
are the long distance metrics. They're measured by the
greater order of magnitude. If an analogy is made with
driving distances, think of typing two routes as being
derived from the national roadmap. And measured in hundered
of miles, while type one metrics use local distance measured
in miles.
Figure below shows two routes to an external network, N. The
type 1 metrics would be ignored in the distance calculation,
and the type 2 metric equal to 2 would be chosen.
Network N
|==============|
|
_|_
| |<--------------
|___|<--- |
| type 2 = 6
type 2 = 2 |
___|____ ___|_____
|Boundary| |Boundary |
.....| Router |.| Router |.....
: |________| |_________| :
: ^ ^ :
: | | :
: 287 \ / 64 :
: \________/ :
: | | :
: |________| :
:...............................
Choosing Route Type 2 Metrics.
Another feature of OSPF (especially convinient for Service
Providers) is that a router on the boundary of autonomous
systems can act as a route server and can advertise entries
that identify routes trough other boundary routers.
Information would include:
Destination, Metric, Boundary Router to be used.
OSPF Protocol
Now we are to describe the internals of the OSPF protocol.
Every OSPF router mantains a detailed database of
information needed to bould its area routing tree, such as
description of:
- Each router's interfaces, connections, annd ascociate
metrics.
- Each multiaccess network and a list of alll routers on the
networks
How does a router gets its information? It starts by finding
out who its neighbors are by mean of hello messages.
Hello messages
Each OSPF router is configured with a unique identifier that
is used in messages. Usually, the router's smallest IP
address is used as its unique ID.
A router periodically multicasts Hello messages in a multi
access network (such as FDDI LAN, Ethernet, Token Ring).
to let other Routers know that it is active. It also sends
hello messages to peers attached by point-to-point links or
virtual circuits to let these network know that it is awake.
One reason that Hello messages works well is that a message
contains a list of IDs of neighbours whose Hellos the sender
anlready has heard. That way, every router knows whether its
messages are getting trough.
Designated Router
On a multiaccess route, Hello messages also are used to
select and identify a designated router. A designated router
has two jobs:
- It s responsible for reliability updatingg its adjacent
neighbors with the latest network topology news.
- It originates network links advertisementts, which lists
all routers connected to multiaccess network.
In figure below, Designated router A exchanges information
with routers B, C and D on its lan as well as with router E,
which is connected by a point-to-point link.
====
__________ ||
| Router B |__|| Designated
|__________| || Router
|| ________ ________
__________ ||__|Router A|___|Router E|
| Router C |__|| |________| |________|
|__________| ||
__________ ||
| Router D |__||
|__________| ||
====
A Designated routers updates its neighbours
Adjacencies
Designated router A acts as the local expert and keeps up to
date on the local topology. It then communicates this
topology to the adjacent routers.
B, C, and D keep their databases sincronize by talking to A.
They do not have to talk to one another. Two Routers that
synchronize their database with one another are called
adjacent. B and C are neighbor, but they are not adjacent to
one another.
Clearly, this is an efficient method of keeping the LAN
router database synchronized. It can also be used by frame
relay or X.25 networks. Routers can exchange Hellos accross
virtual circuits, choose a designated router, and
synchronize their databases with the designated router. This
speeds up synchronization and cuts down on network traffic.
The loss of a designated router would be a pretty disruptive
event. For this reason, a backup designated router always is
selected and is ready to take over immediately.
Initializing a Router Database
Now suppose that router B has just been restarted after
being off-line for maintenance. First B listen to Hellos,
discover its neighbors, and finds out that Router A is the
designated router. Next, B brings itself up-to-date by
talking to A.
More specifically, A and B will exchange Database
Description messages contain a list of what it has in its
database. Each item has a sequence number that is used to
established which router has the freshest information for
the item (The sequence number of a routing entry is
increased whenever the entry is updated).
After this excange of this information is complete, each
knows :
- Which items are not yet in its local dataabase.
- Which items are present but out of date.
Link state request message are used to ask for entries that
are in need of an update. Link state update messages respond
to the these requests. After a full and acknowledged
exchange of information, the databases are sychronized. Link
State Update messages are also used to report changes in
topology. Topology updates are flooded through the area
topology. So that all database are kept in sychronization.
OSPF Messages Type.
The five message types used in the OSPF protocol exchanges
that we have described are:
*Hello
Used to identify neighbors, to elect a designated router for
a multi access network, to find out about as an "I am alive
signal".
*Database Description
During initialization, used to exchange information so that
a router can find out what data is missing from its
database.
*Link State Request
Used to ask for data that a router has discovered is
missing from its database or is out of date.
*Link State Update
Used to reply to a Link State Request and also to
dynamically report changes in network topology.
*Link State ACK
Used to confirm receipt of a Link State Update. The sender
will retransmit until an update is ACK-ed.
OSPF Messages
OSPF Messges are carried directly in IP Datagrams, with
protocol type 89. All OSPF messages start with 24-octet
header that is shown below. The type field contains a number
corresponding to the message type. The length is the total
length including the header.
Authentication type are registered in IANA. Secure and
authenticated transmission is important for the robustnes
of networks.
|<--8 bit-->|<---8 bit--->|<-----16 bit---->|
+-----------+-------------+-----------------+
| version=2 |Message type | message length |
+-----------+-------------+-----------------+
| ID of router that originated this message |
+-------------------------------------------+
| Area ID |
+-------------------------------------------+
| Checksum Authentication type |
+-------------------------------------------+
| Authentication data |
+-------------------------------------------+
| Authentication data |
+-------------------------------------------+
Standard 24-octet OSPF Message header
Contents of an OSPF Link State Update
The critical OSPF routing information is transmitted in Link
State update messages. Updates are sent between adjacent
routers. When the designated router on a broadcast network
receives an update, it multicast it to the other routers on
the network. Updates propagate area quite efficiently. Every
newly link-state advertisement must be acknowledged.
A Link State Update messages contains items that are called
advertisements. The type of advertisements are:
* Router links
The state of each of the interfaces on a router.
* Network links
The list of routers connected to the multiaccess network.
This is provided by the designated router on the net.
* Summary Link to a Network
A route to a network outside the local area but in the
Autonomous System. This is provided by the border router.
* Summary link to a Boundary Router
Route trough the Autonomous System to the its Boundary
Router. This is also provided by the border router.
* AS External link.
A route to destination in other AS. This is provided by
boundary router.
(
geocities.com/gandautama)