One of the most important algorithms in an IP router is the Longest Prefix Matching which is used in finding the next hop and/or output port for each incoming packet. In an IP router, the destination IP address is extracted from each incoming packet. Then, its Longest Matching Prefix will be chosen from the set of prefixes stored in the routing table. According to the growing rate of communication links, much effort has been done to improve the required time for prefix search and table updates. In this thesis, a novel concept is introduced for processing, storing and comparing the prefixes, considering each prefix as a number. The properties of this kind of treating prefixes leads to fast search and update of routing tables in a way that the proposed schemes are capable of storing prefixes in balanced trees. As an advantage, these structures make the prefix search and update times limited to O(log n) . Also, the proposed idea is mathematically modeled using a novel concept of relations. In addition, a lower bound is introduced for the storage requirements in coding a set of prefixes. Finally, the proposed algorithms are compared with some of the competitive solutions. Keywords: Longest Prefix Matching, Longest Matching Prefix, Coded Prefixes, Scalar Prefixes, Double Relation Chains
