Efficient precomputation of quality-of-service routes

摘要

The present invention provides a method and system for computing and storing minimum-cost routes to all destination nodes in a network. According to one embodiment, the present invention is applied in the context of computing quality of service routes using a source-directed connection-oriented routing environment. The route computation scheme employs an extension to Dijkstra's algorithm coupled with discretized link costs to generate a shortest-path graph with one or more routes to each destination. The present invention provides a compact data structure for storing at least one minimum-cost route to each destination node in a network. In particular, the routes are stored using a directed acyclic graph representing at least one minimum-cost pre-computed route for each destination node in the network. Each destination node in the network is associated with one or more parent pointers pointing to an upstream node in network that lies along a minimum-cost route. Routes are retained in the data structure and not extracted until connection arrival.Upon connection arrival, a route is extracted from the data structure by performing a depth-first search of the acyclic graph, which returns the first route in the common case. As part of the route extraction process, the feasibility of each link in the route is determined based upon a recent link-state. Links that are infeasible are excluded from the extracted route. In addition, according to one embodiment, promising routes are re-ranked in the data structure to provide computational benefits for future route extractions.