Prefix caching improves the performance of IP lookup by exploiting spatial and temporal locality of IP references. However, it cannot cache non-leaf prefixes, so several prefix expansion schemes have been proposed to handle those prefixes. Such schemes have some drawbacks to incur modification of routing table or severe miss penalty. We propose an efficient prefix expansion scheme which achieves good performance without additional burden to lookup scheme. In the proposed scheme a non-leaf prefix is expanded to the length of the longest immediate descendant prefix when it is cached. Evaluation result shows our scheme achieves very low miss ratio even though it does not increase the size of routing table and cache miss penalty.

High-speed IP address lookup with fast prefix update is essential for designing wire-speed packet forwarding routers. The developments of optical fiber and 100 Gbps interface technologies have placed IP address lookup as the major bottleneck of high performance networks. In this paper, we propose a novel structure named Compressed Multi-way Prefix Tree (CMPT) based on B+ tree to perform dynamic and scalable high-speed IP address lookup. Our contributions are to design a practical structure for high-speed IP address lookup suitable for both IPv4 and IPv6 addresses, and to develop efficient algorithms for dynamic prefix insertion and deletion. By investigating the relationships among routing prefixes, we arrange independent prefixes as the search indexes on internal nodes of CMPT, and by leveraging a nested prefix compression technique, we encode all the routing prefixes on the leaf nodes. For any IP address, the longest prefix matching can be made at leaf nodes without backtracking. For a forwarding table with u independent prefixes, CMPT requires O(logmu) search time and O(mlogmu) dynamic insert and delete time. Performance evaluations using real life IPv4 forwarding tables show promising gains in lookup and dynamic update speeds compared with the existing B-tree structures.

Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.

In this work, we propose a scheme of routing table compaction for IP forwarding engines based on ternary content addressable memory (TCAM). Our scheme transforms the original routing table into a form with only disjoint prefixes. The most prevalent next hop of the routing table is then calculated and the route prefixes corresponding to the next hop are replaced by one TCAM entry. In combination with Espresso-II logic minimization algorithm, the proposed scheme reduces the TCAM storage requirements by more than 75% compared to the original routing tables. We also present an effective approach to support incremental updates.

This letter proposes a fast IP address lookup algorithm based on search space reduction. Prefixes are classified into three types according to the nesting relationship and a large forwarding table is partitioned into multiple small trees. As a result, the search space is reduced. The results of analyses and experiments show that the proposed method offers higher lookup and updating speeds along with reduced memory requirements.

Most routing protocols in MANET use IP addresses as one of the most important routing information. To implement the routing protocol of MANET, the IP assignment in MANET should be solved. Allocating IP addresses is one of current key issues in the MANET, due to the absence of a centralized agent server. Previous methods require a large address space or can not use all the IP addresses of the given IP address space. For that reason, many IP addresses remain unused. To resolve this, we propose an IP address assignment protocol that uses the contiguous IP address assignment strategy without unused IP addresses. Simulations perform on ns-2 and confirm the viability of our protocol.

Secure communication in Mobile Ad Hoc Networks (MANETs) is important as nodes communicate over the wireless medium, which can be easily eavesdropped. Currently, the literature of secure IP address autoconfiguration in MANETs is extremely rare. In this paper, we propose five protocols that provide both secure IP address autoconfiguration and authenticated group key agreement (GKA) to give a more efficient and secure solution for MANET communications. Whenever a dynamic group membership event such as node join, node leave, network merge and network partition occurs, our protocols ensure that the IP address allocation table and group key are updated so that there are no address conflicts and leaving and joining users cannot decrypt future and previous communications respectively. A complexity analysis shows that despite having additional capabilities such as IP address autoconfiguration and key authentication, our protocols are still efficient when compared to other GKA protocols.

We propose an efficient IP address assignment protocol in mobile ad hoc networks, which use a proactive routing protocol. In this method, which is termed the Bisected-Range based Assignment (BRA), a node repeatedly broadcasts an Agent Request to ask for address assignment. If there are one or more neighbor MANET nodes, one of them becomes an agent to select and assign an IP address to the requesting node. We use address location in the IP address space so that each agent maintains its own exclusive address range to be used for address selection, resulting to decrease the possibility of address conflict. If the requesting node cannot discover any neighbor MANET node over pre-determined random agent-search time, it selects by itself an IP address at random from the given address block. We evaluate performance of the basic and enhanced BRAs by computer simulation. It is shown that the basic and enhanced BRAs can reduce address conflict compared with random assignment. It is also shown that the enhanced BRA is superior in terms of control traffic overhead as well as address assignment delay over the random assignment with the strong Duplicate Address Detection.