LCDial.sh v.1.1

INTRODUCTION AND SYSTEM REQUIREMENTS

LCDial.sh is an AGI script to implement Least-Cost Routing of calls placed to standard telephone numbers. It is intended to run on embedded systems without database facilities or powerful scripting language interpreters, such as the OpenWRT Linux environment for Linksys WRT54GS and similar devices. Therefore, it was written as a script for the shell interpreter ash (http://en.wikipedia.org/wiki/Almquist_shell), an almost complete version of which is embedded in the Busybox executable that provides functionality for most of OpenWRT's basic command-line utilities (the only missing command appears to be "setvar").

Besides ash, LCDial.sh relies upon a few other standard utilities such as sed (GNU version), expr and sort. It works also if the shell is bash rather than ash (please report any incompatibility found). The implementation uses a few slightly exotic features, so compatibility with other shell interpreters should not be assumed as a given.

USAGE

The syntax is almost identical to the Dial command's, but the first parameter is restricted to be a single number in country_code-local_part format. Also, it is possible to specify an additional parameter that represent a ceiling to the acceptable cost-per-minute (expressed in thousands of cents). For example, the following call (in extensions.conf) will ignore routes costing more than 14.5 cents per minute:

_9X. => nnn,1,AGI(LCDial.sh,${EXTEN:1},30,T,,14500)

Leaving that parameter unset sets no ceiling; using 0 makes the script consider only free routes (e.g., to toll free numbers through FWD).

Starting with the version 0.7, an optional 7th parameter to the AGI() call allows to define a suffix for an alternate configuration file, to be used only for that particular call. For example, assuming that the default configuration file (described further below) is /etc/asterisk/lcdialsh/LCDial.sh.conf , a call:

AGI(LCDial.sh,${EXTEN:1},30,T,,14500,xyz)

...will instruct the script to use, instead, the configuration file /etc/asterisk/lcdialsh/LCDial.sh.conf-xyz . This comes handy e.g. to use different sets of providers depending on the context, which may be made dependent on the originator of the other leg of the call.

Starting with the version 1.0, an optional 8th parameter to the AGI() call allows to define the pathname of a shell script (by default located in Asterisk's agi-bin directory, or in any directory if its pathname starts with '/') that, if found and readable by Asterisk, will be executed just before attempting a Dial(), receiving as first parameter the cost of the call in millicents. This script may be used to play an announcement to the caller. For example, a .../agi-bin/announce.sh containing:

#!/bin/sh
cost="$1"
# divide by 1,000 to get cost in cents, rounding up...
# ...but treat < 10 millicents as zero
cost=$((($cost + 990) / 1000))
if [ $cost -gt 0 ]; then # only announce if call is not free
sh_agi_cmd EXEC SayNumber \""$cost"\"
sh_agi_cmd EXEC Background cents
sh_agi_cmd EXEC Background pls-wait-connect-call
fi

...can be invoked through LCDial.sh with a dialplan line like:

exten => _9X.,1,AGI(LCDial.sh,${EXTEN:1},60,,,50000,,announce.sh)

...and it will play "nnn cents, please wait while I connect you a call" just before dialing call to destinations that are not free of charge.

CONFIGURATION

The routes may be provided though two channels: ENUM and rates files.

The existence of an ENUM route is checked first, using Asterisk's EnumLookup application (so, enum.conf should be properly configured: it is recommended to point to both e164.org and e164.arpa). To test this feature, you may access via ENUM the "echo test" number at FreeWorldDialup, dialing one of the following numbers:

8829990613
8781039311613

Starting from version 0.2, if the program "dig" is installed and in the $PATH, the scripts avoids using EnumLookup and instead builds routes from NAPTR records obtained through dig. The domain names searched (e.g., e164.org and e164.arpa) are retrieved from /etc/asterisk/enum.conf .
dig for OpenWRT can be found in the "bind-utils" package: http://tracker.openwrt.org/search/?b=search&query=bind-utils As the package is pretty large, just extract dig with tar or 7zip and place it manually in /usr/bin


If the ENUM method yields no route, or if dialing the route provided by EnumLookup returns CONGESTION or CHANUNAVAIL, the script proceeds to inspect the configuration file LCDial.sh.conf (its full pathname is hardcoded at the beginning of LCDial.sh). This file define a number of providers, one per line, in the following format:

provider rates_file number2URI_rule [number2outdialdigits]

Whitespaces act as separator, and are not allowed to occur in any of the three parameters. Quoting is not allowed with either single or double quotes. Carriage return ('\r') characters are ignored; each line must be terminated by a linefeed (this allows to create them with editors for either UNIX or DOS, but not Mac). Empty lines and lines whose first non-whitespace character is ';' are ignored; however, ';' on non-comment lines are NOT inline comment starters.

The optional number2outdialdigits field, available in version 0.4 or later, is a rule to convert the telephone number into a sequence of digits that will be passed as parameter of the D() option in the Dial() command (replacing sequences specified in the call to LCDial.sh, if any). This is useful in applications such as call card dialing, where some digits have to be dialed AFTER the called party has answered the call. Please note that some FXO analog gateways (like the Sipura SPA-3000) consider the call answered immediately after starting dialing the number, so extra "pause" metadigits will have to be prefixed to the digits string in order to wait for the remote side to answer and start accepting DTMF tones.

Here are four examples:

voipjet rates/voipjet s!^!011!;s!0111!!;s!\(.*\)!IAX2/3462@voipjet/\1!
iaxtel rates/iaxtel s!\(.*\)!IAX2/guest@iaxtel.com/\1@iaxtel!
hkcall rates/hkcall s!.*!SIP/22966487#@spa3kpstn! s!\(.*\)!wwwwwwwwwwww00\1#!;s/\(.\)/w\1/g
fwdout rates/fwdout s!\(.*\)!IAX2/enzom@fwdOUT/\1!

The first field (provider) is just a label, used primarily in error messages. Starting with the version 0.7, it may be optionally followed by a "minimum cost indicator" made by a '>' character followed by an integer (no spaces allowed in between). This declares that the rate file for that provider only contains routes with a cost in millicents/minute higher than that integer, and allows some speed optimization when looking for low-cost (or free) routes: the LCDial.sh script will skip altogether rate files that can't provide routes at a cost below the given limit. Example:

voipjet>999 rates/voipjet s!^!011!;s!0111!!;s!\(.*\)!IAX2/3462@voipjet/\1!

...declares that all VoipJet's routes cost more than 0.999 cent (999 millicents) per minute. Therefore, a call like:

_9X. => nnn,1,AGI(LCDial.sh,${EXTEN:1},30,T,,1000)

...would scan also VoipJet's rate file, but

_9X. => nnn,1,AGI(LCDial.sh,${EXTEN:1},30,T,,999)

...would skip it, as 999 is the maximum acceptable cost, and VoipJet's entry declares that all its routes have a cost higher than that.

The second field (rates_file) points to a file containing information about the termination rates of that provider. If the pathname does not start with a '/', it is assumed to be relative to the same directory of LCDial.sh.conf. The format of the content is specified further below.

The string in the third field (number2URI_rule) is a sed script applicable to the called numbers in order to obtain a URI acceptable by Asterisk (the format of which is generally different from IETF-compliant URI's). Typically, a number2URI for a SIP provider will be:

s!\(.*\)!SIP/\1@sipaccount!

and a number2URI rule for a IAX provider will be:

s!\(.*\)!IAX2/iaxuser@iaxaccount/\1!

More complicated rules may help in formatting special numbers. For instance, the following rule for FWD converts toll-free numbers in a few countries into the format acceptable by FWD to terminate them (see: http://www.freeworlddialup.com/advanced/peering_numbers ):

fwd rates/fwd s!^\(18\|1700\|31800\|44800\|44500\|44808\|47800\|49800\|49130\)!*\1!;s!\(.*\)!SIP/\1@fwd1!


Of course, for those URI's to work in Dial commands, sipaccount and iaxaccount must be defined respectively in sip.conf iax.conf (which must also specify authentication usernames and passwords).

The optional [number2outdialdigits], available in version 0.4 or greater and present in the third example, converts the telephone number into a sequence of digits that will be passed as parameter of the D() option in the Dial() command. This is useful in applications such as callcard dialing, where some digits have to be dialed AFTER the called party has answered the call. Please note that some FXO analog gateways (like the Sipura SPA-3000) consider the call answered immediately after dialing the number, so extra "pause" metadigits will have to be prefixed to the digits string in order to wait for the remote side to answer and start accepting DTMF tones. The example above also inserts an extra 'w' (500 ms pause) between each digit (and metadigit) in order to work around a bug in the SPA-3000 (insufficient separation of successive DTMF digits).

Sub-rules can be chained, as always in sed scripts, with ';' separators.
For example, the following number2URI rule accepts a number in US format (1xxxxxxxxxx or 011x*) and, as first step, massages it to the standard country_code-local_part format; then it converts it into an Asterisk URI to dial through the SIP account "provideracct" which requires no leading '1' for NANPA numbers and "011" before country code of numbers to other countries:

s!^!011!;s!0111!!;s!\(.*\)!SIP/\1@provideracct!

HOW IT WORKS

The script scans the rates files for each provider in order to find, in each one, the best match with the telephone number to be dialled. "Best match" is defined as the entry containing the longest prefix which is a substring of the number to be dialled, starting from the leftmost digit of both. Some provider rates files may provide no matches at all, and in that case they are ignored, unless they contain a line with a "default prefix" (see below). If no match can be found with any provider, the script fails, logs an error to Asterisk and hangs up.
The best-match entries for each provider are then sorted in ascending order of cost, and tried in sequence by passing the URI obtained by number and provider's number2URI rule to the Dial application. If Dial returns setting DIALSTATUS to anything different from CONGESTION or CHANUNAVAIL, the script hangs up and terminates normally. Otherwise, the script tries the next entry (if any) or terminates logging an error message.
Starting with the version 1.1, two providers with same cost are tried based on their position in the configuration file. Before, they were sorted based on the alphabetical order of their name, which makes little sense and makes it difficult to define preferences among same-cost providers.

PERFORMANCES CONSIDERATIONS

Despite the fact that rates files are fully sequentially scanned, the inner loop is performed by sed which is quite efficient. Typically, on a WRT54GS (a 200-MHz 4712 Broadcom CPU) the scanning takes 230 uS per line; a typical 2000-line rates file is scanned in less than half second.

FORMAT OF THE RATES FILES

They are plaintext files with a name equal to the one referenced in the configuration file, and contain a number of lines in the format:

prefix cost_in_thousands_of_US_cent

Any amount of whitespace separates the two parameters, both of which can only contain decimal digits.

For example:

46769 37210
4679 37210
47 1650
474 17450

The first parameter is a prefix, starting with country code and continuing with the digits to be dialled next. No '+' or IDD access codes such as "011" are required or allowed; NANPA numbers (for US, Canada and Caribean region) must start with "1". A prefix consisting of a single '-' represents a default: its rate is the one charged by the provider for numbers not matching any other prefix in the file. If that line is not present, it is assumed that the provider will decline termination of calls to destinations not listed in the rates file.

The second number is the cost to dial a number starting by that prefix, expressed in thousands of cents of US dollar. Starting with the version 0.8, a cost equal to a single exclamation mark ("!") can be used as "exclusion" mark, as equivalent of "infinite cost". This new formalism, unlike the previously-used "9999999" hack, allows to put in the same ratefile two line for the same destination, one with exclusion marks and another with an actual cost, and have the latter prevail. It's an important feature because it allows to join together fragments for e.g. landline-only entries (with "!" lines excluding cellular codes) and cellular-only entries, and obtain the intended effect of enabling both landline and cellular destinations; this is used in the new "automated generation of rate files" feature described further below in this document.

Rate files don't need to be sorted, because finding the best match requires the script to read all the lines anyway. This is achieved through a (deeply unreadable) sed script, with the performances mentioned above.

Starting from the version 0.3, each line in the rate file may contain one or more additional integer parameters representing start time, end time and weekdays of the interval when the tariff applies. The format for the time fields is hhmm in 24-hour format (like the output of the shell command "date +%H%M"). If there is only one parameter, this is assumed to represent the start time. Two parameters represent start and end time (so that a missing second parameter is equivalent to one equal to "2359") and the rate apply to every day of the week. A third parameter, if present, represent the days of the week to which the rate applies (0 = Sunday, 1 = Monday, ... 6 = Saturday).

For example:

12345 2160 2000 0759 06

...means that the prefix 12345 will be billed at the rate of 2.16 cents/minute between 8 pm and 7:59 am of the next day, and the tariff will apply for calls started on Saturday or Sunday. The line will be disregarded for calls started at any other time.

Starting from the version 0.4, anything on a line following a ';' or '#', as well as that character itself, will be ignored. That allows to comment out lines without deleting them.

AUTOMATED GENERATION OF RATE FILES

Starting from the version 0.8, rate files may be automatically built from two other components: provider files (with names starting by "p_") and country files (with names starting by "c_"). Both types are physically located in the same directory as the rate files.
Country files are fragments of rate files, with exactly the same format. They typically contain the rates for a single country, with the same syntactical rules as the rate files.
Provider files are lists of country names, i.e. names of country files stripped of the initial "c_", one per line without further formatting. They are used to produce rate files with the same name but stripped of the initial "p_", using criteria similar to the "make" utility. The thing works as follows:
When LCDial.sh starts, it goes to check, for each provider file, if the derived rate file has a timestamp more recent the the one on the provider file itself and all the country files of the countries referenced in the provider file. If not (i.e., if either provider file or referenced country file was changed after the last change to the rate file) LCDial.sh rebuilds a fresh rate file by pasting together the referenced country files, and removing comments or useless whitespace.
This procedure is especially handy to keep the ratefiles current with the "free destinations" offers by providers affiliated to Finarea SA / Betamax GmbH: every time a free destination is added or removed, the user will just have to update the provider file, and the ratefile will be automatically updated. Of course, country files for countries referenced in all provider files must have been prepared in advance.

A FASTER ALTERNATIVE, FOR FREE ROUTES ONLY

Finding the least-cost route with many providers and a large number of destinations per provider can be rather slow on platforms with limited CPU horsepower: on OpenWRT, it may add several seconds to the dialling cycle. Starting with the version 0.9, a simpler alternative exists limited to finding free (rather than lowest-cost) routes. The script /usr/sbin/buildfreeroutes uses the information in the p_ and the c_ files mentioned in the previous section, as well as the "number2URI" sed rules in LCDial.sh.conf, to build a fragment of dialplan that can be #include'd in extensions.conf, and referenced by other dialplan lines through a macro. For example, let's suppose we want to call such macro "cx". All we have to do is to execute the following command at the shell prompt:

buildfreeroutes -v cx

("-v" enables "verbose mode", and is optional. Executed with no parameters, it prints a "usage" help).

The execution of such command will create a file named "cx.inc" in the same directory as LCDial.sh.conf, that can be included in the dialplan by placing at the end of extensions.conf a line like:

#include /etc/asterisk/lcdialsh/cx.inc

From the dialplan, its content can be used by lines such as:

exten => _00X.,1,Macro(cx,${EXTEN:2})

...which are basically equivalent to:

exten => _00X.,1,AGI(LCDial.sh,${EXTEN:2},,,,3)

...but execute MUCH faster. There are, however, some important semantic differences between the two:

1. AGI(LCDial.sh...) always returns. Macro(cx,...) only returns if the call could not be established due to lack of free routes, or for channel-related failures: in which case, ${DIALSTATUS} will be set to either CHANUNAVAIL or CONGESTION. It will not return in case of BUSY, ANSWER or NOANSWER.

2. Macro(cx,...) will not make any use of either number2outdialdigits patterns in LCDial.sh.conf or time-of-day validity parameters in the c_files.

Due to its characteristics, it makes sense to place calls to Macro(cx,...) just before calls to AGI(LCDial.sh...) without zero-cost restrictions: if a free route exists, it will be found fast; if not, the control will pass to LCDial.sh to look for the cheapest paid route. For example:

[...]
exten => _9X.,4,Macro(cx,${EXTEN:1})
exten => _9X.,5,AGI(LCDial.sh,${EXTEN:1},60,,,50000) # max USD 0.5/min
[...]

Please note that free routes will be created in the .inc file ONLY for providers with BOTH a p_ file (to define the destinations) and an entry in LCDial.sh (for the "number2URI" rule).

SIMPLE TOOLS FOR RATE FILES

Rates files may be handcrafted starting from the variety of formats supplied by each termination provider (comma-delimited or Excel files, HTML tables, etc.) which often are in US-specific format, with prefixes for destinations outside North America starting by "011"; using tools makes the task much easier. Here are a few suggestions for one-line sed filters (accepting an input from stdin and producing an output to stdout):

- Adding the country code "1" to prefixes NOT starting with "011":

sed -e '/^011/!s/^/1/'

- Removing "011" access codes from non-US numbers:

sed -e 's/^011//'

- Reformatting Voxee- or Gafachi-derived formats:

sed ':1;s/\([0-9]\+\)[^0-9]\+\([0-9]\+\)[^0-9]\+\([0-9]\+\)/\1\3 \2\n\1 \2\4/;t2;b;:2;P;s/.*\n//;/[0-9]\+[^0-9]\+[0-9]\+[^0-9]\+[0-9]\+/t1;d'


It converts forms like these (prefix, cost, subprefix list), derived from Voxee's rates tables:

18000 1264
20376 1264 "235&772,774"
17508 1268
19212 1268 "4,7,406,409,464,723,724,725,726,727,728,729,764,770,771,773,774,775"
7392 1242
7392 1242 "357,359,457"
17340 1246
17928 1246 "23,24,250,251,252,253,254"
9000 1441

Into:

18000 1264
20376235 1264
20376772 1264
20376774 1264
17508 1268
192124 1268
192127 1268
19212406 1268
19212409 1268
19212464 1268
19212723 1268
19212724 1268
19212725 1268
19212726 1268
19212727 1268
19212728 1268
19212729 1268
19212764 1268
19212770 1268
19212771 1268
19212773 1268
19212774 1268
19212775 1268
7392 1242
7392357 1242
7392359 1242
7392457 1242
17340 1246
1792823 1246
1792824 1246
17928250 1246
17928251 1246
17928252 1246
17928253 1246
17928254 1246
9000 1441

- Optimizing files. Once the ratefile is SORTED in ascending lexicographical order, remove lines with prefix as superstring of (or same as) an immediately preceding prefix and same rate. NOTE: it only works if each line only contains two fields; it produces undefined output if additional parameters are present on each line.


sed -e ':1;1!h;$!N;/^[^0-9]*\([0-9]\+\)[^0-9]\+\([0-9]\+\)[^0-9]*\n[^0-9]*\1[0-9]*[^0-9]\+\2/!{P;D};g;b1'

From the input:

123 45
1234 44
456 28
4561 28 << These two lines...
4562 28 << ...are redundant
4563 30
789 90

it produces:

123 45
1234 44
456 28
4563 30
789 90

GATHERERS FOR RATE FILES

Starting from the version 0.5, the package contains ash scripts to build rate files for some providers starting from the comma-delimited tables made available by the providers on their websites. At present, gathering scripts are available for Teliax and VoipJet, and should keep working unless the respective providers change format or URL of their tables... In any event, in case or error they should terminate without corrupting the existing rate files (please report bugs or problems). The scripts are stored in /usr/bin and may be executed by cron jobs with entries like:

10 10 * * * /usr/sbin/getratesteliax /etc/asterisk/lcdialsh/rates/teliax asterisk.asterisk
15 10 * * * /usr/sbin/getratesvoipjet /etc/asterisk/lcdialsh/rates/voipjet asterisk.asterisk

Besides extracting the relevant fields and converting the rates to millicents, as required by LCDial.sh, they also perform some optimization by removing entries whose prefix is a superstring of (or same as) another prefix and whose rate is the same, as described in the previous section. This optimization manages to shrink Teliax' current rate file from 2703 to 2349 lines, and VoipJet's from 2704 to 2486 lines.
Starting from the version 0.5a, the gatherers refrain from updating their rate files (located in directories mapped to flash memory) if there have been no changes from the current one. This avoids unecessary wear and tear of the flash memory device.

Also, this release includes a small "Termination rates check" web application written for Haserl (http://haserl.sourceforge.net/ , http://tracker.openwrt.org/search/?b=search&match=sub&query=haserl ). It requires the version 0.5 (or higher) of LCDial.sh and it expects it to be installed at /usr/lib/asterisk/agi-bin/LCDial.sh ; Haserl is expected to be in /usr/bin/haserl (both locations may be changed by editing checkrates.cgi). The IPKG package installs checkrates.cgi in /www/cgi-bin/ , but any CGI directory will be fine for it to run.