On the stability of local scheduling policies in networks of packet switches with input queues

A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. We identify scheduling policies that require no coordination among switches (and are, thus, said to be local), and that guarantee 100% throughput in a network of IQ/CIOQ switches. The only assumptions on the input traffic pattern are that it is stationary, satisfies the strong law of large numbers and does not oversubscribe any link in the network.     

Power allocation and routing in multibeam satellites with time-varying channels

We consider power and server allocation in a multibeam satellite downlink which transmits data to N different ground locations over N time-varying channels. Packets destined for each ground location are stored in separate queues and the server rate for each queue, i, depends on the power, p/sub i/(t), allocated to that server and the channel state, c/sub i/(t), according to a concave rate-power curve /spl mu//sub i/(p/sub i/,c/sub i/). We establish the capacity region of all arrival rate vectors (/spl lambda//sub 1/,...,/spl lambda//sub N/) which admit a stabilizable system. We then develop a power-allocation policy which stabilizes the system whenever the rate vector lies within the capacity region. Such stability is guaranteed even if the channel model and the specific arrival rates are unknown. Furthermore, the algorithm is shown to be robust to arbitrary variations in the input rates and a bound on average delay is established. As a special case, this analysis verifies stability and provides a performance bound for the choose-the-K-largest-connected-queues policy when channels can be in one of two states (ON or OFF ) and K servers are allocated at every timestep (K相似文献   

QoS provisioning and tracking fluid policies in input queueingswitches

The concept of tracking fluid policies by packetized policies is extended to input queueing switches. It is considered that the speedup of the switch is one. One of the interesting applications of the tracking policy in TDMA satellite switches is elaborated. For the special case of 2×2 switches, it is shown that a tracking nonanticipative policy always exists. It is found that, in general, nonanticipative policies do not exist for switches with more than two input and output ports. For the general case of N×N switches, a heuristic tracking policy is provided. The heuristic algorithm is based on two notions: port tracking and critical links. These notions can be employed in the derivation of other heuristic tracking policies as well. Simulation results show the usefulness of the heuristic algorithm and the two basic concepts it relies on     

Lightpath concentrators for all-optical networks

In some deployments of all-optical networks, it is necessary to concentrate the lightpaths from some fibers to fewer fibers. An N/spl times/M lightpath concentrator is an optical component for this purpose, and it concentrates the lightpaths from N incoming fibers to M outgoing fibers. In this paper, three designs of N/spl times/M lightpath concentrators are proposed. The first design is a generalization of optical crossconnects, and it requires M/spl times/M optical switches. The second design incorporates the concept of partial concentration so that it requires only m/spl times/m optical switches (where m相似文献   

Low-power InP-HEMT switch ICs integrating miniaturized 2/spl times/2 switches for 10-Gb/s systems

This paper presents a wideband cold-FET switch with virtually zero power dissipation. The use of InP HEMTs with a low R/sub on//spl middot/C/sub off/ product enables us to configure a DC-to-over-10-GHz single-pole double-throw (SPDT) switch without using a shunt FET. The series-FET configuration offers a logic-level-independent interface and makes possible positive control voltage operation in spite of using depletion-mode FETs. A miniaturized 2/spl times/2 switch using two SPDT switches yields an insertion loss of less than 1.16 dB and isolation of more than 21.2 dB below 10 GHz, which allows us to increase the scale of the switch in a single chip easily. The add-drop operation combining two 2/spl times/2 switches in a single chip and a 4/spl times/4 switch IC integrating four 2/spl times/2 switches are presented. The packaged ICs achieve error-free operation up to 12.5 Gb/s with either positive or negative logic-level input. Extremely fast switching of /spl sim/140 ps is also successfully demonstrated.     

ATM交换的最佳缓存器分配

研究具有输入和输出队的ＡＴＭ交换的缓存器分配策略。文中首先建立了描述交换网络的模型，然后分析了在有限缓存容量下在输入队和输出队中分组的丢失率。分析表明总的丢失率是输入队和输出队容量的复杂函数，因而在总的缓存容量一定的情况下，必存在使丢失率最小的缓存分配方法。最后用数值结果说明了最佳的分配策略。     

On protective buffer policies

Studies buffering policies which provide different loss priorities to packets/cells, while preserving packet ordering (space priority disciplines). These policies are motivated by the possible presence, within the same connection, of packets with different loss probability requirements or guarantees, e.g., voice and video coders or rate control mechanisms. The main contribution of the paper is the identification and evaluation of buffering policies which preserve packet ordering and guarantee high priority packets performance (loss probability), irrespective of the traffic intensity and arrival patterns of low priority packets. Such policies are termed protective policies. The need for such policies arises from the difficulty to accurately characterize and size low priority traffic, which can generate large and unpredictable traffic variations over short periods of time. The authors review previously proposed buffer admission policies and determine if they satisfy such “protection” requirements. Furthermore, they also identify and design new policies, which for a given level of protection maximize low priority throughput     

Polymeric 2/spl times/2 electrooptic switch consisting of asymmetric Y junctions and Mach-Zehnder interferometer

2/spl times/2 electrooptic switches consisting of a pair of asymmetric Y junctions and Mach-Zehnder interferometer have been demonstrated in polymeric waveguides. The switching voltage is 15 V with 1.5 cm long electrode for TM polarized light at 1.3 /spl mu/m. When the branching angle of the asymmetric Y junction is 0.2/spl deg/, crosstalk of -27 to -22 dB are obtained for both input arms. The measured insertion loss by the lens coupling is about 9-10 dB.     

Convexity in queues with general inputs

In this correspondence, we develop fundamental convexity properties of unfinished work and packet waiting time in a queue serving general stochastic traffic. The queue input consists of an uncontrollable background process and a rate-controllable input stream. We show that any moment of unfinished work is a convex function of the controllable input rate. The convexity properties are then extended to address the problem of optimally routing arbitrary input streams over a collection of K queues in parallel with different (possibly time-varying) server rates (/spl mu//sub 1/(t),...,/spl mu//sub K/(t)). Our convexity results hold for stream-based routing (where individual packet streams must be routed to the same queue) as well as for packet-based routing where each packet is routed to a queue by probabilistic splitting. Our analysis uses a novel technique that combines sample path observations with stochastic equivalence relationships.     

First InP-based reconfigurable integrated add-drop multiplexer

A four-channel reconfigurable integrated add-drop multiplexer on InP-substrate is reported. The device consists of a 5/spl times/5 PHASAR demultiplexer integrated with Mach-Zehnder interferometer electrooptical switches. Total device size is 3/spl times/6 mm/sup 2/. All routing configurations of four wavelengths have been demonstrated. Crosstalk values are better than -20 dB. On-chip loss for the dropped or added signals and for the signals coupled from the input to the output port are lower than 7 and 11 dB, respectively.     

Analysis of input power dynamic ranges in two types of expanded semiconductor optical amplifier gate switch arrays

Two types of expanded semiconductor optical amplifier gate switches (front 3/spl times/4 to 32/spl times/32) are analyzed numerically with respect to input power dynamic ranges. The dependences of the dynamic range on switch size, amplifier placement, and gain are studied. It is concluded that a large integrated switch is preferred over a large switch constructed from fiber-optic couplers and integrated 4/spl times/4 switches.     

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.     

Optimal buffer management policies for shared-buffer ATM switches

Shared-buffer ATM switches can have severe cell loss under asymmetrical or heavy loading conditions, which makes buffer management essential. In this paper, we study the shared-buffer system under the class of all work-conserving pushout policies and derive the properties of the optimal policy, which gives the least-average expected total cell loss probability. In a 2×2 system with independent identically distributed Bernoulli arrivals, we show that the optimal policy can be characterized by a single threshold. In the case of correlated arrivals, modeled by a discrete batch Markovian arrival process, the optimal policy has multiple thresholds, one for each phase of the arrival process. For the N×N shared buffer ATM switch, we are unable to prove optimality of any policy, but we study the system via simulations. We provide a dynamic buffer management policy and compare its performance with that of static threshold-type policies     

Array interconnection for rearrangeable 2-D MEMS optical switch

Two-dimensional (2-D) microelectromechanical systems (MEMS) optical switches can be constructed by arranging the MEMS-actuated micromirrors as an array. We consider here the switching capability, routing, and optimization of the rectangular array interconnection on which the capability and efficiency of 2-D MEMS switches depend. The switching capability of a rectangular array is proved analytically. Two routing algorithms, namely, the most-bend routing and the least-bend routing, are developed, which, respectively, maximize and minimize the number of 2 /spl times/ 2 switches in the "bend" state. A method of counting the number of permutations realizable with a given number of switches in the "bend" state is proposed to evaluate the performance of both routing schemes. The understanding of the underlying interconnection pattern enables us to study the problem of constructing rearrangeable optical switches of arbitrary size.     

Low loss fully reconfigurable wavelength-selective optical 1/spl times/N switch based on transversal filter configuration using silica-based planar lightwave circuit

A low loss wavelength-selective switch is proposed and demonstrated. The switch has a 1/spl times/4 transversal filter configuration that includes arrayed waveguide gratings and thermooptic phase shifters, and can route arbitrary wavelength input light to arbitrary outputs with no loss variation. We confirmed its operating principle and obtained an average loss of 2.7 dB and a worst extinction ratio of more than 20 dB.     

Maximum size matching is unstable for any packet switch

Input-queued packet switches use a matching algorithm to configure a nonblocking switch fabric (e.g., a crossbar). Ideally, the matching algorithm will guarantee 100% throughput for a broad class of traffic, so long as the switch is not oversubscribed. An intuitive choice is the maximum size matching (MSM) algorithm, which maximizes the instantaneous throughput. It was shown (McKeown et al. (1999)) that with MSM the throughput can be less than 100% when N /spl ges/ 3, even with Terms-Instability,benign Bernoulli i.i.d. arrivals. In this letter, we extend this result to N /spl ges/ 2, and hence show it to be true for switches of any size.     

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.     

Wavelength-selective 1/spl times/K switches using free-space optics and MEMS micromirrors: theory, design, and implementation

The design and performance of several generations of wavelength-selective 1/spl times/K switches are reviewed. These optical subsystems combine the functionality of a demultiplexer, per-wavelength switch, and multiplexer in a single, low-loss unit. Free-space optics is utilized for spatially separating the constituent wavelength division multiplexing (WDM) channels as well as for space-division switching from an input optical fiber to one of K output fibers (1/spl times/K functionality) on a channel-by-channel basis using a microelectromechanical system (MEMS) micromirror array. The switches are designed to provide wide and flat passbands for minimal signal distortion. They can also provide spectral equalization and channel blocking functionality, making them well suited for use in transparent WDM optical mesh networks.     

Optimization of optical cross-connects with wave-mixing conversion

This paper presents new constructions of multistage wave-mixing networks with arbitrary b/spl times/b space-switching elements, where b /spl ges/ 2. In these networks, for a size of F fiber links and W wavelengths per link, converter requirements are O(Flog/sub b/W) or O(FW/b) for rearrangeable nodes, and O(Flog/sub b/Wlog/sub b/(FW)) or O(FWlog/sub b/(FW)/b) for different types of strictly nonblocking nodes inspired from the Cantor topology. In all cases, the worst case number of cascaded conversion is O(log/sub b/W). When b=W /spl les/ F, the required number of converters, and the worst case number of cascaded conversions are respectively O(F) and O(1), and are both optimal up to a constant. The new networks generalize and improve upon previous wave-mixing networks based on 2/spl times/2 space switches.     

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.