Routingtabels

[Ulf Wiger]

You can make a pretty elegant prefix-match implementation using an
ordered_set ets table. Whether it's efficient enough depends on what
you're doing, but the AXD 301 ATM Switch is using a similar
implementation (we used to have a linked-in driver, but found this
approach efficient enough.)

The following shell dialog illustrates the principle.

Eshell V4.9.1.1  (abort with ^G)
1> ets:new(ana,[ordered_set,named_table]).
ana
2> ets:insert(ana, {"255.255.254", data}).
true
3> ets:insert(ana, {"255.255.252", data}).
true
4> ets:insert(ana, {"255.255.250", data}).
true
5> Prefix1 = ets:prev(ana, "255.255.254.13").
"255.255.254"
6> Prefix2 = ets:prev(ana, "255.255.251.13").
"255.255.250"

To find out whether the prefix matches, you can use e.g.
lists:prefix/2.

7> Prefix2 = ets:prev(ana, "255.255.251.13").
"255.255.250"
8> lists:prefix(Prefix2, "255.255.251.13").
false

/Uffe


On Wed, 24 May 2000, Ingela Anderton wrote:

>
>Hello!
>
>I am trying to figure out if you can implement a ruoting table in
>Erlang that is efficient enough or if you have to use c? Someone in the 
>project that I currently work in made a version using ets-tables and
>looking backwards starting with the mask 255.255.255.255 and then
>trying 255.255.255.254, 255.255.255.252 etc. until they
>find a entry and then they know that they have the longest prefix
>match. As far as I understand it would be a better idea to use some
>kind of tree-based algorithm. Would it be possible to do this
>efficiently in Erlang?
>
>

-- 
Ulf Wiger, Chief Designer AXD 301         <ulf.wiger@REDACTED>
Ericsson Telecom AB                          tfn: +46  8 719 81 95
Varuvägen 9, Älvsjö                          mob: +46 70 519 81 95
S-126 25 Stockholm, Sweden                   fax: +46  8 719 43 44