Introduction

Shortest path algorithms are applicable to IP networks and widest path algorithms are useful for telephone network dynamic call routing and Quality-of-Service (QOS) based routing. If you are primarily interested in learning about routing in IP networks, you may read material on shortest path routing algorithms, and then come back to read about widest path algorithms later. If you are interested in understanding routing in a voice over IP (VoIP) environment or a Multiprotocol Label Switching (MPLS) network, researching widest path routing is also recommended.

This lesson, describes two classes of routing algorithms: shortest path routing and widest path routing. They appear in network routing in many ways and have played critical roles in the development of routing protocols. The primary focus of this lesson is to describe how they work, without discussing how they are used by a specific communication network, or in the context of routing protocols.

This lesson, presents the discussion using origin and destination nodes. When a network structure is somewhat complicated, that is, when we have a backbone network that is the carrier of traffic between access networks, we also use the term ingress node to refer to a entry point in the core network and the term egress node to refer to an exit point in the core network. It is important to keep this in mind.

Finally, it is worth noting that the Bellman–Ford algorithm can operate with negative link cost while Dijkstra's algorithm requires the link costs to be nonnegative; on the other hand, Dijkstra's algorithm can be modified to work with negative link cost as well.

Introduction

Communication network routing protocols such as Open Shortest Path First (OSPF) and Intermediate Systemto- Intermediate System (IS-IS) (refer to Chapter 7) that are based on the link state protocol concept do not allow negative weights. Thus, for all practical purposes, negative link cost rarely plays a role in communication networking protocols. Thus, in this book, we primarily consider the case when link costs are nonnegative.

Certainly, from a graph theory point of view, it is important to know whether a particular algorithm works with negative link cost. Network design experts have developed the hierarchical network design model to help you develop a topology in discrete layers. Each layer can be focused on specific functions, allowing you to choose the right systems and features for the layer.

For example, high-speed WAN routers can carry traffic across the enterprise WAN backbone, medium-speed routers can connect buildings at each campus, and switches can connect user devices and servers within buildings. A typical hierarchical topology is:

	A core layer of high-end routers and switches that are optimized for availability and performance.
	A distribution layer of routers and switches that implement policies.
	An access layer that connects users via lower-end switches and wireless access points.

Introduction

The Classic Three-Layer Hierarchical Model

	The three-layer model permits traffic aggregation and filtering at three successive routing or switching levels.
	This makes the three-layer hierarchical model scalable to large international internet works.
	Although the model was developed at a time when routers delineated layers, the model can be used for switched networks as well as routed networks.
	Each layer of the hierarchical model has a specific role.
	The core layer provides optimal transport between sites
	The distribution layer connects network services to the access layer, and implements policies regarding security, traffic loading, and routing.
	In a WAN design, the access layer consists of the routers at the edge of the campus networks.
	In a campus network, the access layer provides switches or hubs for end-user access.

Introduction

Figure 2.1: The Classical Three-Layer Hierarchical Model

Introduction

Guidelines include:

	Controlling the network diameter provides low and predictable latency.
	It also helps you predict routing paths, traffic flows, and capacity requirements.
	A controlled network diameter also makes troubleshooting and network documentation easier.
	Finally, one other guideline for hierarchical network design is that one should design the access layer first, followed by the distribution layer, and then finally the core layer.
	By starting with the access layer, one can more accurately perform capacity planning for the distribution and core layers.