Open Access
Add to BibSonomyAbstract
We provide here a new loss model for an optical hybrid switch that can function as an optical burst switch or optical circuit switch or both simultaneously. We introduce the feature of circuit queued reservation. That is, if a circuit request arrives and cannot find a free wavelength, and if there are not too many requests queued for reservations, it may join a queue and wait until such wavelength becomes available. We first present an analysis based on a 3-dimension state-space Markov chain that provides exact results for the blocking probabilities of bursts and circuits. We also provide results for the proportion of circuits that are delayed and the mean delay of the circuits that are delay. Because it is difficult to exactly compute the blocking probability in realistic scenarios with a large number of wavelengths, we derive computationally scalable and accurate approximations which are based on reducing the 3-dimension state space into a single dimension. These scalable approximations that can produce performance results in a fraction of a second can readily enable switch dimensioning.
©2005 Optical Society of America
1. Introduction
We consider an optical hybrid switch (OHS) [1, 2, 3] which supports both optical circuit switching (OCS) and optical burst switching (OBS) [4, 5, 6, 7, 8, 9, 10]. We use here the concept OCS to include all cases where connection between Edge routers or switches is set up end-to-end and capacity is exclusively available for the duration of the connections. These may include situations where capacity is permanently or semi-permanently available. These are the so-called Static OCS. By OCS, we also include cases where connections are set up and taken down frequently (Dynamic OCS). We also include in OCS the so-called OBS with acknowledgement [11], or the similar proposal called Wavelength Routed OBS [12]. By OBS we include all methods of optically transmitting and routing bursts of data using one way reservation, but without the ability to buffer the bursts optically. In other words, packet data are aggregated in Edge routers in large buffers from where they are transmitted optically to other edge routers through the core network without being buffered on their way in the core network. In an OBS optical cross connect (OXC) inside the core optical network, we may have the situation that too many bursts arrive from many input wavelengths that wish to be forwarded to the same output link, but there are not enough suitable output wavelengths to accommodate them. In such a case, a burst is dumped and lost.
The motivation of OHS relies primarily on the widely publicized motivation of OBS [7, 9]. OHS may provide a solution that combines the benefits of OBS and OCS and may provide evolutionary path beyond OCS. For example, setting up origin destination (OD) pair for OCS may be inefficient, so OBS can complement OCS to efficiently connect all OD pairs. For certain bursty traffic streams the OBS part of the hybrid switch may be efficiently used while for the more deterministic part, the OCS functionality will be more suitable.
In this paper, we consider an OHS implementation where advantage is given to circuits over bursts by allowing circuits to wait. More specifically, if all wavelengths are busy in the optical fibres of a desired output link, we allow an incoming circuit in some cases the option to queue for service and wait a short period of time before a wavelength is free. Because circuits can be queued, they enjoy priority over bursts in two ways: 1) in a case of contention between a circuit and a burst that arrives earlier, the circuit will not be blocked, instead it will wait a short while until the burst is served and then access the desired output link, 2) as long as there are circuits queued, all arriving bursts are blocked. In fact, we consider here an optical circuit switch where quality of service is better provided for the circuits and the bursts may use the scraps for better utilization. Clearly, implementation of such a circuit queueing feature introduces some additional cost associated with the increase in signalling complexity. Nevertheless, it may be justified by not blocking circuit requests that may access after a short delay. An alternative model without allowing circuits to wait is considered in [3, 13]. In order to evaluate the performance for an OHS, we will first present an analysis based on a 3-dimension state-space Markov chain that provides exact results for the blocking probabilities of bursts and circuits and also results for the proportion of circuits that are delayed and the mean delay of the circuits that are delay. However, the analysis is not scalable for the system with hundreds of wavelengths. On the other hand, for such a system, computer simulation is also not scalable as it takes a very long time to visit the large number of states, associated with a 3-dimensional state-space Markov chain, a sufficient number of times to obtain accurate results. The time required is especially longer if we are interested in the probability of a rare event such as blocking. It is worth noting that there have been numerous studies published on electronic hybrid switching over the last 30 years (See [14, 15] and references therein). However, the “curse of dimensionality” always has been considered a problem, and no accurate approximations of the type proposed in their paper have been provided.
Our contributions in this paper are scalable and accurate approximations for the blocking probability of circuits and bursts, proportion of circuits that are delayed and the mean delay of the circuits that are delayed. The scalability is achieved by reducing the 3-dimension state space Markov chain to a single dimension. A special case of the present model was analyzed in [3] where circuits are not allowed to wait. These scalable approximations that can produce performance results in a fraction of a second can readily enable switch dimensioning. Therefore, for a given traffic loading we can compute the performance measures and increase the switch capacity until the required quality of service is obtained.
2. Node Model
Consider an output link of an OHS. Such an output link has F optical fibers and each optical fiber can carry W wavelengths. If full wavelength conversion is available, this output link has C = FW wavelength channels, otherwise, an arriving burst/circuit that uses a given wavelength, must use the same wavelength at the output, thus, only F wavelength channels are available to it. Consider traffic flows coming from M input wavelengths from a number of input links directed to an output link comprising K wavelengths, which can take the values of C or F for the cases of with or without wavelength conversion, respectively. As in [3], we assume full wavelength conversion capabilities in the switching fabric and that the switching fabric is strictly non-blocking. There is no loss when M ≤ K. Blocking probability computations only apply in the case of (0 < K < M), where loss may occur. In comparison, the assumption of Poisson arrivals used in previous studies of OBS performance [16, 17, 18] will incorrectly predict some loss of traffic even in situations where K ≥ M.
We assume that the effect of offset time for OBS [23] is negligible. Since the introduction of OBS in 1997 [23], different versions of OBS have been proposed. For example, in [19] the offset time for OBS can be zero by introducing the fiber delay line (FDL) to allow the buffering of the burst while the header is processed. (Note that using the FDL for processing a header is not as much of a burden as for buffering and queueing bursts to avoid collision.) In [20] the offset time for OBS is constant so it does not affect the blocking probability results and the delay results only differ by a constant from their evaluated values. In these cases, neglecting the offset time is apparently acceptable. Under OBS-JIT [21], the arriving header immediately reserves a wavelength. This means that the system behaves as if the burst length increases by its offset, so clearly, longer offsets increases the blocking probability. Our analysis can apply to OBS-JIT if we consider the “burst” to be equal to sum of the burst length and its offset. Under OBS-JET, again, if the offset is constant, it can be neglected [22]. Otherwise, offsets may have non-negligible effect on blocking probability. Clearly, longer offsets mean more advanced reservation and therefore give higher priority to their bursts at cost of higher delays. This can be used to induce priorities in a multiclass OBS system [17, 23, 24 , 25]. Analyses of OBS-JET with offsets that approximate the blocking probability of bursts with the longest offset are available in [22, 26].
We assume that a burst is transmitted on a wavelength for an exponentially distributed period of time with mean 1/μb, while a circuit is allocated for an exponentially distributed period of time with mean 1/μc. We consider the following on-off process associated with each input wavelength. It is an alternating process where an off period follows an on period and an on period follows an off period. A period of time used to transmit a single burst or allocated for a circuit on an input wavelength is called an on period, and the time between consecutive on periods on that input wavelength is called an off period. The off period on an input wavelength is assumed to be exponentially distributed with mean 1/λ. This assumption of exponential times is not as limiting as it may seem. It is well known that Engset formula [27] is insensitive to on and off distribution [28]. The model we consider here has exponential times, but it has been shown that the burst blocking probability is not too sensitive to the distribution of the on and off periods [3,8,13,29], where there are no circuit queued reservations. Although the sensitivity of the blocking probability to the on and the off distribution is likely to increase with the maximal number of queued circuits (denoted as N), it should not increase too much since N is designed to be small.
Upon termination of an off period, circuit transmission on period will commence with probability pc, and a burst transmission on period will commence with probability pb = 1 - Pc. Define λc = λpc and λb = λpc. In addition, we assume that if all K output wavelengths are busy, c(n) (0 ≤ c(n) ≤ 1,n = 1,2, …,N,N ≤ M- K) proportion of the circuit arrivals are willing to wait until no more than n items (circuits and/or bursts) complete their transmission. Thus, their arrival rate is c(n)λc.
3. Exact solution
Let π i,j,k (i,j,k ≥ 0,i ≤ K,k ≤M - K,j ≤ K + N) be the probability that i input wavelengths are used for bursts transmission, j are for transmitting and for waiting circuits and k are for dumping blocked bursts. The number of idle input wavelengths is given by M - i - j - k. The π i,j,k probabilities satisfy the following steady state equations. For i + j < K,
and for i + j = K,
and for i + j > K,
where
and
Introducing the normalization equation
gives rise to a set of equations, which can be used to obtain the π i,j,k probabilities.
The total load offered by circuits is given by
The total load carried by circuits is given by
Thus, the circuit blocking probability Bc is given by
The total load offered by bursts is
and the total load carried by bursts is
Thus, the burst blocking probability Bb is given by
The carried load of circuits in the queue is
where
The proportion of circuits that are delayed, denoted as Dp, is
The average number of circuits in the queue conditioning on all K output wavelengths being used, namely, the system is busy, is given by
where
The average rate for circuits departing the busy system is evaluated by
where ∑i+j=K,k π i,j,kis the probability that the system is busy. By Little’s formula, the mean queueing delay for a delayed circuit, denoted as Dc, is given by
Solving Eqs. (1), (2) and (3) is not scalable for large K and M. Scalable approximations are derived next.
4. Approximations
In the approximations we present here, the three-dimensional system of the previous section is reduced to a single dimension. In particular, using a fixed point approximation approach, we analyze a single dimension combined circuit/burst system and consider only one type of ”customers” representing both circuits and bursts, excluding the dumped bursts.
As in [3], we argue that from the point of view of the switch, when a burst arrival is blocked and dumped, the input wavelength behaves as if it were inactive until the end of the burst has arrived at the switch. This can be considered equivalent to a situation whereby the blocked input wavelength having a longer off period with mean equal to 1/μb + 1/λ. This happens with probability pbBb where Bb is the burst blocking probability calculated later on. Let 1/λ * be the modified mean off period; it is given by
Let pi be the probability that there are i bursts/circuits in progress/waiting. The modified mean on period, denoted 1/μ*, is estimated by the following weighted average:
where Cb is given by
and
where
Note that when the ratio of μb and μc is large (say 100), the estimate value of circuit blocking probability, denoted as Bc, decreases drastically and becomes quite inaccurate when compared with the exact solution. Realizing that the circuit blocking probability Bc cannot be lower than the circuit blocking probability in the case where the circuits are given preemptive priority over bursts, denoted as Bpc, we remedy this inaccuracy, by checking whether Bc, given by
where
is lower than Bpc (derived in Appendix). If it is found that Bc < Bpc, we will bound the Bc value to Bpc by setting Cc in Eq. (5) to OcCpc/Opc where Cpc and Opc are given in the Appendix. Notice also that when circuit holding times are much longer than burst transmission times, namely, μb/μc is very large, given the fact that the circuits may queue, the system behaves very close to a system where the circuits do have preemptive priority over bursts. This means that in some cases when we need to use the preemptive priority bound, it is in fact a very tight bound.
This gives rise to a single dimension birth-death process described by the following steady state equations. For 1 ≤ i ≤ K,
and for K+1 ≤ i ≤ K+N,
where
and the normalization equation
by which the pi values can be obtained.
The functional relation between λ *, μ * and pi expressed in Eqs. (4), (5), (6) and (7) gives rise to a set of fixed-point equations. The fixed-point is computed by repeated substitutions.
Recall that the blocking probability for circuits is given by
Then, we will calculate the blocking probability for bursts. The total load offered by bursts is given by
Thus, the blocking probability for bursts is given by
The carried load of circuits in the queue is
where
The proportion of circuits that are delayed, denoted as Dp, is
The average number of circuits in the queue for a busy system is given by
where
The average rate for circuits departing given that the system is busy is obtained by Rc = Kμ *. The mean queueing delay for a delayed circuit, denoted as Dc, is given by
5. Pure OBS
In this section, we provide approximations for a special case where there are only burst traffic and no circuit traffic. The exact (non-scalable) model for this special case can be found in [8, 29, 30]. However, since such exact results are not scalable it is important to have a scalable approximations for the burst blocking probability in a pure OBS switch. Such approximation is readily obtained as a special case of the OHS approximation developed in this paper, but because of its importance we treat it separately.
Since there are no circuit traffic, λ is equal to λb, μ * in Eq. (5) is equal to μb and λ * in Eq. (4) is given by
This gives rise to another single dimension birth-death process described by the following steady state equation. For 1 ≤ i ≤ K,
and the normalization equation
by which the pi values can be obtained. Thus, the blocking probability for bursts is given by
where
and
6. Numerical Evaluation
Here we quantify, via exact solution obtained by Eqs. (1), (2) and (3), the accuracy of our approximations. Results are presented here for the blocking probability and delay versus what we call the normalized combined traffic intensity, which is defined by
Fig. 2. Mean queueing delay for a delayed circuit [sec.] (left) and probability of a circuit being delayed (right) versus normalized combined traffic intensity.
We set for all the examples in this section the following values: 1/μb = 1sec. and 1/μc = 100sec. Also, denote the Burst Proportion (BP) as
In all our examples, we consider the c(n) values evenly distributed, that is c(n) = 1/N, ∀n.
In all scenarios studied regardless of the values of M, N, K, the traffic intensity, the ratio of μb and μc, and the ratio of burst-to-circuit traffic intensity per input wavelength, our numerical results show that the approximations in general agree with the exact solutions as demonstrated, for example, in Figs. 1 and 2. The agreement demonstrated in Figs. 1 and 2 have also been observed in many other cases we considered; however, for brevity, we do not present them here. Instead, we present in Figs. 3 – 6 the worst results we obtain in terms of accuracy. Even for these cases, we observe that the approximations still generate acceptable solutions, especially for burst and circuit blocking probabilities.
Fig. 7 shows the blocking probability versus the normalized traffic intensity for burst traffic only. The approximation tightly matches the exact solution as demonstrated in Fig. 7.
The number of states of the underlying Markov process is in the order of MK(M - K). In Figures 8, and 9, we consider a realistic case with M = 200, K = 100. For such a case, where we have millions of states, neither exact solution is possible, nor simulation results can give accurate results. However, our approximations can produce accurate results in less than a second. Figures 8 and 9 demonstrate how we can use N to trade off between the burst blocking Bb, and circuit blocking Bc. As demonstrated in Figures 8 and 9, that with slight increase of N from 0 to 5, the circuit blocking reduces dramatically while the burst blocking increases slightly with small additional queuing delay for the circuits. This is in line with our intention in this paper to provide advantage to circuits over bursts by allowing circuits to wait for available wavelengths.
Fig. 4. Mean queueing delay for a delayed circuit [sec.] (left) and probability of a circuit being delayed (right) versus normalized combined traffic intensity.
Fig. 6. Mean queueing delay for a delayed circuit [sec.] (left) and probability of a circuit being delayed (right) versus normalized combined traffic intensity.
Fig. 9. Mean queueing delay for a delayed circuit [sec.] (left) and probability of a circuit being delayed (right) versus normalized combined traffic intensity.
7. Conclusion
In this paper, we have considered an optical hybrid switch implementation where advantage is given to circuits over bursts by allowing circuits to wait. We have derived computationally scalable and accurate approximations for the blocking probabilities of bursts and circuits, the proportion of circuits that are delayed and the mean delay of the circuits that are delay. These scalable approximations that can produce performance results in a fraction of a second can readily enable switch dimensioning with the scale of hundreds of wavelengths where neither exact solution is possible, nor simulation results can give accurate results. Numerical results show that by allowing the circuits to await small amount of time the circuit blocking reduces dramatically while the burst blocking increases slightly. This is in line with our intention in this paper to provide advantage to circuits over bursts by allowing circuits to wait for available wavelengths.
Appendix: A model with preemptive priority to circuits
Here, we provide an approximation for the distribution of the number of circuits in the system, denoted as p′j, = 0 …, N, for the system which provides circuits with preemptive priority over bursts. This is obtainable by a standard analysis of a state–dependent multi-server finite–source finite–buffer queueing system.
To obtain the distribution of the number of circuits in the system, we do not need to distinguish an active input wavelength belonging to a burst in progress from a blocked input wavelength in which a burst is being dumped. In both such cases the input wavelength appears busy and is assigned to a single state labeled the active state. The approximation makes use of the fact that an input wavelength is either active or inactive from the viewpoint of a circuit.
The effect of burst arrivals can be taken into account by modifying (increasing) the mean off period between two successive circuits [3]. Let the modified mean off period between two circuits be 1/λ′ given by
or,
The term 1/λ + 1/μb + 1/λ′ in Eq. (10) is the mean off period given that the next arrival is a burst, which occurs with probability λb/λ, while the term 1/λ is the mean off period given that the next arrival is a circuit, which occurs with probability λc/λ. This gives rise to the following steady state equations. For 1 ≤ j ≤ K,
and for K+1 ≤ j ≤ K+N,
Together with the normalization equation
the p′j values can be obtained.
The total load offered by circuits is given by
and the total load carried by circuits is
Thus, the blocking probability for circuits is given by
Acknowledgments
This work was supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. 9041037] and by the Australian Research Council.
References and links
1 . C. Xin , C. Qiao , Y. Ye , and S. Dixit , “ A hybrid optical switching approach ,” in Proceedings of IEEE GLOBECOM 2003, 7 , 3808 – 3812 , Dec. ( 2003 ).
2 . G. M. Lee , B. Wydrowski , M. Zukerman , J. K. Choi , and C. H. Foh , “ Performance Evaluation of an Optical Hybrid Switching System ,” in Proceedings of IEEE GLOBECOM 2003 5 , 2508 – 2512 , Dec. ( 2003 ).
3 . H. L. Vu , A. Zalesky , E. W. M. Wong , Z. Rosberg , S. M. H. Bilgrami , M. Zukerman , and R. S. Tucker , “ Scalable Performance Evaluation of a Hybrid Optical Switch ,” J. Lightwave Technol. 23 , 2961 – 2973 , Oct. ( 2005 ). [CrossRef]
4 . M. Yoo and C. Qiao , “ Just-enough-time (JET): A high speed protocol for bursty traffic in optical networks ,” in Proceeding of IEEE/LEOS Conf. on Technologies For a Global Information Infrastructure, 26–27, Aug. ( 1997 ).
5 . C. Qiao and M. Yoo , “ Optical Burst Switching (OBS): A New Paradigm for an Optical Internet ,” J. High Speed Nets. 8 , 69 – 84 , Jan. ( 1999 ).
6 . J. Turner , “ Terabit Burst Switching ,” J. High Speed Nets. 8 , 3 – 16 , Mar. ( 1999 ).
7 . S. Verma , H. Chaskar , and R. Ravikanth “ Optical Burst Switching: A Viable Solution for Terabit IP Backbone ,” IEEE Network, 48 – 53 , Nov./Dec. ( 2000 ).
8 . A. Detti , V. Eramo , and M. Listanti , “ Performance evaluation of a new technique for IP support in a WDM optical network: optical composite burst switching (OCBS) ,” J. Lightwave Technol. 20 , 154 – 165 , Feb. ( 2002 ). [CrossRef]
9 . T. Battestilli and H. Perros , “ An Introduction to Optical Burst Switching ,” IEEE Communs. Mag. 41 , S10 – S15 , Aug. ( 2003 ). [CrossRef]
10 . Y. Chen , C. Qiao , and X. Yu , “ Optical Burst Switching (OBS): A New Area in Optical Networking Research ,” IEEE Network Magazine 18 , 16 – 23 , May/June ( 2004 ). [CrossRef]
11 . A. Zalesky , E. W. M. Wong , M. Zukerman , H. L. Vu , and R. S. Tucker , “ Performance Analysis of an OBS Edge Router ,” IEEE Photonic Technol. Lett. 16 , 695 – 697 , Feb. ( 2004 ). [CrossRef]
12 . M. Duser and P. Bayvel , “ Analysis of a Dynamically Wavelength Routed Optical Burst Switched Network Architecture ,” J. Lightwave Technol. 20 , 574 – 585 , Apr. ( 2002 ). [CrossRef]
13 . A. Zalesky , E. W. M. Wong , H. L. Vu , M. Zukerman , Z. Rosberg , and M.S. Bilgrami , “ Performance evaluation of a hybrid optical switch ,” in Proc. ITC19, Aug./Sep. ( 2005 ).
14 . A. Leon-Garcia , R. H. Kwong , and G. F. Williams , “ Performance Evaluation Methods for an Integrated Voice/Data Link ,” IEEE Trans. on Communs. 30 , 1848 – 1858 , August ( 1982 ). [CrossRef]
15 . M. Zukerman , “ Circuit allocation and overload control in a hybrid switching system ,” Computer Networks and ISDN Systems 16 , 281 – 298 , ( 1989 ). [CrossRef]
16 . Z. Rosberg , H. L. Vu , M. Zukerman , and J. White , “ Performance analyses of optical burst-switching networks ,” J. Sel. Areas Commun. 21 , 1187 – 1197 , Sept. ( 2003 ). [CrossRef]
17 . H. L. Vu and M. Zukerman , “ Blocking Probability for Priority Classes in Optical Burst Switching Networks ,” IEEE Communications Letters 6 , 214 – 216 , May ( 2002 ). [CrossRef]
18 . J. White , M. Zukerman , and H. L. Vu , “ A framework for optical burst switching network design ,” IEEE Communications Letters 6 , 268 – 270 , Jun ( 2002 ). [CrossRef]
19 . M. C. Yuang , P. L. Tien , and J. Shih , “ QoS Scheduler/Shaper for Optical Coarse Packet Switching IP-over-WDM Networks ,” J. Sel. Areas Commun. 22 , Nov. ( 2004 ). [CrossRef]
20 . N. Barakat and E. H. Sargent , “ Dual-header optical burst switching: a new architecture for WDM burst-switched networks ,” in Proc. IEEE INFOCOM’05, March ( 2005 ).
21 . I. Baldine , G. N. Rouskas , H. G. Perros , and D. Stevenson , “ JumpStart: A just-in-time signaling architecture for WDM burst-switched networks ,” IEEE Communications Magazine , 82 – 89 , February ( 2002 ). [CrossRef]
22 . N. Barakat and E. H. Sargent , “ Analytical modeling of offset-induced priority in multiclass OBS networks ,” IEEE Transactions on Communications 53 , 1343 – 1352 , Aug. ( 2005 ). [CrossRef]
23 . M. Yoo , C. Qiao , and S. Dixit , “ Optical burst switching for service differentiation in the next-generation optical internet ,” IEEE Commun. Mag. 39 , 98 – 104 , Feb. ( 2001 ). [CrossRef]
24 . M. Yoo and C. Qiao , “ Supporting multiple classes of services in IP over WDM networks ,” in Proc. Globecom 1999, 1023 – 1027 , Dec. ( 1999 ).
25 . K. Dolzer , C. Gauger , J. Späth , and S. Bodamer , “ Evaluation of reservation mechanisms for optical burst switching ,” AE Ü Int. J. Electron. Commun. 55 , 18 – 26 , Jan. ( 2001 ). [CrossRef]
26 . P. Taylor and R. Maillardet , “ Queues with reservations ,” Presented at the Australian and New Zealand Industrial and Applied Mathematics (ANZIAM) 2005 meeting, Napier, New Zealand, Jan./Feb. ( 2005 ).
27 . T. Engset , “ Die wahrscheinlichkeitsrechnung zur bestimmung der wahleranzahl in automatischen fern-sprechamtern ” Elektrotechnische zeitschrift 39 , 304 – 306 , Aug. ( 1918 ).
28 . J. Hui ,Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Press ( 1990 ).
29 . M. Zukerman , E. W. M. Wong , Z. Rosberg , G. M. Lee , and H. L. Vu , “ On Teletraffic Application to OBS ,” IEEE Commun. Letters 8 , 116 – 118 , Feb. ( 2004 ). [CrossRef]
30 . H. Overby “ Performance modelling of optical packet switched networks with the Engset traffic model ,” Opt. Express 13 , 1685 – 1695 ( 2005 ), http://www.opticsexpress.org/abstract.cfm?URI=OPEX-13-5-1685 [CrossRef] [PubMed]
