Routing

OSPF - Part 6: OSPF LSA Types - Purpose and Function of Every OSPF LSA

2016-11-24T10:26:24+11:00

Our previous article explained the purpose of Link State Update (LSU) packets and examined the Link State Advertisement (LSA) information contained within LSU packets. We also saw the most common LSA packets found in OSPF networks. In this article we’ll be diving deeper to analyse all eleven OSPF LSA Types using network network diagrams and examples to help understand when each LSA type is used and how they keep the OSPF network updated.

LSA Types - Quick Overview

Before we begin, let’s take a quick look at the different type of OSPF LSA packets we’ll cover:

LSA Type 1: OSPF Router LSA
LSA Type 2: OSPF Network LSA
LSA Type 3: OSPF Summary LSA
LSA Type 4: OSPF ASBR Summary LSA
LSA Type 5: OSPF ASBR External LSA
LSA Type 6: OSPF Group Membership LSA
LSA Type 7: OSPF Not So Stubby Area (NSSA) External LSA
LSA Type 8: OSPF External Attributes LSA (OSPFv2) / Link Local LSA (OSPFv3)
LSA Type 9: OSPF Link Scope Opaque (OSPFv2) / Intra Area Prefix LSA (OSPFv3)
LSA Type 10: OSPF Area Scope Opaque LSA
LSA Type 11:OSPF AS (Autonomous System) Scope Opaque LSA

Below is a complete list of articles covering our OSPF Series:

- Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics.

- Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview.

- Part 3: OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU).

- Part 4: OSPF Neighbor States – OSPF Neighbor Forming Process.

- Part 5: Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types.

- Part 6 (This article) - OSPF LSA Types - Purpose and Function of Every OSPF LSA.

The LSA payload varies in size according to the LSA type and the information it includes. The diagram below clearly shows how LSAs are contained within LSUs:

Figure 1. LSA Types contained within an OSPF LSU packet

As mentioned, OSPF currently supports 11 types of LSAs. Each LSA is used within specific boundaries of an OSPF network.

OSPF concepts, including router roles such as Designated Router (DR), Area Border Router (ABR), Autonomous System Border Router (ASBR), OSPF Areas and more, are analyzed in great depth in our article OSPF Basic Concepts – OSPF Areas – Router Roles. This article assumes the reader has a good understanding of basic OSPF theory and is comfortable with OSPF concepts.

LSA Type 1 – OSPF 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.

Figure 2. LSA Type 1 Packets exchanged between OSPF routers within 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.

Figure 3. LSA Type 2 Packets exchanged between OSPF DR and neighbor routers

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 192.168.0.0/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.

Figure 4. LSA Type 3 - An OSPF ABR router advertises the summarized route 192.168.2.0/24 to Area 0

Looking at the diagram above, ABR router R2 creates a Type 3 Summary LSA and floods it into Area 0. In a similar way, ABR router R3 creates a Type 3 Summary LSA and floods it into Area 2. Type 3 Summary LSAs appear as O IA entries in the router routing table.

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.

Figure 5. LSA Type 4 packets injected into Area 0 & 2 by the R2 ABR and R3 ABR

While LSA Type 4 packets are used by ABRs to advertise the ASBR route through their areas, it will not be used by the ASBR itself within its local area (Area 1); ASBR uses LSA Type 1 to inform its neighbors (R2 in this case) within its networks.

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 192.168.10.0/24 or default route (internet) as shown below:

Figure 6. LSA Type 5 packets advertise the default route to all OSPF routers

This external route/prefix is redistributed in to the OSPF network by the ASBR (R1) and seen as O E1 or E2 entries in other OSPF routers routing tables.

LSA Type 6 – OSPF Group Membership LSA

LSA Type 6 (Group Membership LSA) packets were designed for Multicast OSPF (MOSPF), a protocol that supports multicast routing through OSPF. MOSPF is not supported by Cisco and is not widely used and is expected to be retired soon.

LSA Type 7 – OSPF Not So Stubby Area (NSSA) External LSA

LSA Type 7 (NSSA External LSA) packets are used for some special area types that do not allow external distributed routes to go through and thus block LSA Type 5 packets from flooding through them, LSA Type 7 packets act as a mask for LSA Type 5 packets to allow them to move through these special areas and reach the ABR that is able to translate LSA Type 7 packets back to LSA Type 5 packets.

Figure 7. LSA Type 7 packets passing through an NSSA and being transformed into LSA Type 5 by the ABR

In the above example, ABR R2 translates LSA Type 7 into a LSA Type 5 and floods it into the OSPF network.

LSA Type 8 - OSPF External Attributes LSA (OSPFv2) / Link Local LSA (OSPFv3)

LSA Type 8 packets (External Attributes LSA -OSPFv2-/ Link Local LSA -OSPFv3-) in OSPFv2 (IPv4) are called External Attribute LSAs, and are used to transit BGP attributes through an OSPF network while BGP destinations are conveyed via LSA Type 5 packets, however, this feature isn’t supported by most routers. With OSPFv3 IPv6), LSA Type 8 is redefined to carry IPv6 information through OSPF network.

LSA Type 9, 10 & 11

Generally Opaque LSAs (LSA Type 9, 10 & 11) are used to extend the capabilities of OSPF allowing the protocol to carry information OSPF doesn’t necessarily care about. Practical application of Opaque LSAs is in MPLS traffic engineering where they are used to communicate interface parameters such as maximum bandwidth, unreserved bandwidth, etc. Following is a short analysis of each of the three Opaque LSAs.

LSA Type 9 – OSPF Link Scope Opaque (OSPFv2) / Intra Area Prefix LSA (OSPFv3)

LSA Type 9 in OSPFv2 (IPv4) is defined as a Link Scope Opaque LSA for carrying OSPF information. For OSPFv3 it’s redefined to handle a communication prefix for a special area type called Stub Area.

LSA Type 10 – OSPF Area Scope Opaque LSA

LSA Type 10 packets are used to flood OSPF information through other area routers even if these routers do not process this information in order to extend OSPF functionality, this LSA is used for traffic engineering to advertise MPLS and other protocols.

LSA Type 11 – OSPF AS Scope Opaque LSA

LSA Type 11 packets serve the same purpose as LSA Type 10 packets but are not flooded into special area types (Stub areas).

Summary

In this article we examined all 11 OSPF LSA packet types and explained their purposes. We also examined the structure of an LSA packet and used network diagrams to help illustrate how LSA packets flow between routers & OSPF Areas. For more high-quality OSPF articles visit our OSPF Section.

OSPF - Part 5: Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types

2016-04-10T10:00:00+10:00

This article explains how OSPF uses Link State Advertisement (LSA) to exchange information about the network topology between routers. When a router receives an LSA, it is stored in the Link-State DataBase (LSDB). Once the LSDBs between routers are in sync, OSPF uses the Shortest Path First (SPF) algorithm to calculate the best routes for each network. It is important to understand that LSAs are information about a route that is transported inside Link State Update (LSU) packets.

Each single 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.

Below is a complete list of articles covering our OSPF Series:

- Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics.

- Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview.

- Part 3: OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU).

- Part 4: OSPF Neighbor States – OSPF Neighbor Forming Process.

- Part 5 (This article): Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types.

- Part 6: OSPF LSA Types - Purpose and Function of Every OSPF LSA.

It is very important for any network engineer to understand how LSAs are contained within an LSU. We’ll use the example below, where an OSPF router sends an LSU to the OSPF Designated Router (DR) containing LSA information about a new network:

Figure 1. OSPF Link State Multicast Update (LSU) packet containing a Link State Advertisement (LSA)

As shown above, LSAs are contained within LSUs, which are all part of an OSPF packet encapsulated within an Ethernet frame (assuming an Ethernet network).

Our diagram of the LSU/LSA packet structure is confirmed by capturing an OSPF Ethernet frame below. We’ve highlighted each section (LSA, LSU, OSPF Header) using the same colors:

Figure 2. OSPF Link State Update and List State Advertisement within an Ethernet frame

Notice that the destination IP address is multicast address 224.0.0.6, as expected since routers send updates to the Designated Router (DR) using this multicast address. This is also analyzed under the Working Inside a Single Area section in our article How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview

Most Popular OSPF LSA Types

OSPF currently defines 11 different LSA types, however, despite the large variety of LSAs only around half of them are commonly found in OSPF networks. Table 1 below shows the most popular LSA types, the type of OSPF routers (DR, ABR, ASBR etc) that generate them along with their function and the OSPF areas they affect:

LSA	Generated by	Function	Flooding Map
Type 1	Normal Area Routers	Advertising router's interface and status to neighbors	Intra-Area (Area of origin)
Type 2	DR	Advertising DRs direct connected neighbors	Intra-Area (Area of origin)
Type 3	ABR	Advertising ABRs areas summary	Inter-Area (Multiple Areas)
Type 4	ABR	Advertising the presence of ASBRs	Inter-Area (Multiple Areas)
Type 5	ASBR	Advertising external routes to internet	Inter-Area (Multiple Areas)
Type 7	ASBR	Advertising external routes to internet to NSSA areas	Inter-Area (Multiple Areas)

Table 1. Most often used LSA Types, router origin type, their function and Areas affected

Looking at the OSPF packet captured with our network analyzer, we can now understand that the specific LSA was a Type-3 LSA (LS Type: Summary-LSA IP network 3) which means it was generated by an ABR OSPF router.

Link State Advertisement (LSA) Packet Structure (Within a Link State Update - LSU)

Each LSA packet consists of a header and a body that contains all the information needed to exchange network information within an OSPF network. The diagram below shows the structure of an OSPF LSA packet:

Figure 3. OSPF LSA Packet structure and fields

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.

The LSA body varies in size according to the LS type and the details it identifies, LSA types are explained in great detail in our upcoming article.

This article explained OSPF Link State Update (LSA) packets and showed how they contain Link State Advertisements (LSAs). We also analyzed OSPF LSU & LSAs packet structure and explained each field in an OSPF LSA packet. Finally, we spoke about the most common LSA Types, router origin type (ABR, ASBR, DR etc), their function and Areas affected. Read more on OSPF by visiting any of the below articles:

- Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics

- Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview

- Part 3 - OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU)

- Part 4 - OSPF Neighbor States – OSPF Neighbor Forming Process

- Part 5 - (This article) Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types

- Part 6 - OSPF LSA Types - Purpose and Function of Every OSPF LSA

OSPF - Part 4: OSPF Neighbor States – OSPF Neighbor Forming Process

2016-03-20T16:54:13+11:00

This is the third article of our OSPF series which analyzes the different OSPF States routers go through during the OSPF discovery and neighbor forming process. We analyze OSPF states (Init state, 2-way state, Exstart state, Exchange state, Loading state Full state, Down state), LSA Hello messages and more.

Below is a complete list of articles covering our OSPF Series:

- Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics.

- Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview.

- Part 3: OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU).

- Part 4 (This article): OSPF Neighbor States – OSPF Neighbor Forming Process.

- Part 5: Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types.

- Part 6: OSPF LSA Types - Purpose and Function of Every OSPF LSA.

OSPF Neighbor States

When OSPF forms adjacency with neighbors, the connection goes through several states before the routers are fully adjacent with each other, this section describes each state in detail. Following are the OSPF States we'll be examining:

Down state
Attempt state
Init state
2-Way state
Exstart state
Exchange state
Loading state
Full state

The diagram below shows the different states OSPF routers will go through when discovering their OSPF neighbors:

Figure 1. OSPF Neighbor States & OSPF Neighbor Forming Process

Down State

The Down State is the first OSPF neighbor state and means no Hello packets have been received from a neighbor. In an already established OSPF adjacency, an OSPF state will transition from a FULL or 2-Way State to the Down State when the router Dead Interval Timer expires (4 x Hello Interval timer), which means OSPF has lost communication with its neighbor and is now considered non-reachable or dead.

This is a special state used only for manually configured neighbors in a Non-Broadcast MultiAccess (NBMA) network, it indicates that the router is sending Hello packets to its neighbor in a Non-Broadcast MultiAccess (NBMA) environment via unicast but no reply is received within the Dead Interval (4 x Hello Interval).

An example of an NBMA network is a Frame Relay network where there are no intrinsic broadcast and multicast capabilities.

2-Way State

This state indicates that a Hello packet was received from a neighbor router but the receiving Router’s ID wasn’t listed in the Hello packet. When a router receives a Hello packet from a neighbor, it should list the sender's Router ID as an acknowledgment that it previously received a valid Hello packet.

This state describes the Bi-Directional communication state, Bi- Directional means that each router has received the other’s Hello packet and that each router can see its own Router ID included within the Hello packet’s neighbor field.

On broadcast media (e.g LAN) and Non-Broadcast MultiAccess (NBMA) networks (e.g Frame Relay, ATM, X.25), a router becomes full state (analyzed below) only with the Designated Router (DR) and the Backup Designated Router (BDR). It will, however, stay in the 2-way state with all other neighbors.

When the 2-Way state is complete, the DR and DBR routers are elected, considering they are on a broadcast or NBMA network.

Exstart State

This state specifies that DR and BDR have been elected and master-slave relation is determined. An initial sequence number for adjacency formation is also selected. The router with the highest router ID becomes the master and begins to exchange Link State data. Only the Master router is able to increment the sequence number.

Exchange State

In this state, OSPF routers exchange DataBase Descriptor (DBD) packets. These contain Link State Advertisement (LSA) headers describing the content of the entire Link State Database (LSD). The contents of the DataBase Descriptor (DBD) received by the router are compared with its own Link State Database (LSD) to check if changes or additional link-state information is available from its neighbor.

Loading State

In this state, routers exchange full Link State information based on DataBase Descriptor (DBD) provided by neighbors, the OSPF router sends Link State Request (LSR) and receives Link State Update (LSU) containing all Link State Advertisements (LSAs).

Link State Updates (LSU) actually act as an envelope that contains all the Link State Advertisements (LSAs) – that have been sent to neighbors with new changes or new networks learned.

Full State

Full state is the normal operating state of OSPF that indicates everything is functioning normally. In this state, routers are fully adjacent with each other and all the router and network Link State Advertisements (LSAs) are exchanged and the routers' databases are fully synchronized.

For Broadcast and NBMA media, routers will achieve the Full State with their DR and BDR router only, while for Point-to-point and Point-to-multipoint networks a router should be in the Full State with every neighboring router.

This article analyzed the states OSPF routers go through during OSPF neighbor discovery and adjacency process. We examined in detail each OSPF State including: Down state, Attempt state, Init state, 2-way state, Exstart state, Exchange state, Loading state and Full state.

OSPF - Part 3: OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU)

2016-01-15T10:19:03+11:00

This is the thrid article of our 6-part OSPF series (see below) that describes how OSPF routers perform neighbor relationship and adjacency. We’ll examine how OSPF discovers neighbors by sending Hello packets through the router interfaces and how it shares Link State Advertisements (LSAs) to form adjacencies and build its topology table. We’ll also examine the contents of OSPF Hello packets (Router ID, Hello/Dead Intervals, Subnet Mask, Router Priority, Area ID, DB & BDR IP Address, Authentication information) and more.

Below is a complete list of articles covering our OSPF Series:

- Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics.

- Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview.

- Part 3 (This article): OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU).

- Part 4: OSPF Neighbor States – OSPF Neighbor Forming Process.

- Part 5: Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types.

- Part 6: OSPF LSA Types - Purpose and Function of Every OSPF LSA.

How OSPF Forms Neighbor Relations

Once OSPF is enabled on a router interface, a Link State Database (LSD) is established and all interfaces running OSPF are added to this table to be used in Link State Advertisements (LSAs), OSPF then the begins neighbor discovery and forming adjacency process.

We’ll now take a closer look at both, neighbor discover and adjacency forming process:

Figure 1. R1 sends an initial OSPF Hello packet. R2 responds with an OSPF Reply Hello packet.

Sending & Receiving OSPF Hello Messages

An OSPF router generates a Hello packet every poll interval -10 seconds for Peer-to-Peer (P2P) networks and 30 seconds for Non-Broadcast-Multiple-Access (NBMA) networks by default- and advertises it through multicast address 224.0.0.5 to all routers connected to its interfaces while it searches for potential OSPF neighbors. The Hello message contains a list of information needed to form an OSPF neighbor relation between two neighboring routers, the following a list of information contained the Hello messages:

OSPF Router ID. The router’s ID which is configured or automatically selected by OSPF (analyzed below)
Hello Interval Timer. Frequency upon which Hello packets are sent.
Dead Interval Timer. Defines how long we should wait for hello packets before we declare the neighbor dead.
Subnet Mask
Router Priority. Used to help determine the Designated Router (DR). Higher priority takes precedence. A configured Priority of 0 means the router will not become a DR or BDR.
List of reachable OSPF neighbors in the network.
Area ID
DR & BDR’s IP addresses (if exists)
Authentication Password (if configured)

Once a neighbor router (R2) running OSPF receives the Hello message, it runs a check on the above list.

The following conditions must be met for two routers to become neighbors:

They must have the same IP network/subnet
The Hello and Dead Interval timers must be identical
Router interfaces connecting two routers must have the same Area ID
Type of area must be identical (normal or stub area)
Authentication password (if used) must be identical

Hello Parameters Mismatch

If there’s a mismatch between some of the items (Hello/Dead interval, Subnetmask, Area ID etc), a Bouncing Relation case occurs as this potential neighbor (R2) keeps flapping on the router’s OSPF topology, indicating a mismatch with the Hello message information.

Note: Router ID can be a name, a number or an IP address. By default, OSPF will choose the highest active interface’s IP address as the Router ID. In case the interface does down (e.g Ethernet interface begin disconnected), it can create problems with the OSPF process. For this reason, it is always recommended to either configure a suitable IP address on a Loopback interface (virtual interface that is always ‘Up’) or manually configure the Router ID to something suitable for the OSPF network.

Hello Parameters Match - Replying Hello messages

When R2 receives the OSPF Hello message from R1 and all necessary Hello parameters match, R2 will send a Reply Hello packet back to R1.

The Reply Hello allows the R1 (who sent the original Hello message) to investigate if the neighboring router R2 is listed in its neighbor list or not.

If the neighboring router R2 is listed as a neighbor already, then R1 resets its dead timer and the Reply Hello messages act as a Keep Alive mechanism.

If the neighboring router R2 is not listed in R1’s neighbor database, it will add the newly discovered neighbor R2 router to its OSPF neighbor database. All further OSPF Hello and Hello Reply messages will act as a Keep Alive mechanism.

Establishing Master-Slave Relation

When a neighbor relation is formed between two routers running OSPF, a hierarchy order of exchanging information must be established, which determines which router sends DataBase Descriptor (DBD) updates first (Master) while the other router (Slave) listens. Once the Master sends the DBD packets, the Slave follows by sending its DataBase Descriptor (DBD) packets next.

OSPF elects master router based on highest priority -which can be configured manually-, however if priority is not configured, OSPF will use the router ID as a reference.

Note that the Designated Router (DR) is doesn’t have to be the master, it’s only a router priority based relation to arrange the exchanging data between neighbors but doesn’t affect the role of DR & BDR.

Exchanging DataBase Descriptor (DBD's) - DBD Acknowledgement & Review

OSPF neighbors follow a strict process of exchanging routing information and updates to prevent fault containment caused by updates flood, this process follows the order described below:

Figure 2. Steps 1 & 2: R1 sends a DBD Packet while R2 replies with a Link State Request (LSR)

1. Master sends DataBase Descriptor (DBD) update packet first.

2. Slave checks DataBase Descriptor (DBD) and finds new routes information, it then requests updates by sending a Link State Request (LSR) packet.

Figure 3. Steps 3 & 4. R1 replies with a Link State Update (LSU) and R2 Acknowledges with a LSAck

3. Master sends back updates through Link State Updates (LSU) packets.

4. Slave acknowledges the reception of updates by sending a Link State Acknowledge (LSAck) packet.

5. Slave sends DataBase Descriptor (DBD) update packet next.

6. Master requests updates by sending a Link State Request (LSR) packet.

7. Slave sends updates through the Link State Update (LSU) packets.

8. Master acknowledges receiving updates by sending a Link State Acknowledge (LSAck) packet.

There are no diagrams showing steps 5 to 8, however these are similar to the first 4 steps, but with the Master router requesting the Link State Request (LSR).

This article explained how OSPF routers build neighbor relationships and adjacencies. We saw the OSPF neighbor discovering process via OSPF Hello packets and the role of Link State Requests (LSR) and Link State Updates (LSU). We also examined the contents of OSPF Hello packets and which fields are necessary to ensure an OSPF adjacency is formed. Finally, we saw how OSPF routers exchange information and update their database via DataBase Descriptor (DBD) packets.

OSPF - Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview

2015-10-02T17:00:00+10:00

This article covers basic OSPF concepts and operation. We explain how OSPF works, how OSPF tables are built on an OSPF-enabled router and their purpose (Neighbour Table, Topology Table, Routing Table), OSPF areas and their importance. Next we cover OSPF Link State Packet types used to exchange data between OSPF routers: Link State Advertisement (LSA), Link State Database (LSDB), Link State Request (LSR), Link State Update (LSU) and Link State Acknowledgment (LSAcK).

Finally, we take a look at the OSPF roles: Area Boarder Router (ABR), Autonomous System Boundary Router (ASBR), Designated Router (DR), Backup DR and more.

Below is a complete list of articles covering our OSPF Series:

- Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics.

- Part 2 (This article): How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview.

- Part 3: OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU).

- Part 4: OSPF Neighbor States – OSPF Neighbor Forming Process.

- Part 5: Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types.

- Part 6: OSPF LSA Types - Purpose and Function of Every OSPF LSA.

What Is OSPF & How Does It Work?

OSPF is a Link State protocol that’s considered may be the most famous protocol among the Interior Gateway Protocol (IGP) family, developed in the mid 1980’s by the OSPF working group of the IETF.

When configured, OSPF will listen to neighbors and gather all link state data available to build a topology map of all available paths in its network and then save the information in its topology database, also known as its Link-State Database (LSDB). Using the information from its topology database. From the information gathered, it will calculate the best shortest path to each reachable subnet/network using an algorithm called Shortest Path First (SFP) that was developed by the computer scientist Edsger W. Dijkstra in 1956. OSPF will then construct three tables to store the following information:

Neighbor Table: Contains all discovered OSPF neighbors with whom routing information will be interchanged
Topology Table: Contains the entire road map of the network with all available OSPF routers and calculated best and alternative paths.
Routing Table: Contain the current working best paths that will be used to forward data traffic between neighbors.

Understanding OSPF Areas

OSPF offers a very distinguishable feature named: Routing Areas. It means dividing routers inside a single autonomous system running OSPF, into areas where each area consists of a group of connected routers.

The idea of dividing the OSPF network into areas is to simplify administration and optimize available resources. Resource optimization is especially important for large enterprise networks with a plethora of network and links. Having many routers exchange the link state database could flood the network and reduce its efficiency – this was the need that led to the creation of concept Areas.

Areas are a logical collection of routers that carry the same Area ID or number inside of an OSPF network, the OSPF network itself can contain multiple areas, the first and main Area is called the backbone area “Area 0”, all other areas must connect to Area 0 as shown in the diagram below:

Figure 1. OSPF Areas, Area 0 (Backbone Area), ABR and ASBR OSPF routers

All routers within the same Area have the same topology table -Link State Database- but different routing table as OSPF calculates different best paths for each router depending on its location within the network topology while they will all share the same Link State topology.

The goal of having an Area is to localize the network as follow:

The Area boundaries will give the opportunity of using summarization, as it’s not possible to summarize network prefixes in normal link state protocols because routers are supposed to have the same map topology of the entire network coincide in all neighbors.
Area boundaries will also help preventing fault containment by suppressing updates that take place when a change occurs in the network causing a flood of updates between routers. This also happens to be a weakness of link state protocols: When connecting large sized networks it is very difficult to avoid link state database floods.

With Area boundaries, updates are kept only inside the same area, while other areas remain completely unaware of the update.

OSPF Link State Packet Types

OSPF routers generate packets of information that are exchaged with neighboring routers. These packets are designed for several purposes such as forming neighbor relations between routers, calculating cost and best path for a specific route and more.

The following is a list of the most frequently used OSPF packets:

Link State Advertisement (LSA): The primary mean of communication between OSPF routers, it's the packet that carries all fundamental information about the topology and is flooded between areas to perform different functions, there are 11 types of LSA packets that will be covred in great depth in future OSPF articles here on Firewall.cx

Link State DataBase (LSDB): LSDB packet contains all updated link-state information exchanged among the network, and all routers within the same area have identical LSDB, and when two routers form new neighbor adjacency, they sync their LSDB to be fully adjacent.

Link State Request (LSR): Once neighbor adjacency is formed and LSDB is exchanged, neighbor routers may locate a missing LSDB information, they then send a request packet to claim the missing piece, neighbors receive this packet and respond with LSU.

Link State Update (LSU): A response packet sends a specific piece of LSDB information requested by an OSPF neighbor via LSR packet.

Link State Acknowledgment (LSAcK): The router that sends the LSR packet confirms receiving the LSU from neighbor by sending a confirmation packet acknowledging receiving the requested LSUs.

Working Inside Of A Single Area

Working inside of an Area is hierarchically organized among routers that share this area and are categorized as:

Area Boarder 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.

Designated Router (DR):
A Designated Router is elected by the routers on multi-access segments (e.g Local Area Network), based on its priority (Router ID, priority). The DR router performs special functions such as generating Link State Advertisements (LSAs) and exchanging information with all other routers in the same Area. Every router in the same Area will create an adjacency with the DR and BDR (analysed below).

The DR sends updates to all Area routers using the Multicast address 224.0.0.5. All OSPF routers except the DR use Multicast address 224.0.0.6 to send Link State Update (LSU) and Link State Advertisements (LSAs) packets to the DR.

Backup Designated Router (BDR):
The BDR is a router that becomes the DR should the existing DR fail. The BDR has the second highest priority (the DR having the highest priority) in the OSPF network. When the BDR becomes a DR, a new election is made to find a new BDR.

This article introduced the OSPF protocol and examined how OSPF works. We covered important OSPF concepts such as OSPF areas, OSPF Neighbour Table, Topology Table and Routing Table, plus OSPF Link State packet types (LSA, LSDB, LSR, LSU & LSAcK). To complete our introduction, we analysed the OSPF roles Area Boarder Router (ABR), Autonomous System Boundary Router (ASBR), Designated Router (DR), Backup DR.

Introduction to Routing Protocols

2011-05-30T00:32:23+10:00

Distance Vector, Link State RIP, IGRP, EIGRP, OSPF

Routing protocols were created for routers. These protocols have been designed to allow the exchange of routing tables, or known networks, between routers. There are a lot of different routing protocols, each one designed for specific network sizes, so I am not going to be able to mention and analyse them all, but I will focus on the most popular.

The Two Main Types of Routing: Static Routing & Dynamic Routing

The router learns about remote networks from neighbor routers or from an administrator. The router then builds a routing table, the creation of which I will explain in detail, that describes how to find the remote networks. If the network is directly connected then the router already knows how to get to the network. If the networks are not attached, the router must learn how to get to the remote network with either static routing (administrator manualy enters the routes in the router's table) or dynamic routing (happens automaticlly using routing protocols).

The routers then update each other about all the networks they know. If a change occurs e.g a router goes down, the dynamic routing protocols automatically inform all routers about the change. If static routing is used, then the administrator has to update all changes into all routers and therefore no routing protocol is used.

Only Dynamic routing uses routing protocols, which enable routers to:

Dynamically discover and maintain routes
Calculate routes
Distribute routing updates to other routers
Reach agreement with other routers about the network topology

Statically programmed routers are unable to discover routes, or send routing information to other routers. They send data over routes defined by the network Administrator.

A Stub network is so called because it is a dead end in the network. There is only one route in and one route out and, because of this, they can be reached using static routing, thus saving valuable bandwidth.

Dynamic Routing Protocols

There are 3 types of Dynamic routing protocols, these differ mainly in the way that they discover and make calculations about routes:

Distance Vector routing protocols. Distance Vector routers compute the best path from information passed to them from neighbors
Link State routing protocols. Link State routers each have a copy of the entire network map and compute best routes from this local map
Hybrid routing protocols. A combination of Distance Vector & Link State protocols.

The table below shows the main characteristics of a few different types of dynamic routing protocols:

You can also clasify the routing protocols in terms of their location on a network. For example, routing protocols can exist in, or between, autonomous systems.

Exterior Gateway Protocols (EGP's) are found between autonomous systems, whereas Interior Gateway Protocols (IGP's) are found within autonomous systems:

Example of an EGP is the Border Gateway Protocol (BGP) which is also used amongst the Internet routers, whereas examples of IGP protocols are RIP, IGRP, EIGRP.

Enhanced Interior Gateway Routing Protocol - EIGRP

2011-05-26T08:48:14+10:00

Enhanced Interior Gateway Routing Protocol (EIGRP), similar to IGRP, is a Cisco proprietary routing protocol that is used to exchange routing information between different routers within a network. EIGRP is an advanced routing protocol that combines the features of both distance vector and link-state routing protocols. This protocol is used to provide faster convergence times and improved scalability. EIGRP uses a composite metric composed of Bandwidth, Delay, Reliability, and Loading to determine the best path between two locations.

Article Key Topics:

Key Points of EIGRP

Fast convergence times: EIGRP has a fast convergence time, which means that it can quickly adapt to changes in the network topology.
Loop-free paths: EIGRP provides loop-free paths. This helps prevent routing loops and ensures the integrity and convergence stability of the network.
Support for VLSM: EIGRP supports variable length subnet masks (VLSM), therefore allowing for more efficient use of IP address space.
Scalability: EIGRP can scale to support almost any size network but is usually found in small to large networks.

Diffusing Update Algorithm (DUAL)

The Diffusing Update Algorithm (DUAL) is the core of EIGRP's operation. DUAL is responsible for calculating the shortest path to a network destination and for selecting the best path among multiple paths. DUAL is also responsible for providing loop-free paths, reducing network convergence times, and minimizing the use of network bandwidth.

DUAL uses three tables: the neighbor table, the topology table, and the routing table. The neighbor table keeps track of neighboring routers, the topology table contains information about network topology, and the routing table contains the best paths to network destinations.

EIGRP and Multicast

EIGRP uses multicast addresses to distribute routing updates and queries to its neighboring routers. The multicast address used by EIGRP is 224.0.0.10. This address is used by EIGRP routers to send hello messages to each other and also to send updates and queries to their neighbors.

When a router sends a multicast update to its neighbors, it includes only the routes that have changed since the last update. This helps to reduce the amount of traffic on the network and also reduces the processing power required by the routers. EIGRP also supports incremental updates, which means that only the changes to the routing table are sent, not the entire routing table.

EIGRP's use of multicast communication is also advantageous because it enables routers to discover new neighbors quickly. When a router sends a hello message to the multicast address, any neighboring routers that receive it will respond with their own hello messages. This allows routers to quickly learn about the topology of the network and update their routing tables accordingly.

However, there are some potential limitations to using multicast communication with EIGRP. One potential issue is that the multicast packets can be dropped or delayed on networks with high congestion. Additionally, if there are any network segments that do not support multicast communication, EIGRP may not be able to communicate with routers on those segments.

Despite these potential limitations, EIGRP's use of multicast communication remains a powerful tool for efficiently sharing routing information in large networks. By using a combination of distance-vector and link-state technologies, EIGRP is able to provide fast convergence times and efficient use of network resources.

Classless Operation

EIGRP is a classless routing protocol. This means that it supports variable length subnet masks (VLSM), which means it includes subnet mask information in its routing updates and enables network administrators to use subnets of different sizes within a network. This allows for more efficient use of IP address space.

Since an EIGRP update it includes the IP address of the destination network along with its, it enables the receiving routers to calculate the correct network address and determine the length of the prefix for the network, allowing them to support VLSMs.

In addition to supporting VLSMs, EIGRP also supports automatic summarization of routes at network boundaries. This means that EIGRP routers will automatically summarize the routes within their own networks and advertise the summary to neighboring routers. This reduces the amount of routing information that needs to be transmitted across the network and improves network efficiency.

However, there are some potential disadvantages to using classless operation with EIGRP. One potential issue is that it can increase the complexity of network designs and configurations. Additionally, classless operation can also increase the size of routing tables, which can impact the performance of routers with limited memory or processing power.

Despite these potential challenges, EIGRP's support for classless operation remains a valuable feature that enables network administrators to create more efficient and flexible network designs. By using VLSMs and automatic summarization, EIGRP is able to provide more granular control over network subnets and reduce the amount of routing traffic on the network.

EIGRP Limitations

One of the main limitations of EIGRP is that it is a proprietary protocol that is only supported by Cisco networking equipment. This means that it cannot be used in networks that include non-Cisco devices, and can limit the ability to interoperate with other routing protocols.

Another limitation of EIGRP is that it requires a certain amount of resources to operate efficiently. Specifically, EIGRP requires a significant amount of CPU and memory resources to calculate and maintain its routing tables. As a result, it may not be the best choice for networks with limited resources or older equipment.

EIGRP also has limitations when it comes to scalability. While EIGRP can scale well within an autonomous system (AS), it may not be the best choice for very large networks or networks with many ASs. In these cases, other routing protocols like OSPF (Open Shortest Path First) may be a better choice.

Finally, EIGRP's default metrics may not always be the most appropriate for certain types of networks or traffic patterns. While EIGRP allows for the tuning of its metrics, this can be a complex and time-consuming process, and may not always result in optimal performance.

Despite these limitations, EIGRP remains a popular and effective routing protocol in many networks, especially those that are primarily composed of Cisco equipment. However, network administrators should carefully evaluate the specific needs and limitations of their networks before selecting EIGRP as their routing protocol of choice.

EIGRP Disadvantages

Proprietary protocol: EIGRP is a proprietary protocol, which means that it is only supported on Cisco routers.
Limited support for non-Cisco devices: EIGRP has limited support for non-Cisco devices, which makes it difficult to use in heterogeneous network environments.

Summary

EIGRP is an advanced Cisco proprietary routing protocol that combines the features of both distance vector and link-state routing protocols. EIGRP uses the Diffusing Update Algorithm (DUAL) to provide loop-free paths, fast convergence times, and scalability. EIGRP uses multicast to distribute routing updates, which reduces network traffic and improves scalability. EIGRP is a classless routing protocol that supports VLSM.

Interior Gateway Protocol - IGRP

2011-05-26T08:45:42+10:00

IGRP (Interior Gateway Routing Protocol) is a Cisco proprietary distance-vector routing protocol used in enterprise networks to exchange routing information between routers. IGRP is a predecessor to the more advanced Enhanced Interior Gateway Routing Protocol (EIGRP) but is still used in some legacy networks. IGRP is a classful protocol, which means it does not support variable-length subnet masks (VLSMs) and is limited to classful addressing. In this article, we will explore IGRP in more detail, covering its hop counts, IGRP timers, limitations, advantages, and disadvantages.

Article Key Topics:

IGRP Hop Count

IGRP uses a maximum hop count of 100 by default, meaning that any destination beyond 100 hops is considered unreachable. IGRP allows network administrators to set a maximum hop count (255) for each network, which can be customized based on the network topology. A higher hop count limit allows packets to reach more remote networks but increases the time required to route the packets.

IGRP Timers

IGRP uses several timers to control its operation and prevent routing loops. The main IGRP timers are the update timer, hold-down timer, flush timer, and invalid timer.

Update Timer: The update timer controls how often IGRP routers send routing updates to their neighboring routers. By default, the update timer is set to 90 seconds.

Hold-Down Timer: The hold-down timer prevents routers from accepting routing information about a network that is not available. This timer is activated when a router detects that a network is down, preventing other routers from advertising the same network for a set period.

Flush Timer: The flush timer removes a route from the routing table when it has not been updated for a certain period, preventing outdated information from being used.

Invalid Timer: The invalid timer is used to determine when a route should be marked as invalid. If a router has not received an update about a particular route after the invalid timer expires, the route is marked as invalid and removed from the routing table.

IGRP Limitations

One of the main limitations of IGRP is its classful addressing scheme, which does not support VLSMs. This means that network administrators must use subnets of the same size across the entire network, limiting the network's scalability. Additionally, IGRP has a limited hop count of 100, which can prevent packets from reaching remote networks. IGRP is also susceptible to routing loops, where packets are sent in a loop between routers, leading to congestion and delays. Finally, IGRP is a proprietary protocol that is only compatible with Cisco routers, limiting interoperability with routers from other vendors.

IGRP Advantages and Disadvantages

One of the main advantages of IGRP is its ease of use and configuration. IGRP is relatively easy to set up and configure, making it a good choice for small to medium-sized networks. Additionally, IGRP has lower bandwidth usage compared to other routing protocols, making it ideal for networks with limited bandwidth. IGRP also supports unequal-cost load balancing, which allows routers to use multiple paths to reach a destination, improving network efficiency.

However, IGRP also has several disadvantages. One of the main disadvantages of IGRP is its limited scalability, due to its classful addressing scheme and maximum hop count of 100. This makes it unsuitable for large networks that require VLSMs and the ability to reach remote networks. Additionally, IGRP is prone to routing loops and convergence issues, which can lead to network congestion and delays. Finally, IGRP is a proprietary protocol, meaning that it is not an open standard and is only compatible with Cisco routers, limiting interoperability with other vendors' routers.

Summary

In this article we talked about IGRP, explained a Cisco proprietary distance-vector routing protocol used in enterprise networks to exchange routing information between routers. We talked about it being a classful protocol, analyzed its four different timers (update timer, hold-down timer, flush timer, and invalid timer), hop counts and more. Finally, we talked about the advantages and disadvantages of the IGRP protocol.

OSPF - Part 1: Introduction, OSPF Packet Structure, OSPF Messages and Characteristics

2011-05-26T08:38:57+10:00

Open Shortest Path First (OSPF) is a popular routing protocol developed for Internet Protocol (IP) networks by the Interior Gateway Protocol (IGP) working group of the Internet Engineering Task Force (IETF). The working group was formed in 1988 to design an IGP based on the shortest path first (SPF) algorithm for use in the Internet. Similar to the Interior Gateway Routing Protocol (IGRP), OSPF was created because in the mid-1980s, the Routing Information Protocol (RIP) was increasingly unable to serve large, heterogeneous internetworks.

Article Key Topics:

Below is a complete list of articles covering our OSPF Series:

- Part 1 (This article): Introduction, OSPF Packet Structure, OSPF Messages and Characteristics.

- Part 2: How OSPF Protocol Works & Basic Concepts: OSPF Neighbor, Topology & Routing Table, OSPF Areas & Router Roles, Theory & Overview.

- Part 3: OSPF Adjacency & Neighbor Forming Process. OSPF Hello Messages, OSPF Database Updates via Link State Requests (LSR & LSU).

- Part 4: OSPF Neighbor States – OSPF Neighbor Forming Process.

- Part 5: Analysis of OSPF Link State Update (LSU) - Link State Advertisement (LSA) Packet Structure. Common LSA Types.

- Part 6: OSPF LSA Types - Purpose and Function of Every OSPF LSA.

OSPF Packet Structure & Analysis

OSPF is a classless routing protocol, which means that in its updates, it includes the subnet of each route it knows about, thus, enabling variable-length subnet masks. With variable-length subnet masks, an IP network can be broken into many subnets of various sizes. This provides network administrators with extra network-configuration flexibility.These updates are multicasts at specific addresses (224.0.0.5 and 224.0.0.6).

The diagram below shows us the information that each field of an OSPF packet contains:

The numbers shown inside the coloured blocks represent the field length in bytes.

All OSPF packets begin with a 24-byte header, which is shown right above.

OSPF 'Type' Field

The 'Type' field (1-byte long) is a critical component of an OSPF (Open Shortest Path First) package. It indicates the type of OSPF message contained within the package, such as a Hello message, Link State Request message, Link State Update message, or Link State Acknowledgment message. The type field plays a crucial role in the OSPF protocol by helping to ensure that routers exchange the correct types of messages with each other, enabling them to learn about the network topology and establish the shortest path to the destination network.

Understanding the significance of the "Type" field is essential for network administrators to troubleshoot OSPF network issues and optimize the performance of their networks. Below are the Type field messages contained with a bit more information about their purpose and role:

Hello: Establishes and maintains neighbor relationships.
Database Description: Describes the contents of the topological database. These messages are exchanged when an adjacency is initialized.
Link-state Request: Requests pieces of the topological database from neighbor routers. These messages are exchanged after a router discovers (by examining database-description packets) that parts of its topological database are out of date.
Link-state Update: Responds to a link-state request packet. These messages also are used for the regular dispersal of Link-State Acknowledgments (LSA). Several LSAs can be included within a single link-state update packet.
Link-state Acknowledgment: Acknowledges link-state update packets.

OSPF's Primary Characteristics

OSPF - The Open Routing Protocol

The protocol is open (non proprietary), which means that its specification is in the public domain. The OSPF specification is published as Request For Comments (RFC) 1247. This has allowed vendors around the world to produce products and devices that fully support OSPF, without the need of paying any royalty licenses. This also played a major role in making OSPF as a widely acceptable routing protocol for small, medium and large networks.

OSPF - Dijkstra SPF Algorithm

The second principal characteristic is that OSPF is based on the SPF algorithm, which sometimes is referred to as the Dijkstra algorithm, named for the person credited with its creation.

The SPF algorithm calculates the shortest path by constructing a graph of the network, assigning costs to the links based on their bandwidth and determining the shortest path from each router to every other router in the network. The algorithm ensures that the path chosen has the lowest cost and that the route is loop-free, providing fast and efficient communication across the network.

The SPF algorithm also helps to ensure network stability and performance by quickly detecting changes in the network topology and recalculating the shortest path. When a change occurs, such as a link failure or a new link being added to the network, OSPF sends out Link State Advertisement (LSA) messages to inform all routers in the network of the change. The routers then use the SPF algorithm to recalculate the shortest path to the destination network based on the updated network topology. This ensures that the network continues to operate efficiently and that data is routed along the most optimal path.

OSPF - A Link State Routing Protocol

OSPF is a Link State routing protocol that calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables is included in OSPF LSAs. As OSPF routers accumulate link-state information, they use the SPF algorithm to calculate the shortest path to each node.

As a Link State routing protocol, OSPF contrasts with RIP and IGRP, which are Distance Vector routing protocols. Routers running the Distance Vector algorithm send all or a portion of their routing tables in routing-update messages to their neighbors.

Additional OSPF features include equal-cost, multipath routing, and routing based on upper-layer type-of-service (TOS) requests. TOS-based routing supports those upper-layer protocols that can specify particular types of service. An application, for example, might specify that certain data is urgent. If OSPF has high-priority links at its disposal, these can be used to transport the urgent datagram.

OSPF supports one or more metrics. If only one metric is used, it is considered to be arbitrary, and TOS is not supported. If more than one metric is used, TOS is optionally supported through the use of a separate metric (and, therefore, a separate routing table) for each of the eight combinations created by the three IP TOS bits (the delay, throughput, and reliability bits). If, for example, the IP TOS bits specify low delay, low throughput, and high reliability, OSPF calculates routes to all destinations based on this TOS designation.

Summary

This article introduced the OSPF routing protocol. It provided an overview of the routing protocol, its purpose, capabilities, and analyzed its structure within an Ethernet II frame. The 'Type' field within the OSPF header was examined and we also saw the different type of messages supported (Hello, Database description, Link-state Request, Link-state Update and Acknowledgment).

Routing Information Protocol - RIP

2011-05-26T08:26:22+10:00

Routing Information Protocol (RIP) is a distance-vector routing protocol that is commonly used in small to medium-sized networks. It is one of the oldest routing protocols still in use today, having been developed in the 1980s. Despite its age, RIP remains a popular choice due to its simplicity and ease of use.

Article Key Topics:

How RIP Works

RIP works by exchanging routing information between routers using a hop count metric. Each router sends out updates at regular intervals, which contain information about the routes it knows about and the number of hops to reach those routes. Routers then use this information to build their routing tables, which they use to determine the best path to reach a destination network.

One of the key features of RIP is that it limits the number of hops a packet can travel, with a maximum of 15 hops allowed. This means that RIP is not suitable for large networks or those with complex topologies, as it may not be able to find the most efficient path to a destination network.

RIP Versions

There are two versions of RIP in use today: RIP version 1 (RIPv1) and RIP version 2 (RIPv2). RIPv1 is the original version of the protocol and is limited to classful routing, meaning that it does not support the use of subnet masks. This can cause problems in networks with multiple subnets. RIPv1 uses network broadcasts (255.255.255.255) to exchange messages, routes and information between routers.

RIPv2, on the other hand, is a classless routing protocol and supports the use of subnet masks. It also includes support for authentication, which helps to prevent unauthorized routers from participating in the network. RIPv2 uses multicasts (224.0.0.9) to exchange messages, routes and information between routers.

RIP Key Component: Route Update Timer

The RIP Route Update Timer is a critical component of the Routing Information Protocol (RIP). It determines how often routing updates are sent out by a router to inform other routers of the network topology. The default value for the update timer is 30 seconds, meaning that updates are sent out every 30 seconds. However, this value can be tweaked to suit the needs of the network.

A shorter update timer can lead to more frequent updates, resulting in faster convergence times, but can also increase network traffic. A longer update timer can reduce network traffic, but may result in slower convergence times.

RIP Key Component: Route Invalid Timer

The RIP Route Invalid Timer is another important component of the Routing Information Protocol (RIP). It determines how long a router will wait before considering a route as invalid or unusable. The default value for the invalid timer is 180 seconds, meaning that if a router does not receive an update for a route for 180 seconds, it will consider the route as invalid and remove it from its routing table. However, this value can be changed to suit the needs of the network.

A shorter route invalid timer can lead to more frequent updates, resulting in faster convergence times, but can also increase network traffic. A longer update timer can reduce network traffic, but may result in slower convergence times.

RIP Key Component: Route Flush Timer

The RIP Route Flush Timer is a vital component of the Routing Information Protocol (RIP). It determines how long a router will wait before removing a route from its routing table after it has been declared invalid. The default value for the flush timer is 240 seconds, meaning that after a route has been declared invalid, the router will wait for 240 seconds before removing the route from its routing table. This delay ensures that any delayed or out-of-order packets that were en route to the destination can be delivered before the route is removed. However, this value can be changed to suit the needs of the network.

A shorter route flush timer can lead to more frequent updates, resulting in faster convergence times, but can also increase network traffic. A longer update timer can reduce network traffic, but may result in slower convergence times.

Advantages of RIP

One of the main advantages of RIP is its simplicity. It is easy to configure and can be implemented quickly in small to medium-sized networks. It is also a widely supported protocol, meaning that it can be used with a range of networking equipment from different vendors.

Another advantage of RIP is its stability. The protocol is designed to prevent routing loops from occurring, which can help to ensure the stability and reliability of the network.

Disadvantages of RIP

Despite its advantages, RIP has some limitations that can make it unsuitable for larger or more complex networks. One of these limitations is its hop count metric, which can lead to suboptimal routing decisions in networks with more than 15 hops between routers.

Another disadvantage of RIP is its slow convergence time. When a network topology changes, it can take several minutes for the routers to update their routing tables, which can lead to network downtime.

Summary

RIP is a simple and easy-to-use routing protocol that is still widely used in small to medium-sized networks today. Its hop count metric and slow convergence time can make it unsuitable for larger or more complex networks, but for smaller networks, it remains a reliable and stable routing protocol. The introduction of RIPv2 has addressed some of the limitations of the original protocol, making it a more versatile option for modern networks. Ultimately, the choice of routing protocol will depend on the specific needs of the network and the resources available for implementation and maintenance.

Hybrid Routing Protocols - Advantages and Disadvantages - Comparison

2011-05-26T08:24:10+10:00

Hybrid routing protocols are a combination of distance-vector and link-state routing protocols, and are used to provide a more efficient and scalable routing solution in larger networks. These protocols are particularly useful in environments where there are multiple paths available between nodes, and the network topology is subject to change.

Article Key Topics:

How do hybrid routing protocols work?

As mentioned earlier, Hybrid routing protocols use a combination of distance-vector and link-state routing protocols to provide a more efficient and scalable routing solution, while distance-vector routing protocols, such as Routing Information Protocol (RIP), work by exchanging routing information between neighbors, with each router broadcasting its entire routing table periodically. Link-state routing protocols, such as Open Shortest Path First (OSPF), work by distributing information about the state of links throughout the network, with routers constructing a complete map of the network topology.

Hybrid routing protocols combine the best features of these two protocols. They use distance-vector routing for small, stable networks, and link-state routing for large, complex networks with changing topologies.

Advantages of hybrid routing protocols

Scalability: Hybrid routing protocols are highly scalable and can handle networks with thousands of nodes. This is because they use link-state routing to provide a more accurate view of the network topology, and distance-vector routing to reduce the number of updates required.
Faster convergence: Hybrid routing protocols can converge quickly in the event of a network topology change, as they use both distance-vector and link-state routing to update routing tables.
Efficient use of bandwidth: Hybrid routing protocols use distance-vector routing to reduce the amount of bandwidth used for updates. Instead of broadcasting the entire routing table, routers only send updates for changed routes.
Load balancing: Hybrid routing protocols can distribute traffic across multiple paths, providing load balancing and increased network performance.

Disadvantages of hybrid routing protocols

Complexity: Hybrid routing protocols are more complex than either distance-vector or link-state routing protocols alone. This can make them difficult to configure and troubleshoot.
Resource-intensive: Hybrid routing protocols require more memory and processing power than distance-vector or link-state routing protocols alone.
Susceptible to routing loops: Hybrid routing protocols are susceptible to routing loops, which can occur when there are multiple paths between nodes and the routing protocol is not properly configured.

Examples of hybrid routing protocols

Enhanced Interior Gateway Routing Protocol (EIGRP): EIGRP is a Cisco proprietary hybrid routing protocol that combines distance-vector and link-state routing. It uses a modified version of the Diffusing Update Algorithm (DUAL) to calculate routes and has several features that make it efficient and scalable, such as partial updates and route summarization.
Border Gateway Protocol (BGP): BGP is an exterior gateway protocol (EGP) used to route traffic between different autonomous systems (AS). It is a hybrid routing protocol that uses both distance-vector and path-vector routing to determine the best path for traffic.

Summary

Hybrid routing protocols are an effective solution for larger networks that require scalable and efficient routing. By combining distance-vector and link-state routing, hybrid routing protocols offer faster convergence, efficient use of bandwidth, load balancing, and scalability. However, they are also more complex and resource-intensive than either distance-vector or link-state routing protocols alone. Some examples of hybrid routing protocols include EIGRP and BGP.

Link State Routing Protocols

2011-05-26T08:17:36+10:00

Link State routing protocols do not view networks in terms of adjacent routers and hop counts, but they build a comprehensive view of the overall network which fully describes the all possible routes along with their costs. Using the SPF (Shortest Path First) algorithm, the router creates a "topological database" which is a hierarchy reflecting the network routers it knows about. It then puts it's self on the top of this hierarchy, and has a complete picture from it's own perspective.

Link State protocols, unlike Distance Vector broadcasts, use multicast.

Multicast is a "broadcast" to a group of hosts, in this case routers (Please see the multicast page for more information). So if we had 10 router of which 4 where part of a "mutilcast group" then, when we send out a multicast packet to this group, only these 4 routers will receive the updates, while the rest of them will simply ignore the data. The multicast address is usually 224.0.0.5 & 224.0.0.6, this address is defined by the Interior Gateway Routing Protocol (IGRP).

When a router using a Link State protocol, such a Open Shortest Path First (OSPF) knows about a change on the network, it will multicast this change instantly, there for flooding the network with this information. The information routers require to build their databases is provided in the form of Link State Advertisement Packets (LSAP). Routers do not advertise their entire routing tables, instead each router advertises only its information regarding immediately adjacent routers.

Link State protocols in comparison to Distance Vector protocols have:

Big memory requirements
Shortest path computations require many CPU circles
If network is stable little bandwidth is used; react quickly to topology changes
Announcements cannot be “filtered”. All items in the database must be sent to neighbors
All neighbors must be trusted
Authentication mechanisms can be used to avoid undesired adjacencies
No split horizon techniques are possible

Even though Link State protocols work more efficiently, problem can arise. Usually problems occur cause of changes in the network topology (links go up-down), and all routers don't get updated immediately cause they might be on different line speeds, there for, routers connected via a fast link will receive these changes faster than the others on a slower link.

Different techniques have been developed to deal with these problem and these are :

1) Dampen update frequency

2) Target link-state updates to multicast

3) Use link-state area hierarchy for topology

4) Exchange route summaries at area borders

5) Use Time-stamps Update numbering & counters

6) Manage partitions using a area hierarchy

This completes out discussion around Link State Routing Protocols.

Distance Vector Routing Protocols

2011-05-25T06:37:59+10:00

Distance Vector routing protocols use frequent broadcasts (255.255.255.255 or FF:FF:FF:FF) of their entire routing table every 30 sec. on all their interfaces in order to communicate with their neighbours. The bigger the routing tables, the more broadcasts. This methodology limits significantly the size of network on which Distance Vector can be used.

Routing Information Protocol (RIP) and Interior Gateway Routing Protocol (IGRP) are two very popular Distance Vector routing protocols. You can find links to more information on these protocols at the bottom of the page. (That's if you haven't had enough by the time you get there !)

Distance Vector protocols view networks in terms of adjacent routers and hop counts, which also happens to be the metric used. The "hop" count (max of 15 for RIP, 16 is deemed unreachable and 255 for IGMP), will increase by one every time the packet transits through a router.

So the router makes decisions about the way a packet will travel, based on the amount of hops it takes to reach the destination and if it had 2 different ways to get there, it will simply send it via the shortest path, regardless of the connection speed. This is known as pinhole congestion.

Below is a typical routing table of a router which uses Distance Vector routing protocols:

Let's explain what is happening here:

In the above picture, you see 4 routers, each connected with its neighbour via some type of WAN link e.g ISDN.

Now, when a router is powered on, it will immediately know about the networks to which each interface is directly connected. In this case Router B knows that interface E0 is connected to the 192.168.0.0 network and the S0 interface is connected to the 192.168.10.0 network.

Looking again at the routing table for Router B, the numbers you see on the right hand side of the interfaces are the "hop counts" which, as mentioned, is the metric that distance vector protocols use to keep track on how far away a particular network is. Since these 2 networks are connected directly to the router's interface, they will have a value of zero (0) in the router's table entry. The same rule applies for every router in our example.

Remember we have "just turn the routers on", so the network is now converging and that means that there is no data being passed. When I say "no data" I mean data from any computer or server that might be on any of the networks. During this "convergence" time, the only type of data being passed between the routers is that which allows them to populate their routing tables and after that's done, the routers will pass all other types of data between them. That's why a fast convergence time is a big advantage.

One of the problems with RIP is that it has a slow convergence time.

Let's explain the above diagram:

In the above picture, the network is said to have "converged", in other words, all routers on the network have populated their routing table and are completly aware of the networks they can contact. Since the network is now converged, computers in any of the above networks can contact each other.

Again, looking at one of the routing tables, you will notice the network address with the exit interface on the right and next to that is the hop count to that network. Remember that RIP will only count up to 15 hops, after which the packet is discarded (on hop 16).

Each router will broadcast its entire routing table every 30 seconds.

Routing based on Distance Vector can cause a lot of problems when links go up and down, this could result in infinite loops and can also de-synchronise the network.

Routing loops can occur when every router is not updated close to the same time.

Let's have a look at the problem before we look at the various solutions:

Let's explain the above:

In the above picture you can see 5 routers of which routers A and B are connected with Router C, and they all end up connecting via routers D and E to Network 5.

As the above diagram shows, Network 5 suddenly fails.

All routers know about Network 5 from Router E. For example, Router A, in its tables, has a path to Network 5 through routers B, D and E.

When Network 5 fails, Router E knows about it since it's directly connected to it and tells Router D about it on its next update (when it will broadcast its entire routing table). This will result in Router D stopping routing data to Network 5 through Router E. But as you can see in the above picture, routers A B and C don't know about Network 5 yet, so they keep sending out update information. Router D will eventually send out its update and cause Router B to stop routing to Network 5, but routers A and C are still not updated. To them, it appear that Network 5 is still available through Router B with a metric of 3 !

Now Router A sends its regular broadcast of its entire routing table which includes reachability for Network 5. Routers C and B receive the wonderful news that Network 5 can be reached from Router A, so they send out the information that Network 5 is now available !

From now on, any packet with a destination of Network 5 will go to Router A then to Router B and from there back to Router A (remember that Router B got the good news that Network 5 is available via Router A).

So this is where things get a bit messy and you have that wonderful loop, where data just gets passed around from one router to another. Seems like they are playing ping pong :)

To deal with these problems we use the following techniques:

Maximum Hop Count

The routing loop we just looked at is called "counting to infinity" and it is caused by gossip and wrong information being communicated between the routers. Without something to protect against this type of a loop, the hop count will keep on increasing each time the packet goes through a router ! One way of solving this problem is to define a maximum hop count. Distance Vector (RIP) permits a hop count of up to 15, so anything that needs 16 hops is unreachable. So if a loop occurred, it would go around the network until the packet reached a hop count of 15 and the next router would simply discard the packet.

Split Horizon

Works on the principle that it's never useful to send information about a router back to the destination from which the original packet came. So if for example I told you a joke, it's pointless you telling me that joke again !

In our example it would have prevented Router A from sending the updated information it received from Router B back to Router B.

Route Poisoning

Alternative to split horizon, when a router receives information about a route from a particular network, the router advertises the route back to that network with the metric of 16, indicating that the destination is unreachable.

In our example, this means that when Network 5 goes down, Router E initiates router poisoning by entering a table entry for Network 5 as 16, which basically means it's unreachable. This way, Router D is not susceptible to any incorrect updates about the route to Network 5. When Router D receives a router poisoning from Router E, it sends an update called a poison reverse, back to Router E. This make sure all routes on the segment have received the poisoned route information.

Route poisoning, used with hold-downs (see section below) will certainly speed up convergence time because the neighboring routers don't have to wait 30 seconds before advertising the poisoned route.

Hold-Down Timers

Routers keep an entry for the network-down state, allowing time for other routers to recompute for this topology change, this way, allowing time for either the downed router to come back or the network to stabilise somewhat before changing to the next best route.

When a router receives an update from a neighbor indicating that a previously accessible network is not working and is inaccessible, the hold-down timer will start. If a new update arrives from a neighbor with a better metric than the original network entry, the hold-down is removed and data is passed. But an update is received from a neighbor router before the hold-down timer expires and it has a lower metric than the previous route, therefore the update is ignored and the hold-down timer keeps ticking. This allows more time for the network to converge.

Hold-down timers use triggered updates, which reset the hold-down timer, to alert the neighbor's routers of a change in the network. Unlike update messages from neighbor routers, triggered updates create a new routing table that is sent immediatley to neighbor routers because a change was detected in the network.

There are three instances when triggered updates will reset the hold-down timer:

1) The hold-down timer expires

2) The router received a processing task proportional to the number of links in the internetwork.

3) Another update is received indicating the network status has changed.

In our example, any update received by Router B from Router A, would not be accepted until the hold-down timer expires. This will ensure that Router B will not receive a "false" update from any routers that are not aware that Network 5 is unreachable. Router B will then send a update and correct the other routers' tables.

Distance Vector protocol covered here on Firewall.cx include:

The IP Routing Process - Step-by-Step Analysis

2011-05-24T07:06:15+10:00

We are going to analyse what happens when routing occurs on a network (IP routing process). When I was new to the networking area, I thought that all you needed was the IP Address of the machine you wanted to contact but so little did I know. You actually need a bit more information than just the IP Address !

The process we are going to explain is fairly simple and doesn't really change, no matter how big your network is.

The Example:

In our example, we have 2 networks, Network A and Network B. Both networks are connected via a router (Router A) which has 2 interfaces: E0 and E1. These interfaces are just like the interface on your network card (RJ-45), but built into the router.

Now, we are going to describe step by step what happens when Host A (Network A) wants to communicate with Host B (Network B) which is on a different network.

1) Host A opens a command prompt and enters >Ping 200.200.200.5.

2) IP works with the Address Resolution Protocol (ARP) to determine which network this packet is destined for by looking at the IP address and the subnet mask of Host A. Since this is a request for a remote host, which means it is not destined to be sent to a host on the local network, the packet must be sent to the router (the gateway for Network A) so that it can be routed to the correct remote network (which is Network B).

3) Now, for Host A to send the packet to the router, it needs to know the hardware address of the router's interface which is connected to its network (Network A), in case you didn't realise, we are talking about the MAC (Media Access Control) address of interface E0. To get the hardware address, Host A looks in its ARP cache - a memory location where these MAC addresses are stored for a few seconds.

4) If it doesn't find it in there it means that either a long time has passed since it last contacted the router or it simply hasn't resolved the IP address of the router (192.168.0.1) to a hardware address (MAC). So it then sends an ARP broadcast. This broadcast contains the following "What is the hardware (MAC) address for IP 192.168.0.1 ? ". The router identifies that IP address as its own and must answer, so it sends back to Host A a reply, giving it the MAC address of its E0 interface. This is also one of the reasons why sometimes the first "ping" will timeout. Because it takes some time for an ARP to be sent and the requested machine to respond with its MAC address, by the time all that happens, the TTL (Time To Live) of the first ping packet has expired, so it times out!

5) The router responds with the hardware address of its E0 interface, to which the 192.168.0.1 IP is bound. Host A now has everything it needs in order to transmit a packet out on the local network to the router. Now, the Network Layer hands down to the Datalink Layer the packet it generated with the ping (ICMP echo request), along with the hardware address of the router. This packet includes the source and destination IP address as well as the ICMP echo request which was specified in the Network Layer.

6) The Datalink Layer of Host A creates a frame, which encapsulates the packet with the information needed to transmit on the local network. This includes the source and destination hardware address (MAC) and the type field which specifies the Network Layer protocol e.g IPv4 (that's the IP version we use), ARP. At the end of the frame, in the FCS portion of the frame, the Datalink Layer will stick a Cyclic Redundancy Check (CRC) to make sure the receiving machine (the router) can figure out if the frame it received has been corrupted. To learn more on how the frame is created, visit the Data Encapsulation - Decapsulation.

7) The Datalink Layer of Host A hands the frame to the Physical layer which encodes the 1s and 0s into a digital signal and transmits this out on the local physical network.

8) The signal is picked up by the router's E0 interface and reads the frame. It will first do a CRC check and compare it with the CRC value Host A added to this frame, to make sure the frame is not corrupt.

9) After that, the destination hardware address (MAC) of the received frame is checked. Since this will be a match, the type field in the frame will be checked to see what the router should do with the data packet. IP is in the type field, and the router hands the packet to the IP protocol running on the router. The frame is stripped and the original packet that was generated by Host A is now in the router's buffer.

10) IP looks at the packet's destination IP address to determine if the packet is for the router. Since the destination IP address is 200.200.200.5, the router determines from the routing table that 200.200.200.0 is a directly connected network on interface E1.

11) The router places the packet in the buffer of interface E1. The router needs to create a frame to send the packet to the destination host. First, the router looks in the ARP cache to determine whether the hardware address has already been resolved from a prior communication. If it is not in the ARP cache, the router sends an ARP broadcast out E1 to find the hardware address of 200.200.200.5

12) Host B responds with the hardware address of its network interface card with an ARP reply. The router's E1 interface now has everything it needs to send the packet to the final destination.

13)The frame generated from the router's E1 interface has the source hardware address of E1 interface and the hardware destination address of Host B's network interface card. However, the most important thing here is that even though the frame's source and destination hardware address changed at every interface of the router it was sent to and from, the IP source and destination addresses never changed. The packet was never modified at all, only the frame changed.

14) Host B receives the frame and runs a CRC. If that checks out, it discards the frame and hands the packet to IP. IP will then check the destination IP address. Since the IP destination address matches the IP configuration of Host B, it looks in the protocol field of the packet to determine the purpose of the packet.

15) Since the packet is an ICMP echo request, Host B generates a new ICMP echo-reply packet with a source IP address of Host B and a destination IP address of Host A. The process starts all over again, except that it goes in the opposite direction. However, the hardware address of each device along the path is already known, so each device only needs to look in its ARP cache to determine the hardware (MAC) address of each interface.

And that just about covers our routing analysis. If you found it confusing, take a break and come back later on and give it another shot. Its really simple once you grasp the concept of routing.

Back to the Routing Section

Routed Protocols

2011-05-24T06:52:01+10:00

We all understand that TCP/IP, IPX-SPX are protocols which are used in a Local Area Network (LAN) so computers can communicate between with each other and with other computers on the Internet.

Chances are that in your LAN you are most probably running TCP/IP. This protocol is what we call a "routed" protocol. The term "routed" refers to something which can be passed on from one place (network) to another. In the example of TCP/IP, this is when you construct a data packet and send it across to another computer on the Internet

This ability to use TCP/IP to send data across networks and the Internet is the main reason it's so popular and dominant. If you're thinking also of NetBeui and IPx/SPX, then note that NetBeui is not a routed protocol, but IPX/SPX is! The reason for this is actually in the information a packet holds when it uses one of the protocols.

If you looked at a TCP/IP or IPX/SPX packet, you will notice that they both contain a "network" layer. For TCP/IP, this translates to the IP layer (Layer 3), as for IPX/SPX, it's the IPX layer (Layer 3). To make it easy to understand, I will use TCP/IP as an example.

In the picture below, you can see a TCP/IP packet within an Ethernet II Frame (The frame is like an "envelope" which encapsulates the TCP/IP packet):

Looking closely, you will notice that Layer 3 (Network Layer) contains the IP header. It is within this section the computer puts the Source and Destination IP number. Thanks to the existence of this IP header, we are able to put a destination IP which can be one that's not on our network, and the computer will figure it out after completing a simple calculation and know if it needs to send this data to the router for it to be sent to its destination. You can read more on Layer 3 by visiting our OSI Model section.

IPX/SPX contains a similar field which gives it the same ability, which is to send packets over to different networks.

NetBEUI (NetBIOS Extended User Interface) on the other hand has no such information! This means that NetBeui has no information about the destination network to which it needs to send the data, as it was developed for LAN use only, or you could say that all hosts are considered to be on the same logical network and all resources are considered to be local. This classifies NetBeui as a "non routed" protocol.