A Fast Routing Lookup Algorithm Based Trie

With rapid development of Internet, it orders the core router to have the ability of high speed packets forwarding and fast updating.The key to implement this function is data structure of router table and lookup algorithm.This paper proposes a new scheme based multibit Trie tree with a next-hop tree.It consists of a fixed stride routing table based Trie tree and a next-hop tree.For a routing prefix whose length is w, the time for search, insertion, deletion operation are all O ((w-m)/n+1), where m and n are both stride of Trie tree.It solves IP lookup problem with fast updates and has the advantage of simple algorithm, fast lookup and updating easy, and high memory utilization and transition to IPv6 convenient.