WDM optical interconnects with recirculating buffering and limited range wavelength conversion

All-optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has been proposed as a promising candidate to meet the ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. However, with current technology, the cost of optical communication, especially the cost of optical buffering and wavelength conversion, remains a major concern for such applications. In this paper, we study WDM optical interconnects that utilize low cost recirculating buffering and limited range wavelength conversion. We first consider the packet scheduling problem in this type of interconnect, and formalize the problem of maximizing throughput and minimizing packet delay as a matching problem in a bipartite graph. We give an optimal parallel algorithm for this problem that runs in O(Bk/sup 2/) time, compared to O((N+B)/sup 3/k/sup 3/) time if directly applied to existing matching algorithms for general bipartite graphs, where N is the number of input/output fibers of the interconnect, B is the number of fiber delay lines, and k is the number of wavelengths. We also consider efficient switching fabric designs for this type of interconnect. We distinguish between the switching fabric connecting the input fibers to the output fibers and the switching fabric connecting the input fibers to the delay lines and show that by adopting the idea of concentration, the cost of the latter can be reduced significantly in terms of the number of crosspoints.     

Cost-effective designs of WDM optical interconnects

Optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has become a promising networking choice to meet ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/communication applications, such as data browsing in the World Wide Web, multimedia conferencing, e-commerce, and video-on-demand services. As optics becomes a major networking media in all communications needs, optical interconnects will inevitably play an important role in interconnecting processors in parallel and distributed computing systems. We consider a cost-effective design of WDM optical interconnects for current and future generation parallel and distributed computing and communication systems. We first categorize WDM optical interconnects into two different connection models based on their target applications: the wavelength-based model and the fiber-link-based model. Most of existing WDM optical interconnects belong to the first category. We then present a minimum cost design for WDM optical interconnects under wavelength-based model by using sparse crossbar switches instead of full crossbar switches in combination with wavelength converters. For applications that use the fiber-link-based model, we show that network cost can be significantly reduced, and present such a minimum cost design for WDM optical interconnects under this model. Finally, we generalize the idea used in the design for the fiber-link-based model to WDM optical interconnects under the wavelength-based model, and obtain another new design that can trade off switch cost with wavelength converter cost in this type of WDM optical interconnect. The results in this paper are applicable to any emerging optical switching technologies, such as SOA-based and MEMS-based technologies.     

Routing wavelength and time-slot reassignment algorithms for TDM based optical WDM networks

In this paper, we consider the problem of maximizing the time of first lightpath request rejection, T in the circuit-switched time division multiplexed (TDM) wavelength-routed (WR) optical WDM networks. TDM is incorporated into WDM, to increase the channel utilization when the carried traffic does not require the entire channel bandwidth. In TDM–WDM network, multiple sessions are multiplexed on each wavelength by assigning a sub-set of the TDM slots to each session. Thus, given a session request with a specified bandwidth, a lightpath has to be established by using the routing, wavelength and time-slot assignment (RWTA) algorithms. If the lightpath cannot be established, lightpath request rejection or call blocking occurs. As each lightpath is substantial revenue and long-lived, lightpath request rejection is highly unfavourable in the optical backbone networks. In this paper, we are proposing an intelligent routing, wavelength and time-slot reassignment algorithm for multi-rate traffic demands, where, when a call gets blocked, the already established calls in the network are rerouted, wavelength and time-slot reassigned so as to accommodate the blocked call. Since we are talking of slow arrivals and long holding times for the lightpaths, it is possible to do this reassignment while provisioning a new call. Simulation based analyses are used to study the performance of the proposed reassignment algorithm. The results show that the proposed reassignment algorithm can be used to maximize the time of first call blocking, thereby accommodating more calls in the network before upgrading the network capacity.     

Restoration in all-optical GMPLS networks with limited wavelength conversion

A new generation of optical components and the advance of the Generalized Multi-Protocol Label Switching (GMPLS) control plane supporting dynamic provisioning and restoration of optical connections (i.e., lightpaths), brings the vision of the dynamic all-optical network closer to reality. An emerging technology is the conversion between wavelengths, which removes the wavelength continuity constraint, thus allowing an easier and more flexible connection allocation. A limitation in the number of wavelength converters impairs their benefits especially during the restoration phase, when many simultaneous recovery attempts must share residual resources.This paper investigates the restoration performance of GMPLS-controlled all-optical networks with limited wavelength converter deployment. We investigate how different restoration methods, namely span restoration, segment restoration, and end-to-end restoration are affected by the availability of a limited number of wavelength converters at each node. For this purpose an enhanced wavelength assignment scheme compliant with GMPLS signaling is exploited, aiming at saving converters by assigning a higher preference to wavelengths not requiring conversion. An extensive simulation study has been conducted comparing the performance of this scheme to the most advanced scheme based on standard GMPLS signaling for the three restoration methods.Simulation results show that the enhanced wavelength assignment scheme significantly reduces the number of wavelength converters (WCs) necessary to achieve good recovery performance. The enhanced scheme especially improves span restoration performance, where the matching between the stubs’ and recovery segment wavelength may require a WC. End-to-end restoration is the least affected, due to a higher degree of freedom in the route choice, while segment restoration performance lies in between.     

Ant colony optimization for dynamic routing and wavelength assignment in WDM networks with sparse wavelength conversion

Since optical WDM networks are becoming one of the alternatives for building up backbones, dynamic routing, and wavelength assignment with delay constraints (DRWA-DC) in WDM networks with sparse wavelength conversions is important for a communication model to route requests subject to delay bounds. Since the NP-hard minimum Steiner tree problem can be reduced to the DRWA-DC problem, it is very unlikely to derive optimal solutions in a reasonable time for the DRWA-DC problem. In this paper, we circumvent to apply a meta-heuristic based upon the ant colony optimization (ACO) approach to produce approximate solutions in a timely manner. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. The ACO algorithm proposed in this paper incorporates several new features so as to select wavelength links for which the communication cost and the transmission delay of routing the request can be minimized as much as possible subject to the specified delay bound. Computational experiments are designed and conducted to study the performance of the proposed algorithm. Comparing with the optimal solutions found by an ILP formulation, numerical results evince that the ACO algorithm is effective and robust in providing quality approximate solutions to the DRWA-DC problem.     

On burst rescheduling in OBS networks with partial wavelength conversion capability

The core nodes in an optical burst switching (OBS) network are normally equipped with wavelength converters (WCs) to reduce the burst loss probability. Since WCs are expensive and still immature technologically, it is desirable to reduce the number of WCs in the network and to have partial wavelength conversion capability at the core nodes. Nevertheless, a majority of algorithms in the literature are proposed under the full wavelength conversion assumption. As a result, they do not consider the burst loss caused by insufficient WCs, i.e., bursts dropped due to the unavailability of free WCs to convert them to unused wavelengths. In this paper, we demonstrate how to use burst rescheduling to decrease the burst loss due to insufficient WCs and hence cut down on the overall burst loss probability in OBS networks. Two burst rescheduling algorithms are proposed. Their effectiveness in reducing the overall burst loss probability is verified through simulation experiments.     

Optimal control data scheduling with limited controller-plant communication

This paper considers optimal control data scheduling for finite-horizon linear quadratic regulation (LQR) control of scalar systems with limited controller-plant communication. Both the single-system and multiple-system scenarios are studied. For the first scenario, we derive the necessary and sufficient condition for a comparison function to be positive. Using this condition, the optimality of an explicit schedule is extended from unstable systems in the existing work to general systems. For the second scenario, we are able to construct explicit optimal scheduling policies for three particular classes of problems. Numerical examples are provided to illustrate the proposed results.     

Optimal scheduling of contract algorithms with soft deadlines

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time \(w(t)\le c \cdot t\), for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.     

Routing and wavelength assignment for hypercube in array-based WDM optical networks

Hypercube is one of the most versatile and efficient communication patterns shared by a large number of computational problems. As the number of edges in hypercube grows logarithmically with the size of networks, the complexity of network topologies can be significantly reduced to realize hypercube in optical networks by taking advantage of the parallel transmission characteristic of optical fibers. In this paper, we study the routing and wavelength assignment for realizing hypercube on WDM optical networks including linear arrays and rings with the consideration of communication directions. Specifically, we analyze this problem for both bidirectional and unidirectional hypercubes. For each case, we identify a lower bound on the number of wavelengths required, and design the embedding scheme and wavelength assignment algorithm that uses a provably near-optimal number of wavelengths. In addition, we extend the results to meshes and tori. By our embedding schemes, many algorithms, originally designed based on hypercubes, can be applied to optical networks, and the wavelength requirements can be easily derived using our obtained results.     

A comparison of wavelength reservation protocols for WDM optical networks

In WDM optical networks, wavelength is the critical resource for efficient communication of traffic. Hence, suitable protocols are required to allocate and use the wavelengths efficiently. We have studied the wavelength reservation protocols of such networks, which are already developed and reported in literature. Following their historical development, we have outlined some generalized classification for them and provided comparison of their performances. Finally, on the basis of the previous works, we have discussed some future scopes, which may be explored for further improvement in performance of the protocols.     

Adaptive scheduling for integrated traffic on WDM optical networks

One of the important issues in the design of future generation of high-speed networks is to provide differentiated service to different types of traffic with various time constraints. In this paper, we study the problem of providing real-time service to either hard or soft real-time messages and normal transmission service to variable-length messages without time constraints in WDM optical networks. We propose an adaptive scheduling algorithm for scheduling message transmissions in order to improve the network performance when both real-time and non real-time messages are transmitted in one topology. We have analyzed the complexity of the algorithm to show its feasibility. We have conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithm. The study suggests that when scheduling message transmission in WDM networks differentiated services should be considered in order to meet time constraints of real-time messages while non real-time messages are being served so that the overall performance of the network could be improved.     

WDM光网络动态虚拟拓扑重构算法

针对波分复用光纤网络上业务流量动态改变的问题,为了使光纤网络能支持更多的业务连接,需要对虚拟拓扑进行重构。基于链路最大负载和包平均跳步距离,利用混合线性规划公式对重构问题进行描述,在此基础上提出一个自适应拓扑重构算法,达到提高网络吞吐量的目的。仿真结果表明,该算法可以有效地改善网络性能。     

A heuristic for placement of limited range wavelength converters in all-optical networks

Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the optical fiber. Wavelength converters play an important role in enhancing the fiber utilization and reducing the overall call blocking probability of the network. As the distortion of the optical signal increases with the increase in the range of wavelength conversion in optical wavelength converters, limited range wavelength conversion assumes importance. Placement of wavelength converters is a NP complete problem [K.C. Lee, V.O.K. Li, IEEE J. Lightwave Technol. 11 (1993) 962–970] in an arbitrary mesh network. In this paper, we investigate heuristics for placing limited range wavelength converters in arbitrary mesh wavelength routed optical networks. The objective is to achieve near optimal placement of limited range wavelength converters resulting in reduced blocking probabilities and low distortion of the optical signal. The proposed heuristic is to place limited range wavelength converters at the most congested nodes, nodes which lie on the long lightpaths and nodes where conversion of optical signals is significantly high. We observe that limited range converters at few nodes can provide almost the entire improvement in the blocking probability as the full range wavelength converters placed at all the nodes. Congestion control in the network is brought about by dynamically adjusting the weights of the channels in the link thereby balancing the load and reducing the average delay of the traffic in the entire network. Simulations have been carried out on a 12-node ring network, 14-node NSFNET, 19-node European Optical Network (EON), 28-node US long haul network, hypothetical 30-node INET network and the results agree with the analysis.     

Optimal robot task scheduling based on genetic algorithms

Industrial robots should perform complex tasks in the minimum possible cycle time in order to obtain high productivity. The problem of determining the optimum route of a manipulator's end effector visiting a number of task points is similar but not identical to the well-known travelling salesman problem (TSP). Adapting TSP to Robotics, the measure to be optimized is the time instead of the distance. In addition, the travel time between any two points is significantly affected by the choice of the manipulator's configuration. Therefore, the multiple solutions of the inverse kinematics problem should be taken into consideration.In this paper, a method is introduced to determine the optimum sequence of task points visited by the tip of the end effector of an articulated robot and it can be applied to any non-redundant manipulator. This method is based on genetic algorithms and an innovative encoding is introduced to take into account the multiple solutions of the inverse kinematic problem. The results show that the method can determine the optimum sequence of a considerable number of task points for robots up to six-degrees of freedom.     

Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information

In semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. This may not be true in some application. This paper considers semi-online problems on identical machines with inexact partial information. Three problems are considered, where we know in advance that the optimal value, or the largest job size are in given intervals, respectively, while their exact values are unknown. We give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter r ∈[1, ∞). We establish for which r the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal preemptive semi-online algorithms are then obtained. Research supported by Natural Science Foundation of China (10671177) and Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in proceedings of ISAAC’05.     

Optimal algorithms for the batch scheduling problem in OBS networks

This paper introduces optimal batch scheduling algorithms for the problem of scheduling batches of bursts in optical burst switching networks. The problem is modelled as a job scheduling problem with identical machines. The consideration of previously scheduled bursts in the scheduling allows such modeling. Two optimal algorithms with polynomial time complexity are derived and evaluated. Results show that the algorithm that allows re-scheduling of previously scheduled bursts leads to preferred solutions.Moreover, an extended version of the JET reservation protocol is proposed for efficient handling of batches of bursts. Results obtained via simulation prove the superior performance of the BATCHOPT algorithm.     

Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l_p norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾ 1. For minimizing the l_p norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p.     

Microelectromechanical vibration sensor with optical interconnects

A resonant vibration sensor realized using silicon micromachining for wear monitoring of rotating machinery is described. It comprises a mechanical resonator, piezoresistive bridge, and components for fiber-optical signal readout by an infrared light-emitting diode. The performance of the microsystem is demonstrated by its static and dynamical behavior. The results confirm that the described sensor has the potential for on-line vibration control of rotating machinery operated under the conditions of industrial production     

Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) [1], in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio is also given.