Scalar Prefix Search: A New Route Lookup Algorithm for Next Generation Internet
Currently, the increasing rate of routing lookups in Internet routers, the large number of prefixes and also the transition from IPV4 to IPV6, have caused Internet designers to propose new lookup algorithms and try to reduce the memory cost and the prefix search and update procedures times. Recently, some new algorithms are proposed trying to store the prefixes in a balanced tree to reduce the worst case prefix search and update times. These algorithms improve the search and update times compared to previous range based trees. In this paper it is shown that there is no need to treat the prefixes as ranges.