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     

A Knockout Switch for Variable-Length Packets

The Knockout Switch is a new packet switch architecture recently proposed for high-speed local and metropolitan area networks, multiprocessor interconnects, and local or toll switches for integrated traffic loads. We describe an approach to extend the original Knockout Switch to work with variable-length packets. This new architecture employs an input broadcast bus arrangement to achieve complete interconnection of the inputs and outputs. Consequently, there is no congestion in the switch fabric other than the unavoidable conflict of multiple simultaneous packets destined for the same output. It is with this output contention that the Knockout principle is fully utilized to efficiently concentrate and store contending packets while maintaining the first-in first-out discipline of the packet sequence; and yet the fabric speed required is no more than the input/output line speeds, Under these design goals, no switch can yield better delay/ throughout performance. These are the most important attributes that have been preserved in the current proposal from the original Knockout Switch. For anN times Nswitch configuration, the variable-length packet Knockout Switch consists ofNinput broadcast buses, and anN:Lconcentrator (L ll N) and a shared buffer for each output. The design of each subsystem is discussed with emphasis on possible VLSI realization. Using today's technology, we should be able to implement the proposed switch with both input/output lines and internal hardware operating at 50 Mbits/s. The dimension of the switch (N times N) can grow modularly from say 32 × 32 to 1024 × 1024, rendering a total throughput in the range of tens of gigabits per second. Future upgrading of the line interfaces to much higher speed without modification to the internal switch hardware is also possible with a modest restriction on the minimum length of new packets.     

Integrated cell and frame switching in ATM networks

Based on the per-VC queueing architecture, we propose a new technology to integrate cell and frame switching in asynchronous transfer mode (ATM) networks. We demonstrate that we can switch both fixed-length cells and variable-length frames inside the same switch at the same time. The insight is to recognize that we can store not only fixed-length cells, but also variable-length frames in each VC queue. The seamless integration of frame switching with cell switching will have a potential of merging frame relay with ATM     

A growable packet (ATM) switch architecture: design principles andapplication

The problem of designing a large high-performance, broadband packet of ATM (asynchronous transfer mode) switch is discussed. Ways to construct arbitrarily large switches out of modest-size packet switches without sacrificing overall delay/throughput performance are presented. A growable switch architecture is presented that is based on three key principles: a generalized knockout principle exploits the statistical behaviour of packet arrivals and thereby reduces the interconnect complexity, output queuing yields the best possible delay/throughput performance, and distributed intelligence in routing packets through the interconnect fabric eliminates internal path conflicts. Features of the architecture include the guarantee of first-in-first-out packet sequence, broadcast and multicast capabilities, and compatibility with variable-length packets, which avoids the need for packet-size standardization. As a broadband ISDN example, a 2048×2048 configuration with building blocks of 42×16 packet switch modules and 128×128 interconnect modules, both of which fall within existing hardware capabilities, is presented     

一种FDL和LRWC相结合的光分组交换网络的性能分析

研究了FDL和有限长波长转换器(LRWC)相结合的方法来解决异步变长的分组交换网中的冲突问题,对这种冲突解决方案建立了数学模型并进行了理论分析,提出了一个用于修正最佳延迟单元的公式,即在负载较大的情况下,我们要求延迟单元较小,这样可显著的降低在此交换网中的分组丢失率;对系统丢包率与负载、FDL数目和最佳延迟单元的关系进行了研究和讨论,结果表明:在同样的输入负载情况下,有限长波长转换器(LRWC)的引入可以降低缓存的数量;对延迟单元的修正可以大大降低丢包率,同时系统的性能较之单独使用FDL时有较大的改善。     

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.     

Performance Evaluation of Single-Wavelength Fiber Delay Line Buffer With Finite Waiting Places

The performance of single-wavelength fiber delay line buffer with finite waiting places is evaluated in this paper. For Poisson arriving packets with arbitrarily distributed lengths, the generating function of delay time distribution can be derived from the quantized delay buffer model. Then queue length distributions, loss probability, and other important performance measures can be figured out. Specifically, two important cases of negative-exponentially distributed packet lengths and fixed packet lengths are considered and compared. The accuracy of the proposed approach is verified through simulation. It is also observed that the buffer system performs more effectively for the fixed-length packets.     

A Bound and Approximation of Delay Distribution for Fixed-Length Packets in an Unslotted ALOHA Channel and a Comparison with Time Division Multiplexing (TDM)

This paper presents an approximate analysis of a pure unslotted ALOHA random access with fixed-length packets and computes percentiles of delay for various throughputs. It introduces the concept of the burst ratio (mean packet interarrival time/maximum delay) of a source which allows a precise comparison with time division multiplexing (TDM) and indicates when ALOHA is the preferred access technique. The paper presents two curves that should be sufficient for design along with a simple computational procedure. Results are verified and augmented using simulation.     

The Complexity of Optimal Addressing in Radio Networks

We consider the complexity of finding optimal fixed- or variable-length unambiguous address codes for the nodes of a packet radio network. For fixed-length codes this problem is proved to be NP-complete, and its complexity for variable-length codes is still unknown. Some suboptimal heuristic algorithms are proposed.     

Cross-Layer Design Using Superposition Coding Scheme for Multiuser OFDM Systems

In this paper, a cross-layer design is proposed for downlink of orthogonal frequency division multiplexing systems which uses superposition coding (SC) scheme. SC theorem allows two users to share the same subchannel. Firstly, the subchannel will be allocated to degraded user (who is far away from the base station) and then this subchannel will be allowed to be shared by potential user (who is near to the base station). We also employed a packet dependent scheduling at the medium access control layer which decides the transmission order of packets according to the delay, size and quality of service priority level of packets. The weight of each user can be calculated by summing up the weights of all packets in the queues of that user. We have considered that each user is having multiple heterogeneous traffic queues. Simulation results show that the algorithm proposed in this paper is better than the previously reported algorithm in terms of total throughput and packet delay with the same computational complexity.     

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-capacity broadband packet switch architecture based on a multilink approach

Broadband packet networks based on asynchronous transfer mode (ATM) are expected to provide a wide range of services, including motion video, voice, data and image. When these networks become prevalent, some applications such as motion video and high-speed LAN interconnections will place a very large bit rate requirement on the channels. Currently, the physical layer supported by the synchronous optical network (SONET) allows the transmission of up to 2.4 Gbit/s with the OC-48 optical interface. However, it is not feasible for the electronic packet switch to route packets at this rate on a single link. In this paper we present a design of a broadband packet switch that uses multiple links in parallel to realize a high-speed channel. This implementation permits the switch to operate at the lower link rate, which can be at 150 Mbit/s, while having the ability to support a virtual circuit at a higher rate (up to 2.4 Gbit/s). The main contribution of the design is that packet sequence on a channel is still maintained even though packets are allowed to use any of the links belonging to the same channel. Besides allowing the switch to function at a slower rate than the transmission channel rate, the implementation of the multilinks benefits from statistical multiplexing gain. Analytical results show the performance advantages of multilink design with respect to delay, throughput and packet loss probability.     

A Packet Switch with a Priority Scheduling Discipline: Performance Analysis

In this paper, we analyze a discrete-time GI-G₁, Geo₂-1 preemptive resume priority queue. We consider two classes of packets which have to be served, where one class has preemptive resume priority over the other. The high-priority class contains packets with generally distributed service times while the low-priority packets are assumed to have geometrically distributed service times. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. Performance measures of system contents and packet delay are calculated. We apply these theoretical results on the special case of a packet switch.     

Scheduling scheme using Look-ahead Buffer and Loop-back Buffer in Two-stage variable optical packet switch

Programmable variable delay lines have been developed, so as to delay packets in variable durations by combining several lengths of Fiber Delay Lines (FDLs) in optical packet switch. In practice, Two-stage variable optical packet switch with this programmable variable delay lines has been proposed. This switch has two buffers. The one is the programmable variable delay lines (Look-ahead Buffer). The other is the fixed FDLs that re-input a packet from the output to the input (Loop-back Buffer). The switch can foresee following packets and avoid contentions effectively by using two buffers. However, existing studies only focus on the Look-ahead Buffer. Intelligent usage of the Loop-back Buffer is actually out of concern. This paper proposes a sophisticated scheduling method in the Two-stage switch. The proposed method controls both the Look-ahead Buffer and the Loop-back Buffer cooperatively and improves the utilization of the switching process. The proposed method uses the Loop-back Buffer adaptively and distributes traffics in time and space domain. The effectiveness of the proposed method is evaluated through extended simulation experiments and basic hardware design.     

Low-loss switching fabric design for recirculating buffer in WDM optical packet switching networks using arrayed waveguide grating routers

In this paper, we give a new switching fabric design for the recirculating buffer in optical packet switching networks. We note that since a packet to be buffered can be routed to any delay lines, the switching fabric connecting packets to the delay lines can be simplified. We give a design based on the arrayed waveguide grating router, and give a simple linear time-control algorithm for assigning buffer locations to the packets. To the best of our knowledge, this is the first switching fabric specifically designed for recirculating buffers which takes advantage of the fact that packets can be routed to any delay lines.     

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.     

Exact and approximate analytical modeling of an FLBM-based all-optical packet switch

This paper develops both exact and approximate models for the analysis of an all-optical packet switch based on a fiber-loop buffer memory (FLBM). The switch structure and operation is based on the fully shared buffer architecture of the Research and Development in Advanced Communications in Europe - ATM Optical Switching (RACE-ATMOS) project , which uses individual wavelengths to store fixed-length packets in the fiber-loop buffer. An exact model of the switch has been developed , which can be used to determine the blocking performance of the switch and obtain both its throughput and packet loss characteristics. It has been used to study the switch performance under different loading conditions and for different values of the key design parameters of the switch. This model is difficult to use for studying large switches of this kind because of computational complexities. To tackle this problem, an approximate queuing model has also been presented, which may be used to study the performance of large switches of this kind. The results obtained by the two methods are compared to confirm that the approximate model works well under typical loading conditions of the switch.     

Evaluation des performances du réseau en anneau AMBRE pour distribution d’abonnés

ambre is an integrated services digital loop-like network for public local communication. Each communication is a sequence of fixed-length packets separated by fixed-length silences. Performance evaluation is carried through in terms of access-time and transport delays with emphasis on inter packet delay fluctuations.     

Dynamics of TCP traffic over ATM networks

Investigates the performance of transport control protocol (TCP) connections over ATM networks without ATM-level congestion control and compares it to the performance of TCP over packet-based networks. For simulations of congested networks, the effective throughput of TCP over ATM can be quite low when cells are dropped at the congested ATM switch. The low throughput is due to wasted bandwidth as the congested link transmits cells from “corrupted” packets, i.e., packets in which at least one cell is dropped by the switch. The authors investigate two packet-discard strategies that alleviate the effects of fragmentation. Partial packet discard, in which remaining cells are discarded after one cell has been dropped from a packet, somewhat improves throughput. They introduce early packet discard, a strategy in which the switch drops whole packets prior to buffer overflow. This mechanism prevents fragmentation and restores throughput to maximal levels     

Scheduling Algorithms for a Slotted Packet Switch with either Fixed or Variable Length Packets

We address the problem of congestion resolution in optical packet switching (OPS). We consider a fairly generic all-optical packet switch architecture with a feedback optical buffer constituted of fiber delay lines (FDL). Two alternatives of switching granularity are addressed for a switch operating in a slotted transfer mode: switching at the slot level (i.e., fixed length packets of a single slot) or at the burst level (variable length packets that are integer multiples of the slot length). For both cases, we show that in spite of the limited queuing resources, acceptable performance in terms of packet loss can be achieved for reasonable hardware resources with an appropriate design of the time/wavelength scheduling algorithms. Depending on the switching units (slots or bursts), an adapted scheduling algorithm needs to be deployed to exploit the bandwidth and buffer resources most efficiently.