Constraint-based route selection using biased cost

Details Constraint-based route selection using biased cost Constraint-based route selection using biased cost

1999-08-31

2002-03-26

Cuchlinski, Jr., William A. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Determination of travel data based on the start point and...

C370S238000, C370S351000, C709S241000

Reexamination Certificate

active

06363319

ABSTRACT:

BACKGROUND
1. Field of the Invention
This invention relates to computer networks. In particular, the invention relates to route selection.
2. Description of Related Art
One common approach in route selection with bandwidth requirement is to modify the well-known Dijkstra technique so that only links that meet the bandwidth requirement are considered in the Dijkstra procedure. The result is a minimum-cost route over links that can meet the bandwidth requirement.
For example, in a packet forwarding known as Multiprotocol Label Switching (MPLS), to accommodate label switched paths (LSPs) of different priorities, the routing selector may first apply the modified Dijkstra technique based on a given LSP's bandwidth demand. If a feasible path is not found, the route selector may preempt an existing LSP of lower priority from a congested link in order to re-allocate the bandwidth to the new LSP. A pre-empted LSP will have to be re-established on an alternative route.
This approach has a number of shortcomings. First, it is difficult to make an intelligent decision of which LSP to preempt. The traditional technique is to consider all candidate LSPs on all possible links, evaluate the impact of preempting, and select the LSP that has the minimum cost impact. This is computational expensive and is not practically feasible for large networks. Second, if the preempting is made randomly, a preempted LSP may fail to be re-routed, resulting in loss of connection. Third, the approach disrupts the LSP's traffic and degrades service quality due to effort in pre-empting and re-routing. Last, the approach may lead to traffic congestion because some high priority LSPs may be placed on very long routes.
Therefore there is a need in the technology to provide a simple and efficient method to select routes in a system of networks.
SUMMARY
The present invention is a method and apparatus for selecting a route for a flow from a plurality of network paths. Cumulative costs for a plurality of candidate paths from the network paths are determined using a cost bias which is dynamically calculated based on at least one of a flow attribute and a path attribute. An optimal path is then selected which has a minimum of the cumulative costs. The optimal path corresponds to the selected route.
According to one embodiment of the present invention, the flow attribute includes a flow priority and a bandwidth demand, and the path attribute includes a link bandwidth and a maximum available link bandwidth. The cumulative cost for a candidate node in a candidate path includes a current cumulative cost and a biased static cost. The biased static cost includes a static cost of the link biased by a bias value. The bias value is a function of the flow priority, the bandwidth demand, the link bandwidth, and the maximum available link bandwidth.
The advantages of the present invention include increased traffic efficiency by taking into account bandwidth and traffic requirements in route selection.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.


REFERENCES:
patent: 5870564 (1999-02-01), Jensen et al.
patent: 6016306 (2000-01-01), Le Boudec et al.
Bruce Davis, Yakov Rekhter, Eric Rosen, Arun Viswanathan, Vijay Srinivasan, Steven Blake, Use of Label Switching With RSVP, Mar. 1998, Ten (10) pages, Network Working Group.
Bilel Jamoussi, Constraint-Based LSP Setup using LDP, Feb. 1999, Twenty-nine (29) pages, MPLS Working Group.
Eric C. Rosen, Arun Viswanathan, Ross Callon, Multiprotocol Label Switching Architecture, Apr. 1999, Forty-three (43) pages, Network Working Group.
Davie, Lawrence, McCloghrie, Rekhter, Rosen, Swallow, Doolan, MPLS using LDP and ATM vc Switching, Apr. 1999, Thriteen (13) pages, Network Working Group.
Ooms, Livens, Sales, Ramalho, Acharya, Griffoul, Ansari, Framework for IP Multicast in MPLS, Jun. 1999, Twenty-three (23) pages, MPLS Working Group.
Callon, Feldman, Fredette, Swallow, Viswanathan, A Framework for Multiprotocol Label Switching, Jun. 1999, Fifty-six (56) pages, Network Working Group.
Awduche, Malcolm, Agogbua, O'Dell, McManus, Requirements for Traffic Engineering Over MPLS, Jun. 1999, Internet Engineering Task Force.
Andersson, Doolan, Feldman, Fredette, Thomas, LDP Specification, Jun. 1999, Eighty-four (84) pages, Network Working Group.

Affiliated with

Also associated with

Rating

Constraint-based route selection using biased cost does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Constraint-based route selection using biased cost, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint-based route selection using biased cost will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2871033