IP-multicast is a bandwidth efficient transmission mechanism for group communications. Reliability in IP-multicast, however, poses a set of significant challenges. To address the reliability and scalability issues in IP-multicast, this paper proposes a novel, highly distributed, and lightweight overlay peer-to-peer retransmission architecture that exploits path-diversity by taking advantages of both IP-multicast and an overlay network. An approach that leverages both disjoint-path-finding and periodic selective probing to take into account peer's recent packet loss probability, retransmission delay and recent retransmission success rate is proposed to effectively construct an efficient and dynamic overlay retransmission network. We show that the proposed path diversity overlay retransmission architecture has the potential to significantly reduce the retransmission delay, improve the reliability, playback quality, and scalability of IP-multicast based multimedia applications. Given a deployed IP-multicast network, the proposed overlay retransmission architecture is practical, scalable, and easy to deploy, requiring no change to the existing network infrastructure.

IP-multicast is a bandwidth efficient transmission mechanism for multimedia communication. Reliability in IP-multicast, however, remains a significant challenge. This paper addresses the reliability and scalability issues in IP-multicast by exploring a novel, highly distributed overlay peer-to-peer retransmission architecture that exploits path-diversity. A simple unicast-based "tracert" tool is proposed to help to identify peers with disjoint path to the sender as potential retransmission nodes. Probing can help to adapt to the dynamics of the network. We show that a hybrid system with both "tracert" and probing can perform better than probing only or "tracert" only approach. In addition, we identify the proper probing interval that does not introduce significant probing overhead yet can collect sufficiently updated information to help recover most of the lost packets. The proposed hybrid multicast system is practical, scalable, and easy to deploy, requiring no change to the existing network infrastructure.

Ternary Content-Addressable Memory (TCAM) has been widely used for high-performance multi-dimensional packet classification. High power consumption limits the use of TCAM for large filter sets. TCAM power consumption is proportional to the number of TCAM entries enabled for search. Dividing TCAM into many blocks and enabling only a few blocks for search has been proposed to reduce the power consumption dramatically. However, it is quite challenging to design efficient algorithms to partition a set of multi-dimensional filters into many subsets (a subset is placed in one TCAM block). The efficiency of the algorithm is evaluated in three aspects: the maximum number of TCAM blocks that need to be enabled for a single search, the storage utilization of TCAM blocks, and the time and space complexity of the partition algorithm. In this paper, we developed a simple but efficient partition algorithm based on the Hilbert curve. The algorithm reduces TCAM power consumption by a factor of ten on average. The TCAM storage utilization is over 99%. The algorithm takes 0(n log n) time and 0(n) space.

IP-multicast is a bandwidth efficient transmission mechanism for group communications. Reliability in IP-multicast, however, poses a set of significant challenges. To address the reliability and scalability issues in IP-multicast, this paper proposes a novel overlay retransmission architecture that exploits path-diversity by taking advantages of both IP multicast and an overlay network. We show that the proposed path diversity overlay retransmission architecture has the potential to significantly improve the reliability, delay, playback quality, and scalability of IP-multicast based multimedia applications. The general concept of using P2P overlay networks to help improve the QoS performance of multimedia applications as illustrated in this paper is expected to have significant impact on the deployment of next generation multimedia services

Multicast is used to deliver packets to a group of users. To prevent users outside the group from eavesdropping, a group key is maintained to encrypt the group communication, and the group key is changed (rekeying) when a new member joins the group or an existing member leaves the group. Rekeying costs could be as high as n for a group with n members. The hierarchical key-tree approach is widely used to achieve logarithmic rekeying costs. However, the key tree has to be kept balanced in order to keep logarithmic rekeying costs. Goshi and Ladner propose the height-balanced 2-3 tree (a B-tree of order m=3) and found that it has the best performance among the balancing strategies tested. However, balancing a B-tree [J. Goshi et al., (2003)] after member joining involves splitting oversized tree nodes and results in (m+2)h worst-case rekeying cost, where h is the tree height. We propose an NSBHO (nonsplit balancing high-order) tree in which balancing tree after member joining does not involve node splitting, thus having 2h worst-case rekeying cost. An NSBHO tree is always balanced and its nodes may not satisfy the node properties of a standard B-tree. Our proposed NSBHO tree has the same worst-case rekeying cost incurred by a member removing as a B-tree [J. Goshi et al., (2003)] does. Our experiments show that the NSBHO tree has better average-case rekeying performance and far superior worst-case rekeying performance than a B-tree.

Two schemes - prefix partitioning and interval partitioning - are proposed to improve the performance of dynamic IP router-table designs. While prefix partitioning applies to all known dynamic router-table designs, interval partitioning applies to the alternative collection of binary search tree designs of Sahni and Kim [S. Sahni et al., (2004)]. Experiments using public-domain IPv4 router databases indicate that one of the proposed prefix partitioning schemes - TLDP - results in router tables that require less memory than when prefix partitioning is not used. Further significant reduction in the time to find the longest matching-prefix, insert a prefix, and delete a prefix is achieved.

We propose B-tree data structures for dynamic router-tables for the cases when the filters are prefixes as well as when they are nonintersecting ranges. A crucial difference between our data structure for prefix filters and the MRT (multiway range trees) is that, in our data structure, each prefix is stored in O(1) B-tree nodes per B-tree level, whereas, in MRT, each prefix is stored in O(m) nodes per level (m is the order of the B-tree). As a result of this difference, the measured average insert and delete times using our structure are about 30 percent less than when MRT is used. Further, an update operation of MRT will, in the worst case, make 2.5 times as many cache misses as made when our structure is used. The asymptotic complexity to find the longest matching prefix is the same and the measured time for this operation also is nearly the same for both data structures. Both B-tree structures for prefix router-tables take O(n) memory. However, our structure is more memory efficient by a constant factor. For the case of nonintersecting ranges, our data structure requires O(n log/sub m/n) memory and O(log/sub m/n) nodes are accessed during an operation (finding the highest-priority matching range, insert and delete a range).

We show that determining the minimum number of resolve filters that need to be added to a set of two-dimensional (2-D) prefix filters so that the filter set can implement a given policy using the first-matching-rule-in-table tie breaker is NP-hard. Additionally, we develop a fast O(nlogn+s) time, where n is the number of filters and s is the number of conflicts, plane-sweep algorithm to detect and report all pairs of conflicting 2-D prefix filters. The space complexity of our algorithm is O(n). On our test set of 15 2-D filter sets, our algorithm runs between 4 and 17 times as fast as the 2-D trie algorithm of A. Hari et al. (2000) and uses between 1/4th and 1/8th the memory used by the algorithm of Hari et al. On the same test set, our algorithm is between 4 and 27 times as fast as the bit-vector algorithm of Baboescu and Varghese (2002) and uses between 1/205 and 1/6 as much memory. We introduce the notion of an essential resolve filter and develop an efficient algorithm to determine the essential resolve filters of a prefix filter set.

Two schemes - prefix partition and interval partition - are proposed to improve the performance of router-table design. Significant reduction in the time to find the longest matching-prefix, insert a prefix, and delete a prefix is achieved.

We propose B-tree data structures for dynamic router-tables for the cases when the filters are prefixes as well as when they are nonintersecting ranges. A crucial difference between our data structure for prefix filters and the B-tree router-table data structure of Suri et al. (2001) is that in our data structure, each prefix is stored in O(1) B-tree nodes per B-tree level, whereas in the structure of Suri et al. (2001), each prefix is stored in O(m) nodes per level (m is the order of the B-tree). As a result of this difference, a prefix may be inserted or deleted from an n-filter router table accessing only O(log/sub m/ n) nodes of our data structure; these operations access O(m log/sub m/ n) nodes using the structure of Suri et al. (2001). Eventhough the asymptotic complexity of prefix insertion and deletion is the same in both B-tree structures, experiments conducted by us show that because of the reduced cache misses for our structure, the measured average insert and delete times using our structure are about 30% less than when the B-tree structure of Suri et al. (2001) is used. Further, an update operation using the B-tree structure of Suri et al. (2001) will, in the worst case, make 2.5 times as many cache misses as made when our structure is used. The asymptotic complexity to find the longest matching prefix is the same, O(m log/sub m/ n) in both B-tree structures, and in both structures, this operation accesses O(log/sub m/ n) nodes. The measured time for this operation also is nearly the same for both data structures. Both B-tree structures for prefix router-tables take O(n) memory. However, our structure Is more memory efficient by a constant factor.

We develop a data structure called BOB (binary tree on binary tree) for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. We also develop two modified version of BOB - PBOB (prefix BOB) for the case when all rule filters are prefixes and LMPBOB (longest matching-prefix BOB) when all rule filters are prefixes and longest-prefix matching is to be done. On practical n-rule router table, BOB, PBOB and LMPBOB perform search, insert and delete In O(log n) time and with O(log n) cache misses. Experimental results also are presented.

Two versions of the Internet (IP) router-table problem are considered. In the first, the router table consists of n pairs of tuples of the form (p, a), where p is an address prefix and a is the next-hop information. In this version of the router-table problem, we are to perform the following operations: insert a new tuple, delete an existing tuple, and find the tuple with longest matching-prefix for a given destination address. We show that each of these three operations may be performed in O(log n) time in the worst case using a priority-search tree. In the second version of the router-table problem considered by us, each tuple in the table has the form (r, a), where r is a range of destination addresses matched by the tuple. The set of tuples in the table is conflict-free. For this version of the router-table problem, we develop a data structure that employs priority-search trees as well as red-black trees. This data structure permits us to perform each of the operations insert, delete, and find the tuple with most-specific matching-range for a given destination address in O(log n) time each in the worst case. The insert and delete operations preserve the conflict-free property of the set of tuples. Experimental results are also presented.

We develop an enhanced interval tree data structure that is suitable for the representation of dynamic IP router tables. Several refinements of this enhanced structure are proposed for a variety of IP router tables. For example, the data structure called BOB (binary tree on binary tree) is developed for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. When an n-rule router table is represented using BOB, the highest-priority rule that matches a destination address may be found in O(log/sup 2/n) time; a new rule may be inserted and an old one deleted in O(logn) time. For general ranges, the data structure CBOB (compact BOB) is proposed. For the case when all rule filters are prefixes, the data structure PBOB (prefix BOB) permits highest-priority matching as well as rule insertion and deletion in O(W) time, where W is the length of the longest prefix, each. When all rule filters are prefixes and longest-prefix matching is to be done, the data structure LMPBOB (longest matching-prefix BOB) permits longest-prefix matching in O(W) time; rule insertion and deletion each take O(logn) time. On practical rule tables, BOB and PBOB perform each of the three dynamic-table operations in O(logn) time and with O(logn) cache misses. The number of cache misses incurred by LMPBOB is also O(logn). Experimental results also are presented.

We consider router tables comprised of n pairs of tuples of the form (r,a), where r is a range of destination addresses matched by the tuple. The set of ranges in the table is conflict free. We develop a data structure, which employs priority-search trees as well as red-black trees, to represent the router table. This data structure permits us to perform each of the operations insert, delete, and find the tuple with most-specific matching-range for a given destination address in O(log n) each time. The insert and delete operations preserve the conflict-free property of the set of tuples. Our data structure represents the first O(log n) data structure for dynamic router tables with ranges. Experimental results are also presented.

Content-based temporal sampling of video is an efficient method for representing the visual information contained in the video sequence by using only a small subset of the video frames, which can be detected by a scene change detection method. Scene changes include not only the abrupt transitions, but also gradual transitions such as fade, dissolve. Robust detection of gradual transitions has been considered to be difficult. A high-performance gradual scene change detection method is presented in this paper. The proposed method is based on the video edit model. It can be derived that, for dissolve transition without violent motions, the variance, gradient magnitude and double chromatic difference (DCD) of image sequence during dissolve will show parabolic shapes. These features can be used for robust detection of dissolve transition. We approve that in term of recall rate the variance and gradient magnitude have the same efficiency. So, we simply use variance sequence to select possible positions of dissolve transitions and then DCD is used for further confirmation.