An efficient distributed algorithm for generating and updating multicast trees

As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distributed technique for dynamically updating the multicast tree. The approach proposed has been implemented and extensively tested both in simulation, and on experimental networks. Performance evaluation indicates that the distributed algorithm performs as well as the centralized version, providing good levels of convergence time and communication complexity.     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

Efficient multicast schemes for 3-D Networks-on-Chip

3-D Networks-on-Chip (NoCs) have been proposed as a potent solution to address both the interconnection and design complexity problems facing future System-on-Chip (SoC) designs. In this paper, two topology-aware multicast routing algorithms, Multicasting XYZ (MXYZ) and Alternative XYZ (AL + XYZ) algorithms in supporting of 3-D NoC are proposed. In essence, MXYZ is a simple dimension order multicast routing algorithm that targets 3-D NoC systems built upon regular topologies. To support multicast routing in irregular regions, AL + XYZ can be applied, where an alternative output channel is sought to forward/replicate the packets whenever the output channel determined by MXYZ is not available. To evaluate the performance of MXYZ and AL + XYZ, extensive experiments have been conducted by comparing MXYZ and AL + XYZ against a path-based multicast routing algorithm and an irregular region oriented multiple unicast routing algorithm, respectively. The experimental results confirm that the proposed MXYZ and AL + XYZ schemes, respectively, have lower latency and power consumption than the other two routing algorithms, meriting the two proposed algorithms to be more suitable for supporting multicasting in 3-D NoC systems. In addition, the hardware implementation cost of AL + XYZ is shown to be quite modest.     

Scheduling time-constrained multicast messages in circuit-switched tree networks

In this paper, we consider a kind of multicast scheduling problem in a tree network. Each multicast message is transmitted through a directed subtree within the tree network. The transmission time of each multicast message is assumed to be one unit. Two messages can be transmitted at the same time if their subtrees are edge-disjoint. Each message is constrained by a ready time and a deadline, and has a weight we can gain if it is scheduled within its deadline. The optimality criterion is the total weight we gain. We assume that the degree of each subtree is bounded by a constant d and present an approximation algorithm of which the approximation ratio is at most 4d+15.     

GLBM: A new QoS aware multicast scheme for wireless mesh networks

Wireless mesh networks (WMNs) have been attracting significant attention due to their promising technology. The WMN technology is becoming a major avenue for the fourth generation of wireless mobility. Communication in large-scale wireless networks can create bottlenecks for scalable implementations of computationally intensive applications. A class of crucially important communication patterns that have already received considerable attention in this regard are group communication operations, since these inevitably place a high demand on network bandwidth and have a consequent impact on algorithm execution times. Multicast communication has been among the most primitive group capabilities of any message passing in networks. It is central to many important distributed applications in science and engineering and fundamental to the implementation of higher-level communication operations such as gossip, gather, and barrier synchronisation. Existing solutions offered for providing multicast communications in WMN have severe restriction in terms of almost all performance characteristics. Consequently, there is a need for the design and analysis of new efficient multicast communication schemes for this promising network technology. Hence, the aim of this study is to tackle the challenges posed by the continuously growing need for delivering efficient multicast communication over WMN. In particular, this study presents a new load balancing aware multicast algorithm with the aim of enhancing the QoS in the multicast communication over WMNs. Our simulations experiments show that our proposed multicast algorithm exhibits superior performance in terms of delay, jitter and throughput, compared to the most well known multicast algorithms.     

Scheduling and performance analysis of multicast interconnects

Multicast is an important operation in various emerging computing/networking applications. In particular, many multicast applications require not only multicast capability but also predictable communication performance, such as guaranteed multicast latency and bandwidth, called quality-of-service (QoS). In this paper, we consider scheduling in multicast interconnects, which aims to minimize the multicast latency for a set of multicast requests. Unfortunately, such a problem has been proved to be NP-Complete, which means that it is unlikely to find a fast exact algorithm for the multicast scheduling problem. We then turn to propose a simple, fast greedy multicast scheduling algorithm and derive a lower bound and an upper bound on the performance of the algorithm. As can be seen, while a lower bound is fairly straightforward, the upper bound is much more difficult to obtain. By translating the multicast scheduling problem into a graph theory problem and employing a random graph approach, we are able to obtain a probabilistic upper bound on the performance of the multicast scheduling algorithm. Our analytical and simulation results show that the performance of the proposed multicast scheduling algorithm is quite close to the lower bound and is statistically guaranteed by the probabilistic upper bound. The research work was supported in part by the U.S. National Science Foundation under grant numbers CCR-0073085 and CCR-0207999.     

IP multicast group management for point-to-point local distribution

We examine the applicability of existing IP multicast mechanisms for point-to-point links such as wired and wireless telephone lines. We identify problems such as overhead due to IGMP leave latency and unnecessary probing of hosts, both important issues for power constrained mobile hosts and low bandwidth wireless links. We propose alternative mechanisms that preserve the IP multicasting model, but employ join–leave messages to track group membership. We describe the implementation requirements of our mechanisms and compare them to existing ones with respect to performance, mobile power efficiency, interoperability, robustness and implementation complexity, demonstrating that the join–leave approach is uniformly superior for this environment.     

Hardware security platform for multicast communications

Secure multicast applications of multimedia contents, such as Internet TV, pay per view, satellite TV, etc., need to maintain a high number of keys. In these applications, a user contracts a group of channels or even specific content (films, sports, etc.) which do not have to coincide with the services contracted by other users, so different keys are needed to encrypt the contents. These keys must be recalculated, encrypted and redistributed when a user joins or unjoins a specific group in order to prevent users who do not belong to a group from being able to access the contents. Original algorithms generate only one group key for all users, so this key must be recalculated and resent when a user joins or unjoins in the user group. This is an important problem, because a group key could be changed even when one content is performing. This paper presents a high performance implementation of one of the most employed algorithms of group key maintenance, the LKH algorithm, using reconfigurable hardware and a very high and realistic number of users (8,388,609). The performance obtained by this study improves a lot other results found in the literature in terms of both performance and number of users.     

基于校园网的多媒体教室共享教学系统

提出了一种在校园网网络环境下及多个多媒体教室中实现实时共享课堂教学的一种教学方式,介绍了系统面向对象的实现方法,并进一步给出了系统中多媒体同步问题的基本算法描述。     

Distributed reformation of core-based group-shared multicast trees in mobile ad hoc networks

This paper proposes a method to reduce the cost of a core-based group-shared multicast tree, where the cost is evaluated by the total bandwidth consumption of multicasting packets among all group members. Due to the broadcast nature of radio transmissions, we find that the challenge of determining minimum cost multicast tree can be approximated by finding the multicast tree with a minimum number of non-leaves (the minimum non-leaf multicast tree problem). However, we also find that the minimum non-leaf multicast tree problem is NP-complete. Thus, a method is proposed to dynamically reduce the number of non-leaves in an existing multicast tree. Experimental results show that our method reduces the cost of the multicast tree in both geometrically and randomly distributed network models and the random waypoint mobility model.     

Highly dependable concurrent programming using design for verification

There has been significant progress in automated verification techniques based on model checking. However, scalable software model checking remains a challenging problem. We believe that this problem can be addressed using a design for verification approach based on design patterns that facilitate scalable automated verification. In this paper, we present a design for verification approach for highly dependable concurrent programming using a design pattern for concurrency controllers. A concurrency controller class consists of a set of guarded commands defining a synchronization policy, and a stateful interface describing the correct usage of the synchronization policy. We present an assume-guarantee style modular verification strategy which separates the verification of the controller behavior from the verification of the conformance to its interface. This allows us to execute the interface and behavior verification tasks separately using specialized verification techniques. We present a case study demonstrating the effectiveness of the presented approach.     

An iterative local search approach based on fitness landscapes analysis for the delay-constrained multicast routing problem

This paper presents the first fitness landscape analysis on the delay-constrained least-cost multicast routing problem (DCLC-MRP). Although the problem has attracted an increasing research attention over the past decade in telecommunications and operational research, little research has been conducted to analyze the features of its underlying landscape. Two of the most commonly used landscape analysis techniques, the fitness distance correlation analysis and the autocorrelation analysis, have been applied to analyze the global and local landscape features of DCLC-MRPs. A large amount of simulation experiments on a set of problem instances generated based on the benchmark Steiner tree problems in the OR-library reveals that the landscape of the DCLC-MRP is highly instance dependent with different landscape features. Different delay bounds also affect the distribution of solutions in the search space. The autocorrelation analysis on the benchmark instances of different sizes and delay bounds shows the impact of different local search heuristics and neighborhood structures on the fitness distance landscapes of the DCLC-MRP. The delay bound constraint in the DCLC-MRP has shown a great influence on the underlying landscape characteristic of the problem. Based on the fitness landscape analysis, an iterative local search (ILS) approach is proposed in this paper for the first time to tackle the DCLC-MRP. Computational results demonstrate the effectiveness of the proposed ILS algorithm for the problem in comparison with other algorithms in the literature.     

Seamless handover supported by parallel polling and dynamic multicast group in connected WLAN micro-cells system

WLAN (Wireless Local Area Network) has been seen to be one of the promising access technologies that adapts to 4G cellular network systems in providing very high speed connection with QoS guarantee through the polling function. However, when the handover happens, the contention-based medium access mechanism which is mainly used in WLAN is invoked and introduces unbounded transmission delay due to idle time periods and retransmission because of collision during the handover. If this technique is expanded to use in a microcellular network such as connected WLAN micro-cells, contention-based mechanism, therefore, should not be used to handle the MT’s handover, especially for vehicular users who change access point every few seconds. To overcome these difficulties in handover, we introduce parallel polling scheme in dynamic LMC (Logical Macro Cell) which can reduce delays much and remove packet loss rate. LMC is a virtual single macro cell which is built on a multicast group of adjacent micro-cells. In the same LMC, polling signals are sent from every BS (base station) to give MT (mobile terminal) permission to access one of these BSs. Instead of wasting much time to contend for resources of a new BS during handover, the MT answers the polling as an acknowledgment to connect to that new BS. The polling response is controlled to multicast to all BSs of the same LMC via the core network to synchronize for the next polling cycle. LMC is controlled to dynamically change when the MT comes in a new BS to make polling signals be continuous in a new LMC. Through analytical and simulation results, we show that the parallel polling scheme can achieve no handover latency, no packet loss and maintain mobile users’ throughput stably in the high traffic load condition though it causes overhead on the neighboring cells in both of wired and wireless sections. At speeds of up to70 m/s, the MT can still maintain its stable connection. OMNeT++ simulator with INET project is used to evaluate our proposal.     

The complexity of synchronous iterative Do-All with crashes

The ability to cooperate on common tasks in a distributed setting is key to solving a broad range of computation problems ranging from distributed search such as SETI to distributed simulation and multi-agent collaboration. Do-All, an abstraction of such cooperative activity, is the problem of performing N tasks in a distributed system of P failure-prone processors. Many distributed and parallel algorithms have been developed for this problem and several algorithm simulations have been developed by iterating Do-All algorithms. The efficiency of the solutions for Do-All is measured in terms of work complexity where all processing steps taken by all processors are counted. Work is ideally expressed as a function of N, P, and f, the number of processor crashes. However the known lower bounds and the upper bounds for extant algorithms do not adequately show how work depends on f. We present the first non-trivial lower bounds for Do-All that capture the dependence of work on N, P and f. For the model of computation where processors are able to make perfect load-balancing decisions locally, we also present matching upper bounds. We define the r-iterative Do-All problem that abstracts the repeated use of Do-All such as found in typical algorithm simulations. Our f-sensitive analysis enables us to derive tight bounds for r-iterative Do-All work (that are stronger than the r-fold work complexity of a single Do-All). Our approach that models perfect load-balancing allows for the analysis of specific algorithms to be divided into two parts: (i) the analysis of the cost of tolerating failures while performing work under free load-balancing, and (ii) the analysis of the cost of implementing load-balancing. We demonstrate the utility and generality of this approach by improving the analysis of two known efficient algorithms. We give an improved analysis of an efficient message-passing algorithm. We also derive a tight and complete analysis of the best known Do-All algorithm for the synchronous shared-memory model. Finally we present a new upper bound on simulations of synchronous shared-memory algorithms on crash-prone processors.Received: 15 May 2002, Accepted: 15 June 2003, Published online: 6 February 2004This work is supported in part by the NSF TOC Grants 9988304 and 0311368, and the NSF ITR Grant 0121277. The work of the second author is supported in part by the NSF CAREER Award 0093065. The work of the third author is supported in part by the NSF CAREER Award 9984778.     

Improved bounds for electing a leader in a synchronous ring

We consider the problem of electing a leader in synchronous rings of unknown size. We present a tradeoff betweentime andbits where the bit complexity is alwaysindependent of the entities values and the time is alwayslinear in the smallest entity value. We also show how to elect a leader in exactly θ(n)bits, thus matching the same bit complexity achievable whenn is known, with a time complexitypolynomial in the smallest entity values. Both results are achieved using a novel technique,double waiting, and improve significantly on the existing bounds. This research was supported in part by the Natural Sciences and Engineering Research Council of Canada.     

Designing an effective P2P system for a VoD system to exploit the multicast communication

A distributed video-on-demand system (DVoD) with multiple server-nodes is a cost-effective and fault-tolerant solution for a high scalable enterprise video-on-demand (VoD) system. However, such a server-oriented design is highly vulnerable to workload variations given that the service capacity is limited. Peer-to-Peer (P2P) has been introduced as an architectural solution with self-growing capacity. However, the characteristics of a pure P2P system such as the peer transient nature and high network overhead make this kind of architecture unsuitable for a fully interactive VoD system. In this paper, we propose a new efficient integrated VoD architecture, called DPⁿ2P^m$D{P}^{n}2P^m$, that combines DVoD with a P2P system and multicast communications. The DVoD’s server-nodes provide a minimum required quality of service (QoS) and the P2P system is able to offer the mechanism to increase the system service capacity according to client demands. Multicast communication, wherever it is possible, is effectively exploited by our P2P system. In our design, each client is able to send video information to a set of m$m$ clients using only one multicast channel. Furthermore, the collaboration mechanism is able to coordinate a set of clients to create one collaboration group to replace the server, providing an extensive, efficient and low network-overhead collaboration mechanism from n$n$-peers to m$m$-peers. Regardless of the video the client is watching, our P2P scheme allows every active client to collaborate with the server. The P2P scheme is complemented with recovery mechanisms that are able to replace the failed client before affecting the QoS, offering continuous playback. The proposed approach has been broadly evaluated, firstly using a mathematical model to derive the theoretical performance and secondly using a simulation environment to analyze the system’s dynamic behavior, the VCR interaction impact and the client failures. Comparing DPⁿ2P^m$D{P}^{n}2P^m$ with other DVoD architectures and the most relevant P2P delivery policies, we show that our design is an improvement on previous solutions, providing a higher scalability.     

Bandwidth guaranteed multicast scheduling for virtual output queued packet switches

Multicast enables efficient data transmission from one source to multiple destinations, and has been playing an important role in Internet multimedia applications. Although several multicast scheduling schemes for packet switches have been proposed in the literature, they usually aim to achieve only short multicast latency and high throughput without considering bandwidth guarantees. However, fair bandwidth allocation is critical for the quality of service (QoS) of the network, and is necessary to support multicast applications requiring guaranteed performance services, such as online audio and video streaming. This paper addresses the issue of bandwidth guaranteed multicast scheduling on virtual output queued (VOQ) switches. We propose the Credit based Multicast Fair scheduling (CMF) algorithm, which aims at achieving not only short multicast latency but also fair bandwidth allocation. CMF uses a credit based strategy to guarantee the reserved bandwidth of an input port on each output port of the switch. It keeps track of the difference between the reserved bandwidth and actually received bandwidth, and minimizes the difference to ensure fairness. Moreover, in order to fully utilize the multicast capability provided by the switch, CMF lets a multicast packet simultaneously send transmission requests to multiple output ports. In this way, a multicast packet has more chances to be delivered to multiple destination output ports in the same time slot and thus to achieve short multicast latency. Extensive simulations are conducted to evaluate the performance of CMF, and the results demonstrate that CMF achieves the two design goals: fair bandwidth allocation and short multicast latency.     

Generating asynchronous test cases from test purposes

Context

Input/output transition system (IOTS) models are commonly used when next input can arrive even before outputs are produced. The interaction between the tester and an implementation under test (IUT) is usually assumed to be synchronous. However, as the IUT can produce outputs at any moment, the tester should be prepared to accept all outputs from the IUT, or else be able to block (refuse) outputs of the implementation. Testing distributed, remote applications under the assumptions that communication is synchronous and actions can be blocked is unrealistic, since synchronous communication for such applications can only be achieved if special protocols are used. In this context, asynchronous tests can be more appropriate, reflecting the underlying test architecture which includes queues.

Objective

In this paper, we investigate the problem of constructing test cases for given test purposes and specification input/output transition systems, when the communication between the tester and the implementation under test is assumed to be asynchronous, performed via multiple queues.

Method

When issuing verdicts, asynchronous tests should take into account a distortion caused by the queues in the observed interactions. First, we investigate how the test purpose can be transformed to account for this distortion when there are a single input queue and a single output queue. Then, we consider a more general problem, when there may be multiple queues.

Results

We propose an algorithm which constructs a sound test case, by transforming the test purpose prior to composing it with the specification without queues.

Conclusion

The proposed algorithm mitigates the state explosion problem which usually occurs when queues are directly involved in the composition. Experimental results confirm the resulting state space reduction.     

A 4-states algebraic solution to linear cellular automata synchronization

In this paper, we aim to present a completely new solution to the firing squad synchronization problem based on Wolfram's rule 60. This solution solves the problem on an infinite number of lines but not all possible lines. The two remarkable properties are that the state complexity of it is the lowest possible, say 4 states and 32 transitions (we prove that no line of length n?5 can be synchronized with only 3 states) and that the algorithm is no more based on geometric constructions but relies on some algebraic properties of the transition function. The solution is almost in minimal time: up to one unit of time.     

Keeping track of the latest gossip in a distributed system

Summary.  We tackle a natural problem from distributed computing, involving time-stamps. Let ?={p ₁, p ₂, …, p _N } be a set of computing agents or processes which synchronize with each other from time to time and exchange information about themselves and others. The gossip problem is the following: Whenever a set P⊆? meets, the processes in P must decide amongst themselves which of them has the latest information, direct or indirect, about each agent p in the system. We propose an algorithm to solve this problem which is finite-state and local. Formally, this means that our algorithm can be implemented as an asynchronous automaton. Received: December 1994 / Accepted: July 1996