Adaptive routing system and method for QOS packet networks

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).

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).

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).

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.

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).

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.