Incremental scheduling algorithms for WDM/TDM networks with arbitrary tuning latencies

We focus on all-optical broadcast and select slotted WDM networks. Each network user is equipped with one tunable transmitter and one fixed receiver; full connectivity is achieved by tuning transmitters to all different wavelengths available in the optical spectrum. Tuning latencies are considered to be not negligible with respect to the slot time. A network controller allocates fixed size slots in a TDM/WDM frame according to requests issued by users via signalling procedures. User requests are accommodated in the frame incrementally, as soon as they are received by the network controller. Since we aim at an incremental solution, we impose a transparency constraint in the scheduling algorithm: new user requests may be accepted only without affecting existing allocations, otherwise they are refused. We propose a novel scheduling algorithm that may route some flows from source to destination through some intermediate nodes, following a multi-hop approach. A formal definition of an optimal transparent incremental scheduling algorithm is provided as an integer linear programming problem. The optimal incremental scheduling algorithm is NP-hard. Thus, a heuristic quasi-optimal scheduling algorithm is proposed, and its complexity is evaluated. Performance results show that significant benefits can be achieved with respect to traditional single-hop approaches and to other multi-hop approaches.     

Packet scheduling in broadcast WDM networks with arbitrarytransceiver tuning latencies

We consider the problem of scheduling packet transmissions in a broadcast, single-hop wavelength-division multiplexing (WDM) network, with tunability provided only at one end. Our objective is to design schedules of minimum length to satisfy a set of traffic requirements given in the form of a demand matrix. We address a fairly general version of the problem as we allow arbitrary traffic demands and arbitrary transmitter tuning latencies. The contribution of our work is twofold, First we define a special class of schedules which permit an intuitive formulation of the scheduling problem. Based on this formulation we present algorithms which construct schedules of length equal to the lower bound provided that the traffic requirements satisfy certain optimality conditions. We also develop heuristics which, in the general case, give schedules of length equal or very close to the lower bound. Secondly, we identify two distinct regions of network operation. The first region is such that the schedule length is determined by the tuning requirements of transmitters; when the network operates within the second region however, the length of the schedule is determined by the traffic demands, not the tuning latency. The point at which the network switches between the two regions is identified in terms of system parameters such as the number of nodes and channels and the tuning latency. Accordingly, we show that it is possible to appropriately dimension the network to minimize the effects of even large values of the tuning latency     

Efficient scheduling of nonuniform packet traffic in a WDM/TDMlocal lightwave network with arbitrary transceiver tuning latencies

A passive-star-based, broadcast-and-select, local lightwave network which can support a limited number of wavelength-division multiplexed (WDM) channels, but serve a much larger number of nodes, is considered. Each node is equipped with one tunable transmitter and one fixed receiver, and each WDM channel is operated in a time-division multiplexed (TDM) fashion for carrying packet traffic. Bandwidth is allocated to the node pairs when traffic flow between them is nonuniform, while also accommodating transceiver tuning latency. Our approach exploits well-known results from scheduling theory to create efficient transmission schedules. Multiprocessor task scheduling heuristics that can be applied to load balancing in a multichannel network is also examined     

Message scheduling in WDM optical networks with reduced transmitter tuning overhead

Relatively large transceiver tuning overhead is one major difficulty when designing a medium access control scheme for a single-hop passive-star coupled WDM optical network. To overcome this difficulty, we propose two algorithms, namely continuous channel scheduling (CCS) and continuous channel-minimum scheduling latency (CC-MSL), to reduce the negative impact of tuning overhead as much as possible. Extensive simulations have been conducted. And the simulation results show that significant improvement in average delay can be achieved by our new algorithms.     

Multihop packet scheduling in WDM/TDM networks with nonnegligibletransceiver tuning times

This paper addresses the design of packet transmission schedules in photonic slotted wavelength-division multiplexing/time-division multiplexing broadcast-and-select networks with W wavelengths and N nodes. Nodes are equipped with one tunable-wavelength transmitter with nonnegligible tuning times and one fixed-wavelength receiver. A new scheduling algorithm that exploits multihop packet transfer to shorten the duration of scheduling periods is first proposed. A single-hop scheduling algorithm that performs slightly better than previous proposals is then described. A simulation-based analysis of the two algorithms shows that they jointly lead to significant improvements in both throughput and delay with respect to previous single-hop schedules     

波长二次重用的双向WDM星形单跳网

针对有限的数据信道波长数对波分复用星形单跳网容量的限制问题,文章提出了一种波长二次重用、单纤双向传输和多耦合器内连相结合的组网扩容解决方法.与常规波分复用星形网相比,该方法不但将网络所支持的节点数增加了两倍;而且网络的所有数据信道波长都得到二次重用,网络最大吞吐量也增加了两倍;在网络节点数不变的条件下,不但可节省一半的光纤,而且通过波长的二次重用,可大大减小网络中通信节点的排队时延,缓和各通信节点对数据信道波长使用权的竞争矛盾,有效地改善网络性能。     

An isochronous and asynchronous traffic scheduling algorithm fordual-star WDM networks

In this paper, based on the concept of wavelength reusing, a new architecture for interconnecting two wavelength division multiplexing (WDM) star networks is proposed. According to this architecture, the problem of scheduling isochronous as well as asynchronous traffic is investigated. The lower bounds for the problem of minimizing the switching duration and the number of switching modes are derived. A transmission scheduling algorithm for the proposed architecture to efficiently reuse the wavelength is also proposed. For only asynchronous traffic, the analytical result shows that the proposed scheduling algorithm produces solutions equal to the lower bounds. For both isochronous and asynchronous traffic, simulation results show that the average switching duration and the average number of switching modes obtained by the proposed algorithm are quite close to the lower bounds. Simulation results also show that given the same number of users and available wavelengths, the solutions (in terms of the average switching duration and the average number of switching modes) obtained by the proposed scheduling algorithm on the dual-star WDM networks are better than the solutions obtained by the two-phase algorithm on the similar dual-star WDM networks     

Rerouting technique with dynamic traffic in WDM optical networks

In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a shortest path wavelength rerouting (SPWRR) algorithm for dynamic traffic in WDM optical networks. The results have shown that SPWRR algorithm can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network.     

Grooming of arbitrary traffic in SONET/WDM BLSRs

SONET add-drop multiplexers (ADMs) are the dominant cost factor in the SONET/WDM rings. They can potentially be reduced by optical bypass via optical add-drop multiplexers (OADMs) and traffic grooming. In this paper we study the grooming of arbitrary traffic in WDM bidirectional line-switched rings (BLSRs) so as to minimize the ADM cost. Two versions of the minimum ADM cost problem are addressed. In the first version, each traffic stream has a predetermined routing. In the second version, the routing of each traffic stream is not given in advance; however, each traffic stream is fully duplex with symmetric demands, which must be routed along the same path but in opposite directions. In both versions, we further consider two variants depending on whether a traffic stream is allowed to be split at intermediate nodes. All the four combinations are NP-hard even for any fixed line-speed. General lower bounds on the minimum ADM cost are provided. Our traffic grooming follows a two-phased approach. The problem targeted at in each phase is NP-hard itself, except the second phase when the line speed is two. Various approximation algorithms are proposed in both phases, and their approximation ratios are analyzed.     

Multicast traffic aggregation in MPLS-based VPN networks

This article gives an overview of the current practical approaches under study for a scalable implementation of multicast in layer 2 and 3 VPNs over an IP-MPLS multiservice network. These proposals are based on a well-known technique: the aggregation of traffic into shared trees to manage the forwarding state vs. bandwidth saving trade-off. This sort of traffic engineering mechanism requires methods to estimate the resources needed to set up a multicast shared tree for a set of VPNs. The methodology proposed in this article consists of studying the effect of aggregation obtained by random shared tree allocation on a reference model of a representative network scenario.     

WDM光网络中的动态流量疏导

针对波分复用光网络中的业务疏导问题,文章基于通道组交换网络模型,采用波分复用网络中的相对容量算法来解决业务疏导的路由、波长分配和时隙分配问题.基于该模型的算法能够将波长和时隙分配这两个通常分开解决的问题一步解决,因此比现有方法具有更好的效能,仿真也验证了这一点.     

Supporting bursty traffic with bandwidth guarantee in WDM distribution networks

This paper presents new research results of the DARPA-funded ONRAMP consortium on the next generation Internet to study efficient WDM-based network architectures and protocols for supporting broadband services in regional access networks. In particular, we present new efficient scheduling algorithms for bandwidth sharing in WDM distribution networks. The current ONRAMP distribution network architecture has a tree topology with each leaf node (e.g., a router or workstation) sharing access to the root node of the tree, which corresponds to an access node in the feeder network. Our model allows a leaf node to use one or more fixed-tuned or tunable transceivers; moreover, different leaf nodes can support different subsets of wavelengths depending on their expected traffic volumes. An important goal of ONRAMP is to support bandwidth-on-demand services with QoS guarantee over WDM. As a first step toward this goal, we have developed several fast scheduling algorithms for flexible bandwidth reservations in a WDM distribution network. The scheduling algorithms can provably guarantee any bandwidth reservations pattern that does not overbook network resources, i.e., bandwidth reservation (throughput) up to 100% network capacity can be supported.     

Multicast connection capacity of WDM switching networks with limited wavelength conversion

Currently, many bandwidth-intensive applications require multicast services for efficiency purposes. In particular, as wavelength division multiplexing (WDM) technique emerges as a promising solution to meet the rapidly growing demands on bandwidth in present communication networks, supporting multicast at the WDM layer becomes an important yet challenging issue. In this paper, we introduce a systematic approach to analyzing the multicast connection capacity of WDM switching networks with limited wavelength conversion. We focus on the practical all-optical limited wavelength conversion with a small conversion degree d (e.g., d=2 or 3), where an incoming wavelength can be switched to one of the d outgoing wavelengths. We then compare the multicast performance of the network with limited wavelength conversion to that of no wavelength conversion and full wavelength conversion. Our results demonstrate that limited wavelength conversion with small conversion degrees provides a considerable fraction of the performance improvement obtained by full wavelength conversion over no wavelength conversion. We also present an economical multistage switching architecture for limited wavelength conversion. Our results indicate that the multistage switching architecture along with limited wavelength conversion of small degrees is a cost-effective design for WDM multicast switching networks.     

支持不同可靠性要求的WDM网状网业务量疏导算法

WDM光网络中不同的业务流具有不同的可靠性要求，本文研究动态业务下如何解决此类业务量疏导问题，提出了一种在WDM网状网中支持多种可靠要求的业务量疏导算法(MRTG)。仿真结果表明该算法具有很好的性能。     

WDM光网络中动态流量的疏导

流量疏导是当今光网络研究中的一个前沿和热点问题,在波分复用(WDM)光网络中使用流量疏导技术能有效降低网络的成本,减少网络节点中业务信息的处理量.文章讨论了动态流量疏导的意义及其分类,分析了关于在各种网络结构中动态流量疏导的研究近况,最后对今后的发展方向做了一番展望.     

A scheduling application for WDM optical networks

Optical networking using WDM technology has matured considerably, and commercial WDM network equipment and WDM network control and management prototypes have appeared. To use such a network efficiently, a scheduling facility and its enabling mechanisms have to be provided. This scheduling facility should be integrated to interoperate with the rest of the network control and management software such as connection manager or signaling daemon. We present a scheduling application to address this need. The architecture for the application and its key components are presented. Agent-related enabling mechanisms are introduced to monitor the optical signal quality and collect performance measurements. A resource broker is used to manage the communication and interoperability between agents and the application. An event service is developed to decouple the communication between the agents and the scheduling application, and to enable the communication among the agents themselves. The scheduling application consists of the quality of signal information and threshold objects, current network usage, history data module, scheduling module, and access to a performance database. To provide traffic control and high network resource utilization, the application is equipped with wavelength scheduling algorithms. An experimental study for the basic scheduling algorithms has been conducted over the MONET DC network.     

Designs of high-performance multicast scheduling mechanisms in WDM networks

In this article, we propose three multicast scheduling mechanisms, lookback queue access, lookback ratio access, and double check head access, for the employment in the single-star Wavelength Division Multiplexing optical network. Each of the proposed scheduling schemes consists of two phases and is executed in real time. In general, the first phase is to search for a candidate multicast packet that can be sent, without partition, to all of its intended recipients. If phase 1 fails, the second phase is then activated to partition a multicast packet into multiple transmissions in accordance with specific criteria of each individual mechanism. These algorithms are designed to mitigate the head-of-line blocking effect, while at the same time achieving excellent network throughput levels and delay performance via the partitioning procedure. Performance results reveal the distinct features of each mechanism under various scenarios. For a wider range of networking environments, we further propose an interconnected dual-star structure and enhanced multicast scheduling algorithms. These enhanced schemes aim to exploit the inter-data channels efficiently and utilize the wavelength reuse property of the intra-data channels properly. Performance results have demonstrated the merits of deploying the proposed multicast algorithms in such a dual-star structure.     

Virtual fully connected WDM network: A high-performance single-hop architecture for metropolitan area networks

With the widespread use of broadband access technologies and the development of high-speed Internet backbones, the requirement for high-performance metropolitan area networks (MANs) is increasing. Traditional ring- or star-based metro networks are costly to scale up to high speed and cannot recover from multiple failures, while backbone solutions are too expensive to fit into the cost-sensitive metro market. This paper proposes a virtual fully connected (VFC) architecture for metro networks to provide high-performance node-to-node all-optical transportation. The architecture emulates a fully connected network by providing optical channels between node pairs without intermediate buffering, and thus realizes single-hop transportation and avoids expensive packet routers. In addition, a scheduling algorithm is developed for medium access control and dynamic bandwidth allocation, which achieves 100% throughput and provides a fairness guarantee. Simulations show that the VFC network achieves good performance under both uniform and non-uniform loads.     

Algorithms for multicast traffic grooming in WDM mesh networks

Several of the new applications in high-performance networks are of the multicast traffic type. Since such networks employ an optical network infrastructure, and since most of these applications require subwavelength bandwidth, several streams are usually groomed on the same wavelength. This article presents an account of recent advances in the design of optical networks for multicast traffic grooming in WDM mesh networks. The article addresses network design and session provisioning under both static and dynamic multicast traffic. Under static traffic conditions, the objective is to accommodate a given set of multicast traffic demands, while minimizing the implementation cost. Optimal and heuristic solution techniques for mesh network topologies are presented. Under dynamic traffic conditions, techniques for dynamic routing and session provisioning of multicast sessions whose objective is to minimize session blocking probabilities are explained. The article also presents a number of open research issues     

WDM网络中基于分簇的静态业务量疏导算法

针对大多数文献中报道的静态业务量疏导技术不适用于大型光网络的问题,文章基于分簇思想提出了一种有效的静态业务量疏导算法.该方法将大型光网络划分为若干个相互独立的簇,并在每个簇中选择一个节点作为簇头节点采负责簇内和簇间的业务量疏导.仿真结果表明:该算法与已知的静态业务量疏导算法相比具有更好的性能.