As a promising solution for the next generation optical Internet, optical burst switching still has much to be improved, especially the design of core routers. This paper mainly focuses on channel scheduling algorithms of core routers and proposes a new practical scheduling algorithm. In the new algorithm, burst segmentation, one of the contention resolution schemes that are another major concern in core router design, is introduced. The proposed algorithm is analyzed theoretically and evaluated by computer simulations. The results show that the new algorithm, compared with existing traditional scheduling algorithms, can lower the packet loss probability and enhance the link utilization and network performance.
©2004 Optical Society of America
Optical burst switching (OBS) is a compromise between the advancing optical Internet technology and the actually immature optical devices, which combines technologies of the currently wide-deployed Optical Circuit Switching (i.e., Wavelength Routing) and the most promising Optical Packet Switching. On the basis of optical devices presently available, OBS is intended to transmit traffic in bursts over Wavelength-Division Multiplexing (WDM) links at high speed and with high efficiency, avoiding the potential bottleneck in electronic routers. For high efficiency, no end-to-end connection is established before data transmission. Instead, OBS separates the control information (Burst Header Packet, BHP) and the pure data (Burst) to different wavelength channels, and uses BHP to reserve resources of switches along the route. Because of no waiting for an acknowledgement of whether the reservation is successful, e.g., in the JET protocol, there are risks for bursts to be dropped at certain busy nodes owing to shortage of resources and no data buffer space, especially when the traffic load is heavy. So the blocking probability (i.e., burst loss probability or packet loss probability) is a crucial performance index when taking network performance into evaluation.
An OBS network consists of edge routers and core routers, interconnected by fibers running WDM. Just as its name implies, the edge routers are located at the edge of the network and assemble the electronic input packets into optical bursts, which are sent to the OBS core routers and transmitted optically over core routers without optical-electronic-optical transformation. To reduce the loss probability and to enhance the utilization at the core network, it is a key program to well design processing algorithms for the core routers, mainly referring to scheduling and contention resolution algorithms.
In the OBS network, when two or more data bursts arrive at a same output wavelength, output data channel contention occurs. In order to avoid burst loss due to contention, contention resolution schemes have been deeply studied. Currently, there are four major approaches to deal with contention, including using FDLs (Fiber Delay Line) to delay data bursts, deploying TWCs (Tunable Wavelength Converter) to change the output wavelength, deflecting to another route, and segmenting data bursts to retain part of the dropped burst. FDL and TWC approaches are hardware dependent and their effects on reducing blocking probability are limited by these component’s maturities and prices. Deflection routing has also difficulty because it needs to recalculate the offset time at the deflecting node, requires FDL at the deflecting node or subsequent nodes to adjust the offset time, and consumes TWC if a wavelength change is necessary. Furthermore, deflection routing may cause out-of-sequence among bursts and increase the blocking probability of other core routers when the network traffic is high.
The contention resolution schemes, such as FDL-delay, TWC-conversion and route-deflection, primarily aim at burst losses rather than packet losses. That is, when contention between two bursts cannot be resolved through these methods, one of the bursts will be dropped entirely, even if the overlap between the two bursts is very small. A promising solution for contention resolution is burst segmentation [4–8], in which, instead of all the burst, only those packets of a burst overlapping with another burst will be dropped. It was put forward by Vinod M. Vokkarane et al. in 2002. The burst is considered as being composed of basic transport segments. Each segment may consist of one or several packets. When contention occurs, the burst is divided into two segments, one dropped and the other transmitted as a new burst. The dropped segment will be retransmitted again.
There are two approaches to drop burst segments, when bursts A and B contend with each other, shown in Fig. 1. The first approach is dropping-tail, which drops the tail of burst A (see Fig. 1(a), while the second approach is dropping-head, dropping the head of burst B (see Fig. 1(b). Specially, when preemption occurs, a trailer is created and sent to downstream core routers on the control channel to tell them the modified burst length. For example, in Fig. 1(b), if the priority of burst B is higher than that of burst A and burst A has been scheduled (that is, its BHP has been processed), the tail of burst A is dropped by preemption and a trailer is sent out.
From above, we can see that this novel idea is only advantageous from the view of contention resolution and has inherent limits. Taking the two dropping-segment approaches into consideration, dropping-head is to result in delivery disorder. The dropped head segment will be retransmitted and certainly lag behind the tail segment. Moreover, when there is preemption, it needs to create a trailer to reconfigure all subsequent nodes, but without guarantee to eliminate all potentialities of contention caused by the dropped head or tail before reconfiguration. Finally, if contention is between two bursts with the same priority, the unscheduled burst cannot preempt the scheduled burst and will be dropped entirely. For instance, if burst A has arrived and been scheduled already, when burst B with the same priority arrives, it cannot preempt burst A, and will be dropped.
To overcome the limits of burst segmentation, this paper combines the idea of burst segmentation with the scheduling algorithm. The remainder of the paper has been structured as follows. Section 2 presents the new scheduling algorithm, burst segmentation for void filling scheduling. Section 3 analyzes the performance of the new algorithm, mainly referred to the packet loss probability. Section 4 provides the numerical results, and the conclusion follows in Section 5.
2. Burst segmentation for void filling scheduling
To eliminate the limits of burst segmentation aforementioned in Section 1, we integrate the idea of burst segmentation into scheduling algorithms, and propose a new practical scheduling algorithm, named BSVF (burst segmentation for void filling scheduling).
Scheduling algorithms are related closely to the hardware architecture. If no TWC is used in the core router of the OBS network, the core router can be regarded as several parallel M/M/1 queuing systems and the scheduling algorithm is rather simple. So, in this paper, all discussion is based on the assumption that full TWCs but no FDL are deployed.
Among the existing scheduling algorithms, FF (First Fit) is the simplest, which searches all output wavelengths and selects the first available one. Obviously, FF is not effective and may lead to large voids between two adjacent data bursts on an output wavelength. To minimize voids, Xiong et al.  proposed an improved algorithm, named LAUC (Latest Available Unscheduled Channel), as well as its derivation, LAUC-VF (LAUC-Void Filling). Its loss probability is much less than that of LAUC, because LAUC-VF makes the best of voids. More, M. Iizuka et al. polished LAUC-VF in  to select voids first when there are both a free channel and a void available. We call it LAUC-VF Plus.
The basic idea of LAUC is to minimize voids, LAUC-VF makes use of the minimized voids and LAUC-VF Plus makes improved use of the minimized voids. However, in the algorithms with void filling, such as LAUC-VF and LAUC-VF Plus, the void-filling is passive. Because the void length and the burst length are random, a void is eligible only if the void length is long enough and the void can contain the burst. Otherwise, the burst will be dropped, even though there are many voids whose lengths are just a bit shorter than that of the burst. In this condition, these voids are wasted, but they can be used more efficiently.
SFMOC-VF (Segment-First Minimum Overlap Channel with Void Filling)  uses FDL and segmentation for the void-filling scheduling. Although SFMOC-VF, compared with other algorithms with void-filling, can make use of more voids, the algorithm is not practical because it allows head dropping which will cause transmission disorder as mentioned above. Secondly, this algorithm needs the help of FDL and imposes dependence on output-buffered FDL that asks for a much more expensive switch matrix with internal speedup. Moreover, the FDL is not a kind of random access memory, and latest researches show that the FDL has limited contribution to the loss performance, especially when the burst length increases.
Our algorithm here is to use burst segmentation but without FDL for active void-filling. If, on different wavelength channels, some ineligible voids which are to be wasted overlap each other and are continuous, we can concatenate and merge these voids into an eligible one, which can be used to serve a burst. And the burst is segmented to these voids, while keeping its BHP aware of the segmentation. Obviously, in this algorithm, it is possible to drop the tail part of the burst when the concatenated void is not long enough to contain this part, and there may be several times of segmentation. However, no dropping-head is permitted. The new algorithm is described in detail as follows. For simplicity, the scheduling algorithm, LAUC-VF Plus, is used as a sub-algorithm in our proposed algorithm.
When a data burst arrives at an optical core router at a certain time, our algorithm first selects the data channel according to LAUC-VF Plus to keep the void newly being generated minimal. In Fig. 2, data bursts are marked with the numbers 1, 2 and 3 to indicate their arrival sequence. For data burst 1, channels 1, 2 and 3 are all suitable to serve it, because the time period of (t3, t5) on these channels is unscheduled. Channels 2 and 3 have voids, while channel 1 is completely free after t3. However, because t2-t3 is less than t1-t3, channel 2 is selected. When scheduling burst 2, only channel 1 is competent.
If there is no void or free channel for the whole burst, all wavelengths of the output port would be searched to collect overlapped continuous voids. When burst 3 arrives, see Fig. 2, no channel meets its expectation. If dropping-tail of the traditional burst segmentation in  is applied, burst 3 would preempt burst 2, and burst 2 would be segmented at the segment point a, with the tail dropped. But in our algorithm, voids t1–t6 on channel 3, t4–t8 on channel 4, and t7–t9 on channel 5 overlap each other and can be merged into a continuous void t1–t9. Burst 3 is segmented at point b and c into three segments, with which the three voids are filled respectively. Obviously, the segment points of burst 3 are independent of the overlapping length of bursts 2 and 3. Furthermore, burst 3 will no longer have any negative effect on burst 2. When segmentation occurs, new BHPs for these new bursts are created. The BHP of the original burst is modified, as the BHP for the first new burst, while the others are newly generated. All these transactions can be easily controlled and processed at the core router.
The combination of burst segmentation and scheduling algorithm overcomes the existing limits of burst segmentation, and makes the new scheduling algorithm more efficient. These will be verified by the original theoretical analyses and numerical results, following in next two sections.
3. Theoretical analysis
A typical optical switch matrix of the core router is shown in Fig. 3. It has n ports and each port has k wavelength channels. Suppose that each input wavelength channel has identical traffic and each burst is uniformly distributed to each output port. For a given output port, it can be modeled as a queuing system. Owing to the fully deployed TWCs on each input port, the queuing system has k servers. And the system capacity is also k, because no FDL is used. Furthermore, we assume that data bursts on every wavelength channel arrive at a core router in accordance with a Poisson process and the service times are i.i.d (identically distributed independent) random variables following the negative exponential distribution. Let λ be the burst arrival rate at an input port and µ the service rate. In brief, the queuing system can be described by the notation M/M/k/k.
The burst number in the queuing system is always changing. Fig. 4 gives a snap shot at a certain period of time. According to our proposed algorithm, bursts arriving during the time when there are already k bursts in the system, e.g., during the time t and t’ in Fig. 4, will be discarded. Otherwise, the algorithm will search an eligible void or free channel, or concatenate overlapped continuous voids to serve the burst. Assume a burst arrives at time 0 with initial system state j (j<k), i.e., j bursts in the system. Then the first passage time tj from j to k, see Fig. 4, can be used to serve the burst, whichever condition the algorithm meets. Let Lb be the burst’s length. If tj<Lb, there will be a burst’s tail of length (Lb-tj) to be dropped. Or else, the burst will pass through the core router with no loss.
When j=0, we have
where, E[t0] is the expectation of the first passage time t0, Y (Δt) is the system state after Δt, and P0,j(Δt) (0≤j≤k) is the transition probability from 0 to j.
Let Tj denote E[tj], (0≤j≤k). Herewith, we can write the following equations.
Owing to properties of the birth-death process, Eq. (2) can be rewritten as follows, where all O (Δt) items are ignored.
From Eq. (4), we can get a closed form solution:
All the solutions can be easily produced by iterating the difference equations (4). But owing to the limited paper length, they are not listed here. With these solutions, we can compute the average loss at the system state j as follow:
So the loss probability of a burst at a core router is
where, To1 and To2 are respectively the offset time of two independent data bursts, with τ 12 as their BHPs’ arrival interval.
4. Numerical results
To evaluate the performance of the proposed algorithm and validate our analytical results, a simulation model has been developed. Instead of the network environment, only a single core router’s behavior is simulated. The core router has a 4×4 non-blocking switch architecture and each port has 8 data wavelength channels. The burst length is exponentially distributed with average burst length of 1/µ=100 µs. Transmission rate is 2.5 Gbps. Packet length is 1250 bytes. There is no buffering at the core router, but full TWCs are deployed. Traffic load of a port is measured in Erlang (not normalized).
Figure 5 plots the packet loss probability versus the traffic load for the well-known scheduling algorithms and the proposed algorithm. It can be seen that the proposed algorithm has a better performance, compared with others, e.g. LAUC-VF lus. Especially, when the traffic load becomes higher, the performance improvement is more obvious. This result indicates that segmentation for void filling can make better use of voids, efficiently decrease the packet losses, and increase the channel utilization. Figure 6 shows the performance as the burst length and the number of data wavelengths increase. The packet loss probability rises slightly, which indicates that the proposed algorithm is robust and independent of the varying of the burst length.
In this paper, we proposed a new practical scheduling algorithm for optical burst switching. It is also is a further development of a contention resolution scheme. The combination of segmentation and scheduling algorithms brings segmentation to a new dimension and makes burst scheduling more efficiently. All problems encountered in traditional burst segmentation, such as out-of-sequence or sending trailer, are eliminated completely. The voids that cannot be used in traditional scheduling algorithms, e.g., LAUC-VF or LAUC-VF Plus, are possible to be utilized, as long as a continuous void can be merged from them. If only a merged continuous void fills the requirement of a burst, the burst is segmented to these voids, exactly, sub-voids. To keep traffic in sequence, no head in the burst can be dropped. When dropping the tail is necessary, there is no preemption permitted and all segmentations are under control. Through computer simulation, it can be concluded that our proposed scheduling algorithm can decrease packet loss probability and have high channel utilization, which is of great benefit to the performance of core routers.
The author gratefully acknowledges 863 Program of China for financially supporting this work (contract number 2002AA12202), and thanks Professor Sheng Wang and Lemin Li for valuable discussions.
References and links
1. Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM network,” IEEE Journal on Selected Areas in Communications 18, 1838–1851 (Oct. 2000). [CrossRef]
2. M. Iizuka, M. Sakuta, and Yoshiyuki, “A Scheduling algorithm minimizing voids generated by arriving bursts in optical burst switched WDM network,” in Proceedings of IEEE Globecom (Nov. 2002), 3, 2736–2740.
3. Jinhui Xu, C. Qiao, J. Li, and G. Xu, “Efficient channel scheduling algorithms in optical burst switched networks,” in Proceedings of IEEE INFOCOM (Mar. 2003), 3, 2268–2278.
4. V. Vokkarane, J.P. Jue, and S. Sitaraman, “Burst segmentation: An approach for reducing packet loss in optical burst switched networks,” in Proceedings of IEEE ICC (May. 2002), 5, 2673–2677.
5. Vinod Vokkarane and Jason Jue, “Burst segmentation: an Approach for Reducing Packet Loss in Optical Burst Switched Networks,” Optical Networks Magazine 4, 81–89 (Nov./Dec. 2003).
6. M. Neuts, H. L. Vu, and M. Zukerman, “Insight into the benefit of burst segmentation in optical burst switching,” in Proceedings of Conference on Optical Internet and Photonics in Switching (Cheju Island, Korea, July 2002), 126–128.
7. Vinod Vokkarane and Jason Jue, “Prioritized burst segmentation and composite burst assembly techniques for QoS support in optical burst-switched networks,” IEEE Journal on Selected Areas in Communications 21, 1198–1209 (Sep. 2003). [CrossRef]
8. Vinod M. Vokkarane, Guru P. V. Thodime, and Venkata U. B. Challagulla, et. al, “Channel Scheduling Algorithms using Burst Segmentation and FDLs for Optical Burst-Switched Networks,” in Proceedings of IEEE ICC (May 2003), 2, 1443–1447.
9. Some parts of this paper have appeared in APOC’03 (Asian Pacific Optical Conference, 2003) with EI access No. 04278246336