Success-to-the-top class of service routing

[0002] This invention relates to a technique for routing telephone calls in a packet-based network.

[0003] 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&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 utilizing Asynchronous Transport Mode (ATM) switches at their core. Within such packetized networks, core ATM switches route packetized calls to and from switches at the edge of the network that exchange traffic with sources such as local exchange carriers, international carriers and direct nodal subscribers. Unlike conventional circuit switches, ATM switches afford the advantage of allocating resources (e.g., time slots) only at packet transfer, rather than for the entire duration of a call. Moreover, packet-based networks can more easily make use of a relatively small number of high bandwidth paths, as compared to the larger number of circuits needed to make connections between switches in conventional circuit-switched networks.

[0004] Traditional switches in circuit-switched networks employ one or more of several well-known techniques for routing calls. One such technique is “Success to the Top” (STT) routing whereby an originating switch initially attempts to route a call to a terminating switch over a direct link (if it exists) between the switches. When a direct link is unavailable, the originating switch looks for a link through an intermediate (via) switch. The originating switch initially selects the via switch that most recently carried a call successfully between the originating and terminating switches. The originating switch selects the most recently successful via switch on the premise that such a via switch, once previously successful, can successfully route a subsequent call in the same manner as before.

[0005] If the most recently successful via switch is incapable of routing the call, then that via switch indicates its unavailability by sending a message, often referred to as a release or crankback message, to the originating switch. Thereafter, the originating switch searches for a next successful via switch. If the originating switch receives a crankback message from a via switch in this search, the originating switch continues its hunt for a next successful via switch. As may be appreciated, the Success to the Top (STT) routing method gets its name from the use made by the originating switch of the most recently successful via switch.

[0006] While the STT routing method is applied within conventional circuit-switched a networks, packet-based networks do not generally use this type of routing. In circuit switched networks that use STT routing, the routing decisions generally depend on the transport capacity of the paths between switches. Generally speaking, the virtual paths that link switches in packet-based networks typically possess sufficient capacity so utilizing transport capacity as the criterion for selecting the most recently successful via switch for routing has not proven useful in efforts to apply STT routing in packet networks.

[0007] Other techniques for routing calls in circuit-switched networks include Class-of-Service (COS) routing that takes account of the particular class or type of call when making routing decisions. Typically, with COS routing, different classes of calls receive different priorities. Thus, for example, certain classes of calls, such as those associated with “key” service, receive high priority while other classes of class receive lower priority. When selecting a trunk for routing, an originating circuit switch examines both the call priority, as well as the transport capacity needed to carry the call. As with STT routing, COS routing determinations generally depend on the transport capacity, a criterion that is generally not of concern in packet networks. For that reason COS routing is not generally employed in packet-based networks, however in the present invention COS routing techniques are extended to packet-based networks.

[0008] Briefly, the present invention provides a method for routing telephone calls in a packet network between an originating switch and a terminating switch using a combination of Success to the Top and Class of Service routing techniques. In accordance with the invention, an originating switch (i.e., a switch receiving a call within the network destined for another switch, hereinafter, a “terminating” switch) first checks for an available direct path to the terminating switch. In other words, the originating switch determines whether a direct path exists to the terminating switch, and whether that direct path possesses an available bandwidth sufficient to carry the call in accordance with its particular class of service. In determining if available bandwidth exists, the originating switch establishes a measure of the existing traffic on the path to establish its load state. From the load state of the path, the originating switch determines whether the direct path possess the requisite bandwidth to carry a particular call in accordance with its class of service. If so, the originating switch routes the call on the direct path to the terminating switch.

[0009] Otherwise, if a direct path is not available, then the originating switch searches for a path through a via switch by searching for the via switch that most recently successfully carried a call from the originating switch. Having identified the most recently successful switch, the originating switch determines whether its path to that via switch has an available bandwidth to carry the call in accordance with the class of service of that call. If the path to the most recently successful via switch has sufficient bandwidth to carry the call, then that via switch determines whether its path to the terminating switch has the available bandwidth to carry the call in accordance with the class of service of that call. If so, then that via switch passes the call from the originating switch to the terminating switch.

[0010] In the event of a lack of an available path linking the most-recently successful via switch and the terminating switch, the via switch sends a message, which may be a release or crankback message, to the originating switch. Upon receipt of the message, or upon determining the lack of an available path from the originating switch to the most recently successful via switch, the originating switch hunts for a next successful via switch. The originating switch determines whether a path exists to a next candidate via switch and has sufficient available bandwidth. If so, then that via switch determines whether it has a path to the terminating switch with available bandwidth. Should the next most recently successful via switch lack the ability to route the call to the terminating switch, the originating switch will continue searching for a successful via switch through which to route the call until the list of possible via switches is exhausted.

[0011] FIG. 1 illustrates a block schematic diagram of a packet-based telecommunications network; and

[0012] FIG. 2 illustrates a portion of the network of FIG. 1 for the purpose of depicting an exemplary call flow using the Success to the Top/Class of Service routing in accordance with the invention.

[0013] FIG. 1 illustrates a packet-based network 10 for carrying telephone calls. At its core, the network 10 includes one more packet switches, illustratively represented as ATM switches 12₁-12₂, although the network could include a larger number of such switches. The ATM core switches 12₁and 12₂communicate packetized information (i.e., packets of data representing telephone calls) between themselves across at least one virtual path 14₁. In practice, each of core ATM switches 12₁and 12₂comprises an ATM switch available from a variety of vendors, including Lucent Technologies, Ascend Communications, Cisco, and others.

[0014] In addition to the core ATM switches 12₁and 12₂, the network 10 includes a plurality of edge switches, depicted as edge switches 16₁and 16₂, each passing traffic between itself and one or more other networks. For example, the edge switches 16₁and 16₂may send traffic to, as well as receive traffic from any or all of the following: (a) a local service provider, as represented by local switch 18, (b) an international network, represented by international switch 20, (c) a nodal customer, represented by PBX 22, and (d) an Inter-exchange network (not shown). The edge switches 16₁and 16₂may take the form of conventional circuit switches, such as the 4ESS or 5 ESS switch available from Lucent Technologies, or alternatively, may comprise ATM switches. In the illustrated embodiment, the edge switch 16₁comprises a circuit switch linked to the ATM core switch 12₁, the edge switch 16₂2, the PBX 22, and the local switch 18 via paths 20₁, 20₂, 20₃, and 20₄, respectively. Conversely, the edge switch 16₂comprises an ATM switch having paths 20₅, 20₆, 20₇, 20₈, and 20₉that link the switch to the PBX 22, the local switch 18, the international switch 20 and the core ATM switches 16₁and 16₂, respectively.

[0015] As discussed in greater detail below, traffic on the paths 20₁, 20₈, and 20₉linking the core switches 12₁and 12₂to the edge switches 16₁and 16₂is routed in both directions using a combination of Success to the Top and Class of Service (STT/COS) routing in accordance with the invention. In other words, each of the edge switches 16₁and 16₂routes a call to another edge switch or a convention circuit switch on an associated one of the paths 20₁, 20₈and 20₉via the core switches 12₁and 12₂using the STT/COS routing of the invention. In contrast to the paths 20₁, 20₈, and 20₉that are associated with bi-directional STT/COS, traffic on the paths 20₃-20₇, linking the edge switches 16₁and 16₂to the PBX 22, the local switch 18, and the international switch 20 is routed in one direction only using the STT/COS routing. In other words, the edge switches 16₁and 16₂route calls to the PBX 22, local service provider switch 18, and the international switch 20 using STT/COS routing in accordance with the invention. However, the PBX 22, local switch 18 and international switch 20 use conventional techniques to route calls to one or more of the edge switches 16₁and 16₂.

[0016] In the illustrated embodiment, the network 10 may include other circuit switches, such as switches 22₁, and 22₂which typically comprise 4ESS switches as are known in the art. A communication channel (trunk) 24₁interconnects the switches 22₁and 22₁while trunks 24₂-24₄and 24₅-24₇link the switches 22₁and 22₂to the PBX 22, local service provider switch 18 and the international switch 20, respectively. The switches 22₁and 22₁also have trunks 25₁and 25₂that link them to the core switch 12₂. Unlike the edge switches 16₁and 16₂, the switches 22₁and 22₁do not necessarily need to utilize the STT/COS routing technique of the invention. Rather, the circuit switches 22₁and 22₂may utilize conventional routing techniques to route calls to and from the PBX 22 local service provider switch 18 and the international switch 20. In other words, various routing techniques can co-exist and interwork within the same network as a feature of the invention.

[0017] FIG. 2 illustrates a simple network 100 to depict an exemplary call flow using the STT/COS routing technique of the invention. The network 100 includes an originating switch 110 and a terminating switch 112 linked by at least one virtual path 116. For purposes of discussion, the originating switch 110 is defined as a switch which receives a call, either from another switch, or even a nodal customer (e.g., PBX 22 of FIG. 1) for routing to the terminating switch. Thus, with respect to the network 10 of FIG. 1, the originating switch may comprise one of ATM one of edge switches 16₁-16₂whereas the terminating switch may comprise an edge switch, the local switch 18, the international switch 20, or the PBX 22, all of FIG. 1.

[0018] In addition to the originating and terminating switches 110 and 112, the network 100 of FIG. 2 includes a plurality of intermediate (via) switches 118₁-118_n(where n is an integer>0). Each via switch may comprise an edge switch or core switch as depicted in FIG. 1. A corresponding one of virtual paths 120₁-120_n, links each of via switches 118₁-118_n, respectively, to the originating switch 110, while one of virtual paths 122₁-122_nlinks a corresponding one of the via switches, respectively, to the terminating switch 112.

[0019] The originating switch 110 routes a connection request comprised of a plurality of packets to the terminating switch 112 using the STT/COS routing technique of the invention in the following manner.

[0020] First, the originating switch 110 checks for available bandwidth (as discussed below) on the direct path 116. If the path 116 has available bandwidth, the originating switch routes the call to the terminating switch 112 on the direct path 116.

[0021] If the direct path 116 is unavailable, the originating switch 110 searches for the most recently successful one of the via switches 118₁-118_nto determine whether that via switch can successfully route the call to the terminating switch 112. If the most recently successful one of the via switches possesses available bandwidth to route the call, the originating switch 110 selects that via switch.

[0022] Otherwise, if the most-recently successful via switch can not route the call, the originating switch 110 searches for a next successful via switch.

[0023] If routing on the direct path 116 or through one of the via switches 118₁-118_ndoes not succeed, the originating switch will either attempt a further route advance or crankback the call to a previous switch for further alternate routing.

[0024] In determining whether to route the call on the direct path 116, the originating switch 110 determines whether the path has available bandwidth in accordance with the class of service of the call in question. In practice, the originating switch originating switch 110 typically receives calls of different types or classes. For example, the originating switch 110 may receive international calls, toll-free calls, Software-Defined Network (SDN) calls, just to name a few. Each different type of call has an associated particular routing priority (e.g., key, normal, or best effort) to meet the grade of service objective for that particular class. The originating switch 110 utilizes the class of service of the call to determine whether a call can be admitted on a particular path, given the Load State of that path.

[0025] The originating switch 110 determines whether the allowable load state of each link in a virtual path is lightly loaded (LL), heavily loaded (HL) or reserved (R) by comparing the idle bandwidth (IBW) as described hereinafter, to a blocking rate threshold established by the grade of service requirement for each class of service. Thus, for example, an international call may have a different blocking rate threshold as compared to a domestic long distance call, or an SDN call, based on the differences in class of service. After determining the allowable Load State, the originating switch determines a Depth of Search (DoS) value for the call to determine if the call can pass on a path having a LL, HL, or R Load State (that is, each link in the path has a Load State of the DoS value or better). As discussed below, the DoS depends on several factors, including: bandwidth in progress on a virtual network, call priority, the average virtual network load, the virtual network bandwidth required to meet the grade of service objective and whether the path is direct path or the path is through a via switch.

[0026] In order to establish the DoS load state threshold of a path, the originating switch 110 establishes for that path, two separate measures of bandwidth, or two Depth Parameters for each originating-terminating switch pair. These depth parameters are:

[0027] 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 BW_vk/Virtual Path_vk] and

[0028] BWmax_vk, the Bandwidth required to meet the blocking probability Grade-of-Service objective=[TREBS(Erlang Load_vk, Grade-of-Service)×Avg BW_vk/ VC_vk]

[0029] In practice, BWavg_vkand BWmax_vkare computed at prescribed intervals, typically weekly. Different values of BWavg_vkand BWmax_vkmay be used for different periods of the day (business peak, residence peak).

[0030] In determining the link Load State, each switch keeps track of two quantities: Bandwidth Peg Count (BWPC) and a Bandwidth Overflow Count (BWOV). During a given interval, (say three minutes) each switch such as switch 110 tracks for each node-pair between switch 110 and another switch:

[0031] BWPC(originating switch/terminating switch linking path)=Sum of all Bandwidth (BW) required for each virtual path setup.

[0032] BWOV(originating switch/terminating switch linking path)=Sum of BW required for each blocked virtual path setup.

[0033] At the end of the given interval, the Node-to-Node blocking (NN) is computed:

[0034] NN(originating switch/terminating switch linking path)=BWOV(originating switch/terminating switch linking path)/BWPC(originating switch/terminating switch linking path).

[0035] Four different blocking reservation thresholds (BR1, BR2, BR3, BR4) are used, where 0%≦BR1≦BR2≦BR3≦BR4≦100%. The reservation level N is 0 if BR1 is not exceeded, N=1 if BR1 is exceeded but not BR2, N=2 if BR2 is exceeded but not BR3, N=3 if BR3 is exceeded but not BR4, and N=4 if BR4 is exceeded. This relationship is depicted in Table I.

[0036] A link, such as link 116, between an originating switch/terminating switch pair is considered in a reserved (R) state if the Idle Bandwidth (ILBW) less than a Reserved Threshold (Rthr), as defined below. The path between the originating switch/terminating switch pair is considered in the Heavily Loaded (HL) state if the Idle Bandwidth is less than a Heavily Loaded threshold (HLthr) but more than Rthr. Conversely, the path between the originating switch/terminating switch pair is considered Lightly Loaded (LL) if the Idle Bandwidth is greater than HLthr. This relationship is best depicted in Table II (here we have omitted, for simplicity, the subscripts k denoting the node-pair for each variable):

[0037] The Reservation Threshold Rthr and Heavily Loaded Threshold Hlthr are given by the relationships

[0038] EQBW=the equivalent amount of bandwidth required for a given connection request Rthr =N×0.05×BWmax_v

[0039] HLthr(originating switch/terminating switch link)=Rthr(originating switch/terminating switch link)+0.05×BWmax_v

[0040] where N is the reservation level based on the Blocking Reservation thresholds (BR1, BR2, BR3, and BR4).

[0041] The Depth-of-Search (DoS) associated with a call to determine which load states for each link in a path are permissible for that call depends of the Bandwidth-In-Progress (BWIP), the BWavg_vand BWmax_vthe HL, LL and R path thresholds, the priority of the call, and the number of links in the path, as illustrated in Table III (here again we have omitted, for simplicity, the subscripts k denoting the node-pair for each variable):

[0042] The originating switch determines the allowed DoS for the call according to Table III. The originating switch 110 of FIG. 2 first attempts to route the call on the direct path 116 to the terminating switch 112 in the following manner.

[0043] For a key service call:

[0044] If BWIP_v≦2×BWmax_v, then the call can be routed on the direct path 116 so long as the required bandwidth for the call is available.

[0045] If BWIP_v>2×BWmax_v, then the call can be routed on the direct path only if the link is in LL state and has the required bandwidth for the call.

[0046] For a normal service call:

[0047] If BWIP_v≦BWavg_v, then the call can be routed on the direct path as long as the required bandwidth for the call is available.

[0048] If BWavg_v>BWIP_v≦BWmax_v, then the call can be routed on the direct path 116 of FIG. 2 only if the link is in HL or LL state and has the required bandwidth for the call.

[0049] If BWIP_v>BWmax_v, then the call can be routed on the direct path 116 only if the link is in LL state and has the required bandwidth for the call.

[0050] For a best effort service call, the call can be routed on the direct path 116 only if the link is in LL State and has the required bandwidth for the call.

[0051] If the originating switch 110 of FIG. 1 cannot route the call on the direct path 116, then the originating switch will attempt to route the call on a 2-link path through the most recently successful one of via switches 118₁-118_nto the terminating switch 112. The originating switch 112 uses the load state information of the first link to determine the first link to select as follows:

[0052] For a key service call:

[0053] If BWIP_v≦2×BWmax_v, then all Load States are allowed. The originating switch starts by checking the last via successfully used (the STT via), or following a crankback, the next allowed via is determined based on circular hunt.

[0054] If BWIP_v>2×BWmax_v, then the originating switch selects the first via switch where the link is in the LL State. The originating switch starts by checking the last via successfully used (the STT via), or following a crankback, the next allowed via is determined based on circular hunt.

[0055] For a normal service call:

[0056] If BWIP_v≦BWavg_v, then only LL and HL Load States are allowed. The originating switch starts by checking the last via successfully used (the STT via), or following a crankback, the next allowed via is determined based on circular hunt.

[0057] If BWIP_v>BWavg_v, then the originating switch selects the first via switch where the link is in the LL state. The originating switch starts by checking the last via successfully used (the STT via), or following a crankback, the next allowed via is determined based on circular hunt.

[0058] For a best effort service call,

[0059] The originating switch selects the first via switch where the first link is in the LL state. The originating switch starts by checking the last via successfully used (the STT via), or following a crankback, the next allowed via is determined based on circular hunt.

[0060] If the originating switch fails to find a path to a via switch and there are other terminating switches that can also complete the call, then the originating switch uses the above-described STT/COS routing method of the invention to route the call to a subsequent terminating switch. Otherwise, the call is blocked.

[0061] When the originating switch 110 routes the call to a via switch, then the originating switch passes the bandwidth requirement and the Depth-of-Search (DoS) information (i.e., the path load state) to the via switch in the initial address message (IAM) or Setup signaling message. The via switch routes the call to the terminating switch if the path therebetween possesses the required bandwidth and load state. Otherwise, the via switch returns call control to the originating switch using a release (crankback) message. Upon receipt of the message, the originating switch accomplishes route advance or routes the call on to other eligible paths.

[0062] As discussed previously with respect to FIG. 1, the edge switches 16₁and 16₂route calls among themselves in both directions using the STT/COS routing technique of the invention described above. The edge switches 16₁and 16₂could use a single-ended version of the STT/COS routing technique, with each edge switch acting like the originating switch 110 of FIG. 2 to determine the egress route. However, once a next link is selected, the edge switch would not pass forward the Depth-of-Search (DoS) to a subsequent switch. Such single-ended STT/COS routing provides COS and direct route reservation for the network 10 and the outlying network receiving the call therefrom.

[0063] In addition to the Class of Service capability which is part of the Call Admission Control (CAC) procedure at the time of call set-up, each switch routing traffic to a subsequent switch will typically utilize a priority queuing as part of the Quality of Service (QoS) capability during the call. In practice, each sending switch maintains a prescribed queuing discipline such that the cells (packets) receive priority, for example, in the following order.

[0064] 1. Constant Bit Rate (CBR)-key service

[0065] 2. Variable Bit Rate (VBR)-key service

[0066] 3. CBR-normal service

[0067] 4. VBR-normal service

[0068] 5. Unassigned Bit Rate-best effort service

[0069] The foregoing describes a technique for routing connection requests such a required by telephone calls in a packet network that utilizes a combination of Success-to-the Top and Class-of-Service principles.

[0070] 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.