OSPF Hello protocol

OSPF Hello protocol
2.2.6 This page will introduce hello packets and the Hello protocol.
When a router starts an OSPF routing process on an interface, it sends a hello packet and continues to send hellos at regular intervals. The rules that govern the exchange of OSPF hello packets are called the Hello protocol.
At Layer 3 of the OSI model, the hello packets are addressed to the multicast address 224.0.0.5. This address is “all OSPF routers”. OSPF routers use hello packets to initiate new adjacencies and to ensure that neighbor routers are still functioning. Hellos are sent every 10 seconds by default on broadcast multi-access and point-to-point networks. On interfaces that connect to NBMA networks, such as Frame Relay, the default time is 30 seconds.
On multi-access networks the Hello protocol elects a designated router (DR) and a backup designated router (BDR).
Although the hello packet is small, it consists of the OSPF packet header. For the hello packet the type field is set to 1.
The hello packet carries information that all neighbors must agree upon before an adjacency is formed, and link-state information is exchanged.
The Interactive Media Activity will help students identify the fields in an OSPF packet header.
The next page will describe the OSPF routing process.

OSPF network types

OSPF network types
2.2.5 This page will introduce the three types of OSPF networks.
A neighbor relationship is required for OSPF routers to share routing information. A router will try to become adjacent, or neighbor, to at least one other router on each IP network to which it is connected. OSPF routers determine which routers to become adjacent to based on the type of network they are connected to. Some routers may try to become adjacent to all neighbor routers. Other routers may try to become adjacent to only one or two neighbor routers. Once an adjacency is formed between neighbors, link-state information is exchanged.
OSPF interfaces automatically recognize three types of networks:

• Broadcast multi-access, such as Ethernet
• Point-to-point networks
• Nonbroadcast multi-access (NBMA), such as Frame Relay

A fourth type, point-to-multipoint, can be manually configured on an interface by an administrator. 
In a multi-access network, it is not known in advance how many routers will be connected. In point-to-point networks, only two routers can be connected.
In a broadcast multi-access network segment, many routers may be connected. If every router had to establish full adjacency with every other router and exchange link-state information with every neighbor, there would be too much overhead. If there are 5 routers, 10 adjacency relationships would be needed and 10 link-states sent. If there are 10 routers then 45 adjacencies would be needed. In general, for n routers, n*(n-1)/2 adjacencies would need to be formed.
The solution to this overhead is to hold an election for a designated router (DR). This router becomes adjacent to all other routers in the broadcast segment. All other routers on the segment send their link-state information to the DR. The DR in turn acts as the spokesperson for the segment. The DR sends link-state information to all other routers on the segment using the multicast address of 224.0.0.5 for all OSPF routers.
Despite the gain in efficiency that electing a DR provides, there is a disadvantage. The DR represents a single point of failure. A second router is elected as a backup designated router (BDR) to take over the duties of the DR if it should fail. To ensure that both the DR and the BDR see the link-states all routers send on the segment, the multicast address for all designated routers, 224.0.0.6, is used.
On point-to-point networks only two nodes exist and no DR or BDR is elected. Both routers become fully adjacent with each other.
The Interactive Media Activity will help students recognize the three types of OSPF networks.
The next page will describe the OSPF Hello protocol.

Shortest path algorithm

Shortest path algorithm
2.2.4 This page will explain how OSPF uses the shortest-path algorithm to determine the best path to a destination.
In this algorithm, the best path is the lowest cost path. Edsger Wybe Dijkstra, a Dutch computer scientist, formulated the shortest path-algorithm, also known as Dijkstra's algorithm. The algorithm considers a network to be a set of nodes connected by point-to-point links. Each link has a cost. Each node has a name. Each node has a complete database of all the links and so complete information about the physical topology is known. All router link-state databases, within a given area, are identical. The table in Figure shows the information that node D has received. For example, D received information that it was connected to node C with a link cost of 4 and to node E with a link cost of 1.
The shortest path algorithm then calculates a loop-free topology using the node as the starting point and examining in turn information it has about adjacent nodes. In Figure , node B has calculated the best path to D. The best path to D is by way of node E, which has a cost of 4. This information is converted to a route entry in B which will forward traffic to C. Packets to D from B will flow B to C to E, then to D in this OSPF network.
In the example, node B determined that to get to node F the shortest path has a cost of 5, through node C. All other possible topologies will either have loops or a higher cost paths.
The next page will explain the concept of OSPF networks.

Comparing OSPF with distance vector routing protocols

Comparing OSPF with distance vector routing protocols
2.2.3 This page will explain how OSPF compares to distance vector protocols such as RIP. Link-state routers maintain a common picture of the network and exchange link information upon initial discovery or network changes. Link-state routers do not broadcast routing tables periodically as distance vector protocols do. Therefore, link-state routers use less bandwidth for routing table maintenance.
RIP is appropriate for small networks, and the best path is based on the lowest number of hops. OSPF is appropriate for large, scalable internetworks, and the best path is determined by the speed of the link. RIP and other distance vector protocols use simple algorithms to compute best paths. The SPF algorithm is complex. Routers that implement distance vector protocols need less memory and less powerful processors than those that implement OSPF.
OSPF selects routes based on cost, which is related to speed. The higher the speed, the lower the OSPF cost of the link.
OSPF selects the fastest loop-free path from the SPF tree as the best path in the network.
OSPF guarantees loop-free routing. Distance vector protocols may cause routing loops.
If links are unstable, flooding of link-state information can lead to unsynchronized link-state advertisements and inconsistent decisions among routers.
OSPF addresses the following issues:

• Speed of convergence
• Support for Variable Length Subnet Mask (VLSM)
• Network size
• Path selection
• Grouping of members

In large networks RIP convergence can take several minutes since the routing table of each router is copied and shared with directly connected routers. After initial OSPF convergence, maintaining a converged state is faster because only the changes in the network are flooded to other routers in an area.
OSPF supports VLSMs and therefore is referred to as a classless protocol. RIP v1 does not support VLSMs, however, RIP v2 does support VLSMs.
RIP considers a network that is more than 15 routers away to be unreachable because the number of hops is limited to 15. This limits RIP to small topologies. OSPF has no size limits and is suitable for intermediate to large networks.
RIP selects a path to a network by adding one to the hop count reported by a neighbor. It compares the hop counts to a destination and selects the path with the smallest distance or hops. This algorithm is simple and does not require a powerful router or a lot of memory. RIP does not take into account the available bandwidth in best path determination.
OSPF selects a path using cost, a metric based on bandwidth. All OSPF routers must obtain complete information about the networks of every router to calculate the shortest path. This is a complex algorithm. Therefore, OSPF requires more powerful routers and more memory than RIP.
RIP uses a flat topology. Routers in a RIP region exchange information with all routers. OSPF uses the concept of areas. A network can be subdivided into groups of routers. In this way OSPF can limit traffic to these areas. Changes in one area do not affect performance in other areas. This hierarchical approach allows a network to scale efficiently.
The Interactive Media Activity will help students learn the differences between link-state and distance vector protocols.
The next page will discuss the shortest path algorithm

OSPF terminology

OSPF terminology
2.2.2 There are many words and concepts for students in this TI and the figures should help to explain them. Use the interactive media activity to reinforce the terms and their abbreviations. Instructors might like to hold an acronym competition to see who can explain the words and concepts in the following table:

Link	A link is a physical and electrical connection between two network devices.
Link-state (LS)	Link-state is the status of a link between two routers. This status includes information about a router interface and its relationship to neighboring routers.
Cost	Cost is the value assigned to a link. Link-state protocols assign a cost to a link, which is based on the speed of the network connection.
Area	An area is a collection of networks and routers that has the same area identification. Each router within an area has the same link-state information. A router within an area is called an internal router.
Designated Router (DR)	A DR is one router on an OSPF multi-access network that represents all the routers in that network. Each OSPF network has a DR and BDR. These routers have special responsibilities that are discussed later in this module.
Backup Designated Router (BDR)	A BDR is a standby router that becomes the DR, if the original DR fails.
Adjacencies database (AD)	An AD is a listing of all the neighbors to which a router has established bi-directional communication.
Link-state database (LSD) or topological database	An LSD is a list of information about all other routers in the network. It shows the network topology. All routers within an area have identical link-state databases.
Routing table	The routing table, also known as the forwarding database, is generated when an algorithm is run on the link-state database. Each routing table is unique and contains information of how and where to send packets to other routers.
SPF algorithm	An SPF algorithm is a routing algorithm that iterates on length of path to determine a shortest-path spanning tree.
Link-state advertisement (LSA)	An LSA is a broadcast packet used by link-state protocols that contain information about neighbors and path costs. LSAs are used by the receiving routers to maintain their routing tables.

Link-state routers identify neighboring routers and then communicate with the identified neighbors. OSPF has its own terminology. The new terms are shown in Figure .
OSPF gathers information from neighbor routers about the link status of each OSPF router. This information is flooded to all its neighbors. An OSPF router advertises its own link-states and passes on received link-states.
The routers process the information about link-states and build a link-state database. Every router in the OSPF area will have the same link-state database. Therefore, every router has the same information about the state of the links and the neighbors of every other router.
Each router then applies the SPF algorithm on its own copy of the database. This calculation determines the best route to a destination. The SPF algorithm adds up the cost, which is a value that is usually based on bandwidth. The lowest cost path is added to the routing table, which is also known as the forwarding database.
Each router keeps a list of adjacent neighbors, called the adjacency database. The adjacency database is a list of all the neighbor routers to which a router has established bidirectional communication. This is unique to each router.
To reduce the number of exchanges of routing information among several neighbors on the same network, OSPF routers elect a designated router (DR) and a backup designated router (BDR) that serve as focal points for routing information exchange.
The Interactive Media Activity will teach students about OSPF terminology.
The next page will compare OSPF to distance vector protocols.

Single-Area OSPF Concepts /

Single-Area OSPF Concepts
OSPF overview
2.2.1 This page will introduce OSPF. OSPF is a link-state routing protocol that is based on open standards. It is described in several standards of the Internet Engineering Task Force (IETF). The Open in OSPF means that it is open to the public and is non-proprietary.

OSPF, when compared to RIP v1 and v2, is the preferred IGP because it is scalable. RIP is limited to 15 hops, it converges slowly, and it sometimes chooses slow routes because it ignores critical factors such as bandwidth in route determination. A drawback to using OSPF is that it only supports the TCP/IP protocol suite. OSPF has overcome these limitations and is a robust and scalable routing protocol that is suitable for modern networks. OSPF can be used and configured as a single area for small networks. It can also be used for large networks.
As shown in Figure , large OSPF networks use a hierarchical design. Multiple areas connect to a distribution area, or area 0 which is also called the backbone. The design approach allows for extensive control of routing updates. Area definition reduces routing overhead, speeds up convergence, confines network instability to an area, and improves performance.
The next page will provide more information about OSPF.
Certification-level claim: Configure routing protocols given user requirements.
Course-level claim: Describe, configure, verify, analyze, and troubleshoot the OSPF link-state routing protocol in a single area mode of operation.
Hands-on skills: none
This is a core TI.
This is an important overview of OSPF and links back to what the students already know about RIP. Ensure that the figures are discussed, especially Figures, which are animated when students press the white arrow. Remember to stress that OSPF uses areas to implement hierarchical routing as illustrated in Figure .
The following are points to emphasize when contrasting OSPF with RIP:

• OSPF only floods changes to other routers instead of the entire routing table.
• OSPF supports VLSM.
• OSPF overcomes the hop count limit of RIP.
• OSPF is event driven, whereas RIP broadcasts every 30 seconds.
• RIP sometimes picks suboptimal paths, in terms of hops rather than bandwidth.

OSPF isolates changes to areas, while changes to a RIP topology affect every router.