# US 6,724,722 B1 · Managing congestion and potential traffic growth in an information network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 6,724,722 B1 - Document ID: US6724722B1 - Status: Granted - Kind: B1 - Application number: 09/520,247 - Filed: 2000-03-07 - Granted: 2004-04-20 - Earliest claimed: 1999-03-19 - Assignees: Lucent Technologies Inc. - Inventors: Yufei Wang; Zheng Wang; Leah Zhang - Web page: https://patentgrep.com/patent/US6724722B1 ## CPC - H04L 47/125: by balancing the load, e.g. traffic engineering - F02D 33/003: {Controlling the feeding of liquid fuel from storage containers to carburettors or fuel-injection apparatus (control of electrical fuel pumps F02D41/3082, controlling fuel flow to a common rail F02D41/3845); Failure or leakage prevention; Diagnosis or detection of failure; Arrangement of sensors in the fuel system; Electric wiring; Electrostatic discharge} - H04L 47/10: Flow control; Congestion control - H04L 47/11: Identifying congestion - H04L 47/15: {in relation to multipoint traffic (arrangements for broadcast or multicast in data networks H04L12/18)} - H04L 47/70: Admission control; Resource allocation - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - F02D: CONTROLLING COMBUSTION ENGINES (vehicle fittings, acting on a single sub-unit only, for automatically controlling vehicle speed B60K31/00; conjoint control of vehicle sub-units of different type or different function, road vehicle drive control systems for purposes other than the control of a single sub-unit B60W) ## Abstract Traffic demands are routed across links of an information network so as to avoid congestion and allow for future traffic growth. Traffic demands from a source node to a destination node of the network are monitored, including bandwidths associated with each of the demands. For each demand, and for a given link of the network, that portion of the bandwidth associated with each traffic demand which is provided by the given link, is determined. A maximum value of link utilization among all links of the network is then determined, wherein link utilization is defined as the amount of bandwidth used by all traffic demands routed through a given link with respect to a total capacity of the link. Traffic demands are then routed across the links of the network in such a manner as to minimize the maximum value of link utilization. ## Claims ### Claim 1 A method of managing traffic flow across links of an information network, comprising: monitoring traffic demands from a source node of an information network to a destination node of the network, including bandwidths associated with each of the traffic demands; determining for each traffic demand and for a given link of the network, that portion of the bandwidth associated with each traffic demand which portion is provided by the given link; determining a maximum value of link utilization among all links of the network, where link utilization is defined as the amount of bandwidth used by all traffic demands routed trough a given link with respect to a total capacity of the link; calculating a cost metric for each link of the network based on information comprising the traffic demand and maximum value of link utilization; selecting a path that minimizes the maximum value of link utilization based on each cost metric; and routing the traffic demands across the path. ### Claim 2 (depends on 1) The method of claim 1, further comprising routing traffic demands over more than one path in the network. ### Claim 3 (depends on 1) The method of claim 1, further comprising routing each traffic demand over a single path in the network. ### Claim 4 A method of managing traffic flow across links of an information network comprising: receiving a demand to route network traffic; determining a demand size of the demand; determining a routing procedure associated with the demand; calculating a cost metric for each of a plurality of links of a network; the cost metric for each link being associated with information comprising the routing procedure and a link utilization, the link utilization being a ratio of link capacities; and selecting a path to route network traffic based on the calculated cost metric for each of the plurality of links. ### Claim 5 (depends on 4) The method of claim 4 wherein, the network traffic is routed over a multi-protocol label switching network. ### Claim 6 (depends on 4) The method of claim 4 wherein, the routing procedure is a shortest path routing procedure and the cost metric is determined by a ratio of the used link capacity and the demand size to the total link capacity. ### Claim 7 (depends on 4) The method of claim 4 wherein, the routing procedure is a shortest-widest path routing procedure and the cost metric is associated with a percentage of link idle capacity. ### Claim 8 (depends on 7) The method of claim 7 wherein, if there are multiple candidate paths, the path with minimum hops or the shortest distance is chosen. ### Claim 9 (depends on 4) The method of claim 4 wherein, the routing procedure is a Min-Max link utilization routing procedure and the cost metric is associated with a maximum link utilization of the link, the demand size, and link utilization of the plurality of links. ### Claim 10 (depends on 9) The method of claim 9 wherein, the cost metric is adjusted by a small scalar value and the demand size where a cost metric for a link is the same as a cost metric for another link. ### Claim 11 (depends on 4) The method of claim 4 wherein, the routing procedure is a hybrid routing procedure and the cost metric is associated with the link utilization, the demand size, a maximum link utilization for the link, a number of hops of a minimum hop path for the demand, and the link utilization of the plurality of links. ### Claim 12 (depends on 11) The method of claim 11 wherein, the selected path to route network traffic is the shortest path. ### Claim 13 (depends on 4) The method of claim 4 wherein, selecting the path to route network traffic is based on a weight associated with the calculated cost metric for each of the plurality of links; each weight being manipulated in a open shortest path first network. ### Claim 14 A computer readable medium including computing instructions for managing traffic flow across links of an information network, the instructions comprising: monitoring traffic demands from a source node of an information network to a destination node of the network, including bandwidths associated with each of the traffic demands; determining for each traffic demand and for a given link of the network, that portion of the bandwidth associated with each traffic demand which portion is provided by the given link; determining a maximum value of link utilization among all links of the network, where link utilization is defined as the amount of bandwidth used by all traffic demands routed trough a given link with respect to a total capacity of the link; calculating a cost metric for each link of the network based on information comprising the traffic demand and maximum value of link utilization; selecting a path that minimizes the maximum value of link utilization based on each cost metric; and routing the traffic demands across the path. ### Claim 15 (depends on 14) The computer readable medium of claim 14, including instructions further comprising routing traffic demands over more than one path in the network. ### Claim 16 (depends on 14) The computer readable medium of claim 14, including instructions further comprising routing each traffic demand over a single path in the network. ### Claim 17 A computer readable medium including computing instructions for managing traffic flow across links of an information network, the instructions comprising: receiving a demand to route network traffic; determining a demand size of the demand; determining a routing procedure associated with the demand; calculating a cost metric for each of a plurality of links of a network; the cost metric for each link being associated with information comprising the routing procedure and a link utilization, the link utilization being a ratio of link capacities; and selecting a path to route network traffic based on the calculated cost metric for each of the plurality of links. ### Claim 18 (depends on 17) The computer readable medium of claim 17 wherein, the network traffic is routed over a multi-protocol label switching network. ### Claim 19 (depends on 17) The computer readable medium of claim 17 wherein, the routing procedure is a shortest path routing procedure and the cost metric is determined by a ratio of the used link capacity and the demand size to the total link capacity. ### Claim 20 (depends on 17) The computer readable medium of claim 17 wherein, the routing procedure is a shortest-widest path routing procedure and the cost metric is associated with a percentage of link idle capacity. ### Claim 21 (depends on 17) The computer readable medium of claim 17 wherein, if there are multiple candidate paths, the path with minimum hops or the shortest distance is chosen. ### Claim 22 (depends on 17) The computer readable medium of claim 17 wherein, the routing procedure is a Min-Max link utilization routing procedure and the cost metric is associated with a maximum link utilization of the link, the demand size, and link utilization of the plurality of links. ### Claim 23 (depends on 22) The computer readable medium of claim 22 wherein, the cost metric is adjusted by a small scalar value and the demand size where a cost metric for a link is the same as a cost metric for another link. ### Claim 24 (depends on 17) The computer readable medium of claim 17 wherein, the routing procedure is a hybrid routing procedure and the cost metric is associated with the link utilization, the demand size, a maximum link utilization for the link, a number of hops of a minimum hop path for the demand, and the link utilization of the plurality of links. ### Claim 25 (depends on 24) The computer readable medium of claim 24 wherein, the selected path to route network traffic is the shortest path. ### Claim 26 (depends on 17) The computer readable medium of claim 17 wherein, the selecting of the path to route network traffic is based on a weight associated with the calculated cost metric for each of the plurality of links; each weight being manipulated in a open shortest path first network.