Narrow Results

High bandwidth and low latency switches are commercially available. Using these switches, it becomes possible to build a system area network to interconnect workstations and processor clusters together to provide a cost-effective parallel computing platform. A processor cluster may be a shared-memory multiprocessor or a mesh-connected multicomputer, etc. The interconnection topology on this kind of platform, called switch-based NOWP, is usually irregular. On such systems, multicast is an important collective communication operation. Two steps are involved in a multicast: (1) the source node sends the multicast message to the destinations which are connected to a switch directly or are the leader of a processor cluster, and (2) the leader node of each cluster sends the message to other destinations in the same cluster. In this paper, we propose two unicast-based multicast algorithms. Algorithm Multicast_1 performs those two steps sequentially; while Algorithm Multicast_2 overlaps them. Performance of the two algorithms will be evaluated and compared.

This paper addresses multicasting and broadcasting in undirected WDM networks and QoS extensions of multicasting. It is given an undirected network G=(V, E), with Λ is the set of the available wavelengths in G, and associated with each edge, there is a subset of wavelengths on it. For a multicast request r=(s, D) with a source s and a set D of destinations, it is to find a tree rooted at s including all nodes in D such that the cost of the tree is minimized in terms of the cost of wavelength conversion at nodes and the cost of using wavelength on edges. This paper proves that multicasting in this model of networks is NP-Hard and cannot be approximated within a constant factor, unless P=NP. Furthermore, an auxiliary graph is constructed for the original WDM network, the multicasting is reduced to a group Steiner tree problem on the auxiliary graph and an approximate algorithm based on the group Steiner tree algorithm proposed by M. Charikar et al. with performance ratio of O(log²(nk) log log(nk) log p) is provided, where k=|Λ| and p=|D∪{s}|. At last, some QoS extensions of multicasting are discussed.

In this paper, we propose a new method of implementing bus operations on mesh wormhole routers with small additional circuits. The bus, called a virtual bus, is set up dynamically upon a request by bypassing existing datapath in wormhole routers. After bus setup, it acts as a real bus by sharing the point-to-point links of the corresponding row/column of the mesh. Simulation results show that the 2D (two-dimensional) mesh with the virtual bus outperforms the mesh with separate buses.

We consider a model of multicast communication in a network whereby multiple sources have messages to disseminate among all sites of a network. We propose that the messages from all sources are disseminated along the same spanning tree of the network and consider the problem of constructing an optimal such tree. One measure for suitability of the construction is the sum of distances from all sources to all other vertices. We show that finding the exact solution in this case in -hard (in the strong sense). We then investigate solutions for some restricted classes of graphs and give efficient algorithms for those. We also consider an alternative measure of goodness for the spanning tree, being the maximum eccentricity of a source. We show that the problem of finding such a minimum eccentricity spanning tree is somewhat easier to solve and give a pseudo-polynomial solution algorithm.

Many new distributed multimedia applications involve dynamic multiple participants, have stringent end-to-end delay requirement and consume large amount of network resources. In this paper, we propose a new distributed dynamic delay-constrained least-cost multicast routing algorithm (DDDCLCMR) to support these applications. DDDCLCMR scales well because the source of the multicast tree needs only limited computation or may even not be involved in the route computation. When group membership changes, the existing multicast tree is perturbed as little as possible. Simulation results show that DDDCLCMR performs very good in terms of delay and cost for both, static and dynamic multicast groups, when compared to the best multicast algorithms known.

In this paper, we consider the problem of constructing a multicast tree in star interconnection networks under the single-port communication model. Unlike previous schemes for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme of time units for the star graph of dimension n.

An ad hoc network is a multi-hop wireless network of mobile nodes without fixed infrastructure. Its limited bandwidth and frequently changing topology require that its protocol should be robust, simple and energy conserving. We have proposed PDAODMRP (Passive Data Acknowledgement ODMRP) based on the passive acknowledgement function of data packets. PDAODMRP defines the adjacent un-forwarding nodes of forwarding nodes as pool nodes. With the help of pool nodes, PDAODMRP reduces its local route maintenance scope to at least one-hop. Although PDAODMRP has reduced its control overhead and data delivery delay greatly, it still selects multiple paths between a source and a member. And, its data overhead is still high. Hence, in this paper, we propose EPDAODMRP (Extended PDAODMRP) to extend PDAODMRP. Compared PDAODMRP, EPDAODMRP only selects the shortest path between a source and a member instead of all disjoint paths between a source and a member; its local route maintenance is as strong as that of PDAODMRP, which can amend all link failures. The simulation results show that EPDAODMRP has lower data overhead and lower data delivery delay.

The lack of resources in routers will become a crucial issue with the deployment of state storing protocols. In particular, single or any source multicast protocols will most probably take over large amounts of resources for maintaining multicast tree information. The aim of this paper is to study the possibility and benefit of using multiple shortest paths in order for a new member to reach a multicast tree. Such a mechanism would not reduce the overall amount of state information in the network but it would distribute this amount more evenly among all routers. The idea is to use alternate shortest paths provided by the underlying unicast routing protocol to avoid saturated routers, that is, routers that can not or do not want to store any more multicast state information. As the simulation results are very sensitive to the topology, we have used subgraphs of an Internet map. We have then simulated our multipath join mechanism and have found that depending on the tree size, the use of our mechanism can increase successful join attempts by up to 55% when the network is half saturated.

We consider the problem of sharing the cost of multicast transmissions in non-cooperative undirected networks where a set of receivers R wants to be connected to a common source s. The set of choices available to each receiver r ∈ R is represented by the set of all (s, r)-paths in the network. Given the choices performed by all the receivers, a public known cost sharing method determines the cost share to be charged to each of them. Receivers are selfish agents aiming to obtain the transmission at the minimum cost share and their interactions create a non-cooperative game. Devising cost sharing methods yielding games whose price of anarchy (price of stability), defined as the worst-case (best-case) ratio between the cost of a Nash equilibrium and that of an optimal solution, is not too high is thus of fundamental importance in non-cooperative network design. Moreover, since cost sharing games naturally arise in socio-economical contests, it is convenient for a cost sharing method to meet some constraining properties. In this paper, we first define several such properties and analyze their impact on the prices of anarchy and stability. We also reconsider all the methods known so far by classifying them according to which properties they satisfy and giving the first non-trivial lower bounds on their price of stability. Finally, we propose a new method, namely the free-riders method, which admits a polynomial time algorithm for computing a pure Nash equilibrium whose cost is at most twice the optimal one. Some of the ideas characterizing our approach have been independently proposed in Ref. 10.

In this paper we propose a new approach of application-level multicast protocol providing a group communication service. This protocol, called End-System Multicast (ESM), and can be used when native multicast routing is not available. ESM is a centralized protocol where everything is being controlled by a single host called Rendez-vous point (RP_L1), connected indirectly to the group members via some hosts called secondary Rendez-vous Point (RP_L2). Each RP_L2 has some group members that constitute a cluster, and each cluster is controlled by its RP_L2. Since the group control is divided among some RP_L2 and a main controller (RP_L1) manages the relation among RP_L2s and between itself and RP_L2s, we found that the scalability is improved and it also avoids the bottleneck problem near the RP_L1, or there is a load balance.

Multicasting protocols deliver data packets from a source node to multiple receivers, and serve a very important function in mobile ad-hoc networks (MANETs). In this paper, a novel receiver-initiated soft-state probabilistic multicasting protocol (RISP) for MANETs is proposed. RISP is inspired by the ant colony's route-seeking mechanism, in which an individual ant chooses the optimal path to its destination through cooperation with others in a totally distributed manner. Imitating the behaviour of ants in nature, RISP introduces probabilistic forwarding and soft-state for making relay decisions that are automatically adaptive to node mobility in MANETs. Compared with other protocols, we show by computer simulations that RISP has lower delivery redundancy, while achieving higher delivery ratio at all mobility scenarios. Furthermore, RISP has lower control overhead.

When analyzing a nonblocking switching network, the typical problem is to find a route for a new request through the network without disturbing existing routes. By solving this problem, we can derive how many hardware components of a certain type (Banyan planes in a multi-log network, for instance) are needed for the network to be nonblocking. This scenario appears in virtually all combinations of switching environments: strictly, widesense or rearrangeably nonblocking, unicast or multicast switching, and circuit, multirate, or photonic switching.

In this paper, we show that the König–Egevarý theorem is a very good tool which helps solve the above prototypical problem. The idea is to somehow "represent" the potential blocking connections as edges of a bipartite graph. The maximum number of blocking connections roughly corresponds to the size of a maximum matching in that bipartite graph. The size of any vertex cover, by the König–Egevarý theorem, is an upper bound on the maximum number of blocking connections. Thus, by specifying a small vertex cover, we can derive the sufficient number of hardware components for the network to be nonblocking. We illustrate the technique by analyzing crosstalk-free and non-crosstalk-free widesense nonblocking multicast multi-log networks.

Particularly, for the first time in the literature we derive conditions for the d-ary multi-log network to be crosstalk-free multicast widesense nonblocking under the window algorithm for any given window size. Several by-products follow from our approach and results. Firstly, our results allow for computing the best window size minimizing the fabric cost, showing that the multi-log network is a good candidate for crosstalk-free multicast switching architectures. Secondly, the analytical approach also gives a much simpler proof of the known case when the network is not required to be crosstalk-free. Thirdly, we show that several known results for the multi-log multicast networks under the so-called fanout constraints are simple corollaries of our results.

Assume that there are players and an eavesdropper Eve of unlimited computational power and that several pairs of players have shared secret keys beforehand. In a key sharing graph, each vertex corresponds to a player, and each edge corresponds to a secret key shared by the two players corresponding to the ends of the edge. Given a key sharing graph, a player wishes to send a message to another player so that the eavesdropper Eve and any other player can get no information on the message. In this paper, we first give a necessary and sufficient condition on a key sharing graph for the existence of such a unicast protocol. We then extend the condition to the case where a multiple number of players other than the sender and receiver passively collude. We finally give a sufficient condition for the existence of a secure multicast protocol.

The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. attackers often use incorrect, or spoofed, source IP addresses. In this paper, We propose a new method for IP traceback that collects audit trails for traffic within the network, and can trace the origin of a single IP packet delivered by the network in the recent past. We demonstrate that the method is effective. We present both analytic and simulation results showing the method’s effectiveness by contrasting with SPIE[1] and Scheme J[2]. We believe that the key contribution of our method is to demonstrate that constructing attack graph is not necessary for tracing.

Optical multicast is usually modeled as a two-step process: multicast routing and wavelength assignment. This paper proposes a new multi-layer model, in which the WDM network is represented as a multilayer wavelength structure, each of which has finite capabilities, to integrate routing and wavelength assignment. The algorithm makes use of the light splitting and wavelength conversion capabilities simultaneously in a deterministic manner, avoiding the re-routing procedure. It handles the finite light splitting capability, thus providing a general solution to the problem. Some simulations results are presented in the paper.

This paper presents a new multicast protocol, called Gateway-Based Multicast Protocol (GBMP). Receivers are grouped into local groups, in which a group-shared tree, whose root is called a Gateway Node, connects receivers and intermediate nodes. The gateway nodes and multicast sources make up a mesh. A hop-limited Receiver-Initiated Attach Procedure is introduced for multicast receivers to cope with link breakages. A new technique, Anonymous Receive Mode, is proposed to improve transmission efficiency. Simulation results show that our protocol outperforms ODMRP.

In a video-on-demand (VOD) environment, batching of requests is often applied to reduce the I/O demand and increase the availability of VOD services. This scheme, however, unfairly forces first comers to wait for subscribers arriving late at the batch. Some of these victims may become impatient and decide to renege. To address this issue, we introduce a chaining technique which allows a client station being served to forward its video data to other client stations, which requested the same video, at a slightly later time. The forwarding of data is done using the same store-and-forward mechanism of the multicast facility used in batching. With this new feature, requests arriving at a chain can be served immediately; yet they are allowed to share a single video stream. Thus, chaining enjoys the benefit of batching without its side effect of causing long access latencies. By combining batching and chaining, we also design a scheme called Virtual Batching. It extends the standard chaining mechanism to allow a client station on a chain to multicast video data to other client stations which are admitted as a batch. Our simulation results indicate that this hybrid approach offers significant performance improvement.

Legacy IEEE 802.11 does not efficiently support multicast transmissions. To cope with the increasing demand for multicast, which is mainly required to deliver multimedia traffic, the IEEE 802.11aa Task Group has recently standardized new mechanisms for allowing efficient and robust transmission of multicast flows in wireless local area networks (WLAN). However, the standard allows the use of different mechanisms for this purpose, and leaves open the choice of which one to use for a given scenario. In this paper, we present an analytical model for evaluating the performance of the mechanisms included in the 802.11aa standard and then compare their performance. Our analysis shows that there is no absolute winner out of these mechanisms and performance strongly depends on the scenario. Building on our model, we then propose a novel algorithm that selects the best multicast mechanism to use as a function of the scenario conditions. Our results are validated by extensive simulations.

Supporting scalable and efficient routing and service provisioning in MANET has been a big research challenge. Hierarchical service provisioning is flexible and takes advantage of centralized and distributed service provisioning schemes. A hierarchical structure is created by dividing the network into manageable square zones called cells. Every cell in the hierarchy has an access point and the entire region has an rendezvous point. The existing techniques choose the leaders based on Zone ID or geographic hash function. This paper aims at selecting an adaptive coordinator that can meet the QoS requirements such as remaining battery power, node mobility and node position. Such scheme can be robust against the unpredictable faults in MANETs.