We present a protocol, named RadGRPM, which runs on a distributed Delaunay triangulation of a set of nodes in Euclidean space. Given coordinates of the source node and a radius, RadGRPM multicasts a message to all nodes within the given radius from the source. Since the target nodes are all within a spherical region centered at the source, RadGRPM provides a special kind of geocast, which we call radius geocast. A multicast tree is not explicitly maintained in RadGRPM. Each node determines the next-hop nodes to forward a message solely using local information (the coordinates of its neighbors) together with the radius and coordinates of the center carried in the message. We prove that RadGRPM delivers a message to all nodes within the given radius. RadGRPM is also efficient in the sense that very few nodes within the radius receive duplicate messages, and nodes outside the radius receive no message. Extensive experimental results are presented to investigate the performance and characteristics of RadGRPM. Furthermore, we show that RadGRPM can be combined with unicast greedy routing to provide geocast to any spherical region not centered at the source node.

We design a new suite of protocols for a set of nodes in d-dimension (d > 1) to construct and maintain a distributed Delaunay triangulation (DT) in a dynamic environment. The join, leave, and failure protocols in the suite are proved to be correct for a single join, leave, and failure, respectively. For a system under churn, it is impossible to maintain a correct distributed DT continually. We define an accuracy metric such that accuracy is 100% if and only if the distributed DT is correct. The suite also includes a maintenance protocol designed to recover from incorrect system states and to improve accuracy. In designing the protocols, we make use of two novel observations to substantially improve protocol efficiency. First, in the neighbor discovery process of a node, many replies to the nodepsilas queries contain redundant information. Second, the use of a new failure protocol that employs a proactive approach to recovery is better than the reactive approaches used in prior work. Experimental results show that our new suite of protocols maintains high accuracy for systems under churn and each system converges to 100% accuracy after churning stopped. They are much more efficient than protocols in prior work.

Pioneering work on Aspect Oriented Programming (AOP) has not flourished enough to enrich the design of distributed systems with the refined AOP paradigm. The more generous perspective today is that a decade of growing research on AOP has brought the paradigm into many exciting areas. We investigate two case studies that cover time-honored issues, fault tolerant computing and parallel computing, in the cluster computing world using the AOP paradigm. Aspects that we define here are simple, intuitive and reusable. We believe that our implementation is very useful in developing other cluster computing software, and AOP can be a powerful method in modularizing source codes.

Delaunay triangulation (DT) is a useful geometric structure for networking applications. In this paper we investigate the design of join, leave, and maintenance protocols to construct and maintain a distributed DT dynamically. We define a distributed DT and present a necessary and sufficient condition for a distributed DT to be correct. This condition is used as a guide for protocol design. We present join and leave protocols as well as correctness proofs for serial joins and leaves. In addition, to handle concurrent joins and leaves as well as node failures, we present a maintenance protocol. An accuracy metric is defined for a distributed DT. Experimental results show that our join, leave and maintenance protocols are scalable, and they achieve high accuracy for systems under churn and with node failures. We also present application protocols for greedy routing, clustering, broadcast, and multicast within a radius, and discuss and prove their correctness.

In this paper, we suggested a vision-based traffic accident detection algorithm and developed a system for automatically detecting, recording, and reporting traffic accidents at intersections. A system with these properties would be beneficial in determining the cause of accidents and the features of an intersection that impact safety. This model first extracts the vehicles from the video image of the charge-couple-device camera, tracks the moving vehicles (MVs), and extracts features such as the variation rate of the velocity, position, area, and direction of MVs. The model then makes decisions on the traffic accident based on the extracted features. In a field test, the suggested model achieved a correct detection rate (CDR) of 50% and a detection rate of 60%. Considering that a sound-based accident detection system showed a CDR of 1% and a DR of 66.1%, our result is a remarkable achievement

In secure group communications, a key server can deliver a group-oriented rekey message [Chung Kei Wong et al., 1998] to a large number of users efficiently using IP multicast. For reliable delivery, Keystone [Chung Kei Wong and Lam, SS, 2000] proposed the use of forward error correction (FEC) in an initial multicast, followed by the use of unicast delivery for users that cannot recover their new keys from the multicast. In this paper, we investigate how to limit unicast recovery to a small fraction /spl gamma/ of the user population. By specifying a very small /spl gamma/, almost all users in the group will receive their new keys within a single multicast round. We present analytic models for deriving /spl gamma/ as a function of the amount of FEC redundant information and the keying interval duration for both Bernoulli and two-state Markov Chain loss models. From our analyses, we conclude that /spl gamma/ decreases roughly at an exponential rate as h increases. we then present a protocol designed to adaptively adjust (h,T) to achieve a specified /spl gamma/. In particular, our protocol chooses from among all feasible (h,T) pairs one with h and T values close to their feasible minima. Our protocol also adapts to an increase in network traffic. Simulation results using ns-2 show that with network congestion our adaptive FEC protocol can still achieve a specified /spl gamma/ by adjusting values of h and T.

Internet radio and television stations require significant bandwidth to support delivery of high quality audio and video streams to a large number of receivers. IP multicast is an appropriate delivery model for these applications. However, widespread deployment of IP multicast on the Internet is unlikely in the near future. An alternative is to build a multicast tree in the application layer Previous studies have addressed tree construction in the application layer However most of them focus on reducing delay. Few systems have been designed to achieve a high throughput for bandwidth-intensive applications. In this paper we present a distributed algorithm to build an application-layer tree. We prove that our algorithm finds a tree such that the average incoming rate of receivers in the tree is maximized (under certain network model assumptions). We also describe protocols that implement the algorithm. For implementation on the Internet, there is a tradeoff between the overhead of available bandwidth measurements and fast convergence to the optimal tree. This tradeoff can be controlled by tuning some parameters in our protocols. Our protocols are also designed to maintain a small number, O(log n), of soft states per node to adapt to network changes and node failures.

We present the design and specification of a protocol for scalable and reliable group rekeying together with performance evaluation results. The protocol is based upon the use of key trees for secure groups and periodic batch rekeying. At the beginning of each rekey interval, the key server sends a rekey message to all users consisting of encrypted new keys (encryptions, in short) carried in a sequence of packets. We present a scheme for identifying keys, encryptions, and users, and a key assignment algorithm that ensures that the encryptions needed by a user are in the same packet. Our protocol provides reliable delivery of new keys to all users eventually. It also attempts to deliver new keys to all users with a high probability by the end of the rekey interval. For each rekey message, the protocol runs in two steps: a multicast step followed by a unicast step. Proactive forward error correction (FEC) multicast is used to reduce delivery latency. Our experiments show that a small FEC block size can be used to reduce encoding time at the server without increasing server bandwidth overhead. Early transition to unicast, after at most two multicast rounds, further reduces the worst-case delivery latency as well as user bandwidth requirement. The key server adaptively adjusts the proactivity factor based upon past feedback information; our experiments show that the number of NACKs after a multicast round can be effectively controlled around a target number. Throughout the protocol design, we strive to minimize processing and bandwidth requirements for both the key server and users.