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. 

Compare and contrast distance vector and link-state routing

Compare and contrast distance vector and link-state routing
2.1.6 This page will compare distance vector and link-state routing protocols.

All distance vector protocols learn routes and then send these routes to directly connected neighbors. However, link-state routers advertise the states of their links to all other routers in the area so that each router can build a complete link-state database. These advertisements are called link-state advertisements or LSAs. Unlike distance vector routers, link-state routers can form special relationships with their neighbors and other link-state routers. This is to ensure that the LSA information is properly and efficiently exchanged.

The initial flood of LSAs provides routers with the information that they need to build a link-state database. Routing updates occur only when the network changes. If there are no changes, the routing updates occur after a specific interval. If the network changes, a partial update is sent immediately. The partial update only contains information about links that have changed. Network administrators concerned about WAN link utilization will find these partial and infrequent updates an efficient alternative to distance vector routing protocols, which send out a complete routing table every 30 seconds. When a change occurs, link-state routers are all notified simultaneously by the partial update. Distance vector routers wait for neighbors to note the change, implement the change, and then pass the update to the neighbor routers. 

The benefits of link-state over distance vector protocols include faster convergence and improved bandwidth utilization. Link-state protocols support CIDR and VLSM. This makes them a good choice for complex and scalable networks. In fact, link-state protocols generally outperform distance vector protocols on any size network. Link-state protocols are not implemented on every network because they require more memory and processor power than distance vector protocols and can overwhelm slower equipment. Another reason they are not more widely implemented is the fact that link-state protocols are quite complex. Link-state routing protocols require well-trained administrators to correctly configure and maintain them.

This page concludes this lesson. The next lesson will introduce a link-state routing protocol called OSPF. The first page will provide an overview. 

Advantages and disadvantages of link-state routing

Advantages and disadvantages of link-state routing
2.1.5 This page lists the advantages and disadvantages of link-state routing protocols. The following are advantages of link-state routing protocols: 

• Link-state protocols use cost metrics to choose paths through the network. The cost metric reflects the capacity of the links on those paths.
• Link-state protocols use triggered updates and LSA floods to immediately report changes in the network topology to all routers in the network. This leads to fast convergence times.
• Each router has a complete and synchronized picture of the network. Therefore, it is very difficult for routing loops to occur.
• Routers use the latest information to make the best routing decisions.
• The link-state database sizes can be minimized with careful network design. This leads to smaller Dijkstra calculations and faster convergence.
• Every router, at the very least, maps the topology of its own area of the network. This attribute helps to troubleshoot problems that can occur.
• Link-state protocols support CIDR and VLSM.

The following are some disadvantages of link-state routing protocols: 

• They require more memory and processor power than distance vector protocols. This makes it expensive to use for organizations with small budgets and legacy hardware.
• They require strict hierarchical network design, so that a network can be broken into smaller areas to reduce the size of the topology tables.
• They require an administrator who understands the protocols well.
• They flood the network with LSAs during the initial discovery process. This process can significantly decrease the capability of the network to transport data. It can noticeably degrade the network performance.

The next page will continue the comparison of link-state and distance vector protocols.e

Link-state routing algorithms

Link-state routing algorithms
2.1.4 Link-state routing algorithms maintain a complex database of the network topology by exchanging link-state advertisements (LSAs) with other routers in a network. This page describes the link-state routing algorithm.
Link-state routing algorithms have the following characteristics:

• They are known collectively as SPF protocols.
• They maintain a complex database of the network topology.
• They are based on the Dijkstra algorithm.

Link-state protocols develop and maintain full knowledge of the network routers and how they interconnect. This is achieved through the exchange of LSAs with other routers in the network.
Each router constructs a topological database from the LSAs that it receives. The SPF algorithm is then used to compute the reachability of destinations. This information is used to update the routing table. This process can discover changes in the network topology caused by component failure or network growth.
An LSA exchange is triggered by an event in the network instead of periodic updates. This speeds up the convergence process because there is no need to wait for a series of timers to expire before the routers can converge. If the network shown in Figure uses a link-state routing protocol, there is no concern about connectivity between routers A and D. Based on the protocol that is employed and the metrics that are selected, the routing protocol can discriminate between two paths to the same destination and use the best one. In Figure there are two routing entries in the table for the route from Router A to Router D. In this figure, the routes have equal costs so the link-state routing protocol records both routes. Some link-state protocols provide a way to assess the performance capabilities of the two routes and choose the best one. If the preferred route through Router C experiences operational difficulties such as congestion or component failure, the link-state routing protocol can detect this change and route packets through Router B.
The next page will describe some advantages of link-state protocols.