Least Cost Routing is harder than it looks

All voice network operators are continually looking for ways to cut the cost of delivering outgoing long distance calls. The best way to do this is to use 2 or more Inter-Exchange Carriers (IEC, in FCC-speak) or what you and I might call “long distance service providers,” and cherry pick the cheaper provider for each dialed destination. This approach is called “Least Cost Routing.” Seems simple, right? Well, it’s not, really.

First there is the tyranny of numbers. A Least Cost Routing application typically will use the Local Exchange Routing Guide (LERG) to determine all possible dialed destinations. The LERG defines roughly 450,000 destinations. For each destination you might have a cost proposal from several IEC. We tried evaluating 8 IEC.

So there are several million tests to run simply to derive a single list of the cheapest routes to each possible destination. But this is only the beginning.

Once the list of cheapest routes is compiled, there are several more steps:

  • Collapse consecutive destinations served by the same IEC into a single route.
  • Interleave “special” routes, such as 411, 611, 911, 976 area codes, specific toll-free destinations, etc. Each of these routes may be dedicated to a particular IEC or service provider. This is necessary when the rules of the switch require routes to be lexically sequential. Our Nortel MTX has such rules.
  • Generate a routing file suitable for uploading to your switch from the list of cheap routes

Collapsing consecutive destinations is not difficult, nor is generating a translations file for your switch. Interleaving exceptional routes has proven particularly vexing. There are several conditions that might make this so:

  • Individual LERG destinations can be entire NPA-NXX blocks of 10,000 MDN, or they might be NPA-NXX-Y blocks of 1,000 MDN. The code must determine this and adjust as needed.
  • If the current exception is lexically less than the next destination then it must be interleaved between destinations.
  • If the next destination is a block of 10,000 MDN, then it might be necessary to split it to interleave the current exception.
  • There might be several exceptions back-to-back.

Of course the whole exercise could be attempted using Excel. To ably handle any list having 450,000 members Excel 2007 would be required, as it can manage worksheets having 1.2 million rows, and earlier versions maxed out at 65,000 or so rows. I know of one operator that has taken this approach and has found that it does not work well when it works at all. Apparently the high-end PC frequently crashes during runs.

We continue working on our Perl and SQL approach. Our ultimate goal is to have a solution that can be run frequently, perhaps as often as every month. But certainly whenever we get new lower pricing from the IEC.