A good P2P file sharing system is usually expected to achieve the following design goals: scalability, routing efficiency and complex query support. In this paper, we propose such a system, called PSON, which can satisfy all the three requirements. PSON is essentially a semantic overlay network of logical nodes, in which queries are routed on the basis of semantics. A logical node is formed by a cluster of peers that are close to each other in the physical network. Each cluster selects a powerful peer as super peer to support routing in the overlay network. To facilitate routing, all the super peers (or logical nodes) are organized in the form of a balanced tree. By exploiting the concepts of hierarchy and semantics, PSON can support complex queries in a scalable and efficient way. In this paper, we will describe the system architecture, and examine the key component of PSON design, i.e., semantic overlay construction and routing. We also conduct simulations, and show that the query routing in PSON is very efficient (O(log(n)) in the case of exact query).

In this paper, we propose a two-tier overlay multicast architecture (TOMA) to provide scalable and efficient multicast support for various group communication applications. In TOMA, multicast service overlay network (MSON) is advocated as the backbone service domain, while end users in access domains form a number of small clusters, in which an application-layer multicast protocol is used for the communication between the clustered end users. TOMA is able to provide efficient resource utilization with less control overhead, especially for large-scale applications. It also alleviates the state scalability problem and simplifies multicast tree construction and maintenance when there are large numbers of groups in the network. To help MSON providers efficiently plan backbone service overlay, we suggest several provisioning algorithms to locate proxies, select overlay links, and allocate link bandwidth. Extensive simulation studies demonstrate the promising performance of TOMA

Multicast solutions have been evolving from "bottom" to "top", i.e., from IP layer (called IP multicast) to application layer (referred to as application layer multicast). Recently, there are some new proposals (named as overlay multicast) using certain "infrastructure" (composed of proxies) in the middle. Although it is well accepted that application layer multicast and overlay multicast are easier to deploy while sacrificing bandwidth efficiency compared with IP multicast, little research has been done to systematically evaluate and compare their performance. In this paper, we conduct a comparative study of different types of multicast routing protocols. We first present a qualitative comparison of three types of protocols, and then we provide a quantitative study of four representative protocols, namely, PIM-SSM, NARADA, NICE, and POM by extensive simulations. Our studies will help to answer some of the most important questions, such as which way to go: top, bottom, or in the middle?.

Traditional IP multicast faces a serious state scalability problem when there are a large number of groups in the network. Recently, a novel approach called aggregated multicast was proposed [6], in which multiple groups share one delivery tree. A key problem in aggregated multicast is group-tree matching (i.e., assigning groups to trees). In this paper, we formally study the dynamic version of the group-tree matching problem. We propose a generic dynamic on-line algorithm (GDOA) and provide an approach to determine the upper bound on its performance. We quantitatively compare the performance of GDOA and other existing on-line heuristics. Extensive simulations demonstrate that GDOA is a very practical solution with promising performance and reasonable computation requirement.

Network clustering is an important technique widely used in efficient hierarchical routing protocol design, network modelling and performance evaluation, etc. In this paper, we discuss the important clustering criteria, such as node connectivity, cluster diameter, number of orphan nodes. Our main contribution is a novel clustering algorithm SACA based on an accurate clustering measure called SCM. SACA adaptively forms clusters to incrementally improve the clustering quality, taking node connectivity into consideration. It can control the cluster size effectively and limit the number of orphan nodes. Our simulation study indicates that SACA is more accurate than MCL, a well accepted scalable and efficient clustering scheme, while requiring comparable running time for power law topologies and grid topologies, and significantly less running time for random topologies.

Recently, there has been extensive research on integrating cellular networks and ad hoc networks to overcome the limitations of cellular networks. Although several schemes have been proposed to use such hybrid networks to improve the performance of individual multicast groups, they do not address the quality of service (QoS) issues when multiple groups are present in the networks. Our work, on the other hand, considers an interesting scenario of hybrid networks when an ad hoc network cannot accommodate all the groups and a base station has to select a subset of groups to optimize its bandwidth savings and maximize the utilization of the ad hoc network, while providing QoS support for multicast users. In this work, we develop a network model for multicast admission control which takes wireless interference into account, formulate the group selection problem as a multidimensional knapsack problem, and propose an integer linear programming (ILP) formulation and a polynomial-time dynamic algorithm. We also examine a distributed implementation of the dynamic algorithm in real systems. Simulation studies demonstrate that the dynamic algorithm is able to achieve very competitive performance under various conditions, in comparison with the optimal solution computed by the ILP approach.

We present a new capacity estimation technique, called CapProbe. CapProbe combines delay as well as dispersion measurements of packet pairs to filter out samples distorted by cross-traffic. CapProbe algorithms include convergence tests and convergence speed-up techniques by varying probing parameters. Our study of CapProbe includes a probability analysis to determine the time it takes CapProbe to converge on the average. Through simulations and measurements, we found CapProbe to be quick and accurate across a wide range of traffic scenarios. We also compared CapProbe with two previous well-known techniques, pathchar and pathrate. We found CapProbe to be much more accurate than pathchar and similar in accuracy to pathrate, while providing faster estimation than both. Another advantage of CapProbe is its lower computation cost, since no statistical post processing of probing data is required.

IP multicast confronts a severe scalability problem when there are large numbers of multicast groups in the network due to state explosion and control explosion. In backbone networks, this state scalability problem is exacerbated, since there are potentially enormous multicast groups crossing backbone domains, in this paper, we propose a scalable protocol, called BEAM (bi-directional aggregate multicast), which uses the concept of aggregated multicast. BEAM is a distributed protocol using bi-directional trees. It is simple and easy to implement. Through simulations, we show that BEAM can greatly improve state scalability with very low overhead: up to 98% state and tree setup and maintenance overhead reduction with less than 0.14 bandwidth waste in our experiments.