Traffic engineering technique for routing inter-class traffic in a computer network

Claim 3

The method of claim 1 wherein said link congestion index further includes a mid subinterval between said low subinterval and said high subinterval, said mid subinterval indicating a relatively average level of congestion, and wherein said residual bandwidth adjustment step (c) includes the step of not adjusting the calculated residual bandwidth value for a selected link within said network portion if the related congestion index of said selected link indicates an average congestion level of lower priority traffic.

Claim 4

The method of claim 2 wherein said plurality of different service classes includes a best-effort service class and a guaranteed service class.

Claim 5

The method of claim 2 wherein said dynamic adjusting step (c) includes: adding a negative credit bandwidth value to the residual bandwidth value of said selected link if the congestion index for said selected link indicates a relatively high congestion level of lower priority traffic; and adding a positive credit bandwidth value to the residual bandwidth value of said selected link if the congestion index for said selected link indicates a relatively low congestion level of lower priority traffic.

Claim 6

The method of claim 4 further including the step of adding a credit bandwidth value of zero to the residual bandwidth value of said selected link if the congestion index for said selected link indicates a relatively average congestion level of lower priority traffic.

Claim 7

The method of claim 1 wherein the dynamically adjusted residual bandwidth value for a selected link corresponds to a virtual residual bandwidth value for said selected link.

Claim 8

In an integrated services network which supports a plurality of different service classes, the network including a plurality of nodes interconnected by links, a method for routing traffic associated with a selected class of service, whereby service classes having respective priorities lower than that of said selected service class are referred to as lower priority, and service classes having respective priorities higher than that of said selected service class are referred to as higher priority, said method comprising: (a) calculating, based on said selected class of service, a respective value of available bandwidth for each link within at least a portion of said network, wherein the calculation of available bandwidth for a selected link is based upon congestion of lower priority traffic on said selected link, said calculated value of available bandwidth being referred to as a virtual residual bandwidth value; and (b) routing traffic associated with said selected class of service, utilizing said virtual residual bandwidth values, to a final destination, along at least one path, in a manner so as to discourage use of links having relatively high congestion levels of lower priority traffic, even if the at least one path traverses more links than a number of links traversed by a minimum hop path to the final destination.

Claim 9

In an integrated services network which supports a plurality of different service classes, the network including a plurality of nodes interconnected by links, a method for routing traffic associated with a selected class of service, whereby service classes having respective priorities lower than that of said selected service class are referred to as lower priority, and service classes having respective priorities higher than that of said selected service class are referred to as higher priority, said method comprising: (a) calculating, based on said selected class of service, a respective value of available bandwidth for each link within at least a portion of said network, wherein the calculation of available bandwidth for a selected link is based upon congestion of lower priority traffic on said selected link, said calculated value of available bandwidth being referred to as a virtual residual bandwidth value; and (b) routing traffic associated with said selected class of service, utilizing said virtual residual bandwidth values, to a final destination, along at least one path, in a manner so as to discourage use of links having relatively high congestion levels of lower priority traffic, even if the at least one path traverses more links than a number of links traversed by a minimum hop path to the final destination.

Claim 10

The method of claim 7 further including calculating a respective link congestion index for each link within said network portion, said link congestion index comprising a plurality of different subintervals including a relatively low congestion subinterval, and a relatively high congestion subinterval.

Claim 11

The method of claim 8 , said method further including: discouraging use of links having relatively high congestion levels of lower priority traffic; and encouraging use of links having relatively low congestion levels of lower priority traffic.

Claim 12

The method of claim 9 , wherein said discouraging step includes the step of increasing respective link cost values associated with said links having relatively high congestion levels of lower priority traffic; and wherein said encouraging step includes the step of decreasing respective link cost values associated with said links having relatively high congestion levels of lower priority traffic.

Claim 13

The method of claim 9 wherein said congestion index includes a mid subinterval between said low subinterval and said high subinterval, said mid subinterval indicating a relatively average level of congestion, said method including the step of not adjusting respective link costs values associated with links having relatively average levels of congestion of lower priority traffic.

Claim 14

The method of claim 10 wherein the respective link cost value for a selected link is the virtual residual bandwidth value for said selected link.

Claim 15

The method of claim 10 wherein said plurality of different service classes includes a best-effort service class and a guaranteed service class.

Claim 16

The method of claim 7 wherein said virtual bandwidth calculating step includes: calculating a respective residual bandwidth value and a respective link congestion index for each link within said network portion, said link congestion index comprising a plurality of different subintervals including a relatively low congestion subinterval, and a relatively high congestion subinterval; and utilizing the calculated residual bandwidth value and congestion index for a selected link to determine the virtual residual bandwidth value for said selected link.

Claim 17

The method of claim 14 wherein said virtual bandwidth calculating step includes: calculating a credit bandwidth value for each respective link in said network portion, wherein: the credit bandwidth for a selected link is assigned a value less than zero if the congestion index for said selected link indicates a relatively high congestion level of lower priority traffic; and the credit bandwidth for said selected link is assigned a value greater than zero if the congestion index for said selected link indicates a relatively high congestion level of lower priority traffic; and summing the residual bandwidth value and credit bandwidth value of said selected link to determine the virtual residual bandwidth value of said selected link.

Claim 18

The method of claim 15 wherein said congestion index includes a mid subinterval between said low subinterval and said high subinterval, said mid subinterval indicating a relatively average level of congestion, wherein said virtual bandwidth calculating step further includes the step of assigning a credit bandwidth value of zero to links having a relatively average level of congestion of lower priority traffic.

Claim 19

A computer program product for routing traffic associated with a selected class of service in an integrated services network which supports a plurality of different service classes, whereby service classes having respective priorities lower than that of said selected service class are referred to as lower priority, and service classes having respective priorities higher than that of said selected service class are referred to as higher priority, the network including a plurality of nodes interconnected by links, the computer program product comprising: at least one computer usable medium having computer readable code embodied therein, the computer readable code comprising: computer code for calculating, based on said selected class of service, a value of available bandwidth for each link within at least a portion of said network, wherein the calculation of available bandwidth for a selected link is based upon congestion of lower priority traffic on said selected link, said calculated value of available bandwidth being referred to as a virtual residual bandwidth value; and computer code for routing traffic associated with said selected class of service, utilizing said virtual residual bandwidth values, to a final destination, along at least one path, in a manner so as to discourage use of links having relatively high congestion levels of lower priority traffic, even if the at least one path traverses more links than a number of links traversed by a minimum hop path to the final destination.

Claim 20

A computer program product for routing traffic associated with a selected class of service in an integrated services network which supports a plurality of different service classes, whereby service classes having respective priorities lower than that of said selected service class are referred to as lower priority, and service classes having respective priorities higher than that of said selected service class are referred to as higher priority, the network including a plurality of nodes interconnected by links, the computer program product comprising: at least one computer usable medium having computer readable code embodied therein, the computer readable code comprising: computer code for calculating, based on said selected class of service, a value of available bandwidth for each link within at least a portion of said network, wherein the calculation of available bandwidth for a selected link is based upon congestion of lower priority traffic on said selected link, said calculated value of available bandwidth being referred to as a virtual residual bandwidth value; and computer code for routing traffic associated with said selected class of service, utilizing said virtual residual bandwidth values, to a final destination, along at least one path, in a manner so as to discourage use of links having relatively high congestion levels of lower priority traffic, even if the at least one path traverses more links than a number of links traversed by a minimum hop path to the final destination.

Claim 21

The computer program product of claim 17 further including: computer code for calculating a respective residual bandwidth value and a respective link congestion index for each link within said network portion, said link congestion index comprising a plurality of different subintervals including a relatively low congestion subinterval, and a relatively high congestion subinterval; and computer code for utilizing the calculated residual bandwidth value and congestion index for a selected link to determine the virtual residual bandwidth value for said selected link.

Claim 22

The computer program product of claim 18 further including: computer code for calculating a credit bandwidth value for each respective link in said network portion, wherein: the credit bandwidth for a selected link is assigned a value less than zero if the congestion index for said selected link indicates a relatively high congestion level of lower priority traffic; and the credit bandwidth for said selected link is assigned a value greater than zero if the congestion index for said selected link indicates a relatively high congestion level of lower priority traffic; and computer code for summing the residual bandwidth value and credit bandwidth value of said selected link to determine the virtual residual bandwidth value of said selected link.

Claim 23

The computer program product of claim 19 , wherein said congestion index further includes a mid subinterval between said low subinterval and said high subinterval, said mid subinterval indicating a relatively average level of congestion, said computer program product further including computer code for assigning a credit bandwidth value of zero to links having a relatively average level of congestion of lower priority traffic.

Claim 24

The computer program product of claim 19 wherein the computer readable medium is a data signal embodied in a carrier wave.

Claim 25

A router for routing traffic in an integrated services network which supports a plurality of different service classes, the network including a plurality of nodes interconnected by links, the router comprising: means for selecting a particular service class of traffic for routing analysis, whereby service classes having respective priorities lower than that of said particular service class are referred to as lower priority, and service classes having respective priorities higher than that of said particular service class are referred to as higher priority; means for calculating link congestion of at least a portion of said network, wherein a respective residual bandwidth value and a respective link congestion index is calculated for each link within said network portion, said link congestion index comprising a plurality of different subintervals including a relatively low congestion subinterval, and a relatively high congestion subinterval; means for dynamically adjusting the calculated residual bandwidth value for each respective link within said network portion such that: if the congestion index for a selected link indicates a relatively high congestion level of lower priority traffic, the residual bandwidth value for said selected link is decreased, and if the congestion index for a selected link indicates a relatively low congestion level of lower priority traffic, the residual bandwidth value for said selected link is increased; and means for determining an optimal path for routing traffic associated with said selected class of service using said dynamically adjusted residual bandwidth values.

Claim 26

A router for routing traffic in an integrated services network which supports a plurality of different service classes, the network including a plurality of nodes interconnected by links, the router comprising: means for selecting a particular service class of traffic for routing analysis, whereby service classes having respective priorities lower than that of said particular service class are referred to as lower priority, and service classes having respective priorities higher than that of said particular service class are referred to as higher priority; means for calculating link congestion of at least a portion of said network, wherein a respective residual bandwidth value and a respective link congestion index is calculated for each link within said network portion, said link congestion index comprising a plurality of different subintervals including a relatively low congestion subinterval, and a relatively high congestion subinterval; means for dynamically adjusting the calculated residual bandwidth value for each respective link within said network portion such that: if the congestion index for a selected link indicates a relatively high congestion level of lower priority traffic, the residual bandwidth value for said selected link is decreased, and if the congestion index for a selected link indicates a relatively low congestion level of lower priority traffic, the residual bandwidth value for said selected link is increased; and means for determining an optimal path for routing traffic associated with said selected class of service using said dynamically adjusted residual bandwidth values.

Claim 27

The router of claim 22 wherein said link congestion index further includes a mid subinterval between said low subinterval and said high subinterval, said mid subinterval indicating a relatively average level of congestion, and wherein said residual bandwidth adjustment means includes means for not adjusting the calculated residual bandwidth value for a selected link within said network portion if the related congestion index of said selected link indicates an average congestion level of lower priority traffic.

Claim 28

The router of claim 23 wherein said plurality of different service classes includes a best-effort service class and a guaranteed service class.

Claim 29

The router of claim 23 wherein said dynamic adjusting means includes: means for adding a negative credit bandwidth value to the residual bandwidth value of said selected link if the congestion index for said selected link indicates a relatively high congestion level of lower priority traffic; means for adding a positive credit bandwidth value to the residual bandwidth value of said selected link if the congestion index for said selected link indicates a relatively low congestion level of lower priority traffic; and means for adding a credit bandwidth value of zero to the residual bandwidth value of said selected link if the congestion index for said selected link indicates a relatively average congestion level of lower priority traffic.

Claim 30

The router of claim 23 wherein the dynamically adjusted residual bandwidth value for a selected link corresponds to a virtual residual bandwidth value for said selected link.

Claim 33

A router for routing traffic of a first class in a network, the network comprising a plurality of links, each link having a residual bandwidth value associated therewith corresponding to the first class, the router comprising: a network interface for connecting to the network; a central processing unit; and memory; wherein the router is configured or designed to determine, on selected links, congestion levels of traffic associated with at least one class of priority which is lower than that of said first priority class; and wherein the router is further configured or designed to route traffic associated with said first priority class in a manner so as to favor traversal links having relatively low congestion levels of lower priority traffic over links along a minimum hop path having relatively high congestion levels of lower priority traffic.

Claim 34

A router for routing traffic of a first class in a network, the network comprising a plurality of links, each link having a residual bandwidth value associated therewith corresponding to the first class, the router comprising: a network interface for connecting to the network; a central processing unit; and memory; wherein the router is configured or designed to determine, on selected links, congestion levels of traffic associated with at least one class of priority which is lower than that of said first priority class; and wherein the router is further configured or designed to route traffic associated with said first priority class in a manner so as to favor traversal links having relatively low congestion levels of lower priority traffic over links along a minimum hop path having relatively high congestion levels of lower priority traffic.

Claim 35

The method of claim 27 further comprising routing traffic associated with said first priority class in a manner so as to encourage use of links having relatively low congestion levels of lower priority traffic.

Claim 36

The method of claim 27 further comprising routing traffic associated with said first priority class in a manner so as to discourage preemption of bandwidth on said selected links which is being used by traffic associated with a lower class of priority than said first priority class.

Claim 37

The system of claim 28 wherein the router is further configured or designed to route traffic associated with said first priority class in a manner so as to encourage use of links having relatively low congestion levels of lower priority traffic.

Claim 38

The system of claim 28 wherein the router is further configured or designed to route traffic associated with said first priority class in a manner so as to discourage preemption of bandwidth on said selected links which is being used by traffic associated with a lower class of priority than said first priority class.