OSPF – Route Table Lookups

When an OSPF router examines the destination address of a packet, it takes the following steps to select the best route:

The lookup procedure described here adheres to RFC 2328. The earlier OSPF RFCs specify creating a set of matching routes first, then choosing the preferred path type, and choosing the longest match last.

1. Select the route or routes with the most specific match to the destination address. For example, if there are route entries for 172.16.64.0/18, 172.16.64.0/24, and 172.16.64.192/27 and the destination address is 172.16.64.205, the last entry will be chosen. The most specific match should
always be the longest match—the route with the longest address mask. The entries may be host, subnet, network, supernet, or default addresses. If no match can be found, an ICMP Destination Unreachable message will be sent to the source address and the packet will be dropped.
2. Prune the set of selected entries by eliminating less-preferred path types. Path types are prioritized in the following order, with 1 being the most-preferred and 4 being the least-preferred:
1. Intra-area paths
2. Inter-area paths
3. E1 external paths
4. E2 external paths

www.pdf24.org    Send article as PDF   

OSPF – Router Types

Internal Routers are routers whose interfaces all belong to the same area. These routers have a single link  state database.

Area Border Routers (ABRs) connect one or more areas to the backbone and act as a gateway for interarea traffic. An ABR always has at least one interface that belongs to the backbone, and must maintain a separate link state database for each of its connected areas. For this reason, ABRs often have more memory and perhaps more powerful processors than internal routers. An ABR will summarize the topological information of its attached areas into the backbone, which will then propagate the summary information to the other areas.

Backbone Routers are routers with at least one interface attached to the backbone. An Internal Router whose interfaces all belong to area 0 is also a Backbone Router.

Autonomous System Boundary Routers (ASBRs) are gateways for external traffic, injecting routes into the OSPF domain that were learned (redistributed) from some other protocol, such as the BGP and EIGRP processes. An ASBR can be located anywhere within the OSPF autonomous
system; it may be an Internal, Backbone , or ABR.

 

www.pdf24.org    Send article as PDF   

OSPF – Areas

Why Areas ?

OSPF, with its multiple databases and complex algorithms, can put greater demands on the memory and processors of a router than other routing protocols. As an internetwork grows, these demands can become significant or even crippling. And although flooding is more efficient than the periodic, full-table updates of RIP and IGRP, it can still place an unacceptable burden on the data links of a large internetwork.

OSPF uses areas to reduce these adverse effects. In the context of OSPF, an area is a logical grouping of  OSPF routers and links that effectively divide an OSPF domain into sub-domains. Routers within an area will have no detailed knowledge of the topology outside of their area.

  • A router must share an identical link state database only with the other routers in its area, not with the entire internetwork. The reduced size of the database reduces the impact on a router’s memory.
  • The smaller link state databases mean fewer LSAs to process and therefore less impact on the
    CPU.
  • Because the link state database must be maintained only within an area, most flooding is also
    limited to the area.

Three types of traffic may be defined in relation to areas:

  • Intra-area traffic consists of packets that are passed between routers within a single area.
  • Inter-area traffic consists of packets that are passed between routers in different areas.
  • External traffic consists of packets that are passed between a router within the OSPF domain and a
    router within another autonomous system.

Backbone Area :  Area ID 0 (or 0.0.0.0) is reserved for the backbone. The backbone is responsible for summarizing the
topographies of each area to every other area. For this reason, all inter-area traffic must pass through the backbone; non-backbone areas cannot exchange packets directly.

Stub Area

A stub area is an area into which AS External LSAs are not flooded. And if type 5 LSAs are not known inside an area, type 4 LSAs are unnecessary; these LSAs are also blocked. ABRs at the edge of a stub area will use Network Summary LSAs to advertise a single default route (destination 0.0.0.0) into the area. Any destination that the Internal Routers cannot match to an intra- or inter-area route will match the default route. Because the default route is carried in type 3 LSAs, it will not be advertised outside of the area.

Restrictions on stub areas
1. As in any area, all routers in a stub area must have identical link state databases. To ensure this condition, all stub routers will set a flag (the E-bit) in their Hello packets to zero; they will not accept any Hello from a router in which the E-bit is set to one. As a result, adjacencies will not be established with any router that is not configured as a stub router.
2. Virtual links cannot be configured within, or transit, a stub area.
3. No router within a stub area can be an ASBR. This restriction is intuitively understandable because ASBRs produce type 5 LSAs and type 5 LSAs cannot exist within a stub area.
4. A stub area may have more than one ABR, but because of the default route, the Internal Routers cannot determine which router is the optimal gateway to the ASBR.
Totally Stubby Areas

If memory is saved by blocking the propagation of type 5 and type 4 LSAs into an area, wouldn’t more memory be saved by blocking type 3 LSAs? In addressing this question, Cisco carries the concept of stub areas to its logical conclusion with a scheme known as totally stubby areas.
Totally stubby areas use a default route to reach not only destinations external to the autonomous system but also all destinations external to the area. The ABR of a totally stubby area will block not only AS External LSAs but also all Summary LSAs—with the exception of a single type 3 LSA to advertise the default route.

Not-So-Stubby Areas
A router with a few stub networks must be attached to the OSPF internetwork via one of the area 2 routers. The router supports only RIP, so the area 2 router will run RIP and redistribute the networks into OSPF. Unfortunately, this configuration makes the area 2 router an ASBR, and therefore area 2 can no longer be a stub area.

The RIP speaker does not need to learn routes from OSPF—a default route pointing to the area 2 router is all it needs. But all OSPF routers must know about the networks attached to the RIP router to route packets to them.

Not-so-stubby areas(NSSAs)[17] allow external routes to be advertised into the OSPF autonomous system while retaining the characteristics of a stub area to the rest of the autonomous system. To do this, the ASBR in an NSSA will originate type 7 LSAs to advertise the external destinations. These NSSA External LSAs are flooded throughout the NSSA but are blocked at the ABR.

The NSSA External LSA has a flag in its header known as the P-bit. The NSSA ASBR has the option of setting or clearing the P-bit. If the NSSA’s ABR receives a type 7 LSA with the P-bit set to one, it will translate the type 7 LSA into a type 5 LSA and flood it throughout the other areas. If the
P-bit is set to zero, no translation will take place and the destination in the type 7 LSA will not be advertised outside of the NSSA.

www.pdf24.org    Send article as PDF   

OSPF – LSA Types

 

  • LSA 1 (Router LSA)

Generated by all routers in an area to describe their directly attached links (Intra-area routes). These do not leave the area.

  • LSA 2 (Network LSA)

Generated by the DR of a broadcast or Nonbroadcast segment to describe the neighbors connected to the segment. These do not leave the area.

  • LSA 3 (Summary LSA)

Generated by the ABR to describe a route to neighbors outside the area. (Inter-area routes)

  • LSA 4 (Summary LSA)

Generated by the ABR to describe a route to an ASBR to neighbors outside the area.

  • LSA 5 (External LSA)

Generated by ASBR to describe routes redistributed into the area. These routes appear as E1 or E2 in the routing table. E2 (default) uses a static cost throughout the OSPF domain as it only takes the cost into account that is reported at redistribution. E1 uses a cumulative cost of the cost reported into the OSPF domain at redistribution plus the local cost to the ASBR.

  • LSA 6 (Multicast LSA)

Not supported on Cisco routers.

  • LSA 7 (NSSA External LSA)

Generated by an ASBR inside a NSSA to describe routes redistributed into the NSSA. LSA 7 is translated into LSA 5 as it leaves the NSSA. These routes appear as N1 or N2 in the ip routing table inside the NSSA. Much like LSA 5, N2 is a static cost while N1 is a cumulative cost that includes the cost upto the ASBR.

A good (and free) document for OSPF is the Cisco´s OSPF Design Guide, which can be found at:

http://www.cisco.com/en/US/tech/tk365/technologies_white_paper09186a0080094e9e.shtml

www.pdf24.org    Send article as PDF   

OSPF – Sequence Numbers, Checksum and Aging

Reliable Flooding: Sequencing, Checksums, and Aging
Each LSA contains three values that are used to ensure that the most recent copy of the LSA exists in
every database. These values are sequence number, checksum, and age.
OSPF uses a linear sequence number space and 32-bit signed sequence numbers ranging from InitialSequenceNumber (0x80000001) to
MaxSequenceNumber (0x7fffffff). When a router originates an LSA, the router sets the LSA’s sequence
number to InitialSequenceNumber. Each time the router produces a new instance of the LSA, the router
increments the sequence number by one.

Sequence number
If the present sequence number is MaxSequenceNumber and a new instance of the LSA must be created,
the router must first flush the old LSA from all databases. This is done by setting the age of the existing
LSA to MaxAge and reflooding it over all adjacencies. As soon as all adjacent neighbors have acknowledged the prematurely aged LSA, the new instance of the LSA with a sequence number of InitialSequenceNumber may be flooded.

Checksum

The checksum is a 16-bit integer calculated using a Fletcher algorithm. The checksum is calculated over
the entire LSA with the exception of the Age field (which changes as the LSA passes from node to node
and would therefore require recalculation of the checksum at each node). The checksum of each LSA is
also verified every five minutes as it resides in the link state database, to ensure that it has not been
corrupted in the database.

Aging

The age is an unsigned 16-bit integer that indicates the age of the LSA in seconds. The range is 0 to 3600
(1 hour, known as MaxAge). When a router originates an LSA, the router sets the age to 0. As the flooded
LSA transits a router, the age is incremented by a number of seconds specified by InfTransDelay. Cisco
routers have a default InfTransDelay of 1 second, which can be changed with the command ip ospf
transmit-delay. The age is also incremented as it resides in the database.

MaxAge
When an LSA reaches MaxAge, the LSA is reflooded and then flushed from the database. When a router
needs to flush an LSA from all databases, it prematurely sets the age to MaxAge and refloods it. Only the
router that originated the LSA can prematurely age it.

www.pdf24.org    Send article as PDF   

OSPF – Decision making when multiple instances of same LSA is received

1. Compare the sequence numbers. The LSA with the highest sequence number is more recent.
2. If the sequence numbers are equal, then compare the checksums. The LSA with the highest
unsigned checksum is the more recent.
3. If the checksums are equal, then compare the age. If only one of the LSAs has an age of MaxAge
(3600 seconds), it is considered the more recent. Else:
4. If the ages of the LSAs differ by more than 15 minutes (known as MaxAgeDiff), the LSA with the
lower age is more recent.
5. If none of the preceding conditions are met, the two LSAs are considered identical.

www.pdf24.org    Send article as PDF   

OSPF – Flooding

What is Flooding ?

To operate the OSPF protocol in a network, it is mandatory that each and every router in that network will have a clear-cut idea of the entire network topology. For that routers should send the update to each other. This process is called Flooding.

In short , Flooding is the process by which these changed or new LSAs are sent throughout the network, to
ensure that the database of every node is updated and remains identical to all other nodes’ databases.

Flooding makes use of the following two OSPF packet types:

  • Link State Update packets (type 4)
  • Link State Acknowledgment packets (type 5)

Each Link State Update and Acknowledgment packet may carry multiple LSAs.

On point-to-point networks, updates are sent to the multicast address AllSPFRouters (224.0.0.5). On
point-to-multipoint and virtual link networks, updates are unicasted to the interface addresses of the
adjacent neighbors.
On broadcast networks, DRothers form adjacencies only with the DR and BDR. Therefore, updates are
sent to the address AllDRouters (224.0.0.6). The DR in turn multicasts an Update packets containing the
LSA to all adjacent routers on the network using the address AllSPFRouters. All routers then flood the
LSA out all other interfaces . Although the BDR hears and records LSAs multicast from
DRothers, it will not reflood or acknowledge them unless the DR fails to do so. The same DR/BDR
functionality exists on NBMA networks, except that LSAs are unicast from DRothers to the DR and
BDR, and the DR unicasts a copy of the LSA to all adjacent neighbors.

 

www.pdf24.org    Send article as PDF   

OSPF – The Neighbor State Machine

Down.
The initial state of a neighbor conversation indicates that no Hellos have been heard from the neighbor in
the last RouterDeadInterval. Hellos are not sent to down neighbors unless those neighbors are on NBMA
networks; in this case, Hellos are sent every PollInterval. If a neighbor transitions to the Down state from
some higher state, the link state Retransmission List, Database Summary List, and link state request list
are cleared.
Attempt.
This state applies only to neighbors on NBMA networks, where neighbors are manually configured. A
DR-eligible router will transition a neighbor to the Attempt state when the interface to the neighbor first
becomes Active or when the router is the DR or BDR. A router will send packets to a neighbor in Attempt
state at the HelloInterval instead of the PollInterval.

Init.
This state indicates that a Hello packet has been seen from the neighbor in the last RouterDeadInterval,
but 2-Way communication has not yet been established. A router will include the Router IDs of all
neighbors in this state or higher in the Neighbor field of the Hello packets.

2-Way.
This state indicates that the router has seen its own Router ID in the Neighbor field of the neighbor’s
Hello packets, which means that a bidirectional conversation has been established. On multi-access
networks, neighbors must be in this state or higher to be eligible to be elected as the DR or BDR. The
reception of a Database Description packet from a neighbor in the init state will also cause a transition to
2-Way.

ExStart.
In this state, the router and its neighbor establish a master/slave relationship and determine the initial DD
sequence number in preparation for the exchange of Database Description packets. The neighbor with the
highest interface address becomes the master.

Exchange.
The router sends Database Description packets describing its entire link state database to neighbors that
are in the Exchange state. The router may also send Link State Request packets, requesting more recent
LSAs, to neighbors in this state.

Loading.
The router will send Link State Request packets to neighbors that are in the Loading state, requesting
more recent LSAs that have been discovered in the Exchange state but have not yet been received.

Full.
Neighbors in this state are fully adjacent, and the adjacencies will appear in Router LSAs and Network
LSAs.

Three flags in the DD packet are used to manage the adjacency building process:
1. The I-bit, or Initial bit, which when set indicates the first DD packet sent
2. The M-bit, or More bit, which when set indicates that this is not the last DD packet to be sent
3. The MS-bit, or Master/Slave bit, which is set in the DD packets originated by the master

www.pdf24.org    Send article as PDF   

OSPF – The Interface State Machine

The Interface State Machine
An OSPF-enabled interface will transition through several states before it becomes fully functional.
Those states are Down, Point-to-Point, Waiting, DR, Backup, DRother, and Loopback.
Down.
This is the initial interface state. The interface is not functional, all interface parameters are set to their
initial values, and no protocol traffic is transmitted or received on the interface.
Point-to-Point.
This state is applicable only to interfaces connected to point-to-point, point-to-multipoint, and virtual link
network types. When an interface transitions to this state, it is fully functional. It will begin sending Hello
packets every HelloInterval and will attempt to establish an adjacency with the neighbor at the other end
of the link.
Waiting.
This state is applicable only to interfaces connected to broadcast and NBMA network types. When an
interface transitions to this state, it will begin sending and receiving Hello packets and will set the wait
timer. The router will attempt to identify the network’s DR and BDR while in this state.
DR.
In this state, the router is the DR on the attached network and will establish adjacencies with the other
routers on the multi-access network.
Backup.
In this state, the router is the BDR on the attached network and will establish adjacencies with the other
routers on the multi-access network.
DRother.
In this state, the router is neither the DR nor the BDR on the attached network. It will form adjacencies
only with the DR and BDR, although it will track all neighbors on the network.
Loopback.
In this state, the interface is looped back via software or hardware. Although packets cannot transit an
interface in this state, the interface address is still advertised in router LSAs (described later) so that test
packets can find their way to the interface.

www.pdf24.org    Send article as PDF   

OSPF – Cost

Cost.
The outgoing cost for packets transmitted from this interface. Cost is the OSPF metric, expressed as an
unsigned 16-bit integer in the range of 1 to 65535. Cisco uses a default cost of 10^8/BW, expressed in
whole numbers, where BW is the configured bandwidth of the interface and 10^8 is the reference
bandwidth.If an interface is configured with a  configured bandwidth of 128K , so
the cost is 10^8/128K = 781.
The cost can be changed with the command ip ospf cost. This command is especially important when
configuring Cisco routers in a multivendor environment. If all routers do not
assign costs in the same manner, OSPF can route improperly.

www.pdf24.org    Send article as PDF