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     

Impact of tuning delay on the performance of bandwidth-limitedoptical broadcast networks with uniform traffic

This paper studies the effects of tuning delay of transmitters in packet-based optical broadcast networks. We consider scheduling of random traffic with tunable transmitters and fixed-tuned receivers and obtain the degradation imposed by tuning delay using several performance criteria, such as schedule completion time, average packet delay, and session blocking rates. We show that for off-line scheduling the effects of tuning delay are small even if the tuning time is as large as the packet duration. We provide a lower bound to the expected completion time of any off-line schedule with an arbitrary number of wavelengths. We then describe a near-optimal schedule which is based on the principle of having idle transmitters tune to wavelengths just-in-time to start their transmissions. Stability and capacity issues in the transmission of real-time traffic are considered and a queueing-theoretic analysis of average packet delay is given. The packet delay is found to be insensitive to tuning delay under near-optimal transmission scheduling. Finally we extend the model to connection-oriented networks and evaluate the session blocking performance for scheduled circuit connections     

Optimal Time Slot Assignment Algorithm for Combined Unicast and Multicast Packets

This paper considers a packet‐scheduling algorithm for a given combined traffic of unicast and multicast data packets and proposes a hybrid router with several dedicated buses for multicast traffic. Our objective is to develop a scheduling algorithm that minimizes schedule length for the given traffic in the hybrid router. We derive a lower bound and develop an optimal solution algorithm for the hybrid router.     

Minimizing Internal Speedup for Performance Guaranteed Switches With Optical Fabrics

We consider traffic scheduling in an N times N packet switch with an optical switch fabric, where the fabric requires a reconfiguration overhead to change its switch configurations. To provide 100% throughput with bounded packet delay, a speedup in the switch fabric is necessary to compensate for both the reconfiguration overhead and the inefficiency of the scheduling algorithm. In order to reduce the implementation cost of the switch, we aim at minimizing the required speedup for a given packet delay bound. Conventional Birkhoff-von Neumann traffic matrix decomposition requires N2 - 2N + 2 configurations in the schedule, which lead to a very large packet delay bound. The existing DOUBLE algorithm requires a fixed number of only 2N configurations, but it cannot adjust its schedule according to different switch parameters. In this paper, we first design a generic approach to decompose a traffic matrix into an arbitrary number of Ns (N² - 2N + 2 > N_S > N) configurations. Then, by taking the reconfiguration overhead into account, we formulate a speedup function. Minimizing the speedup function results in an efficient scheduling algorithm ADAPT. We further observe that the algorithmic efficiency of ADAPT can be improved by better utilizing the switch bandwidth. This leads to a more efficient algorithm SRF (scheduling residue first). ADAPT and SRF can automatically adjust the number of configurations in a schedule according to different switch parameters. We show that both algorithms outperform the existing DOUBLE algorithm.     

Optimal all-to-all broadcast in WDM optical networks with breakdown or power-off transceivers

All-to-all broadcast is an interesting special case of the packet transmission scheduling in which every pair of nodes has exactly one packet to be transferred. This paper considers the all-to-all broadcast problem in wavelength division multiplexed (WDM) optical star network with some breakdown or power-off transceivers. For reaching high data transmission rates, we will focus the problem on the all-optical scheduling where the traffic reaches its destination in single-hop without being converted to electronic form. Each transmitter is tunable with an associated tuning delay and each receiver is fixed-tuned to one of available wavelengths. In this model, we study two kinds of all-to-all broadcast problems depending on whether each node transmits packets to all nodes including or except itself. We identify the lower bound of the scheduling length for each kind of problems and propose single-hop scheduling algorithms to find the optimal solution in both terms of arbitrary number of wavelengths and value of tuning latency.     

Scheduling Combined Unicast and Multicast Traffic in Broadcast WDM Networks

This paper studies the performance of various strategies for scheduling a combined load of unicast and multicast traffic in a broadcast WDM network. The performance measure of interest is schedule length, which directly affects both aggregate network throughput and average packet delay. Three different scheduling strategies are presented, namely: separate scheduling of unicast and multicast traffic, treating multicast traffic as a number of unicast messages, and treating unicast traffic as multicasts of size one. A lower bound on the schedule length for each strategy is first obtained. Subsequently, the strategies are compared against each other using extensive simulation experiments in order to establish the regions of operation, in terms of a number of relevant system parameters, for which each strategy performs best. Our main conclusions are as follows. Multicast traffic can be treated as unicast traffic, by replicating all multicast packets, under very limited circumstances. On the other hand, treating unicast traffic as a special case of multicast traffic with a group of size 1, produces short schedules in most cases. Alternatively, scheduling and transmitting each traffic component separately is also a good choice.     

On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms

We clarify, extend, and solve a long-standing open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is /spl Omega/(logn). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(n/sup a/) for 0相似文献   

Evaluation of algorithms for efficient partitioning and scheduling of data bursts in satellite communications

We evaluate four scheduling algorithms for satellite communications that use the Time Division Multiple Access methodology. All the algorithms considered are based on the open‐shop model. The open‐shop model is suitably represented or modified to exploit some existing algorithms to solve the satellite communication problem. In the first two algorithms, namely pre‐emptive scheduling with no intersatellite links and greedy heuristics with two intersatellite links, a (traffic) matrix representation of the open‐shop model is used to get a near optimal schedule. In the next two algorithms, generalized heuristic algorithm and the branch and bound algorithm, the open‐shop model is modified to accommodate the inter‐satellite link and this modified open‐shop model is used to solve for a near optimal schedule. The basic methodology of all the algorithms are briefly described and their performance was evaluated through extensive simulations. The performance criteria to evaluate the algorithms are—run time of the algorithms, schedule lengths, and optimality of the algorithm against theoretical bounds. Three of the above‐mentioned algorithms are evaluated by comparing the performance criteria under similar conditions. Optimal branch and bound algorithm is not evaluated due to its high complexity. The general heuristic algorithm is found to give a good trade off between computation time and optimality. The computation time is comparable with the pre‐emptive scheduling algorithm and greedy heuristic algorithm and the schedule length achieved is near to the lower bound value. Copyright © 2005 John Wiley & Sons, Ltd.     

On the All-to-All Broadcast Problem in Optical Networks1

This paper considers the transmission of uniform deterministic traffic in an optical broadcast-star network using Wavelength Division Multiplexing. Lower bounds are established on the minimum time to exchange information between every node pair in such a network with tunable transmitters and fixed-tuned receivers. Three different scheduling algorithms are developed that are strictly optimal in three regimes of system parameters. The results are applicable to arbitrary tuning delays and arbitrary numbers of wavelength channels, and indicate the existence of a well-defined transition regime from tuning-limited operation to bandwidth-limited operation. Finally, the problem of computing the optimal number of wavelengths is addressed to achieve a schedule with minimum schedule length, and exact solutions are given.     

EBvN: efficient BvN in multi-fiber/multi-wavelength overlaid-star optical networks

Overlaid-star networks with reservation-based scheduling could be appropriate networks for metro areas. The Birkhoff?Cvon Neumann (BvN) scheduling could be used at the core nodes of an overlaid network to schedule lossless traffic transmission among edge nodes. The common method is to schedule traffic separately for each wavelength channel, called separated BvN (SBvN) scheduling in this paper. However, SBvN cannot schedule all traffic demands, especially at high-traffic loads. In this paper, the BvN scheduling procedure is modified to efficiently schedule traffic in overlaid-star networks with multi-fiber/multi-wavelength architecture, called efficient BvN (EBvN). Instead of using one processor to schedule traffic on one wavelength channel in each core node, the proposed EBvN technique uses only one processor to schedule all traffic demands on all fibers/wavelength channels at the same time. Performance evaluation results under both uniform and non-uniform traffic distributions show that more traffic demands can be scheduled under EBvN compared with SBvN. In addition, the scheduling speed of EBvN is mostly faster than SBvN. Finally, EBvN can provide bound on the maximum scheduling time of EBvN. As a trade-off between scheduling time and residual traffic, EBvN with filling empty cells (EBvN_FEC) is proposed that can reduce residual traffic, but at the expense of slightly increasing scheduling time. EBvN_FEC is more effective than EBvN under non-uniform traffic distribution.     

Latency-rate servers: a general model for analysis of trafficscheduling algorithms

We develop a general model, called latency-rate servers (ℒℛ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an ℒℛ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of ℒℛ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of ℒℛ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of ℒℛ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models     

Optimum scheduling and memory management in input queued switches with finite buffer space

The goal of this paper is to design optimal scheduling and memory management so as to minimize packet loss in input queued switches with finite input buffers. The contribution is to obtain closed-form optimal strategies that minimize packet loss in 2/spl times/2 switches with equal arrival rates for all streams. For arbitrary arrival rates, the contribution is to identify certain characteristics of the optimal strategy, and use these characteristics to design a near-optimal heuristic. A lower bound for the cost associated with packet loss for N/spl times/N switches is obtained. This lower bound is used to design a heuristic which attains near-minimum packet loss in N/spl times/N switches with arbitrary N. These policies reduce packet loss by about 25% as compared to the optimal strategy for the infinite buffer case. The framework and the policies proposed here apply to buffer-constrained wireless networks as well.     

Energy-Efficient Wireless Packet Scheduling with Quality of Service Control

In this paper, we study the problem of packet scheduling in a wireless environment with the objective of minimizing the average transmission energy expenditure under individual packet delay constraints. Most past studies assumed that the input arrivals followed a Poisson process or were statistically independent. However, traffic from a real source typically has strong time correlation. We model a packet scheduling and queuing system for a general input process in linear time-invariant systems. We propose an energy-efficient packet scheduling policy that takes the correlation into account. Meanwhile, a slower transmission rate implies that packets stay in the transmitter for a longer time, which may result in unexpected transmitter overload and buffer overflow. We derive the upper bounds of the maximum transmission rate under an overload probability and the upper bounds of the required buffer size under a packet drop rate. Simulation results show that the proposed scheduler improves up to 15 percent in energy savings compared with the policies that assume statistically independent input. Evaluation of the bounds in providing QoS control shows that both deadline misses and packet drops can be effectively bounded by a predefined constraint.     

Projective Cone Scheduling (PCS) Algorithms for Packet Switches of Maximal Throughput

We study the (generalized) packet switch scheduling problem, where service configurations are dynamically chosen in response to queue backlogs, so as to maximize the throughput without any knowledge of the long term traffic load. Service configurations and traffic traces are arbitrary.     

An Efficient Packet Scheduling Algorithm With Deadline Guarantees for Input-Queued Switches

Input-queued (IQ) switches overcome the scalability problem suffered by output-queued switches. In order to provide differential quality of services (QoS), we need to efficiently schedule a set of incoming packets so that every packet can be transferred to its destined output port before its deadline. If no such a schedule exists, we wish to find one that allows a maximum number of packets to meet their deadlines. Recently, this problem has been proved to be NP-complete if three or more distinct deadlines (classes) are present in the set. In this paper, we propose a novel algorithm named Flow-based Iterative Packet Scheduling (FIPS) for this scheduling problem. A key component in FIPS is a non-trivial algorithm that solves the problem for the case where two classes are present in the packet set. By repeatedly applying the algorithm for two classes, we solve the general case of an arbitrary number of classes more efficiently. Applying FIPS to a frame-based model effectively achieves differential QoS provision in IQ switches. Using simulations, we have compared FIPS performance with five well-known existing heuristic algorithms including Earliest-Deadline-First (EDF), Minimum-Laxity-First (MLF) and their variants. The simulation results demonstrate that our new algorithm solves the deadline guaranteed packet scheduling problem with a much higher success rate and a much lower packet drop ratio than all other algorithms     

A Novel Method of Feedback Reducing and Cross-layer Scheduling Based on Traffic Rates for Relay System

This paper studies the scheduling schemes in multiuser downlink relay systems with orthogonal frequency division multiple access (OFDMA) where base station (BS) supports different traffic rates for different users. We formulate the problem as a cross-layer design of joint feedback reducing and OFDMA scheduling to support traffic rates and minimize packet loss rate. In most previous scheduling mechanisms with feedback, the parameters of traffic arrival process were not taken into account, consequently, the requirement of user traffic can not be guaranteed. In this paper, a dynamic threshold feedback mechanism (DTFM) based on traffic rates is proposed, of which the user with channel gain being larger than the dynamic threshold is only allowed to send its channel state information, thereby reducing the number of required feedback users and the computational burden of exhaustive search for best users at the BS. A cross-layer scheduling algorithm of traffic and queue proportional fairness (TQPF) taking into consideration the traffic fairness, the user queue length and the user transmission rate (related to its channel quality) is then proposed. Finally, a method of feedback reducing and cross-layer scheduling, i.e., TQPF based on DTFM (TQPF-DTFM), is proposed. Theoretical and simulation results show that DTFM reduces feedback by more than 90%, and TQPF-DTFM successfully meets user traffic rates that is, the user with high traffic rate can obtain more transmission rate than the user with low traffic rate and deceases packet loss rate of the system by almost 50% than the conventional methods.     

Scheduling reserved traffic in input-queued switches: new delay bounds via probabilistic techniques

We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known, and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem, therefore, reduces to the problem of constructing a schedule for these permutation matrices. We derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm, we first place tokens randomly in continuous time for each permutation matrix. If the nth token that appears corresponds to permutation matrix M/sub k/, then we schedule matrix M/sub k/ in the nth time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms, we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang et al. (see Proc. IEEE IWQoS, London, U.K., 1999 and Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar 2000).     

Approximating Fluid Schedules in Crossbar Packet-Switches and Banyan Networks

We consider a problem motivated by the desire to provide flexible, rate-based, quality of service guarantees for packets sent over input queued switches and switch networks. Our focus is solving a type of online traffic scheduling problem, whose input at each time step is a set of desired traffic rates through the switch network. These traffic rates in general cannot be exactly achieved since they assume arbitrarily small fractions of packets can be transmitted at each time step. The goal of the traffic scheduling problem is to closely approximate the given sequence of traffic rates by a sequence of transmissions in which only whole packets are sent. We prove worst-case bounds on the additional buffer use, which we call backlog, that results from using such an approximation. We first consider the NtimesN, input queued, crossbar switch. Our main result is an online packet-scheduling algorithm using no speedup that guarantees backlog at most (N+1)² /4 packets at each input port and each output port. Upper bounds on worst-case backlog have been proved for the case of constant fluid schedules, such as the N²-2N+2 bound of Chang, Chen, and Huang (INFOCOM, 2000). Our main result for the crossbar switch is the first, to our knowledge, to bound backlog in terms of switch size N for arbitrary, time-varying fluid schedules, without using speedup. Our main result for Banyan networks is an exact characterization of the speedup required to maintain bounded backlog, in terms of polytopes derived from the network topology     

Wavelength division multiplexing-based video-on-demand systems

Serving video-on-demand (VOD) traffic via isochronous transmission service is highly desirable because of the characteristics of VOD traffic. This paper proposes a mechanism to transfer VOD traffic over wavelength division multiplexing (WDM) networks by employing isochronous transmission service. Based on the proposed mechanism, the problem of scheduling isochronous and asynchronous traffic for single-star WDM networks with multiple receivers and transmitters is investigated. The lower bounds on the total switching duration and the number of switching modes for the isochronous and asynchronous traffic scheduling problem are derived. An optimal scheduling algorithm is presented for the cases where only asynchronous traffic exists; and a heuristic algorithm is also proposed for the cases where both the isochronous and asynchronous traffic coexist in the WDM networks. Simulation results indicate that the average switching duration and the average number of switching modes obtained by the proposed algorithm are close to the lower bounds, which implies that the proposed scheduling algorithm is effective     

Centralized broadcast scheduling in packet radio networks via genetic-fix algorithms

An important, yet difficult, problem in the design of a packet radio network is the determination of a conflict-free broadcast schedule at a minimum cycle length. We first formulate the problem via a within-two-hop connectivity matrix and then, by assuming a known cycle length, determine a conflict-free scheduling pattern using a centralized approach that exploits the structure of the problem via a modified genetic algorithm. This algorithm, called genetic-fix, generates and manipulates individuals with fixed size (i.e., in binary representation, the number of ones is fixed) and therefore, can reduce the search space substantially. We also propose a method to find a reasonable cycle length and shorten it gradually to obtain a near-optimal one. Simulations on three benchmark problems showed that our approach could achieve 100% convergence to solutions with optimal cycle length within reasonable time.