Abstract
Traditionally, Internet routing is achieved through shortest path protocols that base their decision on the number of hops or administrative metrics. The path computation algorithms belong either to the distance vector or link state families. Distance vector protocols have been widely used on the Internet since the ARPANET and remain in use today. The protocols of the Distance Vector family are used by routers to exchange routing information with their neighbours and to select the shortest paths to all destinations within the network using the Bellman-Ford algorithm, such as in the routing information protocol (RIP) (Malkin, 1998).
Key Terms in this Chapter
Feasible Paths: The paths that satisfy these constraints are called feasible paths.
Additive Metric: A metric whose value over a path is the sum of the values at each hop.
NP-Complete: This definition means that there is not an algorithm that is able to find a feasible solution that satisfies both constraints in polynomial time.
Quality of Service Routing: The selection, based on information about the state of the network, of the path that can satisfy traffic requirements while maximizing the utilization of network resources
Concave metric: A metric whose value over a path is the minimum value observed in all hops of that path.
Multiplicative Metric: A metric whose value over a path is the product of the values at each hop.
Multi-Constrained Path Problem: The selection of QoS paths subject to multiple constraints.
Restricted Shortest Path: A simplification of the original MCP problem, when two additive metrics are used.