7179412
Considering Priority in Overlay Multicast Protocols Under Heterogeneous Environments
Hosts participating in overlay multicast applications have a wide range of heterogeneity in bandwidth and participation characteristics. In this paper, we highlight and show the need to systematically consider prioritization as a key criterion in the design of protocols for overlay multicast. We identify trade-offs in the design of prioritization heuristics in two important contexts. The first part of the paper considers prioritization strategies in the context of heterogeneity in node outgoing bandwidth and node stay time durations, and a lack of correlation between the two dimensions. The second part of the paper considers bandwidth allocation and prioritization policies with multi-tree data delivery in environments with heterogeneity in outgoing bandwidth and a certain degree of altruistic behavior. We conduct a systematic study of the trade-offs using both real trace data, and sensitivity studies using synthetic workloads. To the best of our knowledge, this is the first work to identify and study these trade-offs, and to demonstrate the potential benefits of the resulting prioritization heuristics.
383922
Early Experience with an Internet Broadcast System Based on Overlay Multicast
In this paper, we report on experience in building and deploying an operational Internet broadcast system based on Overlay Multicast. In over a year, the system has been providing a cost-effective alternative for Internet broadcast, used by over 4000 users spread across multiple continents in home, academic and commercial environments. Technical conferences and special interest groups are the early adopters. Our experience confirms that Overlay Multicast can be easily deployed and can provide reasonably good application performance. The experience has led us to identify first-order issues that are guiding our future efforts and are of importance to any Overlay Multicast protocol or system. Our key contributions are (i) enabling a real Overlay Multicast application and strengthening the case for overlays as a viable architecture for enabling group communication applications on the Internet, (ii) the details in engineering and operating a fully functional streaming system, addressing a wide range of real-world issues that are not typically considered in protocol design studies, and (iii) the data, analysis methodology, and experience that we are able to report given our unique standpoint.
346423
Enabling contribution awareness in an overlay broadcasting system
We consider the design of bandwidth-demanding broadcasting applications using overlays in environments characterized by hosts with limited and asymmetric bandwidth, and significant heterogeneity in outgoing bandwidth. Such environments are critical to consider to extend the applicability of overlay multicast to mainstream Internet environments where insufficient bandwidth exists to support all hosts, but have not received adequate attention from the research community. We leverage the multi-tree framework and design heuristics to enable it to consider host contribution and operate in bandwidth-scarce environments. Our extensions seek to simultaneously achieve good utilization of system resources, performance to hosts commensurate to their contributions, and consistent performance. We have implemented the system and conducted an Internet evaluation on Planet-Lab using real traces from previous operational deployments of an overlay broadcasting system. Our results indicate for these traces, our heuristics can improve the performance of high contributors by 10-240% and facilitate equitable bandwidth distribution among hosts with similar contributions.
1697925
The Impact of Heterogeneous Bandwidth Constraints on DHT-Based Multicast Protocols
In this paper, we consider support for bandwidth-demanding applications such as video broadcasting using DHTs. Our investigations focus on the impact of heterogeneity in the outgoing bandwidth capabilities of nodes on Scribe, a representative and relatively mature DHT-based multicast protocol. We expose important issues that arise due to the mismatch between the ID space that underlies the DHT and the outgoing bandwidth constraints on nodes.
11142529
Segmentation of hybrid motions via hybrid quadratic surface analysis
In this paper, we investigate the mathematical problem underlying segmentation of hybrid motions: given a series of tracked feature correspondences between two (perspective) images, we seek to segment and estimate multiple motions, possibly of different types (e.g., affine, epipolar, and homography). In order to accomplish this task, we cast the problem into a more general mathematical framework of segmenting data samples drawn from a mixture of linear subspaces and quadratic surfaces. The result is a novel algorithm called hybrid quadratic surface analysis (HQSA). HQSA uses both the derivatives and Hessians of fitting polynomials for the data to separate linear data samples from quadratic data samples. These derivatives and Hessians also lead to important necessary conditions, based on the so-called mutual contraction subspace, to separate data samples on different quadratic surfaces. The algebraic solution we derive is non-iterative and numerically stable. It tolerates moderate noise and can be used in conjunction with outlier removal techniques. We show how to solve the hybrid motion segmentation problem using HQSA, and demonstrate its performance on simulated data with noise and on real perspective images.
27336833
An Efficient Distributed Algorithm for Finding Virtual Backbones in Wireless Ad-Hoc Networks
A minimum connected dominating set is an efficient approach to form a virtual backbone for ad-hoc networks. We propose a tree based distributed time/message efficient approximation algorithm to compute a small connected dominating set without using geographic positions. The algorithm has O(n) time, O(n log n) message complexity, and has an approximation factor of eight. The algorithm is implemented using dominating set simulation program, which shows that our method gives smaller connected dominating set than the existing methods.
37364536
On regular and strongly-regular self-complementary graphs
Abstract In this paper we solve 3 of the 6 problems of A. Kotzig on regular and strongly-regular self-complementary graphs, mentioned in “Graph Theory and Related Topics” edited by J.A. Bondy and U.S.R. Murty.
17940922
Symmetry-based 3-D reconstruction from perspective images
Symmetry is an important geometric cue for 3-D reconstruction from perspective images. In this paper, we introduce a unified theoretical framework for extracting poses and structures of 2-D symmetric patterns in space from calibrated images. The framework uniformly encompasses all three fundamental types of symmetry, i.e., reflective, rotational, and translational, based on a systematic study of the homography groups in image induced by the symmetry groups in space. We claim that if a planar object admits rich enough symmetry, no 3-D geometric information is lost through perspective imaging. Based on two fundamental principles that utilize common spatial relations among symmetric objects, we have developed a prototype system which can automatically extract and segment multiple 2-D symmetric patterns present in a single perspective image. The result of such a segmentation is a hierarchy of new geometric primitives, called symmetry cells and complexes, whose 3-D structures and poses are fully recovered. Finally, we propose a new symmetry-based matching technique, which can effectively establish correspondences among the extracted symmetry cells across multiple images. We demonstrate the application of the proposed algorithms on image segmentation, matching, and 3-D reconstruction with extensive experimental results. The algorithms and systems are more accurate and easier to implement than existing point-or line-based methods.
14267213
Geometric segmentation of perspective images based on symmetry groups
Symmetry is an effective geometric cue to facilitate conventional segmentation techniques on images of man-made environment. Based on three fundamental principles that summarize the relations between symmetry and perspective imaging, namely, structure from symmetry, symmetry hypothesis testing, and global symmetry testing, we develop a prototype system which is able to automatically segment symmetric objects in space from single 2D perspective images. The result of such a segmentation is a hierarchy of geometric primitives, called symmetry cells and complexes, whose 3D structure and pose are fully recovered. Such a geometrically meaningful segmentation may greatly facilitate applications such as feature matching and robot navigation.