Constraint based routing

• US 6,829,347 B1
• Filed: 12/14/2001
• Issued: 12/07/2004
• Est. Priority Date: 12/14/2001
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Odiaka, Sam
• Primary Examiner(s): Bui, Bing Q.
• Application Number:
  US10/020,457
• Time in Patent Office: 1,089 Days
• Field of Search: 379/112.05, 379/112.06, 379/114.02, 379/219, 379/220.01, 379/221.01, 379/221.06, 379/221.07
• US Class Current: 379/220.01
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04Q 3/0083 Network planning or design; Modelling of planned or existing networks
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A method of selecting a trail using a Constraint based routing technique in which at least one user-determined routing policy is used to bias input to a Dijkstra/Yen-K shortest path routing engine, so as to limit output by the routine engine to routes conforming with the user-determined routing policy.

Claims

1. A method of selecting a trail route across a communications network using a routing engine, the method comprising the steps of:

selecting a routing policy profile having at least one route biasing parameter;

inputting information from said routing policy profile to said routing engine, in which said information includes information derived from said selected at least one route biasing parameter which biases the computation of trail routes; and

computing a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.

2. A method as claimed in claim 1, wherein the method is used to select trail routes for different classes of traffic within a network, and wherein the routing policy biases the output of the routing engine independently of the manner in which said different classes of traffic are individually routed.

3. A method as claimed in claim 1, wherein the step of selecting a routing policy profile is performed by a user of the communications network.

4. A method as claimed in claim 1, wherein the step of selecting a routing policy profile is performed by a network operator of the communications network.

5. A method as claimed in claim 1, wherein the step of selecting a routing policy profile is performed automatically by a network operator of the communications network.

6. A method as claimed in claim 1, wherein at least one of said parameters is taken from the group consisting of:

a balancing mode criteria;

a threshold level for link usage criteria;

a cumulative path threshold level criteria;

a diverse routing criteria;

an exclusion profile criteria for excluding some network sector/traffic type;

a Quality of Service criteria;

a Class of Service criteria; and

a User Information criteria.

7. A method as claimed in claim 1, wherein the routing engine comprises a Dijkstra algorithm.

8. A method as claimed in claim 1, wherein the trail route selected provides protection for a working path.

9. A method as claimed in claim 1, wherein the trail route selected provides protection for a working path, and wherein the trail route selected re-uses at least one link along the working path having a higher capacity than any other available link.

10. A routing application having a graphically displayed user interface arranged to enable the selection of a trail route across a communications network using a routing engine, the software comprising:

selection means for a network operator of a communications network to select a routing policy profile having a plurality of parameters;

input means to input information from said routing policy profile to said routing engine to bias the computation of trail routes; and

computational means to compute a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.

11. A constraint based routing scheme for a communications network, the scheme comprising a method of selecting a trail route across a communications network using a routing engine, the method comprising the steps of:

selecting a routing policy profile having a plurality of route constraining parameters which are capable of constraining the output of said routing engine;

inputting information from said routing policy profile to said routing engine, wherein said inputted information includes said route constraining parameters to bias the computation of trail routes; and

computing a set of potential trail mutes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy information by the inputted route constraining parameters.

12. Apparatus arranged to implement a method of selecting a trail route across a communications network using a routing engine, the apparatus comprising:

selection means arranged to enable a network operator to select a routing policy profile having a plurality of parameters;

input means arranged to input information from said routing policy profile to said routing engine to bias the computation of trail routes; and

computational means arranged to compute a set of potential trail routes containing at least one potential trail route whose selection has been biased in accordance with said selected routing policy.

13. A route advising application providing routing policy management which can be selectively based on one or more routing policies, the routing policies having route biasing parameters which bias input into a Dijkstra based routing engine to constrain the number of routes output by the Dijkstra based routing engine to a set of at least one route which conforms with said routing policy.

14. A route advising application as claimed in claim 13, wherein the said one or more routing profiles may be based on at least one criteria taken from the group consisting of:

a balancing mode criteria for balancing traffic across the network, a threshold level for link usage criteria, a cumulative path threshold level criteria, a diverse routing criteria, an exclusion profile criteria for excluding some network sector/traffic type, a Quality of Service criteria, a Class of Service criteria, and/or a User Information criteria.

15. A routing scheme for a network comprising:

applying a biasing factor to a network link in a network topology model;

providing input from said biased network topology model to a routing algorithm;

selecting a route from a subset of at least one potential routes generated by said routing algorithm.

16. A routing scheme as claimed in claim 15, wherein said biasing factor is a weight given to said network link to prejudice said routing algorithm from selecting said network link.

17. A routing scheme as claimed in claim 16, wherein more than one network link is biased.