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   1   , 12   2   , 12   3 ) 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.

Description:
TECHNICAL FIELD 
     This invention relates to technique for routing calls and other types of connection requests in an IP network. 
     BACKGROUND ART 
     Traditional telecommunications networks typically use dedicated circuits to carry telephone traffic between facilities. Within such traditional networks, switching systems, such as the 4ESS switching systems used by AT&amp;T, route calls by setting up a circuit that lasts the entire duration of the call and then tearing down the circuit thereafter. For this reason, such traditional networks are commonly referred to as “circuit-switched” networks. 
     Increases in traffic and capacity constraints on existing switches within such circuit-switched networks has prompted the development of packet-based networks, and in particular, Internet-Protocol (IP) networks. A typical IP network employs a plurality of routers, such as those manufactured by Cisco, Ascend Communications, Bay Networks and Newbridge, among others, to route data packets representing a call or other connection independently from an origin to a destination based on a destination address in each packet. Present day IP networks of the type described above are characterized by best effort routing. In other words, routing, and particularly, path selection occurs generally without regard to criterion such as class of service. Today, examples of the most prevalent routing techniques in IP networks are the Open Shortest Path First (OSPF) protocol and Border Gateway Protocol (BGP). In the OSPF protocol, for example, routers within the network exchange information with each other by a flooding technique so that each maintains a database of the network topology. Using the information in its stored database, each router selects a path for each packet in accordance with user-established cost metrics that typically require the shortest possible path. Using such cost metrics, each router establishes its routing table accordingly so each router can select a path having, for example, a minimum number of links. 
     Traditionally, providers of telecommunications services have offered different grades or classes of service based on customer demand. To meet quality objectives for such different grades of service, telecommunications providers, such as AT&amp;T, have employed Class-of-Service routing techniques in traditional circuit switched networks. U.S. Pat. No. 5,392,344, issued in the name of Gerald R. Ash et al., on Feb. 21, 1995, and assigned to AT&amp;T (incorporated by reference herein) describes and claims such a Class-of-Service routing technique. Unfortunately, Class-of-Service routing does not exist with present day IP telecommunications networks. Thus, there is a need for an Internet Protocol (IP) Class-Of-Service routing technique. 
     BRIEF SUMMARY OF THE INVENTION 
     Briefly, the present invention provides a technique for routing a call or other connection request between an origin and destination in an IP network comprised of routers connected by links that carry data packets between routers. In accordance with the invention, the routers exchange status messages to identify available paths between the origin and destination. Each path includes at least one outgoing link from one router to another. First the class of service of the call or other connection request is determined. Then a path is selected that has a minimum cost, such as for example a minimum number of hops. Thereafter, a check is made by the originating router or possibly a centralized bandwidth broker, based on flooded network status information, of the selected path as to whether the links from that router forming the path have an available depth (i.e., bandwidth capacity not reserved for other services) for the determined class of service. If the links possess the requisite bandwidth, the router routes the packet over the outgoing link. Otherwise, another path is selected and the step of determining if the links forming the path have the requisite depth is repeated. After an allowed path is found, the IP packets are treated according to their class-of-service designated priority in the queuing discipline used by the routers in the path. 
    
    
     BRIEF SUMMARY OF THE DRAWING 
     FIG. 1 depicts a block schematic diagram for practicing the IP Class-of Service routing technique of the invention. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 shows a simplified block schematic diagram of an IP network  10  comprised of a plurality of routers, exemplified by routers  12   1 ,  12   2  and  12   3 . Links  14   1    14   2 , and  14   3  connect router pairs  12   1 - 12   2 ,  12   2 - 12   3 , and  12   1 - 12   3 , respectively allowing the routers to pass data packets, representing telephone calls, or other information among themselves. Although the illustrated embodiment of network  10  includes only the three routers  12   1 - 12   3  and three pairs of connecting links, the network may include a far larger number of routers and interconnecting links. 
     Voice traffic destined for transit through the network  10  enters and exits the network via at least one, and preferably, a plurality of voice/IP gateways, exemplified by voice/IP gateways  15   1 ,  15   2 , and  15   3 . In the illustrated embodiment, the voice/IP gateway  15   1  handles Narrowband Integrated Services Digital Network (NISDN) traffic, e.g., traffic transmitted in 64 kilobit per second blocks. The voice/IP gateway  15   2  handles Broadband Integrated Services Digital Network (BISDN) traffic, e.g., traffic that exceeds 144 kilobits per second, the basic transmission rate for NISDN traffic. Such BISDN traffic may include voice, video and image data, for example. The voice/IP gateway  15   3  handles data already in an IP format. Depending on the nature of the traffic, the network  10  may include other Voice/IP gateways (not shown) each designed for a particular format. 
     Traditionally, the routers  12   1 ,  12   2 , and  12   3  have utilized a best effort routing policy to route traffic within the network  10 , using such algorithms as the Open Shortest Path First (OSPF) algorithm that seeks to route each packet on the shortest possible path. Presently, the OSPF routing protocol could theoretically support different Types of Service (TOS) based on the following criteria: Delay, Throughput and Reliability. However, IP networks, such as network  10 , which utilize OSPF routing have not offered Class of Service (COS) that has been available in circuit-switched networks, making it difficult for telecommunications carriers to offer different classes of service using an IP network. 
     The present invention affords a technique for accomplishing COS routing in an IP network. Upon determination of the class of service, which includes the priority and other parameters of the call or other connection at its initial set-up, an originating router that receives packets from one of the gateways  15   1 ,  15   2  and  15   3  selects a route based on the requisite depth (required bandwidth), which in turn is based on the flow priority and load state of the links ( 14   1 ,  14   2 ,  14   3 ) in network  10 . Once the originating router selects an admissible path, each subsequent router performs routing of the packets according to the determined path and priority, as now described further. 
     To determine requisite depth, the originating router in network  10  determines the equivalent bandwidth needed for the call or other connection and also utilizes a Bandwidth in Progress (BWIP) indication for the determined class of service at the start of the call or other connection. To that end, two quantities: Bandwidth Peg Count (BWPC) and a Bandwidth Overflow Count (BWOV) are kept for each link connecting an originating/terminating router pair. During a given interval of X minutes, each router, such as router  12   1  tracks for each link to another router the following quantities: 
     BWPC(link)=Sum of all Bandwidth (BW) required for flows on the link; and 
     BWOV(link)=Sum of BW required for each blocked flow on the link 
     In the class of service routing method, various virtual networks are maintained which are allocated bandwidth according to demands. Each router also maintains the following two Depth parameters for each virtual network: 
     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 ) [=Erlang Load vk ×(Avg bandwidth per virtual connection) vk ] and 
     BWmax vk , the Bandwidth required to meet the blocking probability Grade-of-Service objective=[TREBS(Erlang Load vk , Grade-of-Service)×(Avg bandwidth per virtual connection) vk ] 
     where TREBS represents the well known Erlang-B formula for trunk requirements. 
     In practice , BWavg vk  and BWmax vk  are computed at prescribed intervals, typically weekly. Different values of BWavg vk  and BWmax vk  may be used for different periods of the day (business peak, residence peak). 
     Four different blocking reservation thresholds (BR 1 , BR 2 , BR 3 , BR 4 ) are used, where 0%≦BR 1 ≦BR 2 ≦BR 3 ≦BR 4 ≦100%. The reservation level N is 0 if the link blocking (NN) does not exceed BR 1 , N=1 if NN exceeds BR 1  but not BR 2 , N=2 if NN exceeds BR 2  but not BR 3 , N=3 if NN exceeds BR 3  but not BR 4 , and N=4 if NN exceeds BR 4 . This relationship is depicted in Table I. 
     
       
         
               
             
               
               
             
           
               
                 TABLE I 
               
             
             
               
                   
               
               
                 Determination of Reservation Level (N) 
               
             
          
           
               
                 N 
                 Condition 
               
               
                   
               
               
                 0 
                 NN (link blocking) ≦ BR1 
               
               
                 1 
                 BR1 &lt; NN ≦ BR2 
               
               
                 2 
                 BR2 &lt; NN ≦ BR3 
               
               
                 3 
                 BR3 &lt; NN ≦ BR4 
               
               
                 4 
                 BR4 &lt; NN 
               
               
                   
               
             
          
         
       
     
     The Idle Link bandwidth (ILBW) for each link is used in the determination of the link Load State. In addition to the Load State of each local link (i.e., the link associated with a particular router), the Load State of all other network links is received from other routers using, for example, an extension of the currently used OSPF flooding mechanism. A metric such as “throughput or bandwidth available” might theoretically be supported by the OSPF routing algorithm to provide an indication of the Load State of all links in the network  10 . Also, another metric such as “delay” may provide an indication of the Load State. In addition to being flooded to every other router in the network, this link metric information on bandwidth available, delay, or other measures could be flooded to a centralized bandwidth broker (BB),  20  which could track the link status information and perform routing computations, as discussed further below. 
     A link extending between a router pair is considered in a reserved (R) state if the Idle Bandwidth (ILBW) is less than or equal to a Reserved Threshold (Rthr), as defined below. The link is considered in the Heavily Loaded (HL) state if the Idle Bandwidth is less than or equal to a Heavily Loaded threshold (HLthr) for the link but more than Rthr. Conversely, the link is considered Lightly Loaded (LL) if the Idle Bandwidth for each link in the path is greater than HLthr for the link. This relationship is best depicted in Table II (hereafter we have omitted, for simplicity, the subscripts k denoting the node-pair for each variable): 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE II 
               
             
             
               
                   
               
               
                 Load State Condition 
               
             
          
           
               
                   
                 Name of State 
                 Condition 
               
               
                   
                   
               
               
                   
                 Busy B 
                 ILBW = 0 
               
               
                   
                 Reserved R 
                 ILBW ≦ Rthr 
               
               
                   
                 Heavily Loaded HL 
                 Rthr &lt; ILBW ≦ HLthr 
               
               
                   
                 Lightly Loaded LL 
                 HLthr &lt; ILBW 
               
               
                   
                   
               
             
          
         
       
     
     The Reservation Threshold Rthr and Heavily Loaded Threshold HLthr are given by the relationships 
     Rthr=N×.0.05×BWmax v    
     HLthr=Rthr+.0.05×BWmax v    
     where N is the reservation level based on the Blocking Reservation thresholds (BR 1 , BR 2 , BR 3 , and BR 4 ). 
     The Depth-of-Search (DoS) for a flow to use various Load States depends on the Bandwidth-In-Progress (BWIP v ), the BWavg v  and BWmax v  thresholds, the priority of the call or other connection, and whether the path is the first choice path or alternate path, as illustrated in Table III (here again we have omitted, for simplicity, the subscripts k denoting the node-pair for each variable): 
     
       
         
               
             
               
               
               
             
               
               
               
               
               
             
           
               
                 TABLE III 
               
             
             
               
                   
               
               
                 DoS CRITERION 
               
             
          
           
               
                   
                 Normal Service 
                   
               
             
          
           
               
                   
                   
                 First 
                   
                   
               
               
                 Load State 
                   
                 Choice 
                 Alternate 
                 Best Effort 
               
               
                 Allowed ν   
                 Key Service 
                 Path 
                 Path 
                 Service 
               
               
                   
               
               
                 R 
                 if BWIP ν ≦ 2 × 
                 if BWIP ν   
                 Not 
                 Not Allowed 
               
               
                   
                 BWmax ν   
                 ≦ 
                 Allowed 
               
               
                   
                   
                 BWavg ν   
                   
               
               
                 HL 
                 if BWIP ν ≦ 2 × 
                 if BWIP ν   
                 if BWIP ν   
                 Not Allowed 
               
               
                   
                 BWmax ν   
                 ≦ 
                 ≦ 
               
               
                   
                   
                 BWmax ν   
                 BWavg ν   
               
               
                 LL 
                 All BWIP ν   
                 All BWIPν 
                 All BWIP ν   
                 All BWIP ν   
               
               
                   
               
             
          
         
       
     
     The originating router determines the allowed DoS for the call or other connection according to Table III. The originating router first attempts to route the call on shortest path to the terminating router. 
     For a key service flow: 
     If BWIP v ≦2×BWmax v , then all load states are allowed. 
     If BWIP v &gt;2×BWmax v , then only LL links are allowed. 
     For a normal service flow: 
     If BWIP v &gt;BWavg v , then all load states are allowed on the first choice path and the HL and LL states are allowed on alternate paths 
     If BWavg v &lt;BWIP v ≦BWmax v , then only HL and LL states are allowed on the first choice path and LL state is allowed on alternate paths 
     If BWIP v &gt;BWmax v , then only the LL links are allowed are on first choice and alternate paths 
     For a best effort service call only LL links are allowed. 
     The originating router first determines the class of service of the call (or other connection request) from information associated with the call. In routing calls in accordance with the invention, an originating router, (e.g., router  12   1 ) will determine the. Load State of the network links. As discussed previously, the Load State information for all links in the network  10  could be distributed, for example, via the OSPF flooding protocol. The originating router selects a path having, for example, a minimum number of hops using the shortest path routing algorithm. Using the depth parameters discussed above, the originating router then checks whether the links forming the selected path have an available depth (bandwidth capacity) for the determined class of service. If so, the router routes the packets of the call or connection request over the links in the selected path. Otherwise, another path is selected and the step of determining if the links in the path have available capacity and depth is repeated. If the originating router cannot route the call or other connection to the selected destination router, and there are other terminating routers that can route the call, then the originating router uses the shortest path algorithm to select candidate paths and the class of service routing technique to route the call to such a terminating router. If there is no available terminating router, the call is blocked. 
     As was discussed earlier, the centralized bandwidth broker (BB)  20  could receive the link status metric information through the flooding mechanism, and perform the same routing computations described above for the originating router. That is, in response to a request from an originating router, for example, the BB  20  could select a path having a minimum number of hops using the shortest path routing algorithm, depth parameters, and available link bandwidth. Once an admissible path is found, the path information is returned to the originating router which can then route the packets in the flow accordingly. 
     After the path is established by the originating router and packets are flowed on the path, at each hop the recipient router performs priority packet queuing based on the routing priority assigned by the originating router to each packet, such as contained in the TOS field indicator of the packet. The TOS indicators in each packet are set so that the recipient router at each subsequent hop uses the same queuing priority as determined by the originating router for the selected shortest path and COS routing treatment. Hence the COS capability afforded by the method of the invention may be enhanced by adding a priority queuing capability. At each link, the router maintains a queuing discipline such that packets having a higher TOS requirement (TOS and precedence bits) have priority over lower TOS requirements, such as best effort service. 
     The foregoing describes a technique for achieving Class-of-Service routing in an IP network. 
     The above-described embodiments merely illustrate the principles of the invention. Those skilled in the art may make various modifications and changes that will embody the principles of the invention and fall within the spirit and scope thereof.