Least Cost Routing explained

Longest Prefix Match

Typically call routing in Telecoms, including VoIP is done based on the longest prefix match basis. That means if there are several prefixes matching number, the longest one will be the right match. Let's take an example this routing table:

(table1)

If the call is made to number 12127773456, it is designated to New York, because it matches both US/Canada code 1 and New York prefix 1212. However, the length of New York prefix 1212 is longer (4 digits) than US/Canada code 1 (1 digit), so New York takes precedence. If the call is made to number 13215551200, it is designated to general US/Canada breakout because the above table does not include specific breakout for Florida (which is 1321).

The call to 44712345678 will be similarly designaed to UK Mobile, whereas call to 44776612345 with be UK Mobile Vodafone because it matches prefix 447766.

Route Cost

Each destination has its cost. Lets add a cost column to the example table:

(table2)

Therefore call to New York will cost 6 units, whereas to any other US/Canada destination starting with 1 it will be 5 units.

More than one choice

There can be more than one provider of any given destination, and the cost of these providers might vary. Lets add cost columns for more route providers:

(table3)

Above example shows 3 different priced routes to US and NY, and some routes to UK. Note, that not all providers can offer all routes. In the example above provider 2 does not offer UK Mobile at all (incl. Vodafone), and provider 3 does not provide UK routes except mobiles.

Least Cost Routing

Least Cost Routing (LCR) is method of finding the cheapest route for the given destination based on several available routes and the costs associated with these routes. The tables as above are used to determine the cheapest routes to the specific destination. Note, that there can be specific maximum prices. For example, user may be willing to pay maximum 5 units for calls to US/Canada. Therefore Provider 3 is out of routing because its cost is 6.

Since the real life code tables are far larger than example (can have 20-50k rows), the problem of finding cheapest route becomes more complex.

Code Range Normalization

Additionally, there is the problem of so called normalization. Not all providers have exactly same breakouts. Lets see 2 table below:

Provider 1

(table4)

Provider 2

(table 5)

As you see, Provider 1 will ask price of 100 units for all calls going to UK Premium service numbers starting with 449, whereas Provider 2 will obviously ask only 25 because it does not have specific prefix, and call fill fall into general 44 range.

In real life the differences are very frequent and must be addressed when building a LCR system.

To summarize, LCR system needs to be able to provide following functions:

1. To have up-to-date routing and cost information and be able to serve in real time;
2. Respect longest prefix match requirement;
3. Respect maximum allowed price requirement;
4. To be able to return least cost choices in the order of increasing costs, i.e. from cheapest to most expensive;
5. To take care of code range normalization, i.e. differences between code breakouts from various providers.