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.     

Buffering management schemes for optical variable length packets under limited packet sorting

This paper studies several buffering strategies for optical packet switching (OPS) under limited packet sorting. Three schemes, which are able to sort newly arrived packets based on packet’s length as well as capability of finding the minimum buffer occupancy, are analyzed and compared. Results show that all three proposed schemes could improve OPS performance considerably in terms of probability of packet loss (PPL) and probability of information loss (PIL). In addition, the simulation results show that not all the newly arrived packets need to be sorted in order to obtain minimum packet loss probability. Since the amount of packets and thus the packet processing time is significant in OPS, it is possible that not all the packets can be processed using one of the buffering strategies. An important finding of this paper is that if only 10% of the packets are sorted, the PPL is comparable to the minimum packet loss value obtained when 100% of the packets are sorted.     

一种支持扇出分割能力的光组播调度算法研究

组播调度是影响光组播分组交换节点吞吐量的重要因素.针对“一次发送”模型下的光组播调度算法对阻塞的源组播实行全部丢弃的缺点,文章基于节点共享有限波长转换器的光分组交换结构,提出了一种支持扇出分割能力的光组播调度算法,该算法采用随机丢弃阻塞的源组播复制的方法,有效地提高了端口资源的利用率.仿真结果表明,该算法与已有算法相比...     

混合缓存型异步光分组交换的一种改进FF-VF算法

光纤延迟线（FDL）是异步光分组交换（OPS）采用的时域冲突解决方案,通过计算其分组丢失率（PLR）发现,在业务负载高,特别是业务负载大于0．7时,PLR性能较差。研究以FDL作为主要的常规缓存、以电存储器作为辅助缓存的光电混合缓存结构,并用改进的首选即中的填空（IFF-VF）算法调度冲突的分组,达到改善可变长OPS的PLR目的。分析和仿真结果表明,光电混合缓存和IFF-VF算法能改善可变长OPS在负载较高时的PLR性能,并减少FDL的数目。     

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.     

具有反馈式光缓存的OPS节点结构性能研究

对反馈式光分组交换节点的性能进行深入分析,并针对现有反馈式光分组交换节点结构的不足,提出一种改进的反馈式光分组交换节点结构,即SMOP-TWC交换结构.最后,本文使用仿真实验的方法对SMOP-TWC交换结构的性能进行深入研究.     

异步光分组交换网的流量建模

研究了异步光分组交换网的流量特性，提出了网络流量的解析模型和近似模型。研究表明，在采用计时门限光分组组装算法的情况下，如输入IP流具有短程相关特性(ShortRangeDependent)，则光分组的到达间隔时间呈负指数分布，光分组的长度趋于高斯分布。     

时隙可变长分组缓存调度算法

提出了一种采用时隙处理光分组竞争冲突的基于光纤延迟线的光分组交换缓存算法——时隙可变长分组缓存调度算法SVPB(slotted variable-length-packet-capable buffer)。该算法根据先到先服务的排队原则,通过对到来的光分组进行时间轴分段处理,解决了FDLs作为缓存器的不足。从仿真结果得到,在网络负载较高时所提出的调度算法SVPB比已有的调度算法分组丢失率有明显的降低。     

Burst transmission algorithm to improve packet level performance in contention-free slotted OBS networks

In contention-free slotted optical burst switching (SOBS) networks, controllers are utilized in order to manage the time-slot assignment, avoiding congestions among multiple burst transmissions. In this network, bursts are never lost at intermediate nodes but packets are lost at an ingress edge node due to a burst transmission algorithm. In addition, packet transmission delay increases depending on the algorithm. In order to improve packet level performance, in this paper, we propose a new burst transmission algorithm. In this method, two different thresholds are used; one is used to send a control packet to a controller and the other is used to assemble a burst. With these thresholds, a time slot can be assigned to a burst in advance and packet level performance can be improved. In order to evaluate its packet level performance and investigate the impact of thresholds, we also propose a queueing model of a finite buffer where a batch of packets are served in a slot of a constant length. Numerical results show that our proposed method can decrease packet loss probability and transmission delay with two thresholds. In addition, we show that our analysis results are effective to investigate the performance of the proposed method when the number of wavelengths is large.     

B—DMB快速分组交换机的性能分析

由于不能预先对进入B-DMB交换机的各分组进行调整,可能出现同一时隙有2个或2个以上的分组都要到达某一输出端的情形,因此在B-DMB交换机中不可避免地要加进一些缓冲器。本文对B-DMB交换机的输入、输出缓冲器长度和分组时延进行了分析和计算,得出了一些有用的结论。     

Routing strategies for maximizing throughput in LEO satellite networks

This paper develops routing and scheduling algorithms for packet transmission in a low Earth orbit satellite network with a limited number of transmitters and buffer space. We consider a packet switching satellite network, where time is slotted and the transmission time of each packet is fixed and equal to one time slot. Packets arrive at each satellite independently with a some probability during each time slot; their destination satellite is uniformly distributed. With a limited number of transmitters and buffer space on-board each satellite, contention for transmission inevitably occurs as multiple packets arrive at a satellite. First, we establish the stability region of the system in terms of the maximum admissible packet arrival rate that can possibly be supported. We then consider three transmission scheduling schemes for resolving these contentions: random packet win, where the winning packet is chosen at random; oldest packet win, where the packet that has traveled the longest distance wins the contention; and shortest hops win (SHW), where the packet closest to its destination wins the contention. We evaluate the performance of each of the schemes in terms of throughput. For a system without a buffer, the SHW scheme attains the highest throughput. However, when even limited buffer space is available, all three schemes achieve about the same throughput performance. Moreover, even with a buffer size of just a few packets the achieved throughput is close to that of the infinite buffer case.     

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.     

Approximate Modeling of Optical Buffers for Variable Length Packets

This paper addresses the problem of dimensioning buffers realized by means of fiber delay lines in optical routers able to switch packets that have variable length and are sent asynchronously on the optical links. The optical buffer is analyzed focusing on the different behavior of a delay buffer and an electronic memory. The role of the time unit of the fiber delay lines is discussed, showing that it is a crucial parameter to determine the queuing performance. The paper presents two approximate analytical models that can be used both for analysis and engineering of the optical buffer and in particular to dimension the buffer time unit in an way that is optimal with respect to packet loss probability. The first model is based on an infinite queuing approximation. It is not very accurate and is valid for a limited set of values of the traffic load, but is extremely simple. The second model is based on a finite queuing approximation. It is more complex but more accurate and is valid for any value of traffic load. The accuracy of the models is compared with simulation and their range of applicability purposes is discussed.     

光交换的时间及空间结构分析

拓扑学上的光网络由边(光传输)和节点(光交换)组成。从业务属性出发,基于连接和无连接方式,分析了光交换的时间结构,包括光分组和光突发的时间结构,以及不同动态性的光电路交换的时长及其度量标准,结合实验结果分析了最短光电路交换的时长极限。从多端口和大容量的要求出发,重点讨论了基于微电子机械系统(MEMS)开关、波长选择开关(WSS)和阵列波导光栅(AWG)的三种光交换结构。分析了光交换结构的扩展方法,并讨论了光交换的几个具有挑战性的问题,包括缓存和能耗问题。通过分析,希望从时间和空间两个维度更清晰地认识光交换的本质及其与电交换的异同。     

未来光因特网中的光交换方式及其发展趋势

Internet的业务流量正以每六个月翻一番的速度快速增长,未来网络中,数据业务超过话音业务只是时间问题,因此,基于电路交换的电信网升级到支持基于分组交换的数据业务是不可避免的,但是对因特网来说,由于光逻辑与光存储等器件不成熟,发展全光分组交换,技术上异常困难。另一方面,近来新提出的光突发交换,技术上相对简单,性能特点优异,因而成为更理想的选择,本文介绍了全光分组交换和光突发交换的研究现状,比较了两者的优缺点,最后指出改进光突发交换性能的两种方式。     

分组交换技术在光传输网中的研究与设计

针对用电路交换技术传输OTN信号面临容量、速率受限的问题,研究了基于包结构的光传送网的优势并提出实现方案。文中首先介绍了分组交换网络和光传送网相结合的基本结构,以及OTN帧结构及混合网络中标准的包格式,最后描述了一个将OTN技术和数据包技术相融合的可实现结构。该结构能将光信道数据单元解复用为低阶形式,并将其切割为离散的数据包。切割好的数据包由标准包接口送往包交换芯片进行交换,交换后的数据包进入重组模块,将其重组为连续的数据流,再由复用模块将光信道数据单元复用到其高阶形态发送出去。     

有优先级的输出排队快速分组交换机性能研究

输出排队结构是快速分组交换中交换性能最佳的交换结构。本文研究输出排队结构交换任意种优先级业务的排队性能。分别在独立和相关到达两种情况下导出了任意优先级业务的平均排队长度等特征参数,发现当N×N规模互连网络的端口数N足够大时,两种业务到达模型的排队性能趋于一致。文中提出了一种数值迭代法来求取用二维Markov过程表示的高、低优先级分组队列长度的稳态解。计算机模拟结果证实了文中的分析。     

异步光分组交换的缓存排序方案及性能

分析了简单的先到先服务(FCFS)光纤延迟线(FDL)循环占用方案性能,发现其分组丢失率(PLR)较高,提出3种输入分组按长度排序,寻找最小的FDL缓存优化分配方案.分析和仿真结果表明:约10%的分组排序后使3种方案都大大地能减小PLR,最小长度分组占用最小可用FDL缓存方案的性能最好.业务负载低于0.8时,排序的缓存方案对管理有限的FDL是有效的.     

A Modular, Scalable, Extensible, and Transparent Optical Packet Buffer

We introduce a novel optical packet switching buffer architecture that is composed of multiple building-block modules, allowing for a large degree of scalability. The buffer supports independent and simultaneous read and write processes without packet rejection or misordering and can be considered a fully functional packet buffer. It can easily be programmed to support two prioritization schemes: first-in first-out (FIFO) and last-in first-out (LIFO). Because the system leverages semiconductor optical amplifiers as switching elements, wideband packets can be routed transparently. The operation of the system is discussed with illustrative packet sequences, which are then verified on an actual implementation composed of conventional fiber-optic componentry     

Performance analysis of a random packet selection policy formulticast switching

This paper studies a random packet selection policy for multicast switching. An input packet generates a fixed number of primary copies plus a random number of secondary copies. Assuming a constant number of contending packets during a slot, the system is modeled as a discrete time birth process. A difference equation describing the dynamics of this process is derived, the solution of which gives a closed form expression for the distribution of the number of packets chosen. Then this result is extended to the steady state distribution through a Markov chain analysis. It is shown that the old packets have larger fanout than the fresh packets and the copy distribution of the mixed packets is determined. The packet and copy throughput taking into account the old packets have been obtained. We determined the mean packet delay as well as an upperbound for packet loss probabilities for finite buffer sizes. The asymptotic distribution of the number of packets is also given for large switch sizes under saturation by applying results from the renewal theory. Finally, simulations are done to determine the performance of the switch under mixed (unicast plus multicast) traffic