This paper addresses the problem of dynamic multicast routing and wavelength assignment in delay constrained wavelength-routed WDM network. Current algorithms focus in minimizing blocking probability or wavelength numbers used, but not on the number of wavelength conversions. Wavelength conversions on either optical or electronics plane are costly and time consuming, hence should be minimized to ensure good transmission quality and manageable cost. In this paper, we proposed an algorithm on generic layered auxiliary graph to construct delay constrained dynamic multicast trees with minimal conversions and low blocking, and compared it with existing optimal algorithms through simulations. The results indicate that our proposed algorithm is able to achieve near optimal performance in terms of blocking, wavelength conversions and delays between source and members.

We propose an efficient heuristic algorithm to rearrange multicast trees proactively in delay constrained dynamic membership multicast networks. The objective is to construct low cost multicast tree with controlled number of disrupted members within a very short rearrangement time when a member joins and leaves the tree. In addition, a heuristic algorithm to obtain near-optimal solution to the problem is introduced as the benchmark. A new performance index to gauge the efficiency of the proposed heuristics more accurately is also introduced. Better performance is obtained when compared with existing methods using simulations.

The problem of dynamic multicast routing and wavelength assignment (MC-RWA) in the wavelength-routed wavelength-division-multiplexing networks is addressed. Current solutions to this problem always rely on homogeneous network constructions. However, future backbone networks tend to be heterogeneous in nature. Thus, the dynamic MC-RWA problem should be studied in a more realistic situation by considering the heterogeneity of network structures. A new graph model is proposed for the MC-RWA problem. This model is based on layered auxiliary graph which is generic and able to support various node architectures and heterogeneous network structures. Based on this graph model, the dynamic MC-RWA problem can be simply solved by an efficient multicast tree algorithm on various light-splitting and wavelength-conversion scenarios. In general, this graph model provides a universal platform to study different aspects of the dynamic MC-RWA as well as related problems.

Load balancing in the provisioning of virtual private network (VPN) service in the hose model is studied. Single-path routing and tree routing for the hose model tend to aggregate bandwidth reservations on a small number of links, thus leading to congestion problems in service provider networks. If the link capacity is depleted as a result of improper routing, all future non-VPN traffic will be blocked. We propose a novel multi-objective multi-path (MOMP) routing linear program with the maximum fraction of traffic on a path (MFTP) constraint to solve the problem. The MOMP routing algorithm is able to reduce the bandwidth reservation on the most loaded link by as much as 50%, thus effectively alleviating the potential congestion problems in service provider network. The MFTP constraint provides a guarantee of the availability of multiple paths for each VPN endpoint pair. Further reduction of the bandwidth reservation can be achieved depending on the MFTP value. This is highly significant.

The multicast wavelength assignment problem in wavelength-routed wavelength-division multiplexing networks with limited wavelength conversions is addressed. A new multi-wavelength multicast wavelength assignment (MMWA) algorithm has been developed based on the multi-wavelength assignment strategy, by allowing multiple available wavelengths in a link to carry the multicast signal. This new multicast wavelength algorithm provides advantages for the network with limited wavelength conversions, by accommodating more multicast requests and providing good trade-off between wavelength cost and wavelength conversion cost. Simulation results show that the MMWA algorithm can satisfy more multicast requests in comparison with the previous single-wavelength assignment strategy. The improvement can be as high as 50–80%. This is highly significant. The MMWA algorithm also provides a good cost trade-off by making significant reduction of wavelength conversion cost (over 50%) while keeping the additional wavelength usage within a reasonable range (around 15%).

In this paper we investigate the problem of availability guaranteed service provisioning in hose model VPNs. We show that this problem is NP-complete and propose a multi-path routing heuristic to solve it. The heuristic finds multiple link-disjoint paths for each VPN endpoint pair, thus enabling alternative paths to raise the overall availability. This approach elegantly solves the too-many-path problem encountered by others in literature and eliminates the associated complexities. It makes the provisioning of availability guaranteed connections fast and straightforward. Simulation results show that the proposed heuristic significantly increases the overall availability for each possible VPN endpoint pair. Compared with tree routing scheme, the blocking probability of the new scheme is reduced by a few orders of magnitude. This is highly significant.

This paper addresses the multicast wavelength assignment (MC-WA) problem in wavelength-routed WDM networks with full light splitting and wavelength conversion capabilities. Current approaches are based on the multicast switch model that supports only split-convert (S-C) switch scheme. This scheme leads to redundant wavelength conversions for a given multicast request. In this paper, we propose a new split-convert-split (S-C-S) switch scheme capable of eliminating the redundant wavelength conversions. In order to implement this new switch scheme, we develop a new multicast switch model based on the concept of sharing of light splitters and wavelength converters. Furthermore, existing multicast wavelength assignment algorithm allows only one wavelength to carry the light signal on a fiber link, the so-called single-wavelength assignment strategy. In this paper, we explore the advantages of a new multi-wavelength assignment strategy which allows multiple available wavelengths in a link to carry the multicast signal. This will reduce the number of wavelength conversions required for the multicast request. Consequently, based on the new S-C-S multicast switch model and the new multi-wavelength assignment strategy, we generalize the existing algorithms to produce a new Multicast 'Wavelength Assignment Algorithm (MWAA) to support both the new switch model and the new wavelength assignment strategy. Compared with the existing algorithm, our new algorithm is a more general one which makes the multicast wavelength assignment more flexible, covering different switch schemes and different assignment strategies. In addition, it delivers good performance in term of minimizing the number of wavelength conversions. The improvement percentage is sensitive to the maximum out-degree value of a node, D. For a 100-node multicast tree, the improvement percentage increases from 38% at D = 3 to about 73% at D = 16. This is highly significant.

Recently, some studies have been made based on the concept of route interference to provide deterministic end-to-end quality of service (QoS) guarantees. Nonetheless, these studies tend to confine to a simple scheduling scheme and study the traffic in a single-class environment or the highest priority traffic in a multi-class environment. This is rather restrictive. In this paper, we propose a new general service scheme to service flows. This scheme is represented by a latency-rate max-min service curve (LRMMSC). Subsequently, for a network of LRMMSC, we prove the existence of tight bounds on end-to-end queuing delay and backlog. Our approach has two salient features: (1) the general nature of the concept of service curve enables the service scheme to be implemented by many well-known scheduling disciplines; (2) the general network model adopted with no constraints on the manner of packet queuing makes the results applicable to many complex networks. In addition, we have also derived a concise expression of end-to-end queuing delay that depends only on the service offered to the buffers containing the considered flow. This is very useful in practice as the expression is simple and requires minimum amount of information input.

This paper addresses Multicast-Nodes (MC-nodes) and Wavelength Converting-Nodes (WC-nodes) placement problem in Multicast Optical Virtual Private Network (M-OVPN). This problem is motivated by the high cost incurred in the usage of optical splitters and converters in the VPN due to complexity and power considerations. An analytical model for computing the approximate blocking probability in MOVPN with wavelength conversion has been developed. The placement is determined using our proposed innovative Removal algorithm together with the blocking performance computed. We perform simulation studies of our algorithms using NSFNET. The results show that the Removal heuristic is able to locate the optimal placement location within a much shorter time and with higher efficiency compared to existing heuristic. In addition, we also show the flexibility of the heuristics by introducing the hybrid (Combined Removal) and dual (Concurrent Removal) removal mode.

This paper addresses the multicast wavelength assignment problem in wavelength-routed WDM networks with full light splitting and wavelength conversion capabilities. Current approach is based on the assumption that only one available wavelength can be used in a link. This assumption is rather restrictive. In this paper, we liberalize the assumption by allowing multiple available wavelengths in a link to carry the multicast signal. Consequently, based on a multicast-capable switch model, we develop a new multiwavelength multicast wavelength assignment (MMWA) algorithm to carry the multicast signal. Simulation results show that our new algorithm outperforms the existing MNWC algorithm by making significant reduction of wavelength conversion cost. The improvement percentage of MMWA is sensitive to the maximum out-degree value of a node, D. For L=10 (L being the maximum number of available wavelengths on each link), the improvement percentage increases from 20% at D=4 to about 70% at D=16. This is a significant improvement.

This paper proposes an analytical model for the blocking performance of adaptive routing over WDM networks with sparse wavelength conversion. Two key components of the model are 1) separate routes into segments, and calculate the blocking performance of each segment; and 2) calculate overflow traffic to wavelength convertible node, and then get the blocking probability of the node. The blocking probability of the whole network is then calculated as the combination of the blocking probability of segments and nodes. Based on the model, an adaptive routing algorithm is proposed, which is able to finish routing and wavelength assignment in one single step. Numerical results show that among the parameters considered, the number of wavelengths turns out to be the primary factor for the blocking performance.

The future multimedia applications demand large bandwidth and require efficient multicast for economic use of network resources. The wavelength division multiplexing (WDM) networks have emerged as a promising technology to support high bandwidth demands. This paper proposes an expanded graph model to handle the multicast routing and wavelength assignment (MCRWA) problem in WDM optical networks. In the model, the WDM network is transformed into a graph. Application of graph theory algorithm will enable the routing and wavelength assignment to be done in a single step. The model is of general nature and is applicable to all kinds of WDM networks. We apply a degree-constrained SPH heuristic as an example to solve the MCRWA problem in a general WDM network that possesses finite light splitting and wavelength conversion capabilities. The simulation results show the broking performance of the optical networks under various constraints.

Error recovery by retransmission for large scale multicast faces two intrinsic scalability challenges: acknowledgment implosion and exposure to retransmission. This paper proposes a new scheme to reduce the cost of error recovery by using the idea of cumulative negative acknowledgment (CNAK). In the scheme, we assume a window control of size W. A receiver does not send back a NAK immediately upon the discovery of a packet loss. Instead, the receiver accumulates the losses and returns a CNAK to the source at about half of the window interval. Retransmission is carried out on multiple multicast channels which are mapped to window size W. The A /sub i/ multicast channel is mapped to the sequence number i where i = 1,2,...,W. Our scheme has these advantages: one CNAK replaces W/2 number of conventional NAK, thus, greatly reducing the NAK overhead. Moreover, the use of multiple multicast channels for packet retransmission completely eliminates the exposure hazard. We apply the CNAK scheme to the DR local recovery model and show that the proposed C4 protocol is the most efficient protocol among all. The protocol is highly scalable and free of unwanted repair packets.

A new distributed information system called DORMIA has been developed to support mobile information access from portable computers with weak network connectivity. This paper describes the design and implementation of DORMIA. The design aims to provide high availability, heterogeneous support and high efficiency. To maximize availability, users can read or write any accessible replica. A scalable algorithm based on logical clocks has been developed to keep object replicas consistent. Novel methods are used to detect and resolve conflicts based on record level checking. The use of reliable multicast provides effective means to update the replicas. The use of CORBA IDL and Java to define interfaces provides the full heterogeneous support. To enable a mobile client to continue accessing critical data during temporary disconnection, we have developed the pre-fetching and reintegration mechanism to support the disconnected operation. A performance measurement study is subsequently conducted with the prototype implementation. The results indicate that the system developed is highly efficient.

An examination is made of a number of possible implementation strategies using the various prevailing system facilities: processes, threads, kernels and front-end processors. The strategies are analyzed, showing their relative merits in implementations. The analysis leads to the recommendation of an enhanced subsystem architecture that holds the best compromise between the conflicting requirements of modularity and efficiency.>