An Improved Radix Tree for Routing Tables

			     Bharat Madan
			      IBM Corp.

			      Abstract:

Routing is an important issue in intra and inter working. Every host
(or a router) on a network maintains a routing table which gives the
destination MAC address (intra-network case) or the next hop network
e.g.  IP address (inter-network case). For every outgoing datagram,
this table has to be searched for this address. Consequently, it is
important to have an efficient implementation of the so called routing
table.

'Radix tree' is a binary tree which has been used to implement the
routing table. Radix tree can perform all the three common operations
viz. searching for a route, adding a route and deleting a route fairly
efficiently. However, often the initial search for route may result in
failure which leads to backtracking. For a large network with many
sub-nets may result in a radix tree which is deep and a result back
tracking which is expensive in terms of time.

In this talk we will describe a modification to the existing radix
tree implementation which substentially reduces the back-tracking
overheads. This modification consists of incorporating threads in the
terminal nodes which lead directly to an ancestor node to reached in
case of backtracking, thus increasing the routing table
efficiency. The three operations viz. search, add and delete are
modified accordingly to support this so called 'threaded radix tree'.