Routing and Congestion Control Open Shortest Path First (OSPF)

Module
7
Routing and
Congestion Control

Open Shortest
Path First (OSPF)

Specific Instructional Objectives
On completion of this lesson, the students will be able to:
•
Explain the operation of the OSPF protocol
•
Explain the routing algorithm used in OSPF
•
State the OSPF message format
•
Explain how shortest path is calculated using Dijkstra’s algorithm
•
Explain the routing hierarchy used in OSPF
7.3.1 Introduction
Open Shortest Path First (OSPF) is another Interior Gateway Protocol. It is a 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. OSPF was created because in the mid-1980s, the Routing Information Protocol (RIP) was increasingly incapable of serving large, heterogeneous internetworks. OSPF being a SPF algorithm scales better than RIP. Few of the important features of OSPF are as follows:
•
This protocol is open, which means that its specification is in the public domain. It means that anyone can implement it without paying license fees. The OSPF specification is published as Request For Comments (RFC) 1247.
•
OSPF is based on the SPF algorithm, which is also referred to as the Dijkstra’s algorithm, named after the person credited with its creation.
•
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 are included in OSPF LSAs. As a link-state routing protocol, OSPF contrasts with RIP, 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 only to their neighbors.
•
OSPF specifies that all the exchanges between routers must be authenticated. It allows a variety of authentication schemes, even different areas can choose different authentication schemes. The idea behind authentication is that only authorized router are allowed to advertise routing information.
•
OSPF include Type of service Routing. It can calculate separate routes for each Type of Service (TOS), for example it can maintain separate routes to a single destination based on hop-count and high throughput.
•
OSPF provides Load Balancing. When several equal-cost routes to a destination exist, traffic is distributed equally among them.
•
OSPF allows supports host-specific routes, Subnet-specific routes and also network-specific routes.
•
OSPF allows sets of networks to be grouped together. Such a grouping is called an Area. Each Area is self-contained; the topology of an area is hidden from the Version 2 CSE IIT, Khargpur
rest of the Autonomous System and from other Areas too. This information hiding enables a significant reduction in routing traffic.
•
OSPF uses different message formats to distinguish the information acquired from within the network (internal sources) with that which is acquired from a router outside (external sources).
In this lesson we shall discuss the important features of OSPF. The lesson is divided into five sections. First we shall look at various distinguishing features of OSPF, which stand it apart from other routing protocols. Then we shall briefly discuss the Link-state Routing. In the next section we will look into the Routing Hierarchy of OSPF. In the fourth section we discuss the various message formats used in OSPF. And finally we will have a look at some of its additional features.
7.3.2 Link-State Algorithm
Just like any other Link state routing, OSPF also has the following features:
•
Advertise about neighborhood: Instead of sending its entire routing table, a router sends information about its neighborhood only.
•
Flooding: Each router sends this information to every other router on the internetwork, not just to its neighbors. It does so by a process of flooding. In Flooding, a router sends its information to all its neighbors (through all of its output ports). Every router sends such messages to each of its neighbor, and every router that receives the packet sends copies to its neighbor. Finally, every router has a copy of same information.
•
Active response: Each outer sends out information about the neighbor when there is a change.
Initialization: When an SPF router is powered up, it initializes its routing-protocol data structures and then waits for indications from lower-layer protocols that its interfaces are functional.
After a router is assured that its interfaces are functioning, it uses the OSPF Hello protocol (sends greeting messages) to acquire neighbors, which are routers with interfaces to a common network. The router sends hello packets to its neighbors and receives their hello packets. These messages are also known as greeting messages. It then prepares an LSP (Link State packet) based on the results of this Hellow protocol.
An example of an internet is shown in Fig. 7.3.1, where R1 is a neighbor of R2 and R4, R2 is a neighbor of R1, R3 and R4, R3 is a neighbor of R2 and R4, R4 is a neighbor of R1, R2 and R3. So each router will send greeting messages to its entire neighbors.
Version 2 CSE IIT, Khargpur
1
2
4
3
1
2
Figure 7.3.1 An example internet
Information from neighbors: A router gets its information about its neighbor by periodically sending them a short greeting packet (this is known as Hello Message format). If neighbor responds to this greeting message as expected, it is assumed to be alive and functioning. If it does not, a change is assumed to have occurred and the sending router then alerts the rest of the network in its next LSP, about this neighbor being down. These Greeting messages are small enough that they do not use network resources to a significant amount, unlike the routing table updates in case of a vector-distance algorithm.
Link state packet: The process of router flooding the network with information about its neighborhood is known as Advertising. The basis of advertising is a short packet called a Link state Packet (LSP). An LSP usually contains 4 fields: the ID of the advertiser (Identifier of the router which advertises the message), ID of the destination network, The cost, and the ID of the neighbor router. Figure 7.3.2 shows the LSP of a router found after the Hellow protocol and Fig. 7.3.3 shows the basic fields of LSP.
Figure 7.3.2 LSP of the router R3
1
1
2
2
1
3
4
Net A
Net B
Net C
Net D
R1
R2
R3
R3 3 1 R2
R3 4 3 R4
R4
LSPofR3
5
1
5
Net D
Net C
Net B
NetA
R1
R3
Note: Numbers in Blue shows the Cost to reach that network
R2
Version 2 CSE IIT, Khargpur
Advertiser
Network
Cost
Neighbor
---------------
-------------
---------------
-------------
---------------
--------------
---------------
-------------
Figure 7.3.3 The LSP fields
Link State Database: Every router receives every LSP and then prepares a database, which represents a complete network topology. This Database is known as Link State Database. Figure 7.3.4 shows the database of our sample internetwork. These databases are also known as topological database.
Advertiser
Network
Cost
Neighbor
R1
A
4
R4
R1
B
1
R2
R2
B
2
R1
R2
C
5
R3
R3
C
1
R2
R3
D
3
R4
R4
A
1
R1
R4
D
2
R3
Figure 7.3.4 Link State Database
Because every router receives the same LSPs, every router builds the same database. Every router uses it to calculate its routing table. If a router is added or deleted from the system, the whole database must be changed accordingly in all routers.
Shortest Path calculation: After gathering the Link State database, each router applies an algorithm called the Dijkstra algorithm to calculate the shortest distance between any two nodes. The Dijkstra’s algorithm calculates the shortest path between two points on a network using a graph made up of nodes and arcs, where nodes are the Routers and the network, while connection between router and network is refer to as arcs.
The algorithm begins to build a tree by identifying its root as shown in Fig. 7.3.5. The router is the root itself. The algorithm then attaches all other nodes that can be reached from that router; this is done with the help of the Link state database.
Version 2 CSE IIT, Khargpur
2
1
1
4
4
Net D
Net A
1
Net B
R1
Net B
Net A
R4
R1
(a)
(b)
1
1
2
2
1
4
Net D
Net C
Net B
Net A
5
R4
R1
R3
(c)
R2
Figure 7.3.5 Path calculation for router R1
From this shortest path calculation each router makes its routing table, as per our example internet table for router R1 is given in Fig. 7.3.6. All other routers too have a similar routing table made up after this point.
Network
Cost
Next Router
A
4
-----
B
1
-----
C
8
R2
D
7
R4
Figure 7.3.6 Routing table example
Version 2 CSE IIT, Khargpur
7.3.3 Routing Hierarchy in OSPF
Unlike RIP, OSPF can operate within a hierarchy. The largest entity within the hierarchy is the autonomous system (AS), which is a collection of networks under a common administration that share a common routing strategy. OSPF is an intra-AS (interior gateway) routing protocol, although it is capable of receiving routes from and sending routes to other ASs.
An AS can be divided into a number of areas, which are groups of contiguous networks and attached hosts. Routers with multiple interfaces can participate in multiple areas. These routers, which are called Area Border Routers, maintain separate topological databases for each area.
A topological database is essentially an overall picture of networks in relationship to routers. The topological database contains the collection of LSAs received from all routers in the same area. Because routers within the same area share the same information, they have identical topological databases. We have already seen how these topological databases are made in the previous section.
The term domain sometimes is used to describe a portion of the network in which all routers have identical topological databases. Domain is frequently used interchangeably with AS. An area's topology is invisible to entities outside the area. By keeping area topologies separate, OSPF passes less routing traffic than it would if the AS were not partitioned.
Area partitioning creates two different types of OSPF routing, depending on whether the source and the destination are in the same or different areas. Intra-area routing occurs when the source and destination are in the same area; inter-area routing occurs when they are in different areas.
An OSPF backbone is responsible for distributing routing information between areas. It consists of all Area Border Routers, networks not wholly contained in any area, and their attached routers. Figure 7.3.7 shows an example of an internet with several areas. In the Fig. 7.3.7, routers 9, 10, 11, 12 and 13 make up the backbone. If host H1 in Area 3 wants to send a packet to host H2 in Area 1, the packet is sent to Router 4, which then forwards the packet along the backbone to Area Border Router 12, which sends the packet to Router 11, and Router 11 forwards it to Router 10. Router 10 then sends the packet through an intra-area router (Router 3) to be forwarded to Host H2.
The backbone itself is an OSPF area, so all backbone routers use the same procedures and algorithms to maintain routing information within the backbone that any area router would. The backbone topology is invisible to all intra-area routers, as are individual area topologies to the backbone. Areas can be defined in such a way that the backbone is not contiguous. In this case, backbone connectivity must be restored through virtual links. Virtual links are configured between any backbone routers that share a link to a nonbackbone area and function as if they were direct links.
Version 2 CSE IIT, Khargpur
Figure 7.3.7 Different areas in an Autonomous system
7.3.4 OSPF Message Format
In this section we will discuss various message formats used by OSPF, first we will see fixed header, which is common to all messages and then we will look at various variable part, different for different messages used in OSPF.
Fixed Header: All OSPF packets begin with a 24-byte header, as illustrated in Figure 7.3.8. Summary of the functions of different fields are given below:
•
Version number—Identifies the OSPF version used.
•
Type—Identifies the OSPF packet type as one of the following:
o
Hello—Establishes and maintains neighbor relationships.
o
Database description—Describes the contents of the topological database. These messages are exchanged when an adjacency is initialized.
o
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 outdated.
R9
R6
R2
R1
H1
H2
Area 1
Area2
Area 3
R3
R5
R4
R8
R7
R10
R13
R11
R12
Note: backbone routers are named in Blue.
Autonomous System
Version 2 CSE IIT, Khargpur
o
Link-state update—Responds to a link-state request packet. These messages also are used for the regular dispersal of LSAs. Several LSAs can be included within a single link-state update packet.
o
Link-state acknowledgment—Acknowledges link-state updates packets.
•
Message length—Specifies the packet length, including the OSPF header, in bytes.
•
Source Router IP address—Identifies the source of the packet.
•
Area ID—Identifies the area to which the packet belongs. All OSPF packets are associated with a single area.
•
Checksum—Checks the entire packet contents for any damage suffered in transit.
•
Authentication type—Contains the authentication type. All OSPF protocol exchanges are authenticated. The authentication type is configurable on per-area basis.
•
Authentication—Contains authentication information.
•
Data—Contains encapsulated upper-layer information.
08162431
DATA
Authentication (Octets 4-7)
Authentication (Octets 0-3)
Authentication type
Checksum
The following descriptions summarize the header
Source Router IP Address
Message length
Type
Version
Variable part
Fixed Header
Figure 7.3.8 24-Octet OSPF Message Header
Hellow Message Format: OSPF sends Hellow (greeting) messages on each link periodically to establish and test neighbor reachability. The ormat of this message is shown in Figure 7.3.9. Functions of the header fields are briefly explained below.
•
Fixed Header: as discussed in previous section and Fig. 7.3.8
•
Network mask: contains mask for the network over which the message is to be send.
•
Dead Timer: gives time in seconds after which a non-responding neighbor is considered dead.
•
Hellow Inter: means Hellow Interval, it is the normal period, in seconds, between hello messages.
•
Gway Prio: means gateway priority, it is the interior priority of this router, and is used in selecting the backup designated router.
•
Designated Router: IP address of the router, which is the designated router for the network as viewed by the sender.
Version 2 CSE IIT, Khargpur
•
Backup Designated Router: IP address of the router, which is the Backup designated router for the network as viewed by the sender.
Neighbor IP Address: IP address of all the neighbors from which the sender has recently received Hellow Messages.
OSPF Fixed Header with TYPE =1
Network mask
Dead Timer
Hellow Inter
Gway Prio
Designated Router
Backup designated Router
Neighbor1 IP address
……………………..
Neighbor2 IP address
Figure 7.3.9 OSPF Hellow Message Format
Database Description message Format: These messages are exchanged by routers to initialize their network topology database. In this exchange one router serves as a master, while other as a slave. The slave acknowledges each database description message with a response. This message is further divided into several messages using I and M bits. The functions of different fields, as shown in Fig. 7.3.10, are summarized below:
•
Fixed Header: as discussed in previous section and Fig. 7.3.8
•
I, M, S bits: Bit I is set to 1 if additional message follows. Bit S indicates whether a message was sent by a master (1) or a slave (0).
•
Database Sequence Number: this is used to sequence the messages so that the receiver can detect if any of the message is missing. Initial message contains a random sequence number R; subsequent messages contain sequential integers starting from R.
•
Link Type: describes one link in network topology; it is repeated for each link. Different possible values for Link Type is as follows:
•
Link ID: gives an identification of the Link, generally an IP address.
•
Advertising Router: specifics the router which is advertising this link.
Link Type
Meaning
1
Router Link
2
Network Link
3
Summary Link (IP Network)
4
Summary Link (Link to Border Router)
5
External Link (Link to another site)
081624
Variable part
Fixed Header
Version 2 CSE IIT, Khargpur
•
Link sequence Number: integer to ensure that messages are not mixed or received out of order.
•
Link Checksum: Checksum to ensure that the information has not been corrupted.
Link Age: Helps order messages, gives the time (in seconds) since link was established.
081624
OSPF Fixed Header with TYPE =2
Must be zero
I
M
S
Database Sequence Number
Link Type
Link ID
Advertising Router
Link Sequence Number
Link Checksum
Link Age
………………………
Variable part
Fixed Header
Figure 7.3.10 OSPF Database Description Message Format
Link Status Request Message: After exchanging Database Description message, router may discover that some part of its database is outdated. Link Status message is used to request the neighbor to supply the updated information. The message lists specific links, as shown in Figure 7.3.11. The neighbor responds with the most current information it has about those links. The three fields as shown are repeated for each link, about which status is requested. More than one request message is required if list is long. All the fields have usual meaning as discussed in previous message format.
08162431
OSPF Fixed Header with TYPE =3
Link Type
Link ID
Advertising Router
……………….
Variable part
Fixed Header
Figure 7.3.11 OSPF Link Status Request Message Format
Link Status Update Message: Routers broadcast the status of links with Link Status Update message. Each update consists of a list of advertisements. Figure 7.3.12 (a) shows the format of link status update message, and Fig. 7.3.12 (b) shows an elaborated view of a single Link Status advertisement (which is within the Link Status Update message).
Version 2 CSE IIT, Khargpur
OSPF Fixed header with TYPE = 4
Number of Link Status Advertisements
Link Status Advertisement 1
…………………………….
Link status Advertisement N
Link Age
Link Type
Link ID
Advertising Router
Link Sequence Number
Link Checksum
Length
(a) (b)
Figure 7.3.12(a) Link Status Update Message, (b) Format of each Link Advertisement
7.3.5 Additional OSPF Features
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). For example, if the IP TOS bits specify low delay, low throughput, and high reliability, OSPF calculates routes to all destinations based on this TOS designation.
IP subnet masks are included with each advertised destination, 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.
Fill In The Blanks
1.
OSPF is __________ Gateway Protocol.
2.
OSPF is abbreviated as _____________________.
3.
OSPF based on ________path ________ algorithm
4.
OSPF is a _______state routing protocol
5.
Link State databases are also known as _________ databases.
6.
OSPF sends ________ messages on each link periodically to establish and test neighbor reachability
Version 2 CSE IIT, Khargpur
Answers
1.
Interior
2.
Open Shortest Path First
3.
Shortest-First
4.
link
5.
topological
6.
Hellow
Short Answer Questions
1. Explain steps involved in Link State Routing.
Ans: In Link state routing, each router shares its knowledge of its neighborhood with every other router in the internetwork. Following are few noteworthy points about the Link state routing:
•
Advertise about neighborhood: instead of sending its entire routing table, a router sends information about its neighborhood only.
•
Flooding: Each router sends this information to every other router on the internetwork, not just to its neighbors. It does so by a process of flooding. In Flooding, a router sends its information to all its neighbors (through all of its output ports). Every router sends such messages to each of its neighbor, and every router that receives the packet sends copies to its neighbor. Finally, every router has a copy of same information.
•
Active response: Each outer sends out information about the neighbor when there is a change.
2.
Explain Routing Hierarchy in OSPF.
Ans: Unlike RIP, OSPF can operate within a hierarchy. The largest entity within the hierarchy is the autonomous system (AS), which is a collection of networks under a common administration that share a common routing strategy. An AS can be divided into a number of areas, which are groups of contiguous networks and attached hosts. Routers with multiple interfaces can participate in multiple areas. These routers, which are called Area Border Routers, maintain separate topological databases for each area.
Area partitioning creates two different types of OSPF routing, depending on whether the source and the destination are in the same or different areas. Intra-area routing occurs when the source and destination are in the same area; interarea routing occurs when they are in different areas.
3.
Explain various types of OSPF message formats.
Ans: Type field in the header format identifies the OSPF packet type as one of the following:
•
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
Version 2 CSE IIT, Khargpur
database-description packets) that parts of its topological database are outdated. Link-state update—Responds to a link-state request packet. These messages also are used for the regular dispersal of LSAs. Several LSAs can be included within a single link-state update packet.
•
Link-state acknowledgment—Acknowledges link-state updates packets.
4.
For what purpose Dead Timer, Hellow Inter, Gateway Priority, designated router fields is used in OSPF Hellow Message.
Ans: Dead Timer gives time in seconds after which a non-responding neighbor is considered dead.
Hellow Inter: It is the normal period, in seconds, between hello messages.
Gway Prio: It is the interior priority of this router, and is used in selecting the backup designated router.
Designated Router: IP address of the router, which is the designated router for the network as viewed by the sender.
5. Explain the various possible options for Link Type filed in Database Description message of OSPF.
Ans: Link Type: describes one link in network topology; it is repeated for each link. Different possible values for Link Type are as follows:
Link Type
Meaning
1
Router Link
2
Network Link
3
Summary Link (IP Network)
4
Summary Link (Link to Border Router)
5
External Link (Link to another site)
Version 2 CSE IIT, Khargpur