Patent ID: 6594268
Filing Date: 2003-07-15
Classification: H04L

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