Searching Longest Matching Prefix Using B-tree

According to the increasing rate of IP routing table lookups and also their fast update rate growth, many algorithms are introduced to achieve preferred memory size or the required speed in table search and update. Because of popularity of IPv4, many of these algorithms are suitable for IPv4 but cannot be used for the new version of IP, IPv6. Nevertheless new efforts are done to fit the available algorithms and techniques to the IPv6 128 bits range addresses and prefixes. The challenging issues in the design of these prefix search structures are minimizing the worst case memory access, processing and pre-processing time for search and update procedures, e.g. ordinary Tries have a worst case performance of O(32) memory accesses for IPv4 and O(128) for IPv6. Other compressed Tries have better worst case lookup performance however their update performance is degraded. One of the proposed schemes to make the lookup algorithm independent of IP address length is to use a binary search tree and keep the prefix endpoints within its nodes. Actually we need at most 2n nodes for n prefixes. Some new methods are introduced based on this idea. As we have showed in this paper, the prefixes can be stored in a B-tree without the need to consider separate end points. According to the method of storing the prefixes in this scheme, it is the first algorithm which processes the stored prefixes as "Numbers", but not as ranges. We will finally compare our method with recent introduced method, PIBT

کلیدواژه ها:

lookup ، insert ، delete ، LMP ، LPM ، SMV