1256853
Efficient Construction of Pipelined Multibit-Trie Router-Tables
Efficient algorithms to construct multibit tries suitable for pipelined router-table applications are developed. We first enhance the 1-phase algorithm of Basu and Narlikar, obtaining a 1-phase algorithm that is 2.5 to 3 times as fast. Next, we develop 2-phase algorithms that not only guarantee to minimize the maximum per-stage memory but also guarantee to use the least total memory subject to the former constraint. Our 2-phase algorithms not only generate better pipelined trees than those generated by the 1-phase algorithm, but they also take much less time. A node pull-up scheme that guarantees no increase in maximum per-stage memory as well as a partitioning heuristic that generates pipelined multibit tries requiring less maximum per-stage memory than required by the tries obtained using the 1-phase and 2-phase algorithms are also proposed
2500739
Efficient construction of multibit tries for IP lookup
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."
39411693
IP lookup by binary search on prefix length
Waldvogel et al. [ACM SIGCOMM, 1997, 25-36] 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].
21768633
IP Lookup by Binary Search on Prefix Length
Waldvogel et al.9 have proposed a collection of hash tables (CHT) organization for an IP router table. Each hash table in the CHT contains prefixes of the same length together with markers for longer-length prefixes. IP lookup can be done with O(log ldist) hash-table searches, where ldist is the number of distinct prefix-lengths (also equal to the number of hash tables in the CHT). Srinivasan and Varghese8 have proposed the use of controlled prefix-expansion to reduce the value of ldist. The details of their algorithm to reduce the number of lengths are given in [7]. The complexity of this algorithm is O(nW2), where n is the number of prefixes, and W is the length of the longest prefix. The algorithm of [7] 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(nW3 + kW4) time, where k is the desired number of distinct lengths. Also, we propose improvements to the heuristic of [7].
42190976
Efficient Dynamic Lookup For Bursty Access Patterns
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.
26550730
Performance of Service Location Protocols in MANET Based on Reactive Routing Protocols
Automatic service discovery, the problem of discovering service providers by specifying desired properties of services, is an important and necessary component for collaboration in the ubiquitous computing environment such as MANET. This paper investigates the effects of the on-demand route discovery on the performance of service location protocols in MANET based on on-demand routing protocols. We first design a service discovery architecture in MANET based on AODV and evaluate both the distributed and centralized versions of the architecture by simulation. For evaluating the performance, we examine such performance metrics as service hit ratio, service discovery time, and control message overheads. The results show that the distributed scheme outperforms the centralized scheme in most simulation scenarios because of the on-demand routing overheads.
6524269
Real-time foreground-background segmentation using codebook model
We present a real-time algorithm for foreground-background segmentation. Sample background values at each pixel are quantized into codebooks which represent a compressed form of background model for a long image sequence. This allows us to capture structural background variation due to periodic-like motion over a long period of time under limited memory. The codebook representation is efficient in memory and speed compared with other background modeling techniques. Our method can handle scenes containing moving backgrounds or illumination variations, and it achieves robust detection for different types of videos. We compared our method with other multimode modeling techniques. In addition to the basic algorithm, two features improving the algorithm are presented-layered modeling/detection and adaptive codebook updating. For performance evaluation, we have applied perturbation detection rate analysis to four background subtraction algorithms and two videos of different types of scenes.
26299662
A Resilient Multipath Routing Protocol for Wireless Sensor Networks
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.
1648937
Optimizing multidimensional index trees for main memory access
Recent studies have shown that cache-conscious indexes such as the CSB+-tree outperform conventional main memory indexes such as the T-tree. The key idea of these cache-conscious indexes is to eliminate most of child pointers from a node to increase the fanout of the tree. When the node size is chosen in the order of the cache block size, this pointer elimination effectively reduces the tree height, and thus improves the cache behavior of the index. However, the pointer elimination cannot be directly applied to multidimensional index structures such as the R-tree, where the size of a key, typically, an MBR (minimum bounding rectangle), is much larger than that of a pointer. Simple elimination of four-byte pointers does not help much to pack more entries in a node.
This paper proposes a cache-conscious version of the R-tree called the CR-tree. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy almost 80% of index data in the two-dimensional case. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading O's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. Our experimental and analytical study shows that the two-dimensional CR-tree performs search up to 2.5 times faster than the ordinary R-tree while maintaining similar update performance and consuming about 60% less memory space.
17794843
TCP throughput analysis under transmission error and congestion losses
This paper analyzes the performance of a large population of long lived TCP flows experiencing random packet losses due to both random transmission errors and congestion created by the sharing of a common tail drop bottleneck router. We propose a natural and simple model for the joint throughput evolution of the set of TCP sessions under such a mix of losses. For the case of Poisson transmission errors, we show that the asymptotic model where the population tends to infinity leads to a well defined and tractable dynamical system. In particular, we get the mean value of the throughput of each session as a function of the transmission error rate and the synchronization rate in the bottleneck router. The large population asymptotic model has two interesting and non-intuitive properties: 1) there exists a positive threshold (given in closed form) on the transmission error rate above which there are no congestion losses at all in steady state; 2) below this threshold, the mean throughput of each flow is an increasing function of the transmission error rate, so that the maximum mean value is in fact achieved when the transmission error rate is equal to this threshold. The finite population model and models based on other classes of point processes are also studied. In particular, a sufficient condition is obtained for the existence of congestion times in the case of arbitrary transmission error point processes.