FAST NETWORK HEURISTIC FOR TRAFFIC FLOW PREDICTION

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present disclosure is related to telecommunication networks. More particularly, the present disclosure is related to systems and methods for allocating traffic among network alternatives.

2. Description of Related Art

Predicting how traffic would flow through a network prior to actually routing traffic on the switch is highly desirable. This can be used to understand the probable impact of routing and carrier-business decisions before actually implementing them. The method further provides a what-if tool for permitting quick business decisions on the economic viability of initiating or terminating business relationships with carriers.

While the particular embodiment of the simulation described here is for a telecommunications network, it can be applied to any network in which one can only intermittently control how flow through the network can be redirected and consequently there is limited or no ability to pre-specify paths through the network from specific origins to specific destinations when traffic from multiple origins flows through the same connections. Examples of this are water flow networks (e.g., irrigation or sewer systems), traffic flow on highways, liquids flowing through a chemical plant etc or flow through an IP network in which packets are not directed along pre-specified paths, but rather at each switch a packet is routed on a link in a manner which is based on some switch related

rule. Such rules are for instance order the connections to other switches by cost or order connections by shortest path to a destination.

The telephone network is extremely complex; routing decisions and inter-carrier business agreements may have significant economic and quality implications. A routing change which might seem to have locally positive impact may result in globally negative impact, and implementing it can result in costly consequences. Simulating the impact of a change quickly without implementing it in switch routing tables (and possibly in new inter-carrier business agreements) could mitigate such costly mistakes. Additionally, the results of such simulation can be used for network planning, examining the economic viability of creating of new routing locations and network links.

Current solutions do not easily expose, a-priori, the expected impact of local routing decisions on the entire network.

A conventional telephone network is exemplified in US Patent 6209033, entitled "Apparatus and Method for Network Capacity Evaluation and Planning". In this network, demands are specified on each link and then a ratio of demand-to-capacity is assigned to each link, following by the ratio of a link's demand to all links demands. Thus, to modify the simulation one must specify changes on specific links. The impact of these changes is not propagated through the network. To address this, US Patent 6209033 resorts to "an adaptive learning mechanism", which it says can be set up to determine the overall effects of changes. However, this patent does not discuss how such a mechanism would be implemented. The only suggestion states that when traffic between origin X and destination Y is increased by some factor, then that factor should be applied to the traffic on all links between X and Y. Furthermore, this patent does not refer to the cost of a routing.

Another approach is described in US Patent 6850491, entitled "Modeling Link Throughput in IP Networks". The approach in this patent is intended for an IP network and statistical in nature and also focuses on a link at a time.

US Patent Publication No. US2002/0103631 discusses simulation of an

IP network. However, it does not address adhering to link capacity constraints.

Sophisticated algorithms and processes have been developed to solve optimal network flow problems. Many of these define the problems as a multicommodity flow method. Much work has gone into optimizing these processes. Such approaches are exemplified by the paper "Approximate Multicommodity Flow for WDM Network Design" by Bouklit et. al. published in Sirocco, June 2003. However such algorithms assume that one can control the flow of traffic through a network so that one can dynamically specify different specific paths through the network for different portions of the traffic even though these different portions are not uniquely identifiable. These are intended to find an ideal distribution of flow through the network with the intention that the network can be dynamically controlled to produce that flow. In contrast, the network being simulated here is dumb in the sense that there is no way to dynamically specify specific paths for specific portions of undifferentiated traffic which arrive at a decision point. Rather route strings are specified on each switch for a time interval (e.g., hour) and all of a class of traffic which comes into a specific route string is only redirected by advancing the call to the first non overflowing carrier, or if there is percent routing, to the first non-overflowing carrier on the route string which is currently selected by the percent routing. Thus, unless the interconnectivity in the network has been constructed so that there is a unique path from source to destination there is no way to explicitly specify a path. The consequence of this distinction is that the multicommodity solutions focus on finding shortest paths through the network which can be

packed with traffic in such a way as to accommodate as much traffic as is theoretically feasible. The simulator described here focuses on finding edges (i.e. carriers or IMTs) which can be packed with traffic in such a way that adheres to the manner in which traffic would flow through a nondynamically controlled network. Thus, it will more accurately predict the flow on such a network than the multicommodity approach.

The following example shows the difference between results that would be generated by the two types of networks.

Given the flow into A of 100 and the flow into B of 100 with a terminating capacity on A of 100 and a tandem capacity to B of 10 and a terminating capacity on B of 100 as below, and as shown in Fig. 1.

The multicommodity approach would push all of the traffic coming into

A onto the non-tandem out of A and all the traffic coming directly into B out for a total flow of 200 accommodating all the demand. This approach assumes that the network can dynamically specify whether the tandem from A to B or the terminating carrier off of A will take the traffic, i.e., it can specify specific paths for each call.

However, in a dumb network the order of the carriers on a route string has to be pre-specified, thus, distinct calls cannot be directed on different paths to the same location. This can be changed during the day at specified intervals, e.g., hourly but not for each call. Therefore unless the route string had been explicitly constructed so that the terminating carrier out of A was first and then followed by the tandem from A to B, only a suboptimal result could be achieved. In this example, if the tandem proceeded the terminating carrier on the route string on A, then as in the schematic, some of the traffic would go from A to B. This would result in some of the terminating carrier on B having to use some of its capacity to accommodate the flow into B from A, resulting in the demand of

100 directly into B not being fully accommodated. This simple example was constructed to show the difference in results. In a complex network there are many reasons why the route string order which appears to be locally best would not be implemented due to considerations such as balancing a carrier or tandems usage among many different locations where it can be used, cost of use of he carrier and quality of service of the carrier.

As described in detail below the simulation method in this case would proceed in the following manner. The tandem from A to B has a capacity of 10 and a demand of 100 (demands means simultaneous calls). The carrier out of B has a capacity of 100 and sees a total demand of 200 (all the demand from A to B is considered). The most constrained connection is the tandem with a capacity to demand ratio of 1. This ratio is now applied to all demands. Thus one tenth of the demand into A, e.g., 10 is assigned to the tandem from A to B which would now be filled and there is a remaining demand of 90 into A that has to be assigned. Similarly one tenth of the total demand into B would be assigned which is one tenth of 200 or 20. Note this is comprised of one tenth of the demand from A and one tenth of the demand directly into B. This would mean the carrier out of B would be assigned a demand of 20 with a remaining capacity of 80, and 90 of the demand directly into B would remain unassigned. Note that even though in actuality the tandem from A to B can only accommodate 10 simultaneous calls and 100 simultaneous calls are coming directly into B, as discussed below one is working under the assumption that he solve the problem by assuming that he are starting from zero demand and increasing the traffic proportionally everywhere. Therefore, at the point that 10 would flow through the tandem from A to B he has only increased the traffic into A to one tenth of the total so only one tenth of the traffic from B would be considered to be in place. Thus, in this case 10 calls would be assumed to be in place on the tandem from A to B and 10 calls would be assumed to be in place coming directly into B. All 20 calls would terminate on the carrier out of B. At this point the connection between A and B is at capacity and all remaining calls into A would

terminated directly off A and all the remaining calls directly entering B would be taken by the carrier off B. Thus, a total of 190 calls are accommodated as in the diagram set forth in Fig. 2.

This comparison demonstrates that a multicommodity flow algorithm will produce a result which does not correspond to how the current telecom network would route the calls and would give an overly optimistic prediction of how much traffic can be accommodated. On the other hand, results produced by the present invention would be consistent with how traffic is routed.

The method described in the present invention only requires that one specify demands incoming to the network, and their destinations. The method of this present invention propagates the impact of this traffic throughout the network. Similarly if changes are made to links or to carrier priorities of at switching locations, the method propagates the impact of such changes throughout the system.

BRIEF SUMMARY OF THE INVENTION

The method provides a heuristic that enables an a-priori assessment of the behavior of a network based on specific routing table settings; the results enable estimating the costs of diverting traffic to various carriers at specific switching locations; the method further provides a what-if tool for permitting quick business decisions on the economic viability of initiating or terminating business relationships with carriers.

The heuristic of the present invention is preferred because of its simplicity and speed, and because the network operates on variable, estimated traffic loads, so more precision does not, in general, improve the quality of the solution. However, these traffic loads tend to correlate very well over specific hours of the day and days of week (e.g., Sunday at 2 PM traffic or weekday traffic at 1 1 AM), thus, historical demands can be used as inputs to the simulator

to accurately predict the consequence of changes in the interconnectivity of the network on the consequent flow and cost.

While it is generally assumed that traffic will be distributed proportionally as it increases, the approach here recognizes that as traffic is increased there are certain points at which the configuration of the network will change due to links (i.e., carriers or tandems) hitting capacity. By recursively determining the next link that will hit capacity we can increase traffic in a minimal number of discrete steps and calculate the impact of these changes at each step.

A method of determining call routing within a telephone system network comprising a plurality of carriers, the method comprising: determining an ordering of the carriers at a specified location (Lj); determining the traffic demand for the location (Lj) for each carrier (Ci) that has an order 1 ; determining the total traffic demand TDCi of all locations where the order of the carrier (Ci) is 1 and which can possibly terminate on Ci either because the traffic comes directly into the switch Ci is on or it can reach that switch via tandem connections; determining the ratio of CPi the capacity of carrier Ci to the total traffic demand TDCi for each carrier (Ci) that has an order 1 ; if the ratio of CPi to the total traffic demand is greater than 1, then allocating all the traffic at each location (Lj) to the carriers (Ci) which are order 1, or if the ratio of CPi to the total traffic demand is 1 or less , then determining the smallest overflow ratio OFRCi = CPi /TDCi (carrier capacity to the total traffic demand where carrier is order 1) for any carrier (Ci) that has an order 1. Call that minimal overflow ratio OFRmin; determining the value of OFRmin x LDjk for carrier (Cj) having an order 1 at each location (Lk), wherein LDjk is the demand at location Lk where Cj is order 1. Note that since OFRmin was the smallest overflow ratio in the graph,

we insure that by applying this ratio to the total demand, on any other carrier Cj we will not overflow Cj; updating the capacity CPj of carrier (C) to CPi- OFRmin x TDCi; and updating the demand LDj at each location Lj to Lj - OFRmin x LDj; and removing each carrier (Ck) which has reached capacity and determining the next available carrier at each of these locations.

The method further comprising repeating the aforementioned steps until all the traffic demand is apportioned to the carriers.

Additionally, there is a tandem from another switch to the carrier (Ci) and if the order of the tandem is also 1 including the traffic demand to location (Lj) from a remote location as part of the total demand (TDCi) on the carrier (Ci).

Additionally, tandem connections between switches are accommodated by placing them in the route string at a position based on the rate of the cheapest remote terminating carrier which is not at capacity for a location the tandem is intended to direct traffic to. Thus, when a tandem is order 1 this is because there is a remote carrier that is order 1 on that switch to the location which is additionally cheaper than any carrier on the originating switch of the tandem for that location and which can be reached by the tandem. Thus, any traffic on the originating switch of the tandem to the location will be directed to the carrier on the remote switch. Thus, the demand seen by that remote carrier at a location will be a sum of the demand to that location originating on the switch the carrier is on and the demand to that location originating on the switch the tandem originates on. Consequently, it follows that the demand on a tandem on a switch is the sum of demands to all locations on the switch where the tandem is order 1 due to the remote carriers they reach being cheaper than any carrier on the originating switch of the tandem.

The method may further comprise the step of assigning a portion of traffic demand at the location (Lk) to carrier (Cj) such that the traffic demand will not overflow the carrier (Cj) and apportioning the traffic demand based on OFRmin. Furthermore, carrier (Cj) receives tandem traffic, such that OFRmin will be applied to the traffic originating on the switch that the tandem connected to the switch that carrier (Cj) is on. Further comprising updating unassigned traffic demand at each location (Lj) to LDj- OFRmin x LDjk.

An alternative embodiment comprises a method of determining call routing within a telephone system network comprising a plurality of carriers, the method comprising varying the capacity of a carrier or switch to switch connection to see the impact on total of routing historical traffic and comparing to actual cost. This embodiment may further comprise the step of negotiating a change in capacity to an existing carrier or capacity on an internal switch to switch connection.

Additionally, this method further comprises the steps of: determining an ordering of the carriers at a specified location (Lj); determining the traffic demand for the location (Lj) for each carrier (Ci) that has an order 1 ; determining the total traffic demand TDCi of all locations where the order of the carrier (Ci) is 1 and which can possibly terminate on Ci either because the traffic comes directly into the switch Ci is on or it can reach that switch via tandem connections; determining the ratio of CPi the capacity of carrier Ci to the total traffic demand TDCi for each carrier (Ci) that has an order 1 ; if the ratio of CPi to the total traffic demand is greater than 1, then allocating all the traffic at each location (Lj) to the carriers (Ci) which are order 1, or if the ratio of CPi to the total traffic demand is 1 or less , then determining the smallest overflow ratio OFRCi = CPi /TDCi (carrier capacity to the total traffic demand

where carrier is order 1) for any carrier (Ci) that has an order 1. Call that minimal overflow ratio OFRmin; determining the value of OFRmin x LDj k for carrier (Cj) having an order 1 at each the location (Lk), wherein LDjk is the demand at location Lk where Cj is order 1. Note that since OFRmin was the smallest overflow ratio in the graph, we insure that by applying this ratio to the total demand on any other carrier Cj we will not overflow Cj; updating the capacity CPj of carrier (C) to CPi- OFRmin x TDCi; updating the demand LDj at each location Lj to LDj — OFRmin x LDj; and removing each carrier (Ck) which has reached capacity and determining the next available carrier at each of these locations.

Still yet another embodiment of the present invention includes a method of determining call routing within a telephone system network comprising a plurality of carriers, the method comprising: assessing the behavior of the network based on predetermined routing table settings, thereby estimating traffic loads on certain of the carriers; and estimating the costs of diverting telephone traffic to at least one other carrier at preset switching locations. This embodiment may further comprise the step of initiating or terminating a business relationship with at least one the carrier based on the cost estimates and/or estimated traffic load.

Additional, this method further comprises the steps of: determining that the traffic is increasing at certain the carriers, such that the carrier is approaching its traffic capacity limitation; determining the next the carrier that will likely reach its traffic capacity; and increasing the traffic in a minimal number of discrete steps to still other the carriers and calculating the impact that the increasing will have on the other carriers.

A media comprising a computer implement method comprising the following steps: determining an ordering of the carriers at a specified location (Lj); determining the traffic demand for the location (Lj) for each carrier (Ci) that has an order 1 ; determining the total traffic demand TDCi of all locations where the order of the carrier (Ci) is 1 and which can possibly terminate on Ci either because the traffic comes directly into the switch Ci is on or it can reach that switch via tandem connections; determining the ratio of CPi the capacity of carrier Ci to the total traffic demand TDCi for each carrier (Ci) that has an order 1 ; if the ratio of CPi to the total traffic demand is greater than 1, then allocating all the traffic at each location (Lj) to the carriers (Ci) which are order 1, or if the ratio of CPi to the total traffic demand is 1 or less , then determining the smallest overflow ratio OFRCi = CPi /TDCi (carrier capacity to the total traffic demand where carrier is order 1) for any carrier (Ci) that has an order 1. Call that minimal overflow ratio OFRmin; determining the value of OFRmin x LDjk for carrier (Cj) having an order 1 at each the location (Lk), wherein LDjk is the demand at location Lk where Cj is order 1. Note that since OFRmin was the smallest overflow ratio in the graph, we insure that by applying this ratio to the total demand on any other carrier Cj we will not overflow Cj ; updating the capacity CPj of carrier (C) to CPi- OFRmin x TDCi; updating the demand LDj at each location Lj to LDj - OFRmin x LDj; and removing each carrier (Ck) which has reached capacity and determining the next available carrier at each of these locations.

This invention can also be modified to simulate shortest path routing through an IP Network. The basic idea is to first determine from each router, for each IP address getting traffic, the link(s) from that router that traffic to the IP address should be sent on, to take the shortest path to the destination IP address. Then all traffic is simultaneously pushed through the network from originating points to the destination IP nodes along the predetermined shortest path links. Again the most overly constrained link is found and the ratio of traffic to capacity is found and then applied to all demands. This causes some links to hit capacity but none to exceed capacity. Now iteratively one applies the process again now ignoring links which hit capacity on previous iterations and based on the remaining available links again determining the links from each router which are on the shortest available paths to each IP address which still has unassigned traffic. Again the remaining traffic is pushed through the network along the currently calculated shortest path links.

This process is repeated until all traffic has been assigned. This algorithm will actually give a more realistic picture of the traffic distribution through the network then would be achieved using standard algorithmic (i.e., not linear programming) multicommodity flow approaches. This is because those approaches work at the level of single shortest paths at a time finding the most flow that can be achieved through that path. Therefore, they ignore the reality that when traffic is flowing through a network there is competition for links and

therefore it is not realistic to treat the problem as if all traffic from a given source to a given sink can flow along the shortest path. Even a linear programming approach will have this problem since if finds a solution which globally minimizes cost or overflow ignoring the fact that the ideal cant be achieved in a dynamic system where flow is simultaneously being directed to numerous connections from multiple sources and there is no global control that will insure that the optimal solution can be adhered to. The approach in the algorithm we are filing considers the interaction among all the incoming traffic flows in a manner which is more consistent with a nonglobally controlled environment.

As to finding the link from each router to each IP address that has traffic that is on the shortest path to the IP address, standard techniques using breadth first search from the IP destinations back through the network can be used. That is we go back a level at a time from the IP destinations. Thus, starting from the routers at the IP destinations we mark each link that terminates at that IP address as being 0 from the IP address and then for the router which is the originating end of each of these links we mark the router as being a distance of 1 from the destination IP addresses and mark all the links which go from the router directly to the router of the IP address (in general there will only be one such link). Then from those routers which are a distance 1 from some IP address we find the routers which are a distance of 2 from some IP address which have not already been marked as being a distance of one from the same IP address. Thus,

we only mark a router as being a distance 2 from a specific IP address if there is no closer path to that IP address from the router. Again we mark all the links from a given router which are a distance 2 to a given IP address. Now because paths can reconverge there can be more than one such link.

Applying this recursively we go back until all sources sending traffic have been reached. If there are E edges in the graph and K IP addresses this takes at most O(E * K) time. Then when pushing traffic through the network to a particular IP address, if there is more than one link from a given router which is on a shortest path to the IP address the traffic is assumed to be equally distributed among these shortest path links.

An additional separate consideration can be applied to the algorithm in general to address a potential problem which will be more significant when dealing with IP networks. The algorithm as described in worst case will bring one edge in the graph to capacity at a time. In an IP network where there can be hundreds of thousands or millions of links to consider this could be slow. However we can round the traffic so that for instance if there is a range of traffic from 1 to 1 million simultaneous packets (or lines used in a telephone network) the traffic and capacities are rounded to the nearest thousand. Thus, there are only values from 1 to 1000 for the traffic. Since on each iteration even the most constrained link will have to have its demand reduced by at least 1 ( since it

is brought down to zero) the max demand through any link through the network will be reduced by at least 1 from the prior maximum demand through the network (if the most constrained link is the max demand link it was reduced by 1 and if it is not a max demand link each of those will have there demand reduced by at least 1 since the same ratio was applied to them) . Thus, in this case in at most 1000 iterations all the rounded traffic will be assigned.

The above-described and other features and advantages of the present invention will be appreciated and understood by those skilled in the art from the following detailed description, drawings, and appended claims.

The implementation of the aforementioned algorithm requires a means for gathering historical traffic data per unit of time (e.g., hour), a set of rates per location and a set of capacities.

A graphical interface can allow the user to run what if experiments by varying capacities, rates, demands, available carriers, and tandem interconnectivity in any combination, and then rerunning the simulation. Cost, carrier and tandem utilization would then be represented as well as deltas from the reference simulation.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 is a schematic representation of a conventional demand network; Fig. 2 is a schematic representation of a conventional unapportioned demand network;

Fig. 3 is a schematic representation of the system of allocating traffic among network alternatives according to the present invention; and

Figs. 4(a) and (b) are tables providing example calculations where initial orders have been assumed based on rates.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The present invention can best be described by referring to Fig. 3, wherein

1) A set of switches Si which receive calls, and direct the calls through various carriers for a. termination, or b. transmission to other switches (which, in turn, can terminate or further forward the calls to still other switches).

2) A set of tandem connections (Tandem connections are inter-switch links for traffic that is destined for termination further downstream) Tij between switch Si and switch Sj which have capacity CTij.

3) A set of Locations Li, each of which can terminate calls which correspond to a specific set of dial strings (Refers to a string of digits designating a called telephone), where these locations are defined consistently in each switch Si.

4) Historical traffic demands DSiLj of calls, which arrive directly into switch Si from a customer, and are destined for location Lj.

5) A set of terminating Carriers CSij on switch Si, who can terminate traffic and have capacity CCSij and rates RCSij.

6) An ordered set of carriers CSLijk on each Switch Si for each Location Lj where the carriers are terminating carriers (discussed in 5) or the tandem carriers (discussed in 2).

_* Determine how the traffic would flow through the network, and estimate the cost of routing the traffic that way.

The method of the present invention helps determine the impact of changes on the network before actually implementing them. This helps save the time, effort and cost of negotiating inter-carrier deals, and of experimentally implementing changes in switch routing tables.

The method assumes (i) the knowledge of historical traffic distribution among switch locations, and (ii) that if all traffic ceases and is then restarted, then at any time after such restart, as traffic increases, the traffic being sent to each location, as a proportion of the historical traffic at the location would be approximately the same for all locations, e.g., if as traffic starts up, at one location 10% of the historical traffic is being taken then at all locations approximately 10% of the historical traffic is being taken (except at very low traffic locations).

The system first looks at the carriers which are first in order at each location. For each carrier CSLijl which is first on switch Si at location Lj, find the total demand to the locations where the carrier is first, i.e. Sum(DSiLj) where the first carrier is equal to carrier CSLij. Thus, for each carrier CSij which is first some where on switch Si get the ratio capacity to total demand where it is first CCSij/ Sum(DSiLj). Find the smallest such ratio OFRmin. Then by the assumption in the prior paragraph if we had increased the traffic from zero until we had reached the ratio OFRmin of the total traffic the carrier Cmin with the OFRmin would hit capacity and every location would have OFRmin proportion

of its total traffic flowing. Thus, at the point when the carrier associated with OFRmin hits capacity each carriers which were first somewhere would be taking OFRmin times the total demand to the locations where it is first. Since we applied the most constraining ratio which results in a carrier hitting its capacity no carrier should have more than its capacity worth of traffic assigned to it after applying this proportion

Subtracting this portion of the total demand to each of these carriers from their capacity we get a remaining capacity and subtracting this portion of the demand from the demand at each location we get a remaining unassigned demand at each location. We can now repeat the process described in the prior paragraph, finding the carriers which are now first at each location and have remaining capacity. The method iterates this process until all traffic has been assigned. After all traffic assigned to carriers, the method calculates the total cost of the assignment.

The above process ignores the fact that there can be traffic which is sent from one switch to another (tandem traffic) en-route to specific locations. Thus the demand to a specific ingress point location does not only originate at the ingress switch, but may "re-originate" (at least in part) on another switch connected via tandem. Therefore, it is necessary to deploy a method to propagate tandem traffic through the network until it gets to a terminating switch.

Consider one location at a time. Assume there are no network loops in traffic to any location, i.e. there is no way that the traffic which originates on the switch can be routed back to that switch to be redirected again. Therefore, if there are N switches in the network, there can be at most N-I instances where traffic could have been directed from another switch for a specific egress location Li. Thus, for any location Li there must be a switch Sk which does not have traffic to Li that came from another switch. Starting with the switches that only have traffic ingress, if the first carrier at Li is a tandem, associate that

demand with that tandem, and add that demand to the demand for Li on the terminating switch of the tandem. Only process a switch when all tandems into the switch for Li have been processed.

This process is repeated for each location. In this way the total demand on each tandem or terminating carrier at each location is determined and the total demand at each location from originating and tandem traffic is determined. The apportioning process described above is then applied.

EXAMPLE

Given a network of interconnected switches, telephone traffic to dial strings that have been grouped into locations, and carriers with rates and capacities, the present invention simulates the way the traffic would flow through the network, and how it would terminate on the carriers. This can be used to determine the impact changes in rates, capacities, demands and interconnectivity on the flow of traffic and the cost of routing the traffic. In addition, it can be used to determine how to best group the dial strings to minimize the impact of rate variations to the different dial strings for given carriers.

The algorithm described here propagates the traffic through the network predicting the order in which the carriers will hit capacity and using this order to distribute traffic until all traffic is distributed.

The following are the steps:

1) Given an ordering of carriers at each location. Let the order of Ci at location Lj be Oij = k if Carrier Ci is the k* carrier in the ordering at location Lj. Note the carrier Ci could be a tandem from one switch to another and therefore the carriers on the remote switch of the tandem will in effect precede the carriers on

the originating switch of the tandem which succeed the tandem as long as the tandem has not reached capacity.

2) For each carrier Ci which had order 1 at some location, let LDij be the demand of location Lj where carrier Ci had order 1.

3) Get the total demand TDCi to all locations where the order of Ci is 1. If there is a tandem from another switch to Ci then if the order of the tandem is also 1 include the demand to Lj from the remote location as part of the total demand TDCi on Ci.

4) For each carrier Ci in 2 get the ratio CPi/TDCi.

5) If no ratio in 4 is less than 1, then all traffic can be taken by the carrier which is first on each route string. Assign traffic at each location to the carriers which are order 1

6) If step 5) is not the case, then find the smallest overflow ratio OFRCi = CPi/TDCi. Ci is then the carrier with the greatest overflow.

7) For all carriers Cj , at each location Lk where Cj is Order 1 find OFRCi x LDj k. Assigning this proportion of traffic at Lk to Cj will not overflow Cj since we are apportioning based on the smallest OFRCi (OFRmin) . Note that for a carrier Cj which is receiving tandem traffic, OFRmin will be applied to the traffic originating on the switch Cj is on. The unassigned demand at each location Lj is then updated to LDj - OFRmin x LDjk.

8) Similarly the Capacity CPi of carrier (Ci) is updated to CPi- OFRmin x TDCi and

9) For each Carrier Ck whose capacity has been fully apportioned, for each location where this has occurred and which still has unassigned traffic, remove the carriers which have reached capacity and determine the next available carrier at each of these locations as in 1. Go to 2.

11) When this process is repeated recursively all demand will be apportioned to carriers.

An example calculation where initial order has been assumed to be based on rates. Note that the tandem connection indicates an internal connections among switches that merely enable the passage of incoming traffic from one switch to the next before egressing to another carrier. For simplicity, it is assumed that the cost of a tandem connection is negligible (since it is, in general, within the originator's network), however, a tandem cost could be added to the carrier cost so that at the originating switch the cost to reach the carrier on the second switch would be higher than the carrier's cost by the tandem cost.

Looking at all Carriers which are Order 1

Cl is order 1 at Ll and L4 so the total traffic to Cl is 110. Its capacity is 100 so CP1/TDC1 = 100/110 = .9

The Tandem is Order 1 at L2 so CPT/TDCT =120/40 = 3

C3 is Order 1 at L3 so CP3/TDC3 = 60/90 = .67

C4 is Order 1 at Ll and L3. However at L3 since there is a tandem connection and its Order is 1 this demand has to be considered as well. So CP4/TDC4 = 90/ (40 + 60 +90) = .48

C5 is Order 1 at L4 so CP5/TDC5 = 80/ 80= 1

C6 is Order 1 at L2 and the Tandem connection is also Order 1 so

CP6/TDC6 = 50/ (40 + 70) = .45

Since C6 has the smallest capacity to demand ratio it will be filled with traffic first.

The traffic has to be assigned proportionally so .45 x 40 = 18 calls are treated as originating on Switch 1 and .45 x 70 = 32 calls are treated as originating on Switch 2.

Thus, on Switch 1 eighteen (18) calls of L2's traffic are assigned to the tandem and on Switch 2 32 calls of L2's traffic originating on Switch 2 are assigned to C6 as well as the 18 Calls of L2's traffic which originated on Switch 1.

Therefore, C6 is now at capacity and the tandem available capacity is 120 - 18 = 102.

We now update the demands at L2. On switch 1 the demand is now 40 — 18 = 22 and on switch 2 the demand is now 70 - 32 = 38.

For all other carriers which are Order 1 at some location we now apportion the traffic to these locations based on the .45 ratio.

For Cl which is Order 1 at Ll and IA, at Ll a demand of .45 x 60 = 27 is assigned to Cl and at L4 a demand of .45 x 50 = 23 is assigned to Cl.

The unassigned demand at Ll is now 60 —27 =33 and at L4 is now 50 — 23 = 27. The capacity of Cl is updated to 100 - (27+23) = 50.

For C3 which is Order 1 at L3 on Switch 1, at L3 a demand of .45 x 90 = 41 is assigned to C3. Thus the unassigned demand on switch 1 is now L3 = 90 — 41 = 59 and the capacity of C3 is updated to 60 - 41 = 19.

For C4 which is Order 1 at Ll and L3 on switch 2, at Ll a demand of .45 x 40 = 18 is assigned to C4 and at L3 a demand of .45 x 60 = 27 is assigned to

C4. So the unassigned demand on Switch 2 for Ll is now 40 -18 =22 and at L3 is now 60-27 =33 and the capacity of C4 is updated to 90 -<18 + 27) = 45.

For C5 which is Order 1 at L4 on Switch 2, at L4 a demand of .45 x 80 = 36 is assigned. Therefore the unassigned demand on Switch for L4 is now 80 - 36 = 44 and the capacity of C5 is updated to 80 - 36 = 44.

We now update the Orders of Carriers at each location where a carrier has hit capacity. Since C6 hit capacity and it was order 1 at location L2 on Switch 2, the Orders of the remaining Carriers at L2 on Switch 2 are reduced by 1. So C4 becomes order 1 at L2 and C5 becomes order 2.

Furthermore, since C6 is at capacity the rate for the tandem on Switch 1 for location L2 is now the rate of C4 which is .10. Note that even though on the first pass we assuming the carriers/tandems were ordered by rate, since the route ordered is fixed we cannot reorder the carriers/tandems. Therefore, the tandem will be first until it hits capacity even though the rate it is directed to is not the cheapest rate accessible from Switch 1 for Location 2. The process is now repeated with the updated values.

Another preferred embodiment of the algorithm can be used where specific routing percentages across carriers are required (as a business practice or as a result of contractual arrangements). That is, rather than the traffic all going to a specific route string at a location, calls are distributed by some pre-specified proportions to a set of route strings at the location. In this case more than one carrier at the location may be designated as "first", since of these routes string at that location has a carrier that is first (which might or might not be first on more than one of the route strings), a carrier that is second etc.

Therefore, when calculating the total demand on a carrier over all the locations where the carrier is first in some route string, for some locations not all

the traffic may be assigned to one specific carrier; rather, the demand could be distributed among multiple carriers. To determine how much of the demand would be assigned to each carrier that is first on a route string at such a location, (i) the pre-specified proportions that determine how traffic is distributed to the different route strings at the location would be applied to the demand; then (ii) the carrier that is first on each of these route strings would get this pre-specified portion of the traffic to the location.

For example, if the demand is 100 at location L and route string 1 is to get 50% of the traffic at L and carrier A is first on that route string, and if route string 2 is to get 30% of the traffic and carrier B is first on that route string, and if route string 3 is to get 20% of the traffic and carrier C is first on that route string, then A would be assigned 50% of the demand to the location or 50 lines, B would be assigned 30 lines and C 20 lines. These are the demands that would be used for this location when calculating the total demands where A, B and C are first at some location. Then, as in the original process, the smallest capacity- to-demand ratio for a carrier would be found, and that ratio would be applied to all demands.

As described previously, this would result in the most constrained carrier now being at capacity and hence it would be removed from the picture for the next iteration. Therefore, in the case described if A was the most constrained carrier after applying the determined ratio, then for the next iteration it would be assumed to have reached capacity; thus D, the carrier that is next on route string 1 at L would get 50% of the unassigned traffic, B would get 30% and C 20%. If A's ratio of capacity-to-demand was .4, then A would be assigned .4 x 50 = 20 lines at L, B would be assigned .4 x 30 = 12 lines at L, and C would be assigned .4 x 20 = 8 lines at L. Therefore, the remaining demand at L would be 100 — 20 — 12 — 8 = 60. Then, on the next iteration, when considering demands to each carrier that it is first in a route string, D would be assigned .5 x 60= 30 at L, B would be assigned .3 x 60 = 18 at L, and C would be assigned .2 x .60 = 12.

These would be the values used to determine which the most constrained carrier at this iteration is. This process would be repeated until all demand is distributed.

Another preferred embodiment of the algorithm can be used where specific routing percentages across carriers are required (as a business practice or as a result of contractual arrangements). That is, rather than the traffic all going to a specific route string at a location, calls are distributed by some pre-specified proportions to a set of route strings at the location. In this case more than one carrier at the location may be designated as "first" since each of these routes string at the location has a carrier that is first (which might or might not be first on more than one of the route strings), a carrier that is second etc. Therefore, when calculating the total demand on a carrier over all the locations where the carrier is first in some route string, for some locations not all the traffic may be assigned to one specific carrier; rather, the demand could be distributed among multiple carriers. To determine how much of the demand would be assigned to each carrier that is first on a route string at such a location, (i) the pre-specified proportions that determine how traffic is distributed to the different route strings at the location would be applied to the demand; then (ii) the carrier that is first on each of these route strings would get this pre-specified portion of the traffic to the location.

For example, if the demand is 100 at location L and route string 1 is to get 50% of the traffic at L and carrier A is first on that route string, and if route string 2 is to get 30% of the traffic and carrier B is first on that route string, and if route string 3 is to get 20% of the traffic and carrier C is first on that route string, then A would be assigned 50% of the demand to the location or 50 lines, B would be assigned 30 lines and C 20 lines. These are the demands that would be used for this location when calculating the total demands where A, B and C are first at some location. Then, as in the original process, the smallest capacity- to-demand ratio for a carrier would be found, and that ratio would be applied to all demands.

As described previously, this would result in the most constrained carrier now being at capacity and hence it would be removed from the picture for the next iteration. Therefore, in the case described if A was the most constrained carrier after applying the determined ratio, then for the next iteration it would be assumed to have reached capacity; thus D, the carrier that is next on route string 1 at L would get 50% of the unassigned traffic, B would get 30% and C 20%. If A' s ratio of capacity-to-demand was .4, then A would be assigned .4 x 50 = 20 lines at L, B would be assigned .4 x 30 = 12 lines at L, and C would be assigned .4 x 20 = 8 lines at L. Therefore, the remaining demand at L would be 100 - 20 - 12 — 8 = 60. Then, on the next iteration, when considering demands to each carrier that it is first in a route string, D would be assigned .5 x 60= 30 at L, B would be assigned .3 x 60 = 18 at L, and C would be assigned .2 x .60 = 12. These would be the values used to determine which the most constrained carrier at this iteration is. This process would be repeated until all demand is distributed.

It should also be noted that the terms "first", "second", "third", "upper", "lower", and the like may be used herein to modify various elements. These modifiers do not imply a spatial, sequential, or hierarchical order to the modified elements unless specifically stated.

While the present disclosure has been described with reference to one or more exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the present disclosure. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the disclosure without departing from the scope thereof. Therefore, it is intended that the present disclosure not be limited to the particular embodiment(s) disclosed as the best mode contemplated, but that the disclosure will include all embodiments falling within the scope of the appended claims.