On scheduling optical packet switches with reconfiguration delay

Using optical technology for the design of packet switches/routers offers several advantages such as scalability, high bandwidth, power consumption, and cost. However, reconfiguring the optical fabric of these switches requires significant time under current technology (microelectromechanical system mirrors, tunable elements, bubble switches, etc.). As a result, conventional slot-by-slot scheduling may severely cripple the performance of these optical switches due to the frequent fabric reconfiguration that may entail. A more appropriate way is to use a time slot assignment (TSA) scheduling approach to slow down the scheduling rate. The switch gathers the incoming packets periodically and schedules them in batches, holding each fabric configuration for a period of time. The goal is to minimize the total transmission time, which includes the actual traffic-sending process and the reconfiguration overhead. This optical switch scheduling problem is defined in this paper and proved to be NP-complete. In particular, earlier TSA algorithms normally assume the reconfiguration delay to be either zero or infinity for simplicity. To this end, we propose a practical algorithm, ADJUST, that breaks this limitation and self-adjusts with different reconfiguration delay values. The algorithm runs at O(/spl lambda/N/sup 2/logN) time complexity and guarantees 100% throughput and bounded worst-case delay. In addition, it outperforms existing TSA algorithms across a large spectrum of reconfiguration values.     

Scheduling algorithms for optical packet fabrics

Utilizing optical technologies to build packet fabrics for high-capacity switches and routers has several advantages in terms of scalability, power consumption, and cost. However, several technology related problems have to be overcome to be able to use such an approach. The reconfiguration times of optical crossbars are longer than those of electronic fabrics and end-to-end clock recovery in such systems add to the reconfiguration overheads. Both these problems can limit the efficiency of optical packet fabrics. In addition, existing work on input-buffered switches mostly assumes fixed size packets (referred as envelopes in this paper). When fixed size switching is used for Internet protocol networks where packets are of variable size, the incoming packets need to be fragmented to fit the fixed size envelopes. This fragmentation can lead to, possibly large loss of bandwidth and even instability. This paper addresses all of the above issues by presenting packetization and scheduling techniques that allow optical packet fabrics to be used within switches and routers. The proposed scheme aggregates multiple packets in a single envelope and when used in combination with proper scheduling algorithms, it can provide system stability as well as bandwidth and delay guarantees. As a result of the aggregation method, the reconfiguration frequency required from the optics is reduced, facilitating the use of optical technologies in implementing packet switch fabrics.     

Optical Burst Switching With Large Switching Overhead

To date, optical burst switching (OBS) schemes assume the switch reconfiguration time to be negligible, a part of the processing delay of the control packet, or a fixed value added to the data burst length, regardless of the switch status. In this paper, we show that the switching overhead can have a significant impact on the performance of some OBS channel scheduling schemes. We have also proposed methods to alleviate the problem     

An analytical model for all-optical packet switching networks with finite FDL buffers

Signal loss and noise accumulation can cause fading in optical buffers implemented by fiber delay lines (FDLs). Optical packets that excessively recirculate through FDLs are easily dropped from their routing paths. Therefore, analytical models and packet scheduling schemes require additional considerations for FDL buffers. This work proposes an analytical model for all-optical packet switching networks with finite FDL buffers and a general class of scheduling schemes including many basic scheduling schemes. We intend to minimize the packet loss probability by ranking packets to achieve an optimal balance between latency and residual lifetime in the general class of scheduling schemes. The analytical model is based on a non-homogeneous Markovian analysis to study the effects of various scheduling schemes on packet loss probability and average latency. Analytical results show how various network parameters affect the optimal balance, and illustrate how properly balancing latency and residual distance can significantly improve network performance.     

Variable IP packets buffer management schemes for optical packet switching

Effective buffering of optical packets is essential to the efficient working of optical packet switches. In this paper three new schemes, which involve sorting and finding the least occupied buffer, are proposed. Their performance is compared with the common round-robin scheme. The results show that all these new schemes are able to enhance the optical packet switch performance significantly in terms of packet drop/loss probability. In addition, the results show that not all the newly arrived packets need to be sorted in order to obtain the minimum packet drop probability. As computation/processing time is significant in optical packet switching, partial sorting of the newly arrived packets with tolerable packet drop probability appears to be a viable proposition. Conversely, a complete sort of newly arrived packets wastes packet processing time unnecessarily while significantly increasing the packet drop probability.     

Scheduling algorithms for shared fiber-delay-line optical packet Switches-part II: the three-stage clos-network case

In all-optical packet switching, packets may arrive at an optical switch in an uncoordinated fashion. To prevent packet loss in the switch, fiber delay lines (FDLs) are used as optical buffers to store optical packets. However, assigning FDLs to the arrival packets to achieve high throughput, low delay, and low loss rate is not a trivial task. In the authors' companion paper, several efficient scheduling algorithms were proposed for single-stage shared-FDL optical packet switches (OPSs). To further enhance the switch's scalability, this work was extended to a multistage case. In this paper, two scheduling algorithms are proposed: 1) sequential FDL assignment and 2) multicell FDL assignment algorithms for a three-stage optical Clos-Network switch (OCNS). The paper shows by simulation that a three-stage OCNS with these FDL assignment algorithms can achieve satisfactory performance.     

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.     

Scheduling variable-length messages in a single-hop multichannellocal lightwave network

The design of a medium access control scheme for a single-hop, wavelength-division-multiplexing-(WDM) multichannel local lightwave network poses two major difficulties: relatively large transmitter/receiver tuning overhead and large ratio of propagation delay to packet transmission time. Most schemes proposed so far have ignored the tuning overhead, and they can only schedule fixed-length packet transmissions. To overcome these two difficulties, the authors propose several scheduling algorithms which can reduce the negative impact of tuning overhead and schedule variable-length messages. A separate channel (control channel) is employed for transmission of control packets, and a distributed scheduling algorithm is invoked at each node every time it receives a control packet. By allowing the length of messages to be variable, a long message can be scheduled with a single control packet transmission, instead of fragmenting it into many fixed-length packets, thereby significantly reducing the overhead of control packet transmissions and improving the overall system performance. Three novel scheduling algorithms are proposed, varying in the amount of global information and processing time they need. Two approximate analytical models are formulated to study the effect of tuning time and the effect of having a limited number of data channels. Extensive simulations are conducted. Average message delays are compared for all of the algorithms     

Scheduling algorithms for shared fiber-delay-line optical packet Switches-part I: the single-stage case

In all-optical packet switching, packets may arrive at an optical switch in an uncoordinated fashion. When contention occurs, fiber delay lines (FDLs) are needed to delay (buffer) the packets that have lost the contention to some future time slots for the desired output ports. There have been several optical-buffered switch architectures and FDL assignment algorithms proposed in the literature. However, most of them either have high implementation complexity or fail to schedule in advance departure time for the delayed packets. This paper studies the packet scheduling algorithms for the single-stage shared-FDL optical packet switch. Three new FDL assignment algorithms are proposed, namely sequential FDL assignment (SEFA), multicell FDL assignment (MUFA), and parallel iterative FDL assignment (PIFA) algorithms for the switch. The proposed algorithms can make FDLs and output-port reservation so as to schedule departure time for packets. Owing to FDL and/or output-port conflicts, the packets that fail to be scheduled are discarded before entering the switch so that they do not occupy any FDL resources. It is shown by simulation that with these algorithms, the optical-buffered switch can achieve a loss rate of /spl sim/10/sup -7/ even at the load of 0.9. These algorithms are extended to the three-stage Clos-Network optical packet switches in the companion paper.     

输入排队中抢占式的短包优先调度算法

调度算法决定了输入排队交换结构的性能.本文根据Internet业务特征提出调度算法应保证短包的高优先级和低延迟.已有包方式调度中,长包信元的连续传输将造成短包长时间等待.为解决该问题,本文设计了一种低复杂度抢占式交换结构,并提出了相应的抢占式短包优先调度算法(P-SPF).短包优先可减小TCP流的RTT,并由此提高TCP之性能.通过排队论分析和实际业务源模型下仿真可知:P-SPF取得短包近似为零的平均包等待时间,同时达到94%的系统吞吐量.     

High-speed buffer management for 40 gb/s-based photonic packet switches

We develop a method of high-speed buffer management for output-buffered photonic packet switches. The use of optical fiber delay lines is a promising solution to constructing optical buffers. The buffer manager determines packet delays in the fiber delay line buffer before the packets arrive at the buffer. We propose a buffer management method based on a parallel and pipeline processing architecture consisting of (log/sub 2/N+1) pipeline stages, where N is the number of ports of the packet switch. This is an expansion of a simple sequential scheduling used to determine the delays of arriving packets. Since the time complexity of each processor in the pipeline stages is O(1), the throughput of this buffer management is N times larger than that of the sequential scheduling method. This method can be used for buffer management of asynchronously arriving variable-length packets. We show the feasibility of a buffer manager supporting 128 /spl times/ 40 Gb/s photonic packet switches, which provide at least eight times as much throughput as the latest electronic IP routers. The proposed method for asynchronous packets overestimates the buffer occupancy to enable parallel processing. We show through simulation experiments that the degradation in the performance of the method resulting from this overestimation is quite acceptable.     

Message Delays with Prioritized HOLP and Round-Robin Packet Servicing

Three disciplines for prioritized transmission of messages in packet switching systems are considered. Messages from a finite number of classes having their lengths drawn independently from general service time distributions are assumed to arrive to the system according to independent Poisson processes. After entering the switch, the messages are divided into packets, overhead is added, and then the packets join a queue to be served according to one of the following disciplines: head-of-the-line (HOL), HOL with message preemption, and prioritized round robin (RR). Preemption of packet transmission is not allowed in any of the disciplines, and the service disciplines of different classes need not be the same. One result of the work presented here is a model to assess delays in the case of the prioritized RR; this work appears to be the first in which messages are not of fixed length and all quanta from a given message are served at the same priority. Numerical results which illustrate effects of choice of packet lengths and service disciplines upon delay of messages from the different classes are presented.     

Logarithmic Delay for N ×N Packet Switches Under the Crossbar Constraint

We consider the fundamental delay bounds for scheduling packets In an N times N packet switch operating under the crossbar constraint. Algorithms that make scheduling decisions without considering queue backlog are shown to incur an average delay of at least O(N). We then prove that O(log(N)) delay is achievable with a simple frame based algorithm that uses queue backlog information. This is the best known delay bound for packet switches, and is the first analytical proof that sublinear delay is achievable in a packet switch with random inputs.     

A high-performance input access scheme for ATM multicast switching

In this paper, we propose an input access scheme for input-queued ATM multicast switches, achieving high system throughput, low packet delay and packet loss probability. Multicast and unicast packets of each input port are separately queued. Multicast queues take priority over the unicast queues, and both types of queues are fairly served in a cyclic-priority access discipline. In particular, each unicast queue is handled on a window-service basis, and each multicast packet is switched in a one-shot scheduling manner. To evaluate the performance of the access scheme, we propose an approximate analysis based on a simplified cyclic-priority model for anN×N finite-buffer multicast switch possessing Bernoulli multicast and unicast arrivals, with window-service (for unicasting) and one-shot scheduling (for multicasting) both taken into account. Finally, we show simulation results to demonstrate the accuracy of the approximate analysis and the superiority of the scheme over existing schemes with respect to normalized system throughput, mean packet delay, and packet loss probability.An earlier version of this paper appeared in IEEE ICC'96.     

Traffic performance evaluation of an optical packet switch with multicast operation

We recently proposed a multicast-enabled optical packet switch architecture utilizing multicast modules. In this paper, we evaluate the traffic performance of our earlier proposed packet switch under a hybrid traffic model through simulations. The multicast packets are given higher priority than unicast packets so that only a small number of multicast modules are needed. The results show that the switch can achieve an acceptable packet loss probability in conjunction with a packet scheduling technique.     

Guaranteed scheduling for switches with configuration overhead

We present three algorithms that provide performance guarantees for scheduling switches, such as optical switches, with configuration overhead. Each algorithm emulates an unconstrained (zero overhead) switch by accumulating a batch of configuration requests and generating a corresponding schedule for a constrained switch. Speedup is required both to cover the configuration overhead of the switch and to compensate for empty slots left by the scheduling algorithm. Scheduling algorithms are characterized by the number of configurations N/sub s/ they require to cover a batch of requests and the speedup required to compensate for empty slots S/sub min/. Initially, all switch reconfiguration is assumed to occur simultaneously. We show that a well-known exact matching algorithm, EXACT, leaves no empty slots (i.e., S/sub min/=1), but requires N/sub s//spl ap/N/sup 2/ configurations for an N-port switch leading to high configuration overhead or large batches and, hence, high delay. We present two new algorithms that reduce the number of configurations required substantially. MIN covers a batch of requests in the minimum possible number of configurations, N/sub s/=N, but at the expense of many empty slots, S/sub min//spl ap/4log/sub 2/N. DOUBLE strikes a balance, requiring twice as many configurations, N/sub s/=2N, while reducing the number of empty slots so that S/sub min/=2. Loosening the restriction on reconfiguration times, the scheduling problem is cast as an open shop. The best known practical scheduling algorithm for open shops, list scheduling (LIST), gives the same emulation requirements as DOUBLE. Therefore, we conclude that our architecture gains no advantages from allowing arbitrary switch reconfiguration. Finally, we show that DOUBLE and LIST offer the lowest required speedup to emulate an unconstrained switch across a wide range of port count and delay.     

Flexible multicasting in high-capacity switches

Since packet switches with input queueing require low-speed buffers and simple cross-bar fabrics, they potentially provide high switching capacities. In these switches, the port that is a source of a multicast session might easily get congested with the increasing popularity of this session. We propose the protocol for scheduling packets in switches with input buffers for varying popularity of different content on the Internet. Copies of a multicast packet are forwarded through the switch, so that multicasting is evenly distributed over switch ports. The performance trade-off between capacity that can be reserved and guaranteed packet delay is discussed.     

Concurrent fault detection for a multiple-plane packet switch

In high-speed and high-capacity packet switches, system reliability is critical to avoid loss of huge amounts of information and retransmission of traffic. We propose a series of concurrent fault-detection mechanisms for a multiple-plane crossbar-based packet switch. Our switch model, called the m+z model, has m active planes and z spare planes. This switch has distributed arbiters on each plane. The spare planes, used for substitution of faulty active ones, are also used in the fault-detection mechanism, thus providing fault detection and fault location for all switching planes. Our detection schemes are able to detect a single fault quickly without increasing transmission overhead. The proposed schemes can be used for switches with different numbers of active planes and a small number of spare planes.     

Performance of fiber delay‐line buffers in asynchronous packet‐based optical switching networks with wavelength conversion

A major challenge in asynchronous packet‐based optical networks is packet contention, which occurs when two or more packets head to the same output at the same time. To resolve contention in the optical domain, two primary approaches are wavelength conversion and fiber delay line (FDL) buffering. In wavelength conversion, a contending packet can be converted from one wavelength to another in order to avoid conflict. In FDL buffering, contending packets can be delayed for a fixed amount of time. While the performance of wavelength conversion and FDL buffering has been evaluated extensively in synchronous networks with fixed‐sized packets, in this paper, we study the performance of FDL buffers in asynchronous packet‐based optical networks with wavelength conversion. An analytical model is proposed to evaluate the performance in terms of packet loss probability and average delay. Extensive simulation and analytical results show that, with appropriate settings, FDL buffers can perform much better in switches with wavelength conversion than in switches with no conversion. Copyright © 2014 John Wiley & Sons, Ltd.     

An evolution to crossbar switches with virtual output queuing and buffered cross points

Input queued (IQ) switch architectures with virtual output queues (VOQ) scale up to very high speeds and have been a subject of intense research in the past decade. VOQ IQ switches require switch matrix scheduling algorithms to match input ports to out ports. In this tutorial article, we present an overview of switch matrix scheduling for VOQ IQ switches with crossbar switch fabrics. We then describe what we believe will be the next generation of high-speed crossbar switches: the evolution of IQ switches to combined input and crossbar queued (CICQ) switches. With the continued increase in density of VLSI, sufficient buffering at crossbar cross points for one cell or packet has become feasible to implement. We show how CICQ switches have simple schedulers and result in lower delay than IQ switches. Both IQ and CICQ switches have unstable regions. We show how a threshold and bursting technique can feasibly achieve stability. We also show how CICQ switches are better suited (than IQ switches) for switching of variable-length packets such as IP packets. Many challenges remain in IQ and CICQ switches. In particular, the inclusion of QoS scheduling methods that are currently only suitable for output queued switches is a major open problem.