Multicasting is an efficient way to deliver multimedia content (streaming, for instance) to different locations in the network. While end-to-end real-time constraints are important for interactive applications, sustained availability of bandwidth is more important to the destinations for multimedia streaming. In this research, we address the problem of multi-stream multi-source multicast routing problem (MMMRP) where each data stream could have multiple sources that will serve it and each source can serve multiple data streams in a sustained manner. The goal of MMMRP is to construct a routing forest for each of the data streams and the destinations while maximizing the residual bandwidth. The residual bandwidth is the available bandwidth after all destinations have been served with their desired streams. Our problem is shown to be NP-hard and we provide an Integer Programming formulation together with an efficient heuristic algorithm (MMForests) based on widest-path algorithm. Our empirical evaluations show that our algorithm MMForests can construct the multicast routing trees both quickly and keeping the residual bandwidth close to the optimal.

There has been a constant barrage of worms over the Internet during the recent past. Besides threatening network security, these worms cause an enormous economic burden in terms of loss of productivity at the victim hosts. In addition, these worms create unnecessary network data traffic that causes network congestion, thereby hurting all users. To develop appropriate tools for thwarting quick spread of worms, researchers are trying to understand the behavior of the worm propagation with the aid of epidemiological models. In this study, we apply the classical SIS model and a modification of SIR model to simulate worm propagation in two different network topologies. Whereas in the SIR model once a node is cured after infection it becomes permanently immune, our modification allows this immunity to be temporary, since the cured nodes may again become infected, maybe with a different strain of the same worm. The simulation study also shows that time to infect a large portion of the network vary significantly depending on where the infection begins. This information could be usefully employed to choose hosts for quarantine to delay worm propagation to the rest of the network.

Farber and Keil [Algorithmica, 4 (1989), pp. 221–236] presented an $O(n^3 )$-time algorithm for finding a minimum-weight dominating set in permutation graphs. This result was improved to $O(n^2 \log ^2 n)$ by Tsai and Hsu [SIGAL ’90 Algorithms, Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 109–117] and to $O(n(n + m)$ by the authors of this paper [Inform. Process. Lett., 37 (1991), pp. 219–224], respectively. In this paper, we introduce a new faster algorithm that takes only $O(n + m)$ time to solve the same problem, where m is the number of edges in a graph of n vertices.

This paper describes a class of interconnection networks based on Cayley graph of (S_n, \Omega_CT)> where S_n is the symmetric group of degree n and order n! and \Omega_CT is the generator set consisting of all the n (n -1)/2 transpositions, called the complete transposition graph (CTG). A complete enumeration of a set of node disjoint paths for CTG is given which in turn implies that CTG has maximum fault-tolerance.

Abstract This paper introduces a new class of interconnection scheme based on the Cayley graph of the alternating group. It is shown that this class of graphs are edge symmetric and 2‐transitive. We then describe an algorithm for (a) packet routing based on the shortest path analysis, (b) finding a Hamiltonian cycle, (c) ranking and unranking along the chosen Hamiltonian cycle, (d) unit expansion and dilation three embedding of a class of two‐dimensional grids, (e) unit dilation embedding of a variety of cycles, and (f) algorithm for broadcasting messages. The paper concludes with a short analysis of contention resulting from a typical communication scheme. Although this class of graphs does not possess many of the symmetry properties of the binary hypercube, with respect to the one source broadcasting, these graphs perform better than does a hypercube, and with respect to the contention problem, these graphs perform better than do the star graphs and are close to the hypercube. © 1993 by John Wiley & Sons, Inc.

Orthogonal graphs are natural extensions of the classical binary and b-ary hypercubes b=2/sup l/ and are abstractions of interconnection schemes used for conflict-free orthogonal memory access in multiprocessor design. Based on the type of connection mode, these graphs are classified into two categories: those with disjoint and those with nondisjoint sets of modes. The former class coincides with the class of b-ary b=2/sup l/ hypercubes, and the latter denotes a new class of interconnection. It is shown that orthogonal graphs are Cayley graphs, a certain subgroup of the symmetric (permutation) group. Consequently these graphs are vertex symmetric, but it turns out that they are not edge symmetric. For an interesting subclass of orthogonal graphs with minimally nondisjoint set of modes, the shortest path routing algorithm and an enumeration of node disjoint (parallel) paths are provided. It is shown that while the number of node disjoint paths is equal to the degree, the distribution is not uniform with respect to Hamming distance as in the binary hypercube.>