Routing Protocol

A routing protocol specifies how routers communicate with each other to distribute
information that enables them to select routes between any two nodes on a computer network.

Routers perform the "traffic directing" functions on the Internet,data packets are forwarded
through the networks of the internet from router to router until they reach their destination
computer.

The purpose of dynamic routing protocols includes:

[Link] of remote networks

[Link] up-to-date routing information

[Link] the best path to destination networks

[Link] to find a new best path if the current path is no longer available

Types

Distance vector

Distance Vector algorithms calculate the best path to each destination prefix separately,
usually trying to find paths that minimize a simple metric, such as the number of router hops to the
destination.

At each intermediate step in the algorithm, each router has its current best path to the
destination prefix. The router then notifies all of its neighbors of its current path; concurrently the
router's neighbors are also notifying the router of their path choices. The router, seeing the paths
being used by all of itsneighbors, may find a better (that is, lower-cost) path through one of its
neighbors. If so,the router updates its next hop and cost for the destination and notifies its
neighbors of its new choice of route, and the procedure iterates.

The main advantage of Distance Vector algorithms is their simplicity.

Disadvantages:

Forms routing loops.

Count to infinity problems.

Slow response to toplogy changes.

Ex: RIP

Link state

Link-state routing algorithms employ a replicated distributed database approach. Each

router in a link-state algorithm contributes pieces to this database by describing the router's local
environment: the set of active links to local IP network segments and neighboring routers, with each
link assigned a cost.

The linkstate advertisements are then distributed to all other [Link] node constructs
a map of the connectivity to the network, in the form of a graph, showing which nodes are
connected to which other nodes.
 Each node then independently calculates the next best logical path from it to every possible
destination in the network. Each collection of best paths will then form each node's routing table.

Advantages:

No routing loops.

Better response to topology changes.

Dis-Advantanges

More complex than distance vector.

Path vector

Each entry in the routing table contains the destination network, the next router and the
path to reach the destination.

Border Gateway Protocol (BGP) is an example of a path vector protocol. In BGP, the
autonomous system boundary routers (ASBR) send path-vector messages to advertise the
reachability of networks.

Each router that receives a path vector message the router modifies its routing table and
the message before sending the message to the next neighbor.

Autonomous system:

AS consists of a collection of routers under the control of a single administrative entity for
example, all the routers belonging to a particular Internet Service Provider, corporation,or university.

Interior Gateway Protocol-IGP

An interior gateway protocol (IGP) is a type of protocol used for exchanging routing
information between gateways (commonly routers) within an autonomous system

Ex: RIP,OSPF,IS-IS

Exterior Gateway Protocol-EGP

An exterior gateway protocol is a routing protocol used to exchange routing information

between autonomous systems.

Ex: BGP,EGP.

OSPF – Open Shortest Path First

ospf packet encapsulation

OSPF runs directly over the Internet Protocol's network layer. IP protocol number 89

Multicast addresses used:

AllSPFRouters - [Link]. All routers running OSPF should be prepared to receive packets
sent to this address. Hello packets are always sent to this destination

AllDRouters - [Link]. Both the Designated Router and Backup Designated Router must
be prepared to receive packets destined to this address
Basic operation

[Link] detection using hello

[Link] synchronization

[Link] update after timer expiry

[Link] in topology

The CPU processes the neighbor and topology tables using Dijkstra’s SPF algorithm. The SPF
algorithm is based on the cumulative cost to reach a destination.

The SPF algorithm creates an SPF tree by placing each router at the root of the tree and
calculating the shortest path to each node.

The SPF tree is then used to calculate the best routes. OSPF places the best routes into the
forwarding database, which is used to make the routing table.

Link-State Operation

To maintain routing information, OSPF routers complete the following generic link-state
routing process to reach a state of convergence:

Establish Neighbor Adjacencies

OSPF-enabled routers must recognize each other on the network before they can share
[Link] OSPF-enabled router sends Hello packets out all OSPF-enabled interfaces to
determine if neighbors are present on those links.

If a neighbor is present, the OSPF-enabled router attempts to establish a neighbor adjacency

with that neighbor.

Exchange Link-State Advertisements

After adjacencies are established, routers then exchange link-state advertisements (LSAs).
LSAs contain the state and cost of each directly connected link. Routers flood their LSAs to adjacent
neighbors.

Adjacent neighbors receiving the LSA immediately flood the LSA to other directly connected
neighbors, until all routers in the area have all LSAs.

Build the Topology Table

After LSAs are received, OSPF-enabled routers build the topology table (LSDB) based on the
received LSAs. This database eventually holds all the information about the topology of the network

Execute the SPF Algorithm

Routers then execute the SPF algorithm. The SPF algorithm creates the SPF tree, program
the routes in the hardware.
Topology Maintenance & Change Notification:

Every change in topology triggers an Link state update and sends the updated
[Link] down triggers remove of routes from that router.

OSPF Packet types:

OSPF Common Header Format

Size
Field Name Description
(bytes)

Version # 1 Version Number: Set to 2 for OSPF version 2.

Type 1

Packet Length: The length of the message, in bytes, including the 24

Packet Length 2
bytes of this header.

Router ID: The ID of the router that generated this message (generally

Router ID 4
its IP address on the interface over which the message was sent).

Area ID: An identification of the OSPF area to which this message

Area ID 4
belongs, when areas are used.

Checksum: A 16-bit checksum computed in a manner similar to

Checksum 2 a standard IP checksum. The entire message is included in the
calculation except the Authentication field.

AuType 2

 
 Authentication: A 64-bit field used for authentication of the message, as
Authentication 8
needed.

Type Description

________________________________

1 Hello

2 Database Description

3 Link State Request

4 Link State Update

5 Link State Acknowledgment

Hello Packet

The OSPF Type 1 packet is the Hello packet. Hello packets are used to:

Discover OSPF neighbors and establish neighbor adjacencies.

Advertise parameters on which two routers must agree to become neighbors.

Elect the Designated Router (DR) and Backup Designated Router (BDR) on
multiaccess networks like Ethernet and Frame Relay. Point-to-point links do not require DR or BDR.
Fields in the Hello packet:

Type - Identifies the type of packet. A one (1) indicates a Hello packet. A value 2 identifies a
DBD packet, 3 an LSR packet, 4 an LSU packet, and 5 an LSAck packet.

Router ID - A 32-bit value expressed in dotted decimal notation (an IPv4 address) used to
uniquely identifying the originating router.

Area ID - Area from which the packet originated.

 Network Mask - Subnet mask associated with the sending interface.

Hello Interval - Specifies the frequency, in seconds, at which a router sends Hello packets.
The default Hello interval on multiaccess networks is 10 seconds. This timer must be the same on
neighboring routers; otherwise, an adjacency is not established.

Router Priority - Used in a DR/BDR election. The default priority for all OSPF routers is 1, but
can be manually altered from 0 to 255. The higher the value, the more likely the router becomes the
DR on the link. Priority 0 excludes the router from DR and BDR election.

Dead Interval - Is the time in seconds that a router waits to hear from a neighbor before
declaring the neighboring router out of service. This timer must be the same on neighboring routers;
otherwise, an adjacency is not established.

Designated Router (DR) - Router ID of the DR.

Backup Designated Router (BDR) - Router ID of the BDR.

List of Neighbors - List that identifies the router IDs of all adjacent routers.

Hello Packet Intervals

OSPF Hello packets are transmitted to multicast address [Link] in IPv4 and FF02::5 in IPv6
(all OSPF routers) every:

10 seconds (default on multiaccess and point-to-point networks)

30 seconds (default on nonbroadcast multiaccess [NBMA] networks; for example, Frame

Relay)

The Dead interval is the period that the router waits to receive a Hello packet before declaring the
neighbor down.

If the Dead interval expires before the routers receive a Hello packet, OSPF removes that
neighbor from its LSDB. The router floods the LSDB with information about the down neighbor out
all OSPF-enabled interfaces.

Cisco uses a default of 4 times the Hello interval:

40 seconds (default on multiaccess and point-to-point networks)

20 seconds (default on NBMA networks; for example, Frame Relay)

Neighbour formation State transition:

The states are Down, Attempt(only NBMA), Init, 2-Way, Exstart, Exchange, Loading, and
Full.
Down state

No Hello packets received = Down

Router sends Hello packets

Transition to Init state

Init state

Hello packets are received from the neighbor

They contain the sending router's Router ID

Transition to Two-Way state

Two-Way state

On Ethernet links, elect a DR and a BDR

Transition to ExStart state

ExStart state

Negotiate master / slave relationship and DBD packet sequence number

The master initiates the DBD packet exchange

Exchange state

Routers exchange DBD packets

If additional router information is required then transition to Loading; otherwise,

transition to Full

Loading state
 LSRs and LSUs are used to gain additional route information

Routes are processed using the SPF algoritm. Transition to Full state

Full state - Routers have converged

Database Description Packet:

OSPF Database Description Message Format

Field Size
Description
Name (bytes)
Interface Interface MTU: The size of the largest IP message that can
2
MTU be sent on this router's interface without fragmentation.
Options: Indicates which of several optional OSPF
Options 1
capabilities the router supports.

Flags 1

 
DD
DD Sequence Number: Used to number a sequence
Sequence 4
of Database Description messages so they are kept in order.
Number
LSA Headers: Contains link-state advertisement headers,
LSA
Variable which carry information about the LSDB. See near the end of
Headers
the topic for more information on LSAs.

 
LINK STATE UPDATE (LSU) - PACKET STRUCTURE

A Link State Update (LSU) packet can contain one or more LSAs inside it and when an LSU is
sent between OSPF routers, it floods the LSA information through the network.  destination IP
address is multicast address [Link]

The LSA header is a 20 byte (32x5 = 160 bits) section that consists of the following fields:

 LS Age (2 Bytes): Time passed since the LSA was generated (in seconds).

 Options (1 Byte): Indicates the OSPF features and options the origin can support.

 LS Type (1 Byte): Defines the LSA type (all types will be explained later).
 Link State ID (4 Bytes): Identifies the network link between OSPF routers (usually IP
address).

 Advertising Router (4 Bytes): Indicates the origin router’s ID.

 LS Sequence Number (4 Bytes): A specific digit on each LSA packet to filter old and repeated

 LS Checksum (2 Bytes): A certain digit given to LS to compare and detect errors.

 Length (2 Bytes): Represents LSA packet length.

 Link State Request Message Format

These messages have a Type value of 3 in the header. Following the header comes one or
more sets of three fields that each identify a link state advertisement (LSA) for which the router is
requesting an update, as shown in Figure 187. Each LSA identification has the format described
in Table 129.

Table 129: OSPF Link State Request Message Format

Size
Field Name Description
(bytes)

Link State Type: The type of link state

LS Type 4
advertisement (LSA) being sought.

Link State ID: The identifier of the LSA, usually the

Link State ID 4
IP address of either the router or network linked.

Advertising Advertising Router: The ID of the router that

4
Router created the LSA whose update is being sought.

Figure 187: OSPF Link State Request Message Format

3. Link State Request packet:

The Link State Request (LSR) packet is an OSPF packet Type 3. After DBD packets exchange
process, the router may find it does not have an up-to-date database. The LSR packet is used to
request pieces of neighbor database that is more up-to-date.

LS Type-  Type of LSA requested (4-bytes)

Link State ID-  Depends upon the type of LSA (4-bytes)
Advertising Router-  Router ID of the requesting router (4-bytes)

The following packet capture shows the LSR sent for Router-LSA (Type-1) to an OSPF neighbor
after DBD packet exchange process is over.

Link State Acknowledgment Message Format

These messages have a Type value of 5 in the header. They then contain a list of LSA headers
corresponding to the LSAs being acknowledged, as shown in Table 131 and Figure 189.

Table 131: OSPF Link State Acknowledgment Message Format

Size
Field Name Description
(bytes)

LSA LSA Headers: Contains link-state advertisement headers, to identify the

Variable
Headers LSAs acknowledged.
Figure 189: OSPF Link State Acknowledgment Message Format

Link State Advertisements (LSAs) and the LSA Header Format

As we saw above, several of the message types include link state

advertisements (LSAs), which are the fields that actually carry topological
information about the LSDB. There are several types of LSAs, which are
used to convey information about different types of links. Like the OSPF
messages themselves, each LSA has a common header with 20 bytes, and
then a number of additional fields that describe the link.

LSA Header

The LSA header contains sufficient information to identify the link. It uses
the subfield structure in Table 132 and Figure 190.

Table 132: OSPF Link State Advertisement Header Format

Subfield Size
Description
Name (bytes)
LS Age: The number of seconds elapsed since the LSA was
LS Age 2
created.
Options: Indicates which of several optional OSPF
Options 1
capabilities the router supports.
 LS Type 1

 
Link State ID: Identifies the link. This usually is the IP
Link State
4 address of either the router or the network the link
ID
represents.
Advertising
4 Advertising Router: The ID of the router originating the LSA.
Router
LS
LS Sequence Number: A sequence number used to detect
Sequence 4
old or duplicate LSAs.
Number
LS LS Checksum: A checksum of the LSA, for data corruption
2
Checksum protection.
Length: The length of the LSA, including the 20 bytes of the
Length 2
header.

Figure 190: OSPF Link State Advertisement Header Format

LSA Body
Following the LSA header comes the body of the LSA, the specific fields of
which depend on the value of the LS Type field. 

LSA Types:

LSA TYPE 1 – ROUTER LSA

LSA Type 1 (Router LSA) packets are sent between routers within the same area of origin and
do not leave the area. An OSPF router uses. LSA Type 1 packets to describe its own interfaces but
also carries information about its neighbors to adjacent routers in the same area.

LSA TYPE 2 – OSPF NETWORK LSA

LSA Type 2 (Network LSA) packets are generated by the Designated Router (DR) to describe
all routers connected to its segment directly. LSA Type 2 packets are flooded between neighbors in
the same area of origin and remain within that area.
 

LSA TYPE 3 – OSPF SUMMARY LSA

LSA Type 3 (Summary LSA) packets are generated by Area Border Routers (ABR) to
summarize its directly connected area, and advertise inter-area router information to other areas
the ABR is connected to, with the use of a summary prefix (e.g [Link]/22). LSA Type 3 packets
are flooded to multiple areas throughout the network and help with OSPF’s scalability with the use
of summary prefixes.

LSA TYPE 4 – OSPF ASBR SUMMARY LSA

LSA Type 4 (ASBR Summary LSA) packets are the LSAs that advertise the presence of an Autonomous
System Border Router (ASBR) to other areas. In the example below when R2 (ABR) receives the LSA
Type 1 packet from R1 it will create a LSA Type 4 (Summary ASBR LSA) packet, which advertises
the ASBR route received from Area 1, and inject it into Area 0.

LSA TYPE 5 – OSPF ASBR EXTERNAL LSA

LSA Type 5 (ASBR External LSA) packets are generated by the ASBR to advertise external
redistributed routes into the OSPF’s AS. A typical example of an LSA Type 5 would be an external
prefix e.g [Link]/24 or default route (internet) as shown below:

Opaque LSA.

Area :

Areas are a logical collection of routers that carry the same Area ID.

The hierarchical-topology possibilities of multiarea OSPF have these advantages:

[Link] routing tables - Fewer routing table entries because network addresses can be
summarized between [Link] summarization is not enabled by default.

[Link] link-state update overhead - Minimizes processing and memory requirements.

[Link] frequency of SPF calculations - Localizes the impact of a topology change within
an area. For instance, it minimizes routing update impact because LSA flooding stops at the
area boundary.

Area Border Routers (ABR):

Routers located on the borders of each Area connect to more than one OSPF area, are
called ABR Routers. ABR Routers are responsible for summarizing IP addresses of each area
and suppressing updates among areas to prevent fault containment.

Autonomous System Boundary Router (ASBR):

An ASBR is a router that has interfaces connected to one or more OSPF areas, similarly as
the ABR, however the difference with an ASBR is that it also connects to other routing systems such
as BGP, EIGRP, Internet and others. An ASBR router normally advertises routes from other routing
systems into the OSPF area to which it belongs.

Stub Areas: (dead end only path is through an ABR).

These areas do not accept routes belonging to external autonomous systems (AS); however,
these areas have inter-area and intra-area routes. In order to reach the outside networks, the
routers in the stub area use a default route which is injected into the area by the Area Border Router
(ABR).

Ex: A stub area is typically configured in situations where the branch office need not know
about all the routes to every other office, instead it could use a default route to the central office
and get to other places from there. Hence the memory requirements of the leaf node routers is
reduced, and so is the size of the OSPF database.

The following restrictions apply to stub areas:

 You cannot create a virtual link through a stub area.

 A stub area cannot contain an AS boundary router.

 You cannot configure the backbone as a stub area.

 You cannot configure an area as both a stub area and an not-so-stubby area (NSSA).

totally stubby area:

A stub area that only allows routes internal to the area and restricts Type 3 LSAs from
entering the stub area is often called a totally stubby area. The ABR injects a default route into the
area and all the routers belonging to this area use the default route to send any traffic outside the
area.

In stub and totally stub areas, the ABR to the stub area generates a summary LSA with the
link-state ID [Link]. This is true even if the ABR doesn't have a default route of its own.

NotSoStubbyArea (NSSA)

 This type of area allows the flexibility of importing a few external routes into the area while
still trying to retain the stub characteristic. Assume that one of the routers in the stub area is
connected to an external AS running a different routing protocol, it now becomes the ASBR, and
hence the area can no more be called a stub area.

However, if the area is configured as a NSSA, then the ASBR generates a NSSA external link-
state advertisement (LSA) (Type-7) which can be flooded throughout the NSSA area. These Type-7
LSAs are converted into Type-5 LSAs at the NSSA ABR and flooded throughout the OSPF domain

Backbone area:

The first and main Area is called the backbone area “Area 0”, all other areas must connect
to Area 0

Virtual Links:

All areas in an OSPF autonomous system must be physically connected to the backbone area
(area 0). In some cases where this physical connection is not possible, you can use a virtual link to
connect to the backbone through a non-backbone area.

Virtual links can also be used to connect two parts of a partitioned backbone through a non-
backbone area. The area through which you configure the virtual link, known as a transit area, must
have full routing information. The transit area cannot be a stub area.

Normal, Stub, Totally Stub and NSSA Area Differences

Area Restriction

Normal None
 Stub No Type 5 AS-external LSA allowed

Totally Stub No Type 3, 4 or 5 LSAs allowed except the default summary route

No Type 5 AS-external LSAs allowed, but Type 7 LSAs that convert to Type 5 at the
NSSA NSSA ABR can traverse

NSSA Totally No Type 3, 4 or 5 LSAs except the default summary route, but Type 7 LSAs that
Stub convert to Type 5 at the NSSA ABR are allowed

This table shows the differences between the types of areas defined in this document:

Max Age

Designated router and Backup designated router election

Reliable flooding, checksum

LS Aging.

Premature aging.

Demand circuit

Inter area routing

importing external routes.

Options Field

E bit

MC
NP

EA

DC

OSPF V3

Features:

Non stop routing

Graceful restart.

OSPF extensions for segment routing.

Graceful link shutdown

OSPF BFD

Link Local signaling

MultiArea adjacency

Sham link

Multi VRF support

Autoroute exclude

Inbound filtering

SPF Throttling

Incremental SPF

Fast Hello Packets.

LinkState Advertisement Throttling.

Database overload protecion

crytographic authentication.

stub router adevrtisement.

IPD implementation:
Tasks :

OspfHello

OspfPublic

Ospf private

Tables

General Table

Area Table

IfTable

VirtIfTable

ShamIfTable

TunnelTable

Area Aggregation Table

IfMD5 Table

StdIfTable

Neighbor table

Adjacency database - Creates the neighbor table

List of all neighbor routers to which a router has estalished bidirectional

communication.

This table is unique for each [Link] Can be viewed using the "show router ospf
neighbor"

Link State DB

Link-state database (LSDB) - Creates the topology table

List information about all other routers in the network.

The database represents the network topology.

All routers within an area have identical LSDB.

Can be viewed using the "show route ospf database" command.

LsdbNbr

LocalLsdbNbr

virtLocalLsdbNbr

Forwarding database - Creates the routing table - programmed in the hardware.

 List of routes generated when an algoritm is run on the link-state database.

Each router's routing table is unique and contains information on how and where to
send packets to other routers.

Can be viewed using the "show router route-table" command.

SPF identify a route and adds the entry to RTM.

ospfRteAdded -> ospfRtmRouteChanged -> RTM_AsyncAddRTEntry / RTE_ADDED posted to RTM

queue RTM_EVNT_NewEntry

RTMD_ProcessRoutes - pRtmUser->pEventParams->eventCallback-> pipIomRouteInfoChanged

Pip registers with RTM-EventParams ->callback -> pipIomRouteInfoChanged

pipIomRouteInfoChanged -> pipIomUpdateRt -> pipIomAddRouteInfo -> Send a ICC message to iom
ip Q

radix_task_loop - drains the ip q with function ip_transaction_dequeue and invoke -

ip_route_handler

ip_route_update -> add_route_table_entry -> treeFlagAddRoute

can we run two routing protocol interface

type 7 LSA

type 9,10,11 LSA

designated router election in hello packet

scenarios

[Link]

[Link]

[Link]

[Link]

[Link] addition