Adaptive routing system and method for QOS packet networks

• US 6,594,268 B1
• Filed: 03/11/1999
• Issued: 07/15/2003
• Est. Priority Date: 03/11/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Stiliadis, Dimitrios, Ramakrishnan, Kajamalai G., Mitra, Debasis, Lakshman, T. V., Aukia, Petri
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): TSEGAYE, SABA
• Application Number:
  US09/266,622
• Time in Patent Office: 1,587 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/400, 370/401, 370/468, 370/389, 370/411, 370/236
• US Class Current: 370/400
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service

Abstract

A packet network employs routers that determine network routing based on quality of service (QoS) provisioning parameters and network topology information. QoS provisioning parameters are provided to each router from a network management database, and the network topology information is determined from a link state database of the router. The link state database may include network topology information collected by the router in accordance with the open shortest path protocol (OSPF). A network link, router, or other node failure initiates a new path-selection process. First, a temporary set of provisioning entries may be determined with a shortest path first (SPF) routing method. Then, the network packet flows may be classified into packet flows, real-time and non-real-time, and then as packet flows that require reserved bandwidth or that may be multiplexed. A multicommodity flow (MCF) routing method is then employed to determine an optimized set of candidate provisioning entries for the packet flows that may be multiplexed. The MCF routing method determines new routing for the packet flows based on QoS provisioning commitments as parameters. The MCF routing method determines the new routing based on an optimization criterion, such as maximized revenue. Once the new routing is determined, routing of network traffic is enabled by converting the provisioning entries into filter rules, which are then loaded into the packet classifier of the router.

Claims

1. An apparatus for routing packets of a plurality of packet flows in a packet network comprising:

a routing processor adapted to;

1) collect network topology information,

2) collect quality of service (QoS) provisioning information for each one of the plurality of packet flows through one or more routers of the packet network, and

3) determine a network path for each one of the plurality of packet flows using a general routing optimization method based on the QoS provisioning and network topology information, wherein said each one of the plurality of packet flows is further classified as either a real-time flow or a non-real-time flow based on a delay threshold;

a control processor adapted to generate, for a first router, a set of one or more filter rules for the first router based on each network path of one or more packet flows passing through the first router, each filter rule defining a physical path through the first router for corresponding ones of the one or more packet flows passing through the first router;

a packet classifier adapted to apply a selected filter rule to each packet of a corresponding packet flow passing through the first router to cause said each packet to traverse the physical path through the first router in accordance with the selected filter rule, and

wherein the routing processor comprises a QoS routing module adapted to;

1) compute an effective bandwidth of said each one of the plurality of packet flows;

2) classify said each one of the plurality of packet flows as either a multiplexable flow or a non-multiplexable flow based on a comparison of the corresponding effective bandwidth with a bandwidth threshold value;

3) reserve i) a first portion of an available capacity of the first router for each one of the one or more packet flows passing through the first router classified as the non-multiplexable flow and ii) a second portion of the available capacity for said each one of the one or more packet flows classified as the multiplexable flow;

4) determine a set of candidate routes, each candidate route corresponding to said each one of the plurality of packet flows, and at least one candidate route allocated to the second portion of the available capacity;

5) calculate said each network path based on the set of candidate routes; and

6) calculate a nodal delay for said each one of the plurality of packet flows based on the network topology information and its corresponding classification as a real-time flow or a non-real-time flow, and

wherein the QoS routing module determines the set of candidate routes by;

4(i) receiving a present value for network revenue and estimates for offered rates of traffic for each class of the plurality of packet flows, wherein said each class identifies a set of QoS commitments of the QoS provisioning information associated with said each one of the plurality of packet flows assigned to said each class;

4(ii) determining route loss probabilities and network sensitivities for said each class based on the nodal delay and the effective bandwidth of said each one of the plurality of packet flows assigned to said each class, the network topology information, the corresponding present value for network revenue of said each class, and the corresponding estimates for offered rates of traffic of said each class;

4(iii) adjusting the estimates for the offered rates of traffic of said each class;

4(iv) forming a new value for network revenue of said each class;

4(v) comparing the new and present values for network revenue of said each class to determine whether the new value converges; and

4(vi) when the new value of said each class converges, determining the set of candidate routes based on the new value of network revenue and the estimates for the offered rates of traffic of said each class;

otherwise, setting the new value of network revenue of said each class as the present value and then repeating 4(ii) through 4(vi).

2. The invention as recited in claim 1, wherein the general routing optimization method is a multicommodity flow (MCF) routing method and the routing processor comprises:

a first routing module adapted to receive, in accordance with a routing protocol, a portion of the network topology information from each of the one or more routers of the packet network into a link state database of the router; and

a second routing module adapted to receiving the QoS provisioning information from a network management database into the link state database.

3. The invention as recited in claim 2, wherein the routing protocol is at least one of a link-state protocol and a protocol allowing for communication of network topology information between the one or more routers of the packet network.

4. The invention as recited in claim 2, wherein the routing protocol is an open shortest path first (OSPF) protocol.

5. The invention as recited in claim 1, wherein the QoS routing module is further adapted to determine one or more of the set of candidate routes for the each of the plurality of packet flows classified as non-multiplexable flows in accordance with a network routing method;

and to calculate a corresponding network path for each one of the set of candidate routes for each of the packet flows classified as non-multiplexable flows.

6. The invention as recited in claim 5, wherein the predetermined network routing method is a shortest path first (SPF) method.

7. The invention as recited in claim 1, wherein the first router includes a plurality of interface cards, each one of the plurality of interface cards having a corresponding packet classifier and each one of the plurality of interface cards adapted to interface with a corresponding link of the packet network, wherein:

the control processor is adapted to;

1) delete a set of running filter rules, one or more packet flow identifiers, and said each class from the packet classifier of each one of the plurality of interface cards of the first router, wherein each one of the one or more packet flow identifiers identifies corresponding ones of the one or more packet flows passing through the first router;

2) allocate a portion of bandwidth of each one of the plurality of interface cards of the first router to said each class based on said each network path determined by the routing processor; and

3) install said each class, the one or more packet flow identifiers, and one or more of a set of new filter rules in the packet classifier assigned to a corresponding one of the plurality of interface cards, the one or more-packet flow identifiers and said each class being assigned to each corresponding one of the plurality of interface cards based on the said each network path, wherein the one or more of the set of new filter rules corresponds to the one or more packet flow identifiers installed in the corresponding one of the plurality of interface cards.

8. A method of routing packets of a plurality of packet flows through a first router of a packet network comprising the steps of:

a) collecting

     1) network topology information and

     2) quality of service (QoS) provisioning information for each one of the plurality of packet flows through one or more routers of the packet network;

b) determining a network path for said each one of the plurality of packet flows using a general routing optimization method based on the QoS provisioning and network topology information, wherein step b) includes the steps of;

b1) computing an effective bandwidth of said each one of the plurality of packet flows;

b2) classifying said each one of the plurality of packet flows as either a multiplexable flow or a non-multiplexable flow based on a comparison of the corresponding effective bandwidth with a bandwidth threshold value;

b3) reserving i) a first portion of an available capacity of the first router for said each one of the plurality of packet flows classified as the non-multiplexable flow and ii) a second portion of the available capacity for said each one of the plurality of packet flows classified as the multiplexable flow;

b4) determining a set of candidate routes, each candidate route corresponding to one of the plurality of packet flows, and at least one of the set of candidate routes allocated to the second portion of the available capacity;

b5) calculating each network path based on the set of candidate routes of the plurality of packet flows,

b6) classifying said each one of the plurality of packet flows as either a real-time flow or a non-real-time flow based on a delay threshold, and

b7) calculating a nodal delay for said each one of the plurality packet flows based on the network topology and its corresponding classification as a real-time flow or a non-real-time flow;

c) generating a set of one or more filter rules for the first router based on the one or more network paths for the one or more packet flows passing through the router, each filter rule of the set of one or more filter rules defining a physical path for one or more packet flows through the router; and

d) applying a selected filter rule to each packet-of a corresponding packet flow to cause said each packet to traverse the physical path through the first router in accordance with the selected filter rule,

wherein step b4) determines the set of candidate routes by the steps of;

i) receiving a present value for network revenue and estimates for offered rates of traffic for each class of the one or more packet flows, wherein said each class identifies a set of QoS commitments of the QoS provisioning information associated with each one of the plurality of packet flows assigned to said each class;

ii) determining route loss probabilities and network sensitivities of said each class based on the nodal delay and effective bandwidth of said each one of the plurality of packet flows, the network topology information, the present value for network revenue, and the estimates for offered rates of traffic;

iii) adjusting the estimates for the offered rates of traffic of said each class;

iv) forming a new value for network revenue for said each class;

v) comparing the new value and the present value for network revenue of said each class to determine whether the new value converges; and

vi) when the new value converges, determining the set of candidate routes based on the new value of network revenue and the estimates for the offered rates of traffic of said each class;

otherwise, setting the new value of network revenue of said each class as the present value and then repeating steps b4(ii) through b4(vi).

9. The method as recited in claim 8, wherein the general routing optimization method is a multicommodity flow (MCF) method, and step a) includes the steps of:

a1) receiving, in accordance with a network protocol, a portion of the network topology information from each of the one or more routers of the packet network into a database of the router; and

a2) receiving the QoS provisioning information from a network management database.

10. The method as recited in claim 9, wherein, for step a1), the network protocol is at least one of a link-state protocol and a protocol allowing for communication of network topology information between the one or more routers of the packet network.

11. The method as recited in claim 9, wherein, for step a1), the network protocol is the open shortest path first (OSPF) protocol.

12. The method as recited in claim 8, wherein step b) further includes the steps of determining one or more of the set of candidate routes for said each one of the plurality of packet flows classified as non-multiplexable flows in accordance with a network routing method;

and calculating a corresponding network path for each one of the set of candidate routes for said each one of the plurality of packet flows classified as non-multiplexable flows.

13. The method as recited in claim 12, wherein, for step b), the network routing method is a shortest path first (SPF) method.

14. The method as recited in claim 8, wherein step c) includes the steps of:

c1) deleting a set of running filter rules from at least one interface card of the first router;

c2) deleting each packet flow identifier and said each class currently installed in the at least one interface card, wherein said each packet flow identifier identifies one or more of the plurality of packet flows and said each class identifies a set of QoS provisioning commitments of the QoS provisioning information associated with said each packet flow identifier;

c3) allocating a portion of bandwidth of the at least one interface card of the first router to said each class based on said each network path determined in step b);

c4) installing said each class and said each packet flow identifier assigned to the at least one interface card based on said each network path determined in step b); and

c5) installing one or more of the set of new filter rules in said at least one interface card, the one or more of the set of new filter rules corresponding to said each packet flow identifier installed in the interface card.

15. A router of a packet network routing packets of a plurality of packet flows in accordance with an Internet protocol, the router comprising:

a routing processor comprising;

an Open Shortest Path First (OSPF) processing module adapted to receive, in accordance with an OSPF routing protocol, network topology information from one or more routers of the packet network into a link state database of the router,

a link state database adapted to receive QoS provisioning information from a network management database into the link state database, and

a QoS routing module adapted to determine a network path for each one of the plurality of packet flows using a multicommodity flow routing method based on the QoS provisioning information and the network topology information, wherein said each one of the plurality of packet flows is further classified as either a real-time flow or a non-real-time flow based on a delay threshold;

a control processor adapted to generate a set of one or more filter rules for the router based on one or more network paths corresponding to one or more packet flows passing through the router, each filter rule defining a physical path for each one of the one or more packet flows passing through the router;

a packet classifier adapted to apply a selected filter rule to each packet of a corresponding packet flow to cause said each packet to traverse the physical path through the router in accordance with the selected filter rule, and

wherein the routing processor comprises a QoS routing module adapted to;

2) compute an effective bandwidth of said each one of the plurality of packet flows;

2) classify said each-one of the plurality of packet flows as either a multiplexable flow or a non-multiplexable flow based on a comparison of the corresponding effective bandwidth with a bandwidth threshold value;

3) reserve i) a first portion of an available capacity of the router for each one of the one or more packet flows passing through the router classified as a non-multiplexable flow and ii) a second portion of the available capacity for said each one of the one or more packet flows passing through the router classified as a multiplexable flow;

4) determine a set of candidate routes, each one of the set of candidate routes corresponding to one of the plurality of packet flows, and at least one of the set of candidate routes allocated to the second portion of the available capacity;

5) calculate the one or more network paths based on the set of candidate routes; and

6) calculate a nodal delay for said each one of the plurality of packet flows based on the network topology information and its corresponding classification as a real-time flow or a non-real-time flow, and

wherein the QoS routing module determines the set of candidate routes by;

4(i) receiving a present value for network revenue and estimates for offered rates of traffic for each class of the one or more packet flows, wherein said each class identifies a set of QoS commitments of the QoS provisioning information associated with said each one of the plurality of packet flows assigned to said each class;

4(ii) determining route loss probabilities and network sensitivities for said each class based on the nodal delay and the corresponding effective bandwidth of said each one of the packet flows assigned to each said class, the network topology information, the corresponding present value for network revenue of said each class, and the corresponding estimates for offered rates of traffic of said each class;

4(iii) adjusting the estimates for the offered rates of traffic of said each class;

4(iv) forming a new value for network revenue of said each class;

4(v) comparing the new value and the present value for network revenue of said each class to determine whether the new value converges; and

4(vi) when the new value of said each class converges, determining the set of candidate routes based on the new value of network revenue and the estimates for the offered rates of traffic of said each class;

otherwise, setting the new value of network revenue as the present value of said each class and then repeating 4(ii) through 4(vi).

16. An apparatus for routing packets of a plurality of packet flows in a packet network, the apparatus comprising:

a routing processor adapted to;

1) collect network topology information,

2) collect quality of service (QoS) provisioning information for each one of the plurality of packet flows through one or more routers of the packet network, and

3) determine a network path for said each one of the plurality of packet flows using a general routing optimization method based on the QoS provisioning and network topology information;

a control processor adapted to generate, for a first router, a set of one or more filter rules for the first router based on each network path of one or more packet flows passing through the first router, each filter rule defining a physical path through the first router for the one or more packet flows passing through the first router; and

a packet classifier adapted to apply a selected filter rule to each packet of a corresponding packet flow passing through the first router to cause said each packet to traverse the physical path through the first router in accordance with the selected filter rule,

wherein the routing processor comprises a QoS routing module that calculates a nodal delay for said each one of the plurality of packet flows based on the network topology information and its corresponding classification as a real-time flow or a non-real-time flow based on a delay threshold, the QoS routing module further adapted to;

1) compute an effective bandwidth of said each one of the plurality of packet flows;

2) classify said each one of the plurality of packet flows as either a multiplexable flow or a non-multiplexable flow based on a comparison of the corresponding effective bandwidth with a bandwidth threshold value;

3) reserve i) a first portion of an available capacity of the first router for said each one of the plurality of packet flows classified as a non-multiplexable flow and ii) a second portion of the available capacity for said each one of the plurality of packet flows classified as a multiplexable flow;

4) determine a set of candidate routes, each candidate route corresponding to one of the plurality of packet flows, and at least one of the set of candidate routes allocated to the second portion of the available capacity; and

5) calculate each network path based on the set of candidate routes, and

wherein the QoS routing module determines the set of candidate routes by;

i) receiving a present value for network revenue and estimates for offered rates of traffic for each class of the one or more packet flows, wherein said each class identifies a set of QoS commitments of the QoS provisioning information associated with the one or more packet flows assigned to said each class;

ii) determining route loss probabilities and network sensitivities for said each class based on the nodal delay and the corresponding effective bandwidth of each one of the plurality of packet flows assigned to said each class, the network topology information, the corresponding present value for network revenue, and the estimates for offered rates of traffic of said each class;

iii) adjusting the estimates for the offered rates of traffic of said each class;

iv) forming a new value for network revenue of said each class;

v) comparing the new value and the present value for network revenue of said each class to determine whether the new value converges; and

vi) when the new value of said each class converges, determining the set of candidate routes based on the new value of network revenue and the estimates for the offered rates of traffic of said each class;

otherwise, setting the new value of network revenue of said each class as the present value and then repeating 4(ii) through 4(vi).

17. An apparatus for routing packets of a plurality of packet flows in a packet network, the apparatus comprising:

a routing processor adapted to;

1) collect network topology information,

2) collect quality of service (QoS) provisioning information for each one of the plurality of packet flows through one or more routers of the packet network, and

3) determine a network path for said each one of the plurality of packet flows using a general routing optimization method based on the QoS provisioning and network topology information;

a control processor adapted to generate a set of one or more new filter rules for a first router based on each network path of one or more packet flows passing through the first router, each filter rule defining a physical path through the first router for corresponding ones of the one or more packet flows passing through the first router; and

a packet classifier adapted to apply a selected filter rule to each packet of a corresponding packet flow passing through the first router to cause said each packet to traverse the physical path through the first router in accordance with the selected filter rule,

wherein the router includes a plurality of interface cards, each one of the plurality of interface cards having a corresponding packet classifier and each one of the plurality of interface cards adapted to interface with a corresponding link of the packet network, and wherein;

the control processor is adapted to;

1) delete a set of running filter rules, each packet flow identifier, and each class from the packet classifier of each interface card of the router, wherein said each packet flow identifier identifies selected ones of the one or more packet flows and said each class identifies a set of QoS provisioning commitments of the QoS provisioning information associated with said each packet flow identifier;

2) allocate a portion of bandwidth of each one of the plurality of interface cards of the first router to said each class based on said each network path determined by the routing processor; and

3) install said each class, said each packet flow identifier, and one or more of a set of new filter rules in each packet classifier and assigned to each corresponding one of the plurality of interface cards, said each packet flow identifier and said each class being assigned to said each corresponding one of the plurality of interface cards based on said each network path determined by the routing processor, wherein the one or more of the set of new filter rules corresponds to said each packet flow identifier installed in the corresponding one of the plurality of interface cards.

18. A method of routing packets of a plurality of packet flows through a first router of a packet network comprising the steps of:

a) collecting

     1) network topology information and

     2) quality of service (QoS) provisioning information for each packet flow through one or more routers of the packet network;

b) determining a network path for said each packet flow using a general routing optimization method based on the QoS provisioning and network topology information;

c) generating a set of one or more filter rules for the router based on one or more network paths for one or more packet flows passing through the router, each filter rule defining a physical path for one or more packet flows through the first router; and

d) applying a selected filter rule to each packet of a corresponding packet flow to cause said each packet to traverse the physical path through the first router in accordance with the selected filter rule, and

wherein step b) includes the steps of;

b1) calculating a nodal delay for said each packet flow based on the network topology and a corresponding classification of said each packet flow as either a real-time flow or a non-real-time flow based on a delay threshold;

b2) computing an effective bandwidth of said each packet flow;

b3) classifying said each packet flow as either a multiplexable flow or a non-multiplexable flow based on a comparison of the corresponding effective bandwidth of said each packet-flow with a bandwidth threshold value;

b4) reserving i) a first portion of an available capacity of the first router for each one of the one or more packet flows passing through the first router classified as the non-multiplexable flow and ii) a second portion of the available capacity of the first router for each one of the one or more packet flows passing through the first router classified as the multiplexable flow;

b5) determining a set of candidate routes, each one of the set of candidate routes corresponding to one of the plurality of packet flows, and at least one of the set of candidate routes allocated to the second portion of the available capacity; and

b6) calculating the network path for said each packet flow based on the set of candidate routes, and

wherein step b5) determines the set of candidate routes by the steps of;

i) receiving a present value for network revenue and estimates for offered rates of traffic for selected ones of the plurality of packet flows assigned to each class, said each class identifying a set of QoS commitments of the QoS provisioning information associated with the selected ones of the plurality of packet flows assigned to said each class;

ii) determining route loss probabilities and network sensitivities of said each class based on the nodal delay and the corresponding effective bandwidth of the selected ones of the plurality of packet flows, the network topology information, the present value for network revenue, and the estimates for offered rates of traffic of said each class;

iii) adjusting the estimates for the offered rates of traffic of said each class;

iv) forming a new value for network revenue of said each class;

v) comparing the new value and the present value for network revenue for said each class to determine whether the new value converges; and

vi) when the new value converges, determining the set of candidate routes based on the new value of network revenue and the adjusted estimates for the offered rates of traffic of said each class;

otherwise, setting the new value of network revenue as the present value of said each class and then repeating steps b5(ii) through b5(vi).

19. A method of routing packets of a plurality of packet flows through a first router of a packet network comprising the steps of:

a) collecting

     1) network topology information and

     2) quality of service (QoS) provisioning information for each packet flow through one or more routers of the packet network;

b) determining a network path for said each packet flow using a general routing optimization method based on the QoS provisioning and network topology information;

c) generating a set of one or more new filter rules for the first router based on each network path for one or more packet flows passing through the first router, each filter rule defining a physical path through the first router for corresponding ones of the one or more packet flows passing through the first router;

wherein step c) comprises the steps of

c1) deleting a set of running filter rules from each interface card of the first router,

c2) deleting each packet flow identifier and each class currently installed in said each interface card, wherein said each packet flow identifier identifies selected ones of the one or more packet flows passing through the first router and said each class identifies a set of QoS provisioning commitments of the QoS provisioning information associated with said each packet flow identifier,

c3) allocating a portion of bandwidth of said each interface card of the first router to said each class based on said each network path,

c4) installing said each class and said each packet flow identifier assigned to said each interface card, said each packet flow identifier and said each class being assigned to said each interface card based on said each network path, and

c5) installing one or more of the set of new filter rules in said each interface card, the one or more of the set of new filter rules corresponding to said each packet flow identifier installed in said each interface card; and

d) applying a selected filter rule to each packet of a corresponding packet flow passing through the first router to cause said each packet to traverse the physical path through the first router corresponding to the selected filter rule.