On ordered scheduling for optical burst switching

Optical burst switching (OBS) is a promising optical networking paradigm for efficient transport of bursty IP traffic over wavelength division multiplexing (WDM) optical Internet networks. In OBS, the header of a burst is sent in advance of the data burst to reserve a wavelength channel at each optical switching node along the path. The nodes use a scheduling algorithm to assign wavelengths to incoming bursts. Our work is motivated from the observation that existing scheduling algorithms assign a wavelength to a burst when its header arrives at the node. Thus, information about other bursts whose headers arrive later is not available when the scheduling decision is made. This leads to suboptimal scheduling decisions and unnecessary burst dropping. The key idea in our proposed algorithm, Ordered Scheduling, is to defer making the scheduling decision until just before the burst arrival in order to have full knowledge about other bursts. The effectiveness of the proposed algorithm is studied through simulation and the computational complexity and signalling overhead are analysed.     

Performance analysis of timer-based burst assembly with slotted scheduling for optical burst switching networks

In this paper, we analyze the performance of a timer-based burst assembly for optical burst switching (OBS) networks. In our analytical model, an ingress edge node has multiple buffers where IP packets are stored depending on their egress edge nodes, and bursts are assembled at the buffers in round-robin manner. Moreover, bursts are transmitted in accordance with slotted scheduling where each burst transmission starts at the slot boundary. We construct a loss model with two independent arrival streams, and explicitly derive the burst loss probability, burst throughput, and data throughput. In numerical examples, we show the effectiveness of our analysis in comparison with the Erlang loss system. It is shown that our model is quite useful for an OBS network with a large number of input and output links.     

Performance analysis of an ingress switch in a JumpStart optical burst switching network

We consider an ingress optical burst switching (OBS) node employing the JumpStart signaling protocol. The switch serves a number of users, each connected to the switch with a fiber link that supports multiple wavelengths. Each wavelength is associated with a 3-state Markovian burst arrival process which permits short and long bursts to be modeled. We model the ingress switch as a closed multi-class non-product-form queueing network, which we analyze approximately by decomposition. Specifically, we develop new techniques to analyze the queueing network, first assuming a single class of customers, and subsequently multiple classes of customers. These analytical techniques have applications to general queueing networks beyond the one studied in this paper. We also develop computationally efficient approximate algorithms to analyze an ingress switch in the limiting case where the number of wavelengths is large. The algorithms have a good accuracy, and they provide insight into the effect of various system parameters on the performance of an ingress OBS switch.     

OBS网络中基于突发的可用信道数组及其调度算法

信道调度算法是提高光突发交换(OBS)网络性能的关键技术之一.现有的数据信道调度算法多是基于单一突发的模式,即每个突发的控制分组(BCP)到达后就立即被调度处理,其效率的提高已迭极限.首次提出基于突发的可用信道数组的概念,将对每个突发仅搜索一次信道组的状况并保存有关信息,从而有效提高系统的调度效率.该设计的调度器能有效减少对信道状况的多次扫描,进一步改善OBS网络的性能.     

Link scheduling state information based offset management for fairness improvement in WDM optical burst switching networks

In wavelength division multiplexed (WDM)-based optical burst switching (OBS) networks, bursts that traverse longer paths are more likely to be dropped compared to bursts that traverse shorter paths resulting in a fairness problem. Fairness here refers to having, for all ingress–egress node pairs in a network, a burst to have equal likelihood to get through independent of the hop length involved. In this paper, we develop a link scheduling state based fairness improvement method which can be used in a classless as well as a multi-class environment. The basic idea is to collect link scheduling state information and use it to determine the offset times for routes with different hop lengths. By using the online link state information, this method periodically computes and adapts the offset times needed, thus inherently accounting for the traffic loading patterns and network topological connectivity. It also ensures that the delay experienced by a burst is low and shorter-hop bursts are not over-penalized while improving the performance of longer-hop bursts. The effectiveness of the proposed method is evaluated through simulation experiments.     

OBS网络中基于优先级与概率的偏射路由算法*

摘 要：为了保证OBS网络中不同优先级业务的服务质量和解决偏射算法在偏射控制上的问题,提出了一种基于优先级与概率的偏射路由算法。该算法根据突发包的优先级和转发概率来控制突发包的偏射,并从网络突发阻塞概率的意义上寻找最佳偏射路由。当冲突发生时,分割优先级低的突发包,并将分割突发包偏射到空闲的链路上;节点根据链路上指定的权值,按概率为分割突发包选择一条可以使网络突发阻塞概率最小的最佳偏射路由。仿真结果表明,虽然网络中可选路由数目的增加对网络性能的改善非常有限,但是该算法能够有效的降低整个网络的丢包率,并且得到的高优先级突发包的丢失率低于低优先级突发包的丢失率,从而很好的保障了网络的服务质量。故这种方法能够有效的提高OBS网络的性能。     

An optical burst reordering model for time-based and random selection assembly strategies

Contention resolution schemes in optical burst switched networks (OBS) as well as contention avoidance schemes delay burst delivery and change the burst arrival sequence. The burst arrival sequence usually changes the packet arrival sequence and degrades the upper layer protocols performance, e.g., the throughput of the transmission control protocol (TCP).In this paper, we present and analyze a detailed burst reordering model for two widely applied burst assembly strategies: time-based and random selection. We apply the IETF reordering metrics and calculate explicitly three reordering metrics: the reordering ratio, the reordering extent metric and the TCP relevant metric. These metrics allow estimating the degree of reordering in a certain network scenario. They estimate the buffer space at the destination to resolve reordering and quantify the number of duplicate acknowledgements relevant for investigations on the transmission control protocol.We show that our model reflects the burst/packet reordering pattern of simulated OBS networks very well. Applying our model in a network emulation scenario, enables investigations on real protocol implementations in network emulation environments. It therefore serves as a substitute for extensive TCP over OBS network simulations with a focus on burst reordering.     

An integrated congestion control mechanism for optimized performance using two-step rate controller in optical burst switching networks

Optical burst switching (OBS) is a promising solution to implement the optical internet backbone. However, the lack of adequate congestion-control mechanisms may result in high burst loss. Schemes such as fiber delay line (FDL), wavelength conversion, and deflection routing to reduce burst collision are unable to prevent the network congestion effectively. To address this problem, we propose and investigate a global solution, called Integrated Congestion-Control Mechanism (ICCM), for OBS networks. ICCM, which combines congestion avoidance with recovery mechanism, restricts the amount of burst flows entering the network according to the feedback information from core routers to edge routers to prevent network congestion. Also, a flow-policing scheme is proposed to intentionally drop the overloaded traffic with a certain probability at a core router to support fairness among flows. Moreover, the transmission rate of each flow is controlled to achieve optimized performance such as maximizing throughput or minimizing loss probability using two-step rate controller at the edge router. Simulation results show that ICCM effectively eliminates congestion within the network and that, when combined with a flow-policing mechanism, the fairness for competing flows can be supported while maintaining effective network performance.     

A novel TCP with dynamic Burst-Contention Loss notification over OBS networks

In this paper, a novel congestion control scheme with dynamic Burst-Contention Loss notifications in Optical Burst Switching (OBS) networks is proposed. The proposed scheme, called TCP-BCL, aims to handle various OBS bursty conditions that negatively affect TCP throughput performance and fairness. The basic design principle of the scheme is to tune the congestion control parameters α and β such that the congestion window sizes in the corresponding TCP senders can be adjusted with an explicit notification from the OBS edge node. The performance impact on TCP in terms of burst dropping due to random contention, which is also known as false congestion detection is considered and investigated. An analytical model is developed and further verified through extensive simulation.     

On burst rescheduling in OBS networks with partial wavelength conversion capability

The core nodes in an optical burst switching (OBS) network are normally equipped with wavelength converters (WCs) to reduce the burst loss probability. Since WCs are expensive and still immature technologically, it is desirable to reduce the number of WCs in the network and to have partial wavelength conversion capability at the core nodes. Nevertheless, a majority of algorithms in the literature are proposed under the full wavelength conversion assumption. As a result, they do not consider the burst loss caused by insufficient WCs, i.e., bursts dropped due to the unavailability of free WCs to convert them to unused wavelengths. In this paper, we demonstrate how to use burst rescheduling to decrease the burst loss due to insufficient WCs and hence cut down on the overall burst loss probability in OBS networks. Two burst rescheduling algorithms are proposed. Their effectiveness in reducing the overall burst loss probability is verified through simulation experiments.     

光突发交换网络中QoS机制研究与实现

光突发交换作为下一代光互联网最有前途的解决方案已经越来越受到人们的关注,如何增强光突发交换网络的服务质量(QoS)保障能力,已成为光交换领域内的一个重要研究课题。论文对光突发交换网络中基于偏置时间的QoS机制进行了研究,采用低优先级直接丢弃算法,结合突发分片技术和最近可用信道-空隙填充算法,提出了一种新的QoS解决方案,通过建立相应的光突发交换网络模型对该解决方案进行了仿真比较,仿真结果表明该方案可以明显地降低阻塞率,提高信道利用率,为各类业务提供良好的QoS保障。     

光突发交换网络中的重调度算法

介绍了光突发交换（OBS）网络,在现有算法LAUC_VF的基础上提出了一种重调度算法,即LAUC_VF_RESCHEDULE算法,它的主要思想是：对新到达的突发运用LAUC_VF算法调度不成功时,将已经调度成功的突发从原有信道Ⅰ重新调度到另一数据信道J上,并保持该突发的到达时刻和结束时刻不变,从而将新到达的突发调度到数据信道Ⅰ上。仿真结果表明在大多数情况下该重调度算法相对于LAUC_VF算法对网络性能的改善是比较大的。     

OBS网络中多重主动重调度算法

信道调度算法是光突发交换（OBS）网络的关键技术之一。在主动重调度算法的基础上,提出了一种新的多重主动重调度算法,通过搜索并重调度数据信道上所有能进行重调度的突发,使多个突发重调度后产生的间隔尽量小,从而降低突发丢失率。     

Dynamic load balancing in IP-over-WDM optical burst switching networks

In this paper, we consider the problem of dynamic load balancing in wavelength division multiplexing (WDM)-based optical burst switching (OBS) networks. We propose a load balancing scheme based on adaptive alternate routing aimed at reducing burst loss. The key idea of adaptive alternate routing is to reduce network congestion by adaptively distributing the load between two pre-determined link-disjoint alternative paths based on the measurement of the impact of traffic load on each of them. We develop two alternative-path selection schemes to select link-disjoint alternative paths to be used by adaptive alternate routing. The path selection schemes differ in the way the cost of a path is defined and in the assumption made about the knowledge of the traffic demands. Through extensive simulation experiments for different traffic scenarios, we show that the proposed dynamic load balancing algorithm outperforms the shortest path routing and static alternate routing algorithms.     

An elastic compensation model for frame-based scheduling algorithms in wireless networks

Scheduling algorithms for high-speed wireless networks need to be simple to implement for serving packets while ensuring quality-of-service (QoS). The ordinary frame-based scheduling principle is well-known for providing fair service with low implementation complexity. However, existing frame-based scheduling algorithms cannot properly handle location-dependent burst errors in wireless networks. To utilize the advantages of frame-based scheduling algorithms in error-prone wireless networks, we propose an elastic compensation model that provides not only smooth compensations without any service disruptions of flows but also flexible compensations to flows that experience frequent errors to provide flows with fairness of service. From our analysis and simulation studies, we found that the proposed compensation model shows smooth compensation performance without any service disruption periods and good fairness performance when channel errors occur.     

Optimal admission control algorithms for scheduling burst data in CDMA multimedia systems

The third generation mobile communication systems are widely envisioned to be based on wideband code division multiple access (CDMA) technologies to support high data rate (HDR) packet data services. To effectively harness the precious bandwidth while satisfying the HDR requests from users, it is crucial to use a judicious burst admission control algorithm. In this paper, we propose and evaluate the performance of a novel jointly adaptive burst admission algorithm, called the synergistic burst admission control algorithm to allocate valuable resources (i.e., channels) in wideband CDMA systems to burst HDR requests. We consider the spatial dimension only, and by that we mean the algorithm performs scheduling and admission control, for the current frame only, based solely on the selection diversity in the geographical and mobility aspects. The scheduler does not exploit the temporal dimension in that it does not make allocation decisions about future frames (i.e., requests that do not get allocation are simply ignored and such requests will be treated as new request in future frames). In the physical layer, we use a variable rate channel-adaptive modulation and coding system which offers variable throughput depending on the instantaneous channel condition. In the MAC layer, we use the proposed optimal multiple-burst admission algorithm, induced by our novel integer programming formulation of the admission control and scheduling problem. We demonstrate that synergy could be attained by interactions between the adaptive physical layer and the burst admission layer. Both the forward link and the reverse link burst requests are considered and the system is evaluated by dynamic simulations which takes into account of the user mobility, power control and soft handoff. We found that significant performance improvement, in terms of average packet delay, data user capacity and coverage, could be achieved by our scheme compared to the existing burst assignment algorithms.     

Optimal algorithms for the batch scheduling problem in OBS networks

This paper introduces optimal batch scheduling algorithms for the problem of scheduling batches of bursts in optical burst switching networks. The problem is modelled as a job scheduling problem with identical machines. The consideration of previously scheduled bursts in the scheduling allows such modeling. Two optimal algorithms with polynomial time complexity are derived and evaluated. Results show that the algorithm that allows re-scheduling of previously scheduled bursts leads to preferred solutions.Moreover, an extended version of the JET reservation protocol is proposed for efficient handling of batches of bursts. Results obtained via simulation prove the superior performance of the BATCHOPT algorithm.     

A method to evaluate the spatial extensibility of a switching unit and network

Switching units and networks have been analyzed as extensible fabrics,mostly in terms of their scheduling algorithms.The traditional literature on switching extensibility has provided complexity theory only relating to the total numbers of inputs(or outputs)and exchange lines.This paper analyzes switching extensibility in terms of not only the scheduling algorithm and also the fabric itself.It is found that determining extensibility from soft complexity related to the number of inputs(or outputs)of the scheduling algorithm and the fabric extensibility in previous studies without quantization is a flawed conception.A method is thus proposed to express the spatial extensibility of a switching unit or network in terms of the connections of a switching resource and capacity.The method calculates parameter ES(the efciency of switching)of an m×n switching unit and obtains two functions of the switching unit to describe spatial extensibility along with the number of unilateral inputs or outputs.It is found that the range of ES is(0,1]and three types of switching unit and two types of crosspoint networks have ES=1.ES is calculated for banyan,Clos,parallel packet,fully interconnected and recirculation switching networks.The ES value for the banyan switching network is larger than that for other networks,and switching networks are classified into three types that have absolute/linear/denied spatial extensibility according to the limES value.It is demonstrated that a switching network has the largest ES value when it contains only the five types of switching unit for which ES=1.Finally,a group-switching-first self-routing banyan switching network with lower blocking probability and time delay is deduced,and the ES method is contrasted with two other methods of evaluating spatial extensibility in terms of their mathematical expressions and intuitive graphics,for the five types of switching network listed above.     

Route optimization in optical burst switched networks considering the streamline effect

Route optimization in optical burst switching (OBS) networks is investigated in this paper. Two route optimization problems are studied. The first problem considers the network in the normal working state where all the links are working properly. The route for each flow is decided so as to minimize the overall network burst loss. The second problem considers the failure states apart from the normal working state. The primary and backup paths for each flow are determined in such a way to minimize the expected burst loss over the normal and failure states. We argue that route selection based on load balancing or the traditional Erlang B formula is not efficient because of an important feature called the streamline effect. We analyze the streamline effect and propose a more accurate loss estimation formula which considers the streamline effect. Based on this formula, we develop mixed integer linear programming (MILP) formulations for the two problems. Since the MILP-based solutions are computationally intensive, we develop heuristic algorithms. We verify the effectiveness of our algorithms through numerical results obtained by solving the MILP formulations with CPLEX and also through simulation results.