Internet protocol (IP) class-of-service routing technique

• US 6,590,867 B1
• Filed: 05/27/1999
• Issued: 07/08/2003
• Est. Priority Date: 05/27/1999
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Fishman, Saul Daniel, Chen, Jiayu, Maunder, Anurag S., Ash, Gerald Richard
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Pezzlo, John
• Application Number:
  US09/321,027
• Time in Patent Office: 1,503 Days
• Field of Search: 370/395.2, 370/395.5, 370/395.51, 370/328, 370/351, 370/236, 370/230, 370/410, 370/401, 370/238.1, 370/233, 370/396, 370/386, 370/238, 370/239, 370/353, 370/342, 370/352, 370/400, 370/355, 370/469, 370/389, 370/348, 370/229, 370/254-258, 709/227, 709/241, 709/236, 709/242, 709/247, 709/240, 709/238, 709/228, 705/30, 707/4
• US Class Current: 370/236
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

The priority of the flow of packets representing calls or other connection requests within a packet network (10) is determined from the Class-of-Service of the call. Upon receipt of a call, a recipient router (12₁, 12₂, 12₃) identifies available paths, typically by exchanging messages with the other routers in the network. After selecting the path, the recipient router or centralized bandwidth broker determines whether the links comprising the selected path have available bandwidth for the class of service of the call. If so, the router routes the call to the next hop along the path. Otherwise, the router selects another path(s) and checks whether the links on the path possess sufficient bandwidth for the class of service of the call.

Claims

1. A method for routing a connection between an origin and destination in an Internet Protocol (IP) network comprised of a plurality of routers connected by links that carry packets between the routers, comprising the steps of:

(a) exchanging status messages within the network to identify a group of available paths each running between the origin and destination, each path including at least one link;

(b) selecting among the group of available paths a first path for routing the connection;

(c) determining a class of service for the connection;

(d) checking the selected path to determine whether each link forming the selected path has an available bandwidth for the class of service of the connection, and if so, routing the data packets representative of the call over said outgoing link;

otherwise;

(e) selecting another path; and

(f) repeating step (d) and repeating step (e) in the event said another path has a link lacking available bandwidth,

wherein the step of checking whether the link has an available bandwidth includes the steps of;

measuring actual bandwidth on said link;

determining link blocking in accordance with the actual bandwidth;

establishing reservation thresholds in accordance with the link blocking;

determining the load state of the links in a path in accordance with the bandwidth reservation thresholds; and

establishing the availability of the path in accordance with the class of service of the connection request, the load state of the links in the path, and a required bandwidth for each virtual network associated with the class of service for the connection.

2. The method according to claim 1, wherein the required bandwidth for the class of service is established periodically.

3. A method for routing a connection between an origin and destination in an Internet Protocol (IP) network comprised of a plurality of routers connected by links that carry packets between the routers, comprising the steps of:

(a) exchanging status messages within the network to identify a group of available paths each running between the origin and destination, each path including at least one link, wherein each link may have one of reserved, lightly loaded, or heavily loaded load states;

(b) selecting among the group of available paths a first path for routing the connection;

(c) determining a class of service for the connection, wherein the classes of service include key service, normal service and best effort service;

(d) checking the selected path to determine whether each link forming the selected path has an available bandwidth for the class of service of the connection, and if so, routing the data packets representative of the call over said outgoing link;

otherwise;

(e) selecting another path; and

(f) repeating step (d) and repeating step (e) in the event said another path has a link lacking available bandwidth,

wherein for key service, all load states are allowed if actual bandwidth in progress (BWIP_v)≦

2×

Bwmax_v, where

BWavg_vk, the Bandwidth required for each Virtual Network_v (VN_v) and node-pair k to carry the average Bandwidth-In-Progress (BWIP_vk) [=Erland Load_vk×

(Avg bandwidth per virtual connection)_vk] and

BWmax_vk, the Bandwidth required to meet a blocking probability Grade-of-Service objective=[TREBS (Erlang Load_vk, Grade-of-Service)×

(Avg bandwidth per virtual connection)_vk].

4. The method according to claim 3, wherein for key service, only lightly loaded links are allowed if BWIP_v>

2×

BWmax_v.

5. A method for routing a connection between an origin and destination in an Internet Protocol (IP) network comprised of a plurality of routers connected by links that carry packets between the routers, comprising the steps of:

(a) exchanging status messages within the network to identity a group of available paths each running between the origin and destination, each path including at least one link;

(b) selecting among the group of available paths a first path for routing the connection;

(c) determining a class of service for the connection, wherein the classes of service include key service, normal service and best effort service;

(d) checking the selected path to determine whether each link forming the selected path has an available bandwidth for the class of service of the connection, and if so, routing the data packets representative of the call over said outgoing link;

otherwise;

(e) selecting another path; and

(f) repeating step (d) and repeating step (e) in the event said another path has a link lacking available bandwidth,

wherein for normal service, all load states are allowed on the first choice path and heavily loaded and lightly loaded states are allowed on alternate paths, if actual bandwidth in progress (BWIP_v)≦

BWavg_v, where

BWavg_vk, the Bandwidth required for each Virtual Network_v (VN_v) and node-pair k to carry the average Bandwidth-In-Progress (BWIP_vk) [=Erland Load_vk×

(Avg bandwidth per virtual connection)_vk] and

BWmax_vk, the Bandwidth required to meet a blocking probability Grade-of-Service objective=[TREBS (Erlang Load_vk, Grade-of-Service)×

(Avg bandwidth per virtual connection)_vk].

6. The method according to claim 5, wherein for normal service calls, heavily loaded and lightly loaded states are allowed on the first choice path and only the lightly loaded load state is allowed on alternate paths, if BWavg_vk<

BWIP_v≦

BWmax_vk.

7. The method according to claim 5, wherein for normal service calls, only lightly loaded links are allowed on all paths when BWIP_v>

BWmax_vk.