On the joint link dimensioning and routing metric assignment problem for reliable WDM networks

In this paper, we tackle the joint link dimensioning and routing metric assignment problem for reliable wavelength division multiplexing (WDM) networks. This design problem consists to find the number of wavelength channels on each link and the routing metrics (considering shortest-path routing) that ensure the routing of all virtual wavelength paths (VWPs) and the successful rerouting of the reliable VWPs for all failure scenarios of interest to the network planner. A mixed integer mathematical programming model is proposed for the problem. The model is adapted for the single link failure scenarios. Since the problem is NP-hard, we propose a tabu search algorithm to obtain good approximate solutions for real-size instances of the problem. Finally, a lower bound is proposed and numerical results are presented and analyzed.     

Scheduling algorithms for multicast traffic in TDM/WDM networks with arbitrary tuning latencies

We consider all-optical Time Division Multiplexing (TDM)/Wavelength Division Multiplexing (WDM) broadcast and select networks with slotted operation. Each network access node is equipped with one fixed transmitter and one tunable receiver; tuning times are not negligible with respect to the fixed size slot time. We discuss efficient scheduling algorithms to assign TDM/WDM slots to multicast traffic in such networks. The problem is shown to be NP-hard; thus, heuristic algorithms based on the Tabu Search meta-heuristic are proposed, and their performance are assessed using randomly created request matrices based on two types of multicast traffic patterns. We show that significant advantages can be obtained by using these novel algorithms with respect to simpler greedy algorithms, even when restricting CPU times to realistic values to make the algorithms of practical use.     

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.     

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.     

Link scheduling state information based offset management for fairness improvement in WDM optical burst switching networks

In wavelength division multiplexed (WDM)-based optical burst switching (OBS) networks, bursts that traverse longer paths are more likely to be dropped compared to bursts that traverse shorter paths resulting in a fairness problem. Fairness here refers to having, for all ingress–egress node pairs in a network, a burst to have equal likelihood to get through independent of the hop length involved. In this paper, we develop a link scheduling state based fairness improvement method which can be used in a classless as well as a multi-class environment. The basic idea is to collect link scheduling state information and use it to determine the offset times for routes with different hop lengths. By using the online link state information, this method periodically computes and adapts the offset times needed, thus inherently accounting for the traffic loading patterns and network topological connectivity. It also ensures that the delay experienced by a burst is low and shorter-hop bursts are not over-penalized while improving the performance of longer-hop bursts. The effectiveness of the proposed method is evaluated through simulation experiments.     

Design and Analysis of a Backbone Architecture with TDMA Mechanism for IP Optical Networking

This paper presents a new technique for constructing IP over photonic systems. The use of lable switching is assumed in the IP routers, while a new routing architecture is introduced to transport IP packets across an optical backbone network. The architecture is based on a two-level TDMA structure with wavelength division multiplexing (WDM). Many IP-based network applications such as high-resolution image, distributed database, and real-time video/audio service generally require high-speed transmissions in WAN/LAN. The network traffic in these applications usually exhibits traffic locality. As a result, traditional TDMA is not efficient for such traffic. Consequently, based on the traffic parameters such as locality and loading, an architecture named a PG (Partition-Group) Network is proposed. Furthermore, the interleaved control slot (ICS) with cross-group section (CGS) or non-cross-group section (NCGS) for reducing collisions is also presented. The slot reuse can be easily achieved by using the ICS scheme, and the slot utilization of the network can be improved within the high traffic locality.     

Traffic grooming, routing, and wavelength assignment in WDM transport networks with sparse grooming resources

While a single fiber strand in wavelength division multiplexing (WDM) has over a terabit-per-second bandwidth and a wavelength channel has over a gigabit-per-second transmission speed, the network may still be required to support traffic requests at rates that are lower than the full wavelength capacity. To avoid assigning an entire lightpath to a small request, many researchers have looked at adding traffic grooming to the routing and wavelength assignment (RWA) problem. In this work, we consider the RWA problem with traffic grooming (GRWA) for mesh networks under static and dynamic lightpath connection requests. The GRWA problem is NP-Complete since it is a generalization of the RWA problem which is known to be NP-Complete. We propose an integer linear programming (ILP) model that accurately depicts the GRWA problem. Because it is very hard to find a solution for large networks using ILP, we solve the GRWA problem by proposing two novel heuristics. The strength of the proposed heuristics stems from their simplicity, efficiency, and applicability to large-scale networks. Our simulation results demonstrate that deploying traffic grooming resources on the edge of optical networks is more cost effective and results in a similar blocking performance to that obtained when distributing the grooming resources throughout the optical network domain.     

A global approach for designing reliable WDM networks and grooming the traffic

In this paper, we address the global problem of designing reliable wavelength division multiplexing (WDM) networks including the traffic grooming. This global problem consists in finding the number of optical fibers between each pair of optical nodes, finding the configuration of each node with respect to transponders, finding the virtual topology (i.e., the set of lightpaths), routing the lightpaths, grooming the traffic (i.e, grouping the connections and routing them over the lightpaths) and, finally, assigning wavelengths to the lightpaths. Instead of partitioning the problem into subproblems and solving them successively, we propose a mathematical programming model that addresses it as a whole. Numerical results are presented and analyzed.     

浅析波分复用技术在电信本地网中的应用

本文在现代光通信的基础上,主要对DWDM技术的基本原理、关键技术、特点和影响因素做一个全面的论述。同时结合实际的工程应用,进一步论证了这种技术的广泛应用前景,最后论述了下一代密集波分复用（DWDM）系统的发展趋势和面临的问题。     

On-Line Resource Management with Application to Routing and Scheduling

We propose a framework to model on-line resource management problems based on an on-line version of positive linear programming. We consider both min cost problems and max benefit problems and propose logarithmic competitive algorithms that are optimal up to a constant factor. The proposed framework provides a general methodology that applies to a wide class of on-line problems: shop scheduling, packet routing, and in general a class of packing and assignment problems. Previously studied problems as on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework. Received December 18, 1996; revised March 2, 1997.     

并行FFT的通信模式在一组规则WDM光互连网络上的波长分配

在光互连网络上实现并行算法的通信模式是当前一个颇受关注的研究领域,基于顺序映射和移位逆序映射两种不同的嵌入方式,分析了在一组规则WDM光网络上实现并行FFT的通信模式所需的波长数．结论表明：将并行FFT的通信模式嵌入在线性阵列、环、二维mesh和二维torus光网络上。采用移位逆序映射方式比采用顺序映射方式所需的波长数少．     

基于博弈均衡的WDM光网络动态恢复策略

提出一种基于博弈论和D*思想的动态均衡启发式算法,求解波分复用(WDM)光网络中波长级恢复问题。算法将网络中的各边代价与当前波长使用情况综合考虑,运用博弈论原理动态构建估计函数,实现了WDM光网络的高效恢复。仿真结果表明,该算法能有效地降低光路阻塞,提高恢复率,其快速和智能特性能够满足恢复时间的要求。     

多粒度光网络中动态路由与波长分配算法

通过分析多粒度光网络路由与波长分配的特点,针对WAPG算法的波长碎片问题,通过定义5种不同的逻辑链路权重,修改了WAPG算法的波长权重标注方法,达到减少波长碎片的目的。仿真结果表明,提出的修正算法有效地减少了多粒度光网络中的波长转换数,降低网络的阻塞概率,同时节省网络资源。     

WDM star single-hop network reusing wavelengths

An efficient scheme of wavelength reuse is presented for solving the capacity limitation of WDM star single-hop networks by limited wavelengths. According to this scheme, the nodes supported by the network can be at least doubled under limited wavelength numbers. Under the same number of nodes, the delay of network can be greatly lowered, the throughput of the network can be increased 1-3 times, and the properties of the network can be efficiently improved.     

基于PCI总线运动控制卡及WDM驱动程序设计

本文从PCI总线的DSP运动控制卡的硬件结构和总线设计出发,研究了基于WDM的PCI总线驱动的设计步骤和方法。     

使用可调ADM的对称全光树网上的调度算法

波分复用技术可以显著提高光传输网络的带宽,是未来主干网的核心技术之一.工作波长可调节的加载/下载复用器(ADM)是实现该技术的主要光学器件之一,研究使用可调ADM的全光网络上的任务调度问题具有重要的理论和应用价值.该文研究了在每个节点放置一个可调ADM的对称全光树网上的任务调度问题,首先证明了它是NP完全的,接着给出了星形网络上的近似算法及其性能分析.最后,将一般树网上任务调度问题规约为星形网络上相同的问题,得到了一个2×(1.1×Opt 0.8 L)/Opt近似算法.     

一种分布式系统的处理机调度算法

本文讨论在分布式系统中当相邻的处理机不能同时工作时的处理机调度算法．     

机群系统中有状态应用的调度算法研究

有状态的应用是当今因特网中较为典型的一种应用，利用机群系统可以有效地实现该种应用的扩容。请求调度算法是该种系统的关键技术，它决定机群系统的性能能否充分发挥。本文研究了轮循算法在有状态应用的使用。通过理论分析和实验仿真，指出了影响系统性能的主要因素。研究表明，该法在不同的应用条件下，有显著不同的性能表现。     

1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings

We give a 1.5-approximation algorithm for the weighted maximum routing and wavelength assignment problem on undirected ring networks. This improves the previous 1.58-approximation result.