Clustering‐based scheduling: A new class of scheduling algorithms for single‐hop lightwave networks

In wavelength division multiplexing (WDM) star networks, the construction of the transmission schedule is a key issue, which essentially affects the network performance. Up to now, classic scheduling techniques consider the nodes' requests in a sequential service order. However, these approaches are static and do not take into account the individual traffic pattern of each node. Owing to this major drawback, they suffer from low performance, especially when operating under asymmetric traffic. In this paper, a new class of scheduling algorithms for WDM star networks, which is based on the use of clustering techniques, is introduced. According to the proposed Clustering‐Based Scheduling Algorithm (CBSA), the network's nodes are organized into clusters, based on the number of their requests per channel. Then, their transmission priority is defined beginning from the nodes belonging to clusters with higher demands and ending to the nodes of clusters with fewer requests. The main objective of the proposed scheme is to minimize the length of the schedule by rearranging the nodes' service order. Furthermore, the proposed CBSA scheme adopts a prediction mechanism to minimize the computational complexity of the scheduling algorithm. Extensive simulation results are presented, which clearly indicate that the proposed approach leads to a significantly higher throughput‐delay performance when compared with conventional scheduling algorithms. We believe that the proposed clustering‐based approach can be the base of a new generation of high‐performance scheduling algorithms for WDM star networks. Copyright © 2008 John Wiley & Sons, Ltd.     

Scheduling in Optical WDM Networks Using Hidden Markov Chain Based Traffic Prediction

This paper presents the design and performance analysis of a predictor-based scheduling algorithm for optical wavelength division multiplexed (WDM) networks. WDM technology provides multiple, simultaneous and independent gigabit-per-second channels on a single fiber. A reservation-based multiple access control (MAC) protocol is considered here for a local area WDM network based on the passive star topology. The MAC protocol schedules reservation requests from the network nodes on the multiple channels. In previous work, we have presented an on-line scheduling algorithm for such a network. We have shown earlier that schedule computation time can significantly affect performance and the scheduling algorithms should be simple for better performance. In this work, we further improve system performance by using a hidden Markov chain based prediction algorithm. The objective here is to reduce the amount of time spent in computing the schedule by predicting traffic requests. Performance analysis based on discrete-event simulation, varying parameters such as number of nodes and channels is presented. The results show that the error of prediction is reasonable for most cases: more than 70% of the time, the error between actual request and predicted request is less than 20%. Network throughput is higher with the proposed prediction algorithm due to pipelining of schedule computation.     

WDM光网络多跳业务量疏导算法

针对具有多跳疏导能力的WDM光网络进行了研究,提出了一种基于固定备选路由的多跳业务量疏导算法（FO-HC-MH）。该算法对备选路由的跳数进行限制,因而可以节约使用网络的收发器资源。仿真实验表明,与FO-MH算法相比,在网络负载较低的情况下该算法节约效果明显。     

Dynamic hybrid grooming based on power efficiency in green IP over WDM networks

Due to the rapid growth of various applications, the network devices scale and complexity are significantly increased. Meanwhile, to deal with the burst IP traffic, the network devices need to provide continuous services, which will result in the excessive power consumption. Meanwhile, with the development of IP network and intelligent optical switch network, the backbone network tends to be an IP over wavelength-division-multiplexing (WDM) network. Therefore, it has attracted wide interests in both academic and industrial communities to build power-efficient (i.e., green) IP over WDM network, where we can switch several IP-level requests as one unit in the WDM optical layer. This method is called hybrid grooming and it requires less component power than that of electronic IP routers in the IP layer. Under this hybrid approach, the traffic grooming multiplexes many IP-level requests into a high-capacity lightpath; meanwhile the reduction in power consumed by optical-electrical-optical conversions is achieved through optical bypass. However, the power consumed by components used to establish lightpaths should also be considered. One network with the higher power efficiency not only saves more power followed by hybrid grooming but also requires the lower power consumption of establishing lightpaths. In this paper, to improve the power efficiency of dynamic IP over WDM network, we design two kinds of Wavelength Integrated Auxiliary Graphs (WIAGs), each of which contains one Virtual Topology Layer and multiple Wavelength-Plane Layers. Based on WIAGs, we propose two heuristic algorithms named single-hop grooming with considering power efficiency and multi-hop grooming with considering power efficiency (MGPE) since grooming is NP-hard. Simulation results demonstrate that MGPE obtains the higher power efficiency, although it has the slightly higher time complexity; the power efficiency mainly depends on the kind of grooming strategy (single- or multi-hop) we use while the increasing number of available transceivers in each node cannot improve the power efficiency, although it can make blocking probability decrease.     

CS-POSA: A High Performance Scheduling Algorithm for WDM Star Networks

In this paper a new packet scheduling algorithm for WDM star networks is introduced. The protocol adopted is pre-transmission coordination-based and packet collisions have been eliminated due to predetermination of the timeslots each node transmits in a demand matrix. The requests of the transmitted packets are predicted through Markov chains in order to reduce the calculation time of the final scheduling matrix. This is accomplished by pipelining the schedule computation. The innovation that this algorithm introduces is to modify the service sequence of the node. The proposed algorithm is studied via extensive simulation results and it is proved that changing the sequence that nodes transmit, from the node with the largest number of requests to the node with the fewest requests, that there is an increase in the throughput of the network, with a minimum (almost zero) cost in mean time delay and in delay variance.     

A simplified optical star network using distributed channelcontrollers

Future photonic networks may be based on emerging wavelength-division-multiplexing (WDM) technology. In single-hop LAN's using a passive optical star coupler, stations normally access the network using some combination of wavelength-agile transmission and reception. Unfortunately, this parallel channel architecture tends to increase and complicate the user station hardware and protocols. In this paper, a new network architecture is presented. The objective of the design is to simplify the user stations as much as possible. This is accomplished through the use of a set of distributed channel controllers-one for each WDM channel. The network is thus referred to as the distributed channel controller network (DCCN). The channel controllers assist in the operation of the network in a number of ways. To further simplify the design, bandwidth is allocated hierarchically on each channel. This decouples system operation into two levels. At the higher level, band width partitioning may be done in a static or dynamic fashion. The lower level determines the dynamic use of slots. Two options for media access are considered. The first is a hybrid approach based upon custom hardware-based request scheduling. Allocations are generated by the channel controllers electronically and data transmission occurs using station wavelength agility. The second is much more distributed. Each set of competing stations builds a distributed queue based upon observed requests. It is found that the proposed architecture supports higher throughput than in other similar networks with the same hardware requirements. An analytic model is introduced for calculating mean station delay. Simulations show that it accurately predicts network performance     

On the macroscopic optimization of multicell wireless systems with multiuser detection and multiple antennas - uplink analysis

In this paper, we consider a system with K single-antenna client users, n/sub B/ base stations (each base station has n/sub R/ antennas), as well as a centralized controller. A client user could be associated with a single base station at any time. All the base stations operate at the same frequency and have optimal multiuser detection per base station which cancels intracell interference only. We consider a general problem of uplink macroscopic resource management where the centralized controller dynamically determines an appropriate association mapping of the K users with respect to the n/sub B/ base stations over a macroscopic time scale. We propose a novel analytical framework for the above macroscopic scheduling problems. A simple rule is to associate a user with the strongest base station (camp-on-the-strongest-cell), and this has been widely employed in conventional cellular systems. However, based on the optimization framework, we found that this conventional approach is in fact not optimal when multiuser detection is employed at the base station. We show that the optimal macroscopic scheduling algorithm is of exponential complexity, and we propose a simple greedy algorithm as a feasible solution.     

基于传输块调度的WCDMA上行负荷控制算法

在WCDMA系统中,小区的无线资源管理通常是在无线网络控制器(RNC)节点内完成.然而,专用传输信道上传输格式可以逐帧改变,基于传输格式的快速变化实际上构成一种无线资源控制能力。这种控制能力是由UE和Node B的MAC实体以及物理层协同完成的,完全不需要三层信令参与。该文根据WCDMA专用传输信道传输格式的快速变化能力,结合基于类的QoS策略,针对上行信道提出一种负荷控制算法,用以支持全分组业务。研究结果表明,在多业务环境下,各个用户能公平共享无线资源、同时能够实现实时业务时延保证。     

An efficient transmission scheduling algorithm for awavelength-reusable local lightwave network

Although single-hop star networks based on wave-length division multiplexing (WDM) are attractive owing to their all-optical communication features, the throughput of such lightwave networks is limited due to the small number of available wavelengths. In this paper, a wavelength-reusable local lightwave network that consists of two interconnected WDM star networks is proposed. Based on this architecture, the lower bounds for the problems of minimizing the switching duration and the number of switching modes are derived. A transmission scheduling algorithm for this architecture to efficiently reuse the wavelengths is also proposed. The analytical result shows that the proposed scheduling algorithm always produces solutions close to the lower bounds. Simulation results 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 matrices) obtained by the proposed scheduling algorithm on the interconnected WDM networks are better than the optimal solution on a single-star WDM network. In most cases, the performance improvement achieves 20 to 45%     

A novel robust routing algorithm for multi-granularity connection requests in wavelength division multiplexing mesh networks

In this paper, we propose a novel robust routing algorithm based on Valiant load-balancing under the model of polyhedral uncertainty (i.e., hose uncertainty model) for WDM (wavelength division multiplexing) mesh networks. Valiant load-balanced robust routing algorithm constructs the stable virtual topology on which any traffic patterns under the hose uncertainty model can be efficiently routed. Considering there are multi-granularity connection requests in WDM mesh networks, we propose the method called hose-model separation to solve the problem for the proposed algorithm. Our goal is to minimize total network cost when constructing the stable virtual topology that assures robust routing for the hose model in WDM mesh networks. A mathematical formulation (integer linear programming, ILP) about Valiant load-balanced robust routing algorithm is presented. Two fast heuristic approaches are also proposed and evaluated. We compare the network throughput of the virtual topology constructed by the proposed algorithm with that of the traditional traffic grooming algorithm under the same total network cost by computer simulation.     

Task Scheduling and Lightpath Establishment in Optical Grids

Data-intensive Grid applications require huge data transferring between multiple geographically separated computing nodes where computing tasks are executed. For a future WDM network to efficiently support this type of emerging applications, neither the traditional approaches to establishing lightpaths between given source destination pairs are sufficient, nor are those existing application level approaches that consider computing resources but ignore the optical layer connectivity. Instead, lightpath establishment has to be considered jointly with task scheduling to achieve best performance. In this paper, we study the optimization problems of jointly scheduling both computing resources and network resources. We first present the formulation of two optimization problems with the objectives being the minimization of the completion time of a job and minimization of the resource usage/cost to satisfy a job with a deadline. When the objective is to minimize the completion time, we devise an optimal algorithm for a special type of applications. Furthermore, we propose efficient heuristics to deal with general applications with either optimization objective and demonstrate their good performances in simulation.     

A slot‐based BS scheduling with maximum latency guarantee and capacity first in 802.16e networks

The IEEE 802.16e standard specifies the QoS support at the MAC level for wireless broadband access network. To meet the QoS requirements, an efficient scheduling algorithm at base station (BS), which is not defined in the standard, is necessary for slots allocation. In this paper, a Slot‐based BS scheduling algorithm with Maximum Latency Guarantee and Capacity First (SMLG‐CF) is proposed. With SMLG‐CF, the connection request is satisfied with highest slot capacity first. Together with the use of dynamic sub‐frame adjustment, the overall system transmission can be efficiently improved. Through the finer slots calculation and accurate transmission time scheduling, the maximum latency guarantee can be better achieved for urgent requests. In the simulation, we compare the proposed mechanism with the deficit fair priority queue scheduling algorithm and the Highest Urgency First scheduling algorithm. The simulation results reveal that SMLG‐CF outperforms both algorithms from the aspect of maximum latency violation rate and average transmission rate. Copyright © 2011 John Wiley & Sons, Ltd.     

A heuristic approach to incremental and reactive scheduling

This paper describes a heuristic approach to incremental and reactive scheduling. Incremental scheduling is the process of modifying an existing schedule if the initial schedule does not meet its stated initial goals. Modifications made to a schedule during incremental scheduling typically consist of adding one or more activities by rescheduling existing activities. Reactive scheduling is performed when changes need to be made to an existing schedule due to uncertain or dynamic environments such as changes in available resources or the occurrence of targets of opportunity. Only minor changes are made during both incremental and reactive scheduling because a goal of rescheduling procedures is to minimally impact the schedule. A scheduling system generates a schedule in three phases. An initial batch scheduling phase, an incremental scheduling phase and a reactive scheduling phase. During the first phase, no rescheduling is attempted. All user requests are submitted to the scheduler and an initial schedule is created. During the second phase, non-computationally complex strategies must be used since the number of possible schedules that can be generated increases exponentially with the number of requests. Since simple strategies must be used for initial schedule creation, any schedule can potentially be greatly improved through the use of an incremental scheduling phase. Reactive scheduling occurs in near real-time in response to the occurrence of targets of opportunity. Consequently, a reactive scheduler must be able to generate schedules within acceptable time limits. Manual reactive scheduling is an inefficient strategy, and automated exhaustive search techniques are infeasible because of time limits. This paper describes the heuristic search techniques employed by the Request Oriented Scheduling Engine (ROSE), a prototype generic scheduler (Zoch & Hall, 1988). Specifically, we describe heuristics that efficiently approximate the cost of reaching a goal from a given state and effective mechanisms for controlling search.     

RMFS：一种支持用户交互的流媒体调度方案

基于组播的流调度算法能够有效降低服务器和网络带宽消耗.但研究表明,在用户进行VCR交互操作情况下,这些算法的性能将急剧恶化.该文提出一种有效支持用户交互的视频点播系统流调度方案:常规组播固定调度RMFS.RMFS采用基于请求类的接纳控制策略,并通过流合并机制来合并单播流.分析了RMFS方案的最佳组播间隔、最佳请求阈值和最小服务器容量需求.仿真结果验证了分析模型的正确性和RMFS方案的可行性.     

A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

Efficient multi-hop scheduling algorithms for packet transmissions in WDM optical star networks

This paper proposes multi-hop scheduling algorithms for the All-to-All Broadcast (AAB) problem in Wavelength Division Multiplexed (WDM) optical star networks. The multi-hop AAB problem can be split into two subproblems: Logical Topologies Construction (LTC) problem, and Transmission Scheduling (TS) problem. For improving the efficiency of multi-hop scheduling, we focus on a new multi-hop transmission model and transfer the LTC problem to a special case of the Round Robin Tournament (RRT) problem. In the proposed logical topologies, our multi-hop scheduling algorithms can easily overlap the tuning latency and reduce the number of tuning operations on each node. We compare our results with previous research in terms of schedule length. Overall results indicate that our multi-hop scheduling algorithms have better performance than previous algorithms.     

Efficient sequencing techniques for variable-length messages in WDMnetworks

Message sequencing and channel assignment are two important issues that need to be addressed when scheduling variable-length messages in a wavelength division multiplexing (WDM) network. Channel assignment addresses the problem of choosing an appropriate data channel via which a message is transmitted to a node. This problem has been addressed extensively in the literature. On the other hand, message sequencing which addresses the order in which messages are sent, has rarely been addressed. In this paper, we propose a set of scheduling techniques for single-hop WDM passive star networks, which address both the sequencing aspect and the assignment aspect of the problem. In particular, we develop two priority schemes for sequencing messages in a WDM network in order to increase the overall performance of the network. We evaluate the proposed algorithms, using analytical modeling and extensive discrete event simulations, by comparing their performance with state-of-the-art scheduling algorithms that only address the assignment problem. We find that significant improvement in performance can be achieved using our scheduling algorithms where message sequencing and channel assignment are simultaneously taken into consideration. This suggests that, when scheduling messages in WDM networks, one has to consider message sequencing, as well as channel assignment. As a result, we anticipate that this research will open new directions into the problem of on-line scheduling in WDM networks     

Channel sharing in multi-hop WDM lightwave networks: realizationand performance of multicast traffic

A local lightwave network can be constructed by employing two-way fibers to connect nodes in a passive-star physical topology, and the available optical bandwidth may be effectively accessed by the nodal transmitters and receivers at electronic rates using wavelength division multiplexing (WDM). The number of channels, ω, in a WDM network is limited by technology and is usually less than the number of nodes, N, in the network. We provide a general method using channel sharing to construct practical multi-hop networks under this limitation. Channel sharing may be achieved through time division multiplexing. The method is applied to a generalized shuffle-exchange-based multi-hop architecture, called GEMNET. Multicasting-the ability to transmit information from a single source node to multiple destination nodes-is becoming an important requirement in high-performance networks. Multicasting, if improperly implemented, can be bandwidth-abusive. Channel sharing is one approach toward efficient management of multicast traffic. We develop a general modeling procedure for the analysis of multicast (point-to-multipoint) traffic in shared-channel, multihop WDM networks. The analysis is comprehensive in that it considers all components of delay that packets in the network experience-namely, synchronization, queuing, transmission, and propagation. The results show that, in the presence of multicast traffic, WDM networks with ω相似文献   

Gain scheduler middleware: a methodology to enable existing controllers for networked control and teleoperation - part I: networked control

Conventionally, in order to control an application over a data network, a specific networked control or teleoperation algorithm to compensate network delay effects is usually required for controller design. Therefore, an existing controller has to be redesigned or replaced by a new controller system. This replacement process is usually costly, inconvenient, and time consuming. In this paper, a novel methodology to enable existing controllers for networked control and teleoperation by middleware is introduced. The proposed methodology uses middleware to modify the output of an existing controller based on a gain scheduling algorithm with respect to the current network traffic conditions. Since the existing controller can still be utilized, this approach could save much time and investment cost. Two examples of the middleware applied for networked control and teleoperation with IP network delays are given in these two companion papers. Part I of these two companion papers introduces the concept of the proposed middleware approach. Formulation, delay modeling, and optimal gain finding based on a cost function for a case study on DC motor speed control with a proportional-integral (PI) controller are also described. Simulation results of the PI controller shows that, with the existence of IP network delays, the middleware can effectively maintain the networked control system performance and stabilize the system. Part II of this paper will cover the use of the proposed middleware concept for a mobile robot teleoperation.