IP lookup by binary search on prefix length
Waldvogel et al.  have proposed a collection of hash tables (CHT) organization for an IP router table. IP lookup can be done with O(log l/sub dist/) hash-table searches, where l/sub dist/ is the number of distinct prefix-lengths (also equal to the number of hash tables in the CHT). Srinivasan and Varghese [ACM transactions on Computer Systems, Feb:1-40, 1999] have proposed the use of controlled prefix-expansion to reduce the value of l/sub dist/. The algorithm of [V. Srinivasan, 1999] does not minimize the storage required by the prefixes and markers for the resulting set of prefixes. We develop an algorithm that minimizes storage requirement but takes O(nW/sup 3/ + kW/sup 4/) time, where k is the desired number of distinct lengths, n is the number of prefixes, and W is the length of the longest prefix. Also, we propose improvements to the heuristic of [V. Srinivasan, 1999].

title: Efficient construction of multibit tries for IP lookup
abstract: Srinivasan and Varghese (1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose dynamic programming algorithms to determine the strides of optimal multibit fixed-stride and variable-stride tries. We improve on these algorithms by providing alternative dynamic programming formulations for both fixed-and variable-stride tries. While the asymptotic complexities of our algorithms are the same as those for the corresponding algorithms of Srinivasan and Varghese, experiments using real IPv4 routing table data indicate that our algorithms run considerably faster. Our fixed-stride trie algorithm is two to four times faster on a SUN workstation and 1.5 to three times faster on a Pentium IV PC. On a SUN workstation, our variable-stride trie algorithm is between two and 17 times faster than the corresponding algorithm of Srinivasan and Varghese; on a Pentium IV PC, our algorithm is between three and 47 times faster. An added feature of our variable-stride trie algorithm is the ability to insert and delete prefixes taking a fraction of the time needed to construct an optimal variable-stride trie "from scratch."

title: Efficient Dynamic Lookup For Bursty Access Patterns
abstract: Internet (IP) packet forwarding is typically done by finding the longest prefix in a router table that matches the packet's destination address. Although significant effort has been devoted to the development of data structures for static and dynamic router-tables for random packet-access-patterns, considerably less effort has been expended in the development of such structures for bursty access-patterns (i.e., streams of packets in which destination addresses repeat frequently within localized windows of packets). In this paper, we first formulate a variant, ACRBT (alternative collection of red-black trees), of the CRBT (collection of red-black trees) data structure proposed earlier for dynamic router-tables. By replacing the red-black trees used in the ACRBT with splay trees, we obtain the CST (collection of splay trees) structure in which search, insert, and delete take O(log n) amortized time per operation, where n is the number of prefixes in the router table. By replacing the front end of the CST with biased skip lists, we obtain the BSLPT (biased skip lists with prefix trees) structure in which search, insert, and delete take O(log n) expected time. The CST and BSLPT structures are designed so as to perform much better when the access pattern is bursty than when it is not. Experimental results using real IPv4 routing databases and synthetically generated search sequences as well as trace sequences are presented. For extremely bursty access patterns, the CST structure is best. Otherwise, the ACRBT is recommended. Our experiments also indicate that a supernode implementation of the ACRBT usually has better search performance than does the traditional one-element-per-node implementation.

title: Mobility Agent Advertisement Mechanism for Supporting Mobile IP in Ad Hoc Networks
abstract: Mobile IP has been proposed to solve the problem of how a mobile node may roam from its network and still maintain connectivity to the internet. Another emerging wireless architecture, mobile ad hoc networks (MANET), can be flexibly deployed in most environments without the need for infrastructure base stations. Integrating Mobile IP and MANET will facilitate the current trend of moving to an all-IP wireless environment. In this paper we propose an architecture of integrating Mobile IP and MANET based on the on-demand routing protocols. The proposed architecture employs two agent advertisement mechanisms, Mobility Agent Advertisement Mechanism (MAAM) and Aggregation-based Mobility Agent Advertisement Mechanism (AMAAM). In both mechanisms the mobility agent uses periodic beaconing of agent advertisement messages with on-demand routing protocols. Despite its architectural advantage, MAAM has some performance issues to be tackled because it incurs excessive generation of registration request messages of mobile nodes. AMAAM is an enhancement of MAAM for reducing the overhead of the beaconing by aggregating the reply messages of the agent advertisement. The simulation results show that AMAAM can effectively reduce the overhead of periodic agent advertisement and registration process.

title: Mapping Cooperating GRID Applications by Affinity for Resource Characteristics
abstract: The Computational Grid, distributed and heterogeneous collections of computers in the Internet, has been considered a promising platform for the deployment of various high-performance computing applications. One of the crucial issues in the Grid is how to discover, select and map possible Grid resources in the Internet for meeting given applications. The general problem of statically mapping tasks to nodes has been shown to be NP-complete. In this paper, we propose a mapping algorithm for cooperating Grid applications by the affinity for the resources, named as MACA. The proposed algorithm utilizes the general affinity of Grid applications for certain resource characteristics such as CPU speeds, network bandwidth, and input/output handling capability. To show the effectiveness of the proposed mapping algorithm, we compare the performance of the algorithm with some previous mapping algorithms by simulation. The simulation results show that the algorithm could effectively utilize the affinity of Grid applications and shows good performance.

title: CORBA-Based, Multi-threaded Distributed Simulation of Hierarchical DEVS Models: Transforming Model Structure into a Non-hierarchical One
abstract: The Discrete Event Systems Specification (DEVS) formalism specifies a discrete event system in a hierarchical, modular form. This paper presents DEVSCluster, a CORBA-Based, multi-threaded distributed simulation scheme for models specified by the DEVS formalism. The simulator transforms a hierarchical DEVS model into a non-hierarchical one. This transformation can ease the synchronization of the distributed simulation of DEVS models by enabling the transfer of events by direct remote method invocations, not explicit message transfers. By virtue of this feature, we can utilize CORBA for the event handling in DEVSCluster. To show the effectiveness of the proposed simulation scheme, we realize DEVSCluster in Visual C++, and conduct a benchmark simulation for a large-scale logistics system. We compare the performance of MPI and CORBA-based implementations. The performance result shows that the proposed methodology works correctly and performs better than the previous approaches.

title: A Resilient Multipath Routing Protocol for Wireless Sensor Networks
abstract: Wireless sensor networks should be self-configuring, highly scalable, redundant, and robust in dealing with shifting topologies due to node failure and environment changes. The energy of a sensor node is the most important system resource, and one of the best ways of conserving energy is to distribute the routing load across all sensor nodes as much equally as possible. Considering the load balance for conserving energy, multipath routing protocols have been employed in sensor networks. In this paper we present a resilient multipath routing protocol based on AODV, named as RMRP, for wireless sensor networks. RMRP is an AODV-based multipath routing protocol in which sensor nodes setup double routing paths toward sink nodes in an AODV fashion and select one of them randomly for forwarding a packet. RMRP proposes a resilient route maintenance scheme which repairs broken links by utilizing localized information around neighbor nodes of the broken link, thereby reducing the flooding range of control messages. To show the effectiveness of the proposed route maintenance scheme, we evaluate the performance enhancement of the proposed scheme by ns2-based simulation.

title: Cognitive and task influences on Web searching behavior
abstract: Users' individual differences and tasks are important factors that influence the use of information systems. Two independent investigations were conducted to study the impact of differences in users' cognition and search tasks on Web search activities and outcomes. Strong task effects were found on search activities and outcomes, whereas interactions between cognitive and task variables were found on search activities only. These results imply that the flexibility of the Web and Web search engines allows different users to complete different search tasks successfully. However, the search techniques used and the efficiency of the searches appear to depend on how well the individual searcher fits with the specific task.