Optimal virtual topologies for one-to-many communication in WDM paths and rings

In this paper we examine the problem of constructing optimal virtual topologies for one-to-many communication in optical networks employing wavelength-division multiplexing. A virtual topology is a collection of optical lightpaths embedded in a physical topology. A packet sent from the source node travels over one or more lightpaths en route to its destination. Within a lightpath, transmission is entirely optical. At the terminus of a lightpath the data is converted into the electronic domain where it may be retransmitted on another lightpath toward its destination. Since the conversion of the packet from the optical to the electronic domain introduces delays and uses limited physical resources, one important objective is to find virtual topologies which minimize either the maximum or average number of lightpaths used from the source to all destination nodes. Although this problem is NP-complete in general, we show that minimizing the maximum or average number of lightpaths in path and ring topologies can be solved optimally by efficient algorithms.     

On the complexity of virtual topology design for multicasting in WDM trees with tap-and-continue and multicast-capable switches

This paper investigates the problem of finding optimal multicast virtual topologies, with respect to minimizing the maximum hop distance, in wavelength-division multiplexing multicast trees. Although the problem of finding optimal multicast trees is itself known to be NP-complete under many optimization metrics, high-quality approximation algorithms are known for this problem. We investigate the case that a multicast tree has been selected and seek to embed an optimal virtual topology in this multicast tree. We show that the problem can be solved in polynomial time when tap-and-continue switches are employed, which allow a lightpath to be tapped by some number of intermediate nodes. However, the problem becomes NP-complete when fully multicast-capable switches are employed. Our results suggest that tap-and-continue switches can be used to obtain high-quality multicast virtual topologies, while heuristics will be required to find good solutions in fully multicast-capable networks.     

Optimal reconfiguration algorithms for real-time fault-tolerantprocessor arrays

In this paper we consider the problem of reconfiguring processor arrays subject to computational loads that alternate between two modes. A strict mode is characterized by a heavy computational load and severe constraints on response time while a relaxed mode is characterized by a relatively light computational load and relaxed constraints on response time. In the strict mode, reconfiguration is performed by a distributed local algorithm in order to achieve fast recovery from faults. In the relaxed mode, a global reconfiguration algorithm is used to restore the system to a state that maximizes the probability that future faults occurring in subsequent strict modes will be repairable. Several new results are given for this problem. Efficient reconfiguration algorithms are described for a number of general classes of architectures. These general algorithms obviate the need for architecture-specific algorithms for architectures in these classes. We show that it is unlikely that similar algorithms can be obtained for related classes of architectures since the reconfiguration problem for these classes is NP-complete. Finally, a general approximation algorithm is described that can be used for any architecture. Experimental results are given, suggesting that our algorithms are very effective     

Origin-based fault-tolerant routing in the mesh

The ability to tolerate faults is critical in multicomputer employing large numbers of processors. This paper describes a class of fault-tolerant routing algorithms for n-dimensional meshes that can tolerate large numbers of faults without using virtual channels. We show that these routing algorithms prevent livelock and deadlock while remaining highly adaptive.     

Multicast routing and wavelength assignment in multihop optical networks

This paper addresses multicast routing in circuit-switched multihop optical networks employing wavelength-division multiplexing. We consider a model in which multicast communication requests are made and released dynamically over time. A multicast connection is realized by constructing a multicast tree which distributes the message from the source node to all destination nodes such that the wavelengths used on each link and the receivers and transmitters used at each node are not used by existing circuits. We show that the problem of routing and wavelength assignment in this model is, in general, NP-complete. However, we also show that for any given multicast tree, the wavelength assignment problem can be solved in linear time.     

Virtual topologies for multicasting with multiple originators in WDM networks

In this paper, we consider the problem of multicasting with multiple originators in WDM optical networks. In this problem, we are given a set S of source nodes and a set D of destination nodes in a network. All source nodes are capable of providing data to any destination node. Our objective is to find a virtual topology in the WDM network which satisfies given constraints on available resources and is optimal with respect to minimizing the maximum hop distance. Although the corresponding decision problem is NP-complete in general, we give polynomial time algorithms for the cases of unidirectional paths and rings.