Application layer multicast (ALM) has been proposed to overcome current limitations in IP multicast for large-group multimedia communication. We address offering data confidentiality tailored for ALM. To achieve confidentiality, a node may need to continuously re-encrypt packets before forwarding them downstream. Furthermore, keys have to be changed whenever there is a membership change, leading to rekey processing overhead at the nodes. For a large and dynamic group, these reencryption and rekeying operations incur high processing overhead at the nodes. We propose and analyze a scalable scheme called Secure Overlay Multicast (SOM) which clusters ALM peers so as to localize rekeying within a cluster and to limit re-encryption at cluster boundaries, thereby minimizing the total nodal processing overhead. We describe the operations of SOM and compare its nodal processing overhead with two other basic approaches, namely, host-to-host encryption and whole group encryption. We also present a simplified analytic model for SOM and show that there exists an optimal cluster size to minimize the total nodal processing overhead. By comparing with a recently proposed ALM scheme (DT protocol), SOM achieves a substantial reduction in nodal processing overhead with similar network performance in terms of network stress and delay.

We consider inferring the underlay topology among a group of hosts by traceroute-like end-to-end measurement tools. Since pair-wise traceroutes among hosts take a long time and generate much network traffic, Max-Delta has been proposed to infer a highly accurate topology with a low number of traceroutes. However, there is still high measurement redundancy in Max-Delta. That is, a router may be repeatedly visited in different traceroutes. In this paper, we integrate a previously proposed Doubletree algorithm into Max-Delta to reduce such redundancy. We study two key issues in the integration, i.e., the selection of h (a parameter of Doubletree) and the distribution of the global stop set of Doubletree. We have conducted extensive simulations on Internet-like topologies to evaluate the proposed scheme. The results show that Doubletree can significantly reduce the measurement redundancy and the bandwidth consumption in Max-Delta while introducing a small penalty in the measurement accuracy.

Provisioning random access functions in peer-to-peer on-demand video streaming is challenging, due to not only the asynchronous user interactivity but also the unpredictability of group dynamics. In this paper, we propose VMesh, a distributed peer-to-peer video-on-demand (VoD) streaming scheme which efficiently supports random seeking functionality. In VMesh, videos are divided into segments and stored at peers' local storage in a distributed manner. An overlay mesh is built upon peers to support random forward/backward seek, pause and restart during playback. Our scheme takes advantage of the large aggregate storage capacity of peers to improve the segment supply so as to support efficient interactive commands in a scalable manner. Unlike previous work based on "cache-and-relay" mechanism, in our scheme, user interactivity such as random seeking performed by a peer does not break the connections between it and its children, and hence our scheme achieves better playback continuity. Through simulation, we show that our system achieves low startup and seeking latency under random user interactivity and peer join/leave which is a crucial requirement in an interactive VoD system.

In recent years, there has been an increasing interest in peer-to-peer (P2P) multimedia streaming. In this paper, we consider constructing a high-bandwidth overlay tree for streaming services. We observe that underlay information such as link connectivity and link bandwidth is important in tree construction, because two seemingly disjoint overlay paths may share common links on the underlay. We hence study how to construct a high-bandwidth overlay tree given the underlay topology. We formulate the problem as building a Maximum Bandwidth Multicast Tree (MBMT) or a Minimum Stress Multicast Tree (MSMT), depending on whether link bandwidth is available or not. We prove that both problems are NP-hard and are not ap-proximable within a factor of (2/3 + epsiv), for any epsiv > 0, unless P = NP. We then present approximation algorithms to address them and analyze the algorithm performance. Furthermore, we discuss some practical issues (e.g., group dynamics, resilience and scalability) in system implementation. We evaluate our algorithms on Internet-like topologies. The results show that our algorithms can achieve high tree bandwidth and low link stress with low penalty in end-to-end delay. Measurement study based on Plan-etLab further confirms this. Our study shows that the knowledge of underlay is important for constructing efficient overlay trees.

Most existing techniques for keyword search in structured peer-to-peer (P2P) networks only support single-keyword exact-match lookups. In practice, however, users often have fuzzy information for identifying these items and tend to submit broad queries. The support of searching based on multiple keywords is hence desirable. In multiple-keyword search, a data item is associated with multiple keywords for storage. A query may also contain multiple keywords. The search result for a query should include all the data items whose storage keywords contain all the query keywords. Traditional DHT-based approaches achieve this by storing a data item (or its index) multiple times, each time with one of its keywords. A query is processed by searching each of the query keywords once. Therefore, the storage cost and search cost are both linear wit the number of keywords. Clearly, it is not efficient in case of a large number of keywords. In this paper, we propose a hybrid structured network called MKey to address this problem. Its backbone is a structured network. Each node in the backbone is also the leader of a cluster formed by non-backbone nodes. Within a cluster, nodes form an unstructured network and cooperate to store data and answer queries. When inserting a data item, multiple copies of its index are stored in a few different clusters. A query is also mapped to multiple clusters, and a flooding search within these clusters is performed. The union of all the search results are returned to users as the final result.

Providing random access function in peer-to-peer on-demand video streaming is a challenging task, due to not only the asynchronous user interactivity but also the unpredictability of group dynamics. In this paper, we propose VMesh, a distributed peer-to-peer video-on-demand (VoD) streaming scheme which efficiently supports random seeking functionality. In VMesh, videos are divided into segments and stored in peers in a distributed manner. An overlay mesh is built upon peers to support jumping forward/backward, pause and restart during playback. Our scheme utilizes the large total storage capacity of peers to improve the segment supply so as to support interactive commands in a scalable manner. Through simulation, we show that our system outperforms a recent work, P2VoD. VMesh also has low segment missing rate under random member join/leave. In addition, the system achieves low joining and seeking latencies which are crucial requirements in an interactive VoD system.

Current peer-to-peer (P2P) streaming systems often assume that hosts are cooperative. However, this may not be true in the open environment of the internet. In this paper, we discuss how to detect malicious hosts (e.g., with attacking actions and abnormal behavior) based on their history performance. In our system, each host monitors the performance of its neighbor(s) and reports this to a server. Based on the reports, the server computes host reputation with hosts of low reputation being malicious. A problem is that hosts may lie by submitting forged reports to the server. We hence formulate the reputation computing problem in the presence of lying hosts as a minimization problem and solve it by the traditional Levenberg-Marquardt algorithm. Simulation results show that our scheme can efficiently detect malicious hosts with high accuracy

We consider using traceroute-like end-to-end measurement to infer the underlay topology for a group of hosts. One major issue is the measurement cost. Given N hosts in an asymmetric network without anonymous routers, traditionally full N(N-1) traceroutes are needed to determine the underlay topology. We investigate how to efficiently infer an underlay topology with low measurement cost, and propose a heuristic called Max-Delta. In the heuristic, a server selects appropriate host-pairs to measure in each iteration so as to reveal the most undiscovered information on the underlay. We further observe that the presence of anonymous routers significantly distorts and inflates the inferred topology. Previous research has shown that obtaining both exact and approximate topology in the presence of anonymous routers under certain consistency constraints is intractable. We hence propose fast algorithms on how to practically construct an approximate topology by relaxing some constraints. We investigate and compare two algorithms to merge anonymous routers. The first one uses Isomap to map routers into a multidimensional space and merges anonymous routers according to their interdistances. The second algorithm is based on neighbor router information, which trades off some accuracy with speed. We evaluate our inference algorithms on Internet-like and real Internet topologies. Our results show that almost full measurement is needed to fully discover the underlay topology. However, substantial reduction in measurements can be achieved if a little accuracy, say 5%, can be compromised. Moreover, our merging algorithms in the presence of anonymous routers can efficiently infer an underlay topology with good accuracy

We consider media streaming using application-level multicast (ALM) where packet loss has to be recovered via retransmission in a timely manner. Since packets may be lost due to congestion, node failures, and join and leave dynamics, traditional "vertical" recovery approach where upstream nodes retransmit the lost packets is no longer effective. We therefore propose lateral error recovery (LER). In LER, hosts are divided into a number of planes, each of which forms an independent ALM tree. Since error correlation across planes is low, a node effectively recovers its error by "laterally" requesting retransmission from nearby nodes in other planes. We present analysis on the complexity and recovery delay on LER. Using Internet-like topologies, we show via simulations that LER is an effective error recovery mechanism. It achieves low overhead in terms of delivery delay (i.e., relative delay penalty) and physical link stress. As compared with traditional recovery schemes, LER attains much lower residual loss rate (i.e., loss rate after retransmission) under a certain deadline constraint. The performance can be substantially improved in the presence of some reliable proxies.

Island multicast (IM) has been recently proposed to achieve efficient global multicast, where IP multicast is used within multicast-capable domains (the so-called islands) while overlay connections are used to bridge islands. In the previously proposed scheme, the number of ping measurement to find good bridge-nodes is at least proportional to island size, and a leader needs to keep track of all its members in the island. In this paper, we improve the system scalability by presenting a bridge-node selection algorithm where both the numbers of ping measurements and members to keep track of are greatly reduced to some constants. We further propose a recovery scheme for packets lost across islands. Our scheme uses a number of recovery meshes formed by overlays of some randomly chosen nodes. Simulation results show that our bridge-node selection is efficient in terms of control overhead and achieves scalability with little cost in network stress and delay. As compared to traditional source and parent recoveries, our loss recovery scheme substantially reduces both the recovery delay and bandwidth overhead to achieve reliability.

Application layer multicast (ALM) has been proposed to overcome current limitations in IP multicast. We address, for the first time, offering data confidentiality in ALM. To achieve data confidentiality, data encryption keys are shared among the multicast group members. Observe that in this system, a node may need to continuously reencrypt packets before forwarding them downstream. Furthermore, keys have to be changed whenever there is a membership change, leading to rekey processing overhead at the nodes. For a large and dynamic group, these reencryption and rekeying operations incur high processing overhead at the nodes. We introduce a scalable scheme called secure overlay tree (SOT) which clusters ALM peers so as to localize rekeying within a cluster and to limit reencryption at cluster boundaries, thereby minimizing the total nodal processing overhead. We describe the operations of SOT and compare its nodal processing overhead with two other basic approaches, namely, host-to-host encryption and whole group encryption. We show that there exists an optimal cluster size to minimize the total nodal processing overhead. SOT achieves substantial reduction in nodal processing overhead with little cost in network performance in terms of network stress and delay.