A brief tutorial on Dijkstra's Shortest Path First Algorithm. This algorithm is used by most link state routing protocols, including OSPF and IS-IS.

Shortest Path First Algorithm

A video podcast showing Cisco hands-on training exercises.

Technology

Tech News

Podcasting

Gadgets

Software How-To

The linked video demonstrates RIPng, our first dynamic routing protocol for IPv6. This is a simple but inefficient routing protocol. The metric is based on number of router hops, with no provision for differentiating between links with drastically different bandwidth (a frame-relay hop has the same cost as a 10-gig-ethernet in RIPng). Each router multicasts its entire routing protocol out each interface every 30 seconds, which wastes router CPU. RIPng routinely takes minutes to reroute around network failures.RIPng does have the refinements added in RIPv2. For example, it multicasts its route updates. It is also capable of including tags in the route updates. The big advantage of RIPng is that it is simple to understand. But in production that is not good enough. RIPng is a perfect protocol for a computer science student to implement as a class project due to its simplicity, but having the PBX unreachable for 3-5 minutes while routing reconverges is unacceptable in a business environment.

IPv6 RIPng dynamic routing

In this hands-on exercise, we configure IPv6 addresses on 3 routers in a triangle. Then we configure IPv6 static routes to allow the 6 IPv6 subnets (3 loopback, 3 P2P links) to be accessible on all 3 routers.Static routes are easy to understand. At first glance they appear simple. You just manually configure which next-hop to go to for each subnet destination. But in actual use they are very complex. In our example with 3 routers and 6 subnets, we end up using 12 static route commands to implement our routing. Even then we do not achieve full redundancy, because static routes do not reroute around network failures. Even a small production network with approximately 20 routers would have too many static route commands necessary to make a static-route implementation feasible. In the real world, using dynamic routing protocols to minimize manual configurations (minimizing both effort and errors) is necessary to achieve a robust environment.That said, static routes are sometimes useful at the edge of your network. You redistribute static routes into your routing protocol at the edge of your network where you don't want to dynamically route with routers outside your administrative control. The goal there is just to use the static route to inject a route into your routing protocol. Not to use the static route as your primary routing mechanism.

IPv6 Static Routing

In 2003, I made a VOIP call from home while downloading a large email attachment. The DSL line saturated and my audio quality became horrible while VOIP packets (and email packets) were being dropped. Doubling the bandwidth to my home would not have solved this problem. The email download would simply have been faster, but the VOIP call would still have suffered packet loss.The solution to this problem is 'quality of service' (QOS). Some applications, particularly realtime interactive applications, are sensitive to packet loss. Other applications, particularly bulk data traffic (including email, ftp, backups, software update downloads) are not time sensitive and can have their traffic delayed in favor of the realtime traffic. QOS is the network function where certain applications and traffic are prioritized over others that are deemed less urgent.The creators of the Internet Protocol version 4 understood that quality of service was a requirement. They included the 'type of service' field in the IPv4 header when it was specified in 1981. When developing IPv6, they cleaned up unnecessary header fields, but still they kept the 'class of service' field in the base IPv6 header. Every Internet Protocol packet sent on the Internet since 1983 (when IPv4 went live) included this service field in the header to enable QOS functionality.In September 2009, Julius Genachowski, chairman of the FCC commissioners, proposed two new 'network neutrality' principles. Among them was the "principle of nondiscrimination." This proposed principle states 'broadband providers cannot discriminate against particular Internet content or applications.' While there is a valid concern that ISP's may choose to impede applications or content from competitors, the current proposal as stated seems to restrict ISP's from using QOS to prioritize traffic for realtime applications, and deprioritize traffic for bulk data applications.Due to the apparent attempt to ignore a fundamental building block of the Internet, I oppose the proposed 'principle of nondiscrimination' as written. ISP's need to prioritize realtime applications, while deprioritizing non-realtime bulk-data-transfer applications. In addition, ISP's need the freedom to block applications which do not 'play nicely' in a bandwidth constrained environment. Network engineers know that sometimes particular applications need to be blocked to allow the majority of the network (and the majority of customers) to enjoy adequate performance.

The need for QOS versus Net Neutrality

The linked video introduces IPv6 theory. IPv6 is the 128-bit address replacement for IPv4. The Internet is expected to run out of it's 4-billion IPv4 addresses in 2012. IPv6 will replace IPv4 at the network-layer of the OSI stack. By replacing one layer in the stack, most applications and most layer-2 network devices will continue to function. IPv6 includes several technical improvements over IPv4. IPv6 uses optional extension headers, so only packets requiring special options will have those headers. As a result most IPv6 packets will have simpler headers than their IPv4 counterparts. IPv6 eliminates broadcast, and instead uses multicast for most neighbor discovery functions. This is more efficient CPU-wise because hosts only need to subscribe to the multicast groups they require. IPv6 hosts use stateless autoconfiguration to acquire link-local and internet routable IPv6 addresses. In many cases this can eliminate the need for a separate DHCP server. And of course IPv6 includes 128-bit addresses, allowing 256 billion billion billion billion hosts. The migration from IPv4 to IPv6 will be the highlight and most significant change of our networking careers. Most of us were not in this business during the IPv3 to IPv4 migration on January 1st 1983 (a 'flag day' migration). Odds are IPv6 will remain the dominant internet protocol until after we retire. A PDF version of my presentation will be attached to the comments section.

IPv6 theory

The linked video provides guidance for optimal IOS version selection.The large number of IOS versions makes choosing the best version for your router or switch difficult. You must pick the most reliable version which includes the features you need. Different IOS "packages" have different features. For example, the "LAN base" package includes basic switching code. "IP base" adds access-layer routing features (RIP and EIGRP-stub). "IP services" adds most layer-3 routing protocols (OSPF, EIGRP, BGP). "Advanced IP services" adds IS-IS and MPLS.Picking a version also means picking one with recently introduced features you need. For example, 16-port 10-gigabit ethernet card support was added to the 6500 line in 12.2(33)SXH code. If you require that card, you cannot pick an older version, such as 12.2(18)SXF. The release notes include details on recently added features.Finally, of all the versions that have the features you require, you want to pick the most stable version. That means picking a version that has been "rebuilt" with many bugfix-only releases. Picking 12.4(2)T, where 60 new features were just introduced, would be a bad idea. On the other hand, 12.4(23) (the lack of a letter means it is a mainline release) would be a good choice because that release has undergone dozens of releases since significant numbers of features were introduced.

Shortest Path First Algorithm

Download our free app to listen on your phone