Performance evaluation of optical packet switches equipped with heterogeneous wavelength converters

Vincenzo Eramo; Marco Listanti; Angelo Germoni

doi:10.1364/OE.17.002166

1. Introduction

Optical Packet Switching (OPS) is a strong candidate to be the future switching scheme for the backbone network. High speed, data rate/format transparency and re-configurability are only some of the advantages of this switching scheme. Unfortunately the introduction of Optical Packet Switching systems is still subordinated to various technological issues [1]. One of the most critical aspects in design of Optical Packet Switches is contention resolution. The lack of optical random access memories does not allow the migration of the traditional store and forward techniques used in electronic routers. Classic techniques exploit different dimensions to solve contention as Space, Time and Wavelength. Wavelength conversion has been studied for many years [1], [2]. To optimize the use of Wavelength Converters (WC), different sharing techniques have been introduced. Optical Packet Switches equipped with Limited Range Wavelength Converters (LRWCs) have also been proposed but this solution has revealed itself as being cost effective because the performance of an Optical Packet Switch (OPS) equipped with Full Range Wavelength Converters (FRWC) is reached only when the conversion range is high.

Optical Packet Switches with Two-Layer Wavelength Conversion (TLWC) have been proposed [3, 4, 5] in asynchronous and synchronous cases. To optimize the conversion cost they use both LRWCs and FRWCs. The first layer is equipped with one LRWC for each input wavelength, the second layer is equipped with shared FRWCs. When the number of FRWCs and the LRWCs’ conversion range are optimally dimensioned, the TLWC OPS allows for a larger saving in conversion cost than an OPS sharing FRWCs only.

In this paper we propose a new Optical Packet Switch architecture equipped with LRWCs and FRWCs. Differently from the switches introduced in [3, 4, 5] in which as many LRWCs as the number of input wavelength channels are used, the switch proposed in this paper shares the LRWCs and allows for a reduction in conversion cost. Because the switch shares both LRWCs and FRWCs, it will be referred to as FLSPN (FRWCs and LRWCs shared-per-node).

To optimally dimension the switch resources (number of FRWCs and LRWCs, LRWCs’ conversion range,…), we propose an analytical model to evaluate the Packet Loss Probability of the switch. By means of the proposed model, we will be able to evaluate the reduction in conversion cost of the FLSPN switch when compared to the switch proposed in [3].

The paper is organized as follows. The FLSPN OPS and the scheduling algorithm are described in Section 2 and Section 3 respectively. Section 4 is devoted to illustrate the analytical model introduced to dimension the switch resources. The main results are described in Section 5. Conclusions and further research items are discussed in Section 6.

2. FLSPN OPS architectures sharing both LRWCs and FRWCs

We consider a WDM optical switch with N input/output fibers (IF/OF) as shown in Fig. 1. Each Output Fiber (OF) supports M wavelengths channels. Let λ_i (i = 0,…,M - 1) be the wavelengths carried on each OF. The switch operation mode is synchronous [6, 7] and packet contention resolution is performed in the wavelength domain using shared Wavelength Converters (WCs). If a packet does not need wavelength conversion it will be directly sent to the output, otherwise it will be addressed to the WCs pool illustrated in Fig. 1 and containing r_l LRWCs and r_f FRWCs. A packet may need a near or far wavelength conversion. A conversion is said to be near if it can be performed with an LRWC. Conversely if an FRWC is needed, the conversion is said to be far. In order to save the expensive FRWCs, the scheduling algorithm of the FLSPN switch uses LRWCs and FRWCs to perform near and far wavelength conversions respectively.

We consider non circular LRWCs with conversion range d [3]. Because an FRWC is able to convert a packet from any input wavelength to any output wavelength, it can be considered as the particular case of an LRWC with conversion range d = M-1.

Fig. 1. FLSPN OPS equipped with r_l LRWC and r_f FRWCs.

Download Full Size | PDF

The objective of our study is to determine the WCs parameters (LRWCs’ conversion range, number of FRWCs and LRWCs), so that the switch conversion cost can be minimized. To evaluate the conversion cost we assume the same cost model introduced in [3]. According to the model, the costs of an LRWC and an FRWC are expressed respectively by:

C_{LRWC} = a d^{b}, C_{FRWC} = a {(M - 1)}^{b}

where b determines how quickly the LRWC’s and FRWC’s cost increases versus the conversion range d. The parameter a is introduced to normalize the sum of the costs of the available WCs with conversion ranges d = 1,2,…,M-1. If the normalized cost is C_norm, the expression for a is simply given by:

a = \frac{C_{norm}}{\sum_{d = 1}^{M - 1} d^{b}} .

Finally we report the expression of the conversion cost of an FLSPN switch:

C^{FLSPN} = r_{l} C_{LRWC} + r_{f} C_{FRWC} .

3. Scheduling algorithms for FLSPN architecture

The Scheduling Algorithm (SA) for the FLSPN architecture is reported in Fig. 2. The SA is composed by various phases. The Initialization (INI), Limited Range Contention Resolution (LRCR) and Wavelength Converters Assignment (WCA) phases are executed in parallel by each Output Fiber Arbiter reported in Fig. 1. The Wavelength Converter Management (WCM) phase is executed by the WC arbiter in Fig. 1 to assign the number of LRWCs and FRWCs to the various OFs.

Fig. 2. Scheduling algorithm for FLSPN architecture

Download Full Size | PDF

The INI phase is performed at the beginning of each time slot to update all the variables and sets used in the other phases.

In LRCR phase, the number of packets forwarded by using near conversions is maximized. As shown in [3, 8, 9] this is performed by solving a maximum matching problem in a convex bipartite graph. The convexity property allows for a simple solution of the maximum matching problem at a O(M) computational complexity. In the end of the LRCR phase, the following sets and variables are evaluated for each OF i:

∏_i: the set containing the ordered pair (a, o_i,j) where a is a packet directed to the OF i that must be converted and o_i,j is the Output Wavelength Channel (OWC) of the OF i on wavelength λ_j assigned to packet a in the phase in which near conversions are scheduled;
Λ_i: the set containing the OWCs in OF i that have not been used yet in the end of the LRCR phase;
I_i,k (k = 0,⋯,M - 1): the set containing the packets arriving on wavelengths λ_k and directed to OF i that have not been scheduled yet in the end of the LRCR phase;
c_l,i: the number of packets needing a near wavelength conversion for OF i;
c_f,i: the number of packets needing a far wavelength conversion for OF i;

In WCM phase, the WCs arbiter shown in Fig. 1 determines the number of LRWCs and FRWCs to assign to each OF. The OFs are randomly scanned and the WCs Arbiter will try to assign a number c_l,i of LRWCs and a number c_f,i of FRWCs to each fiber OF i. Because of the sharing of WCs, fewer LRWCs and FRWCs than c_l,i and c_f,i respectively can be assigned to each OF i. The assigned number of LRWCs and FRWCs is denoted with r_l,i and r_f,i respectively. The time complexity of the WCM phase is equal to O(N) because in the worst case, the control unit has to scan all of the N fibers to determine the right number of LRWCs and FRWCs to assign to each OF.

In WCA phase, the shared converters are assigned to the packets needing conversion. This phase can be divided in two sub-phases referred to as LRWCs Assignment (LRA) and FRWCs Assignment (FRA) respectively. In the two sub-phases, the LRWCs and FRWCs are assigned to the packets needing near and far wavelength conversions respectively. The actions performed in the two sub-phases are reported in Figs 3 and 4 respectively. In LRA sub-phase, shown in Fig. 3, when both the set ∏_i is not empty and WCs are available, an element (a, o_i,j) ∈ ∏_i is randomly extracted and the packet a is scheduled for OWC o_i,j. Because a needs a near conversion, the SA tries to perform the conversion by using an LRWC. When all of the LRWCs have been occupied, FRWCs are used.

Fig. 3. LRWCs Assignment (LRA) sub-phase

Download Full Size | PDF

Fig. 4. FRWCs Assignment (FRA) sub-phase

Download Full Size | PDF

If all of the LRWCs and FRWCs have been used, the remaining packets in set ∏_i are discarded. In FRA sub-phase, shown in Fig. 4, far wavelength conversions are performed by using FRWCs. Until when there are FRWCs, packets stored in set I_i are wavelength converted. The set I_i contains the packets that have lost the contention in LRCR phase. The time complexity of the WCA phase is O(M) because a maximum number of operations proportional to the number of input/output wavelengths per fiber is performed in the LRA and FRA phases.

Finally according to the computational complexity of each phase, we can conclude that the SA for FLSPN switch has O(N+M) complexity.

4. Analytical model

In this section we present the analytical model to dimension the Wavelength Converters of the FLSPN switch. We evaluate the Packet Loss Probability versus the number r_l and r_f of LRWCs and FRWCs employed, under the following assumptions: i) the operation mode of the switching node is synchronous [1] on a time-slot basis; ii) packet arrivals on the NM input wavelength channels at each time-slot are not dependent on each other; iii) packet arrivals occur with probability p on each input wavelength channel; iv) the destination of a packet is uniformly distributed over all N OFs, i.e., the probability that an arriving packet is directed to a given OF is equal to 1/N. No assumption is made for the mutual dependence of packet arrivals at different time-slots, since, due to the bufferless nature of the switch, the performance and the WCs dimensioning procedure depend on p only [11].

The uniform and symmetric traffic scenario is assumed because it is the one requiring the highest number of WCs and thus the highest conversion cost. The explanation of this is illustrated in the following: i) the packet loss is either due to the lack of OWCs or to the lack of WCs and WCs dimensioning must be performed so that the second loss event is negligible with respect to the first one; ii) a higher number of WCs is needed when the packet loss due to the lack of OWCs decreases; iii) the uniform and symmetric traffic assumption involves the lowest packet loss due to the lack of OWCs and then according to the point ii), the highest number of WCs.

Due to the symmetric traffic assumption, the Packet Loss Probability P^FLSPN_loss of the FLSPN switch equals the one of a single OF. According to the actions performed in the WCM phase of the scheduling algorithm, the Packet Loss Probability for a given OF depends on the order in which the OF is selected, as fewer LRWCs and FRWCs will be available for the last selected OFs. For this reason the evaluation of P^FLSPN_loss is simpler if we condition to the number R^av_l and R^av_f of LRWCs and FRWCs still available when the OF is selected. Notice that R^av_l,R^av_f can assume values from 0 to r_l and r_f respectively. In particular we have that R^av_l = r_l and R^av_f = r_f if the OF is the first one to be selected or if the OFs previously selected by the SA have not required WCs. R^av_l=R^av_f=0 if all of the WCs have been used for the previously selected OFs. P^FLSPN_loss can therefore be expressed as follows:

P_{loss}^{FLSPN} (r_{l}, r_{f}) = \sum_{i = 0}^{N (M - 1)} \sum_{j = 0}^{N (M - 1)} p_{R_{l}^{av}, R_{f}^{av}} (i, j) P_{loss}^{FLSPN, OF} {(r_{l}^{av}, r_{f}^{av})}_{∣ \begin{matrix} r_{l}^{av} = i \\ r_{f}^{av} = j \end{matrix}}

where:

p_{R_l^av,R_f^av}(i, j) is the joint probabilities of R^av_l and R^av_l that are the random variables representing respectively the number of LRWCs and FRWCs still available for a given OF when it is selected. The evaluation of the joint probabilities p_{R_l^av,R_f^av}(i, j), reported in Appendixes A and B, can be carried out only when the statistical independence of the conversions needed for the various OFs is assumed.
P^FLSPN,OF_loss(r^av_l,r^av_f) is the Packet Loss Probability of the OF if r^av_l LRWCs and r^av_f FR-WCs are are still available when the OF is selected.

According to the symmetric traffic assumption, P^FLSPN,OF_loss(r^av_l,r^av_f) is given by:

P_{loss}^{FLSPN, OF} (r_{l}^{av}, r_{f}^{av}) = \frac{E [N_{l, WB}] + E [N_{l, CB}]}{E [N_{O}]}

where E[x] denotes the expected value of the random variable x. E[N_O] = M_P is the average number of packets offered to a particular OF in a time slot. E[N_l,WB] is the average number of packets lost due to the lack of OWCs and E[N_l,CB] is the average number of packets lost because of the lack of WCs.

The average number E[N_l,WB] of packets lost due to the lack of OWCs can be easily evaluated as:

E [N_{l, WB}] = \sum_{j = M + 1}^{NM} (j - M) (\begin{matrix} NM \\ j \end{matrix}) {(\frac{P}{N})}^{j} {(1 - \frac{P}{N})}^{NM - j}

On the other hand to evaluate E[N_l,CB] we may condition to the random variables D and W that represent respectively the number of near and far conversions required in the OF respectively. According to this conditioning and denoting as p_D,W(i, j) the joint probabilities of D and W, we can write:

E [N_{l, CB}] = \sum_{i = 0}^{M - 1} \sum_{j = 0}^{M - i} E [N_{l, CB} / d = i, w = j] p_{D, W} (i, j)

According to the scheduling algorithm presented in Section 3, the term E[N_l,CB/d] = i,w= j] can be expressed as:

E [N_{l, CB} / d = i, w = j] = {\begin{matrix} j - r_{f}^{av} i \leq r_{l}^{av}, j > r_{f}^{av} \\ i - (r_{l}^{av} + r_{f}^{av}) + j i > r_{l}^{av} + r_{f}^{av} \\ min (0, j - (r_{l}^{av} + r_{f}^{av} - i)) r_{l}^{av} < i \leq r_{l}^{av} + r_{f}^{av} \\ 0 otherwise \end{matrix}

In order to evaluate the joint probabilities p_D,W(i, j) we introduce the random variables α, β and γ denoting for a given OF, the number of packets to be still scheduled, the number of OWCs still available and the number of near conversions required respectively, in the end of the LRCR phase of the SA introduced in Section 3. Let us denote with p_α,β,γ(i,j,h)(i = 0,…,NM; j = 0,…,M;h = 0,…,M - 1) the joint probabilities of the random variables α,β and γ. The probabilities p_α,β,γ(i,j,h) are evaluated in Appendix A. For the joint probabilities p_D,W(i, j) we can write:

p_{D, W} (i, j) = \sum_{k = j}^{M} p_{α, β, γ} (j, k, i) + \sum_{h = j + 1}^{NM} p_{α, β, γ} (h, j, i)

Finally evaluating the joint probabilities p_α,β,γ(i,j,h) as described in Appendix A, inserting (8), (9) in (7), we are able to evaluate E[N_l,CB]. Then inserting (6),(7) in (5) and (5) in (4) we can evaluate the Packet Loss Probability P^FLSPN_loss(r_l,r_f) and to perform the WCs dimensioning.

5. Numerical results

In this section we verify the validity of the analytical model introduced in Section 4 and we evaluate the effectiveness of the WCs sharing in FLSPN switch. The conversion cost of the FLSPN switch is compared to the one of the Two-Layer Wavelength Conversion shared-per-node (TLWC-SPN) and One-Layer Wavelength Conversion shared-per-node(OLWC-SPN) switches proposed in [3] and [11] respectively. TLWC-SPN and FLSPN switches differ from the way in which the LRWCs are used: as many LRWCs as the number of input wavelength channels are employed in TLWC-SPN switch, conversely the LRWCs are shared in FLSPN switch. Only shared FRWCs are used in OLWC-SPN switch.

Fig. 5. Comparison between the analytical and simulation results for the Packet Loss Probability in the FLSPN switch as a function of the used number of FRWCs. Switch and traffic parameters are N = 8, M = 16, p = 0,4, d = 1. The used number r_l of LRWCs varies from 0 to 120.

Download Full Size | PDF

Figures 5 and 6 show the Packet Loss Probability of the FLSPN switch versus the number of employed LRWCs and FRWCs. Figure 5 shows the analytical and simulation results in the case of switch with N = 8 IF/OF, M = 16 wavelengths per fiber, LRWCs’ conversion range d = 1 and offered traffic to each input wavelength channel p = 0,4. The analytical and simulation results are shown in Figure 6 for N = 8 IF/OF, M = 32, d = 2 and p = 0,8. We note from the results reported in Figs 5 and 6 that in spite of the independence assumption, the results of the analytical model are in good agreement with simulations results. Other results, not shown in this paper, have confirmed the effectiveness of the analytical model in evaluating the Packet Loss Probability of the FLSPN switch. It can thus be considered validated and it will be used in the following to perform the WCs dimensioning and to determine the LRWCs’ conversion range.

The Packet Loss Probabilities shown in Figs 5 and 6 have the same trend: they decrease versus r_f up to the saturation value P^sat_loss that represents the Packet Loss Probability of a switch using one FRWC per each input wavelength channel and for which the packet loss is due to the lack of OWCs only. P^sat_loss also represents the lowest Packet Loss Probability that any switch can reach.

The introduced analytical model allows for a correct switch resource dimensioning. The aim is to optimally dimension the switch resources so that the best performance P^sat_loss is reached at the minimum conversion cost. To do this, we have to suitably dimension the parameters r_l, d and r_f.

The conversion cost, expressed by (2), is reported in Fig. 7 as a function of the LRWCs’ conversion range d for N = 8, p = 0,8 and M varying from 16 to 64.

Fig. 6. Comparison between the analytical and simulation results for the Packet Loss Probability in the FLSPN switch as a function of the used number of FRWCs. Switch and traffic parameters are N = 8, M = 32, p = 0,8, d = 2. The used number r_l of LRWCs varies from 0 to 240.

Download Full Size | PDF

We assume a linear cost model (b=1) and the parameter a for FLSPN switch is chosen so that the normalized cost C_norm in (2) equals 10 for M = 64. For each value of d, r_l and r_f are evaluated by means of the analytical model so that P^sat_loss is reached at the lowest conversion cost. We also report in Fig. 7, the conversion cost for TLWC-SPN switch. For this case only the parameter r_f has to be evaluated by means of the analytical model proposed in [3] so that the conversion cost, expressed by (2) with r_l = NM, is minimized.

The curves reported in Fig. 7 are U-shaped because when d is small, the conversion cost is dominated by the need for more FRWCs since the LRWCs’ conversion range is too small to have a significant impact. When the LRWCs’ conversion range increases, there is no need for as many FRWCs as before, but the increase in cost of the used LRWCs will cause the overall cost to rise again. From Fig. 7 we can see clearly that there is an optimum value d_opt of the conversion range that allows for a minimization of the switch conversion cost. For instance in the case of FLSPN switch, when M = 64, d_opt equals three.

The percentage reduction in conversion cost of the FLSPN and TLWC-SPN switches when compared to the OLWC-SPN switch is reported in Fig. 8 for the same switch and traffic parameters of Fig. 7. As expected FLSPN switch allows for a percentage reduction greater than TLWC-SPN switch and it can reach 80% in some cases.

The impact of the parameter b in the cost model of the WCs is studied in Figs. 9–10, where we report for FLSPN switch the conversion cost and the percentage reduction respectively as a function of the conversion range d for N = 8, M = 64 and p = 0,8. The parameter b varies from 0,5 to 2 and a is chosen so that C_norm = 10. It is easy to see how, when b is low, given that the LRWC’s and FRWC’s cost is similar, the LRWCs sharing in FLSPN architecture is effective and increases savings in terms of conversion cost when compared to the TLWC-SPN switch. As b increases, the conversion cost is mainly determined by the used FRWCs and thus the LRWCs sharing is less effective. For this reason the conversion cost and the percentage reduction in conversion cost for FLSPN switch are close to the ones for the TLWC-SPN switch.

Fig. 7. Conversion cost of the FLSPN and TLWC-SPN switches as a function of the conversion range d. The switch and traffic parameters are N = 8, p = 0,8 and M varying from 16 to 64. A linear cost model (b = 1) is assumed.

Download Full Size | PDF

Fig. 8. Conversion cost percentage reduction of the FLSPN and TLWC-SPN switches with respect to the OLWC-SPN switch as a function of the conversion range d. The switch and traffic parameters are N = 8, p = 0,8 and M varying from 16 to 64. A linear cost model (b = 1) is assumed.

Download Full Size | PDF

Fig. 9. Cconversion cost of FLSPN and TLWC-SPN switches as a function of the conversion range d. The switch and traffic parameters are N = 8, p = 0,8, M = 64 and b varying from 0,5 to 2.

Download Full Size | PDF

Fig. 10. Conversion cost percentage reductions of the FLSPN and TLWC-SPN switches with respect to the OLWC-SPN as a function of the conversion range d. The switch and traffic parameters are N = 8, p = 0,8, M = 64 and b varying from 0,5 to 2.

Download Full Size | PDF

6. Conclusions

A WDM optical packet switching architecture, denoted as FLSPN, was discussed. The switch is equipped with both FRWCs and LRWCs shared. An analytical model was proposed to evaluate the Packet Loss Probability of the FLSPN switch. It allowed us to optimally dimension both the used number of WCs and the LRWCs’ conversion range so that the best performance is reached at the lowest conversion cost. When LRWCs conversion range is low, the FLSPN switch allows for a conversion cost reduction when compared to the TLWC-SPN switch.

Appendix

A. Evaluation of the joint probabilities p_α,β,γ(i,j,h)(i = 0,1,…,NM; j = 0,…,M;h = 0,1,…,M - 1)

In the following we give a recursive method to calculate the probabilities p_α,β,γ(i,j,h)(i = 0,1,…,NM; j = 0,…,M;h = 0,1,…,M -1) analytically. Let us introduce the following random variables:

- R_k(k = 0,…,M - 1) denotes the number of packets arriving on wavelength λ_k and directed to a particular OF. R_k is a random variable whose probability mass function (p.m.f.) p_r(i)(i = 0,…,N) has binomial distribution with parameter (N, p/N); we can write:

p_{r} (i) = (\begin{matrix} N \\ i \end{matrix}) {(\frac{p}{N})}^{i} {(1 - \frac{p}{N})}^{N - i} i = 0,1, \dots, N;

- A ^(k)(h = 1,…,M) denotes the number of packets arriving on k wavelengths and directed to a particular OF. A ^(k) is a random variable whose probability mass function (p.m.f.) p _A^(h)(i)(i = 0,…,Nk) has binomial distribution with parameter (N, p/N); we can write:

p_{A^{(k)}} (i) = (\begin{matrix} Nk \\ i \end{matrix}) {(\frac{p}{N})}^{i} {(1 - \frac{p}{N})}^{N - i} i = 0,1, \dots, N;

- α _p,q,β _p,q and γ _p,q(1 ≤ p ≤ M and 1 ≤ q ≤ M) denote for a given OF, the number of packets arriving on wavelengths λ _M-p to λ _M-1 to be still scheduled, the number of OWCs still available and the number of near conversions from λ _M-q to λ _M-1 respectively, at the end of the LRCR phase of the SA under the conditions that: i) the output wavelengths λ _M-q to λ _M-1 of the OF considered are only assigned to packets arriving on wavelengths λ _M-p to λ _M-1; ii) the packets arriving on wavelengths λ _M-1 to λ _M-1 are only assigned to output wavelengths λ _M-q to λ _M-1. α _p,q, β _p,q and γ _p,q are random variables taking value from 0 to p(N-1), from 0 to q and from 0 to q-1 respectively. We use p_α,β,γ(p,q,i,j,h) to denote the joint p.m.f. of the random variables α _p,q, β _p,q and γ _p,q. Clearly, when p = q = M, α _M,M, β _M,M and γ _M,M are simply α, β, and γ respectively. Hence the joint p.m.f. of α _M,M, β _M,M and γ _M,M is p_α,β,γ(i,j,h).

According to the approach followed in [3], p_α,β,γ(p,q,i,j,h) have to be evaluated in three cases respectively: i) p = 1 and 1≤q≤d + 2; ii) 2≤p≤d+1 and 1≤q≤p + d+1 ; iii) p ≥ d + 2 and p - d≤q≤p + d+1. In the following we will show in subsections A. 1 and A.2, the evaluation of p_α,β,γ(p,q,i,j,h) in the cases i) and ii) respectively. The case iii) is not reported because it is an extension of the case ii). Finally in subsection A.3 the iterative algorithm for the evaluation of the joint p.m.f. p_α,β,γ(p,q,i,j,h) will be given.

A.1. Evaluation of the joint p.m.f. of α_p,q,β_p,q and γ_p,q for p = 1 and 1 ≤ q ≤ d+2

First we evaluate p_α,β,γ(p,q,i,j,h) for p = 1 and 1 ≤ q ≤ d+1. This means that output wavelengths λ _M-q to λ _M-1 are only assigned to packets arriving on wavelength λ _M-1 and packets arriving on wavelength λ _M-1 are only assigned to output wavelengths λ _M-q to λ _M-1. We have the following expression:

p_{α, β, γ} (1, q, i, j, h) = {\begin{matrix} p_{r} (q + i) i \leq N - q, j = 0, h = q - 1 \\ p_{r} (q - j) i = 0, 1 \leq j \leq q, h = q - j \\ 0 otherwise \end{matrix}

In fact when q + i packets arrive on wavelength λ _M-1, according to the LRCR phase of the SA, they are transferred on output wavelengths λ _M-q to λ _M-1; in this case no output wavelengths will be available, q-1 near conversions are needed and i packets will be not yet scheduled at the end of the LCA phase. When q - j packets arrive on wavelength λ _M-1, they are transferred on output wavelengths from λ _M-q to λ _M-j+1, the j output wavelengths from λ _M-j+2 to λ _M-1 will be yet available and q - j near conversions are needed at the end of the LRCR phase. Further all of the arriving packets will be scheduled.

In order to evaluate the joint p.m.f. of the random variables α _p,q, β _p,q and γ _p,q for p = 1 and q = d+2, we notice that, due to the limited range of the LRWCs, the arriving packets on wavelength λ _M-1 may be forwarded on output wavelengths from λ _M-d-1 to λ _M-1 and wavelength λ _M-d-1 always remains available at the end of the LCA phase. Hence we can write for p = 1 and q = d+2:

p_{α, β, γ} (1, d + 2, i, j, h) = {\begin{matrix} p_{α, β, γ} (1, d + 1, i, j - 1, h) j \neq 0 \\ 0 j = 0 \end{matrix}

A.2. Evaluation of the joint p.m.f. of α_p,q, β_p,q and γ_p,q for 2 ≤ p≤d+1 and 1 ≤q≤p+d+1

First we evaluate p_α,β,γ(p,q,i,j,h) for 2 ≤ p ≤ d+1 and 1 ≤ q ≤ p + d. By conditioning on r _M-p which is the number of packets arriving on wavelength λ _M-p, p_α,β,γ(p,q,i,j,h) can be written as:

p_{α, β, γ} (p, q, i, j, h) = \sum_{k = 0}^{N} Prob (α_{p, q} = i, β_{p, q} = j, γ_{p, q} = h / r_{M - p} = k) Prob (r_{M - p} = k)

Notice that Prob(r _M-p = h) is simply p_r(k), the probability that there are k packets on wavelength λ _M-p. The term Prob(α _p,q = i, β _p,q = j, γ _p,q = h/r _M-p = k) is evaluated according to the following remarks.

Remark 1 - In the cases 1≤q≤p-1,k≤q-1 and p≤q≤p - d,k≤q-p - 1, the k arriving packets on wavelength λ _M-p, they are transferred on wavelengths λ _M-q to λ _M-q+k-1. Consequently Prob(α _p,q = i, β _p,q = j, γ _p,q = h/r _M-p = k) equals p_α,β,γ(p-1,q-k,i,j,min(0,h-k)), that is the probability that i packets are to be still scheduled, j OWCs are still available and min(0, h - k) near conversions are needed at the end of the LRCR phase respectively under the condition that output wavelengths λ _M-q+k to λ _M-1 are only assigned to packets arriving on wavelengths λ _M-p+1 to λ _M-1, and packets arriving on wavelengths from λ _M-p+1 to λ _M-1 are only assigned to output wavelengths λ _M-q+k to λ _M-1.

Remark 2 - In the case 1≤q≤p - 1, when k≥q packets arrive on wavelength λ _M-p, all of the OWCs λ _M-q to λ _M-1 will be engaged, no OWCs will be available and exactly k near conversions are needed at the end of the LCA phase. The number of packets not scheduled equals the number of packets not scheduled on wavelengths λ _M-p, that is k-q, plus the number of packets arriving on the (p - 1) wavelengths from λ _M-p+1 to λ _M-1.

Remark 3 - In the case p ≤ q ≤ p + d, when q - p ≤ k ≤ q - 1 packets arrive on wavelength λ _M-p, they are transferred on wavelengths λ _M-q to λ _M-q+-1 and one packet is transferred on wavelength λ _M-p without wavelength conversion. Consequently Prob(α _p,q = i,β _p,q = j,γ _p,q = h/r _M-p = k) equals p_α,β,γ(p-1,q-k,i,j,min(0,h-(k-1))), that is the probability that i packets are to be still scheduled, j OWCs are still available and min(0, h - (k-1))) near conversions are needed at the end of the LRCR phase respectively under the condition that output wavelengths λ _M-q+k to λ _M-1 are only assigned to packets arriving on wavelengths λ _M-p+1 to λ _M-1, and packets arriving on wavelengths from λ _M-p+1 to λ _M-1 are only assigned to output wavelengths λ _M-q+k to λ _M-1.

Remark 4 - In the case p ≤ q ≤ p + d, when k ≥ q packets arrive on wavelength λ _M-p, we have a similar case to the one analyzed in Remark 1 with the difference that one packet is transferred on wavelength λ _M-p without wavelength conversion. According to the Remarks 1,2 we can write in the case 1 ≤ q≤p - 1:

p_{α, β, γ} (p, q, i, j, h) = {\begin{matrix} \sum_{k = 0}^{q - 1} p_{r} (k) p_{α, β, γ} (p - 1, q - k, i, 0, min (0, h - k)) \\ + \sum_{k = q}^{min (N, i + q)} p_{A} (p - 1) (i - (k - q)) δ (h - q) j = 0 \\ \sum_{k = 0}^{q - 1} p_{r} (k) p_{α, β, γ} (p - 1, q - k, i, 0, min (0, h - k)) j \neq 0 \end{matrix}

where:

According to the Remarks 1,3,4 we can write in the case p ≤ q ≤ p+d:

p_{α, β, γ} (p, q, i, j, h) = {\begin{matrix} \sum_{k = 0}^{q - p - 1} p_{r} (k) p_{α, β, γ} (p - 1, q - k, i, 0, min (0, h - k)) + \\ + \sum_{k = q - p}^{q - 1} p_{r} (k) p_{α, β, γ} (p - 1, q - k, i, 0, min (0, h - (k - 1))) + \\ + \sum_{k = q}^{min (N, i + q)} p_{r} (k) p_{A^{(p - 1)}} (i - (k - q)) δ (h - (q - 1)) j = 0 \\ \sum_{k = 0}^{q - p - 1} p_{r} (k) p_{α, β, γ} (p - 1, q - k, i, j, min (0, h - k)) + \\ + \sum_{k = q - p}^{q - 1} p_{r} (k) p_{α, β, γ} (p - 1, q - k, i, j, min (0, h - (k - 1))) j \neq 0 \end{matrix}

In order to evaluate the joint p.m.f. of the random variables α _p,q, β _p,q and γ _p,q for 2 ≤ p ≤ d+1 and q = p+d + 1, we notice that, due to the limited range of the LRWCs, the arriving packets on wavelength λ _M-p may be forwarded on output wavelengths λ _M-p-d to λ _M-1 and wavelength λ _M-p-d-1 always remains available at the end of the LCA phase. Hence we can write for 2 ≤ p ≤ d+1 and q = p+d+1:

p_{α, β, γ} (p, p + d + 1, i, j, h) = {\begin{matrix} p_{α, β, γ} (p - 1, p + d, i, j - 1, h) j \neq 0 \\ 0 j = 0 \end{matrix}

A.3. Iterative algorithm for the evaluation of the joint p.m.f. of α,β and γ

To find the joint p.m.f. of α,β and γ which is the same of the joint p.m.f. of α _M,M, β _M,M and γ _M,M start with random variables with first index p = 1: α _1,1, β _1,1 and γ _1,1, α _1,2, β _1,2 and γ _1,2 …, α _1,d+2, β _1,d+2 and γ _1,d+2 whose joint p.m.f. was evaluated in subsection A.1 by means of Equations (A.3) and (A.4). Then use Equations (A.5)–(A.8) in subsection A.2 and the joint p.m.f. of α _1,1, β _1,1 and γ _1,1, α _1,2, β _1,2 and γ _1,2 …, α _1,d+2, β _1,d+2 and γ _1,d+2 to find the joint p.m.f. for the random variables when p=2: α _2,1, β _2,1 and γ _2,1, α _2,2, β _2,2 and γ _2,2 …, α _2,d+3, β _2,d+3 and γ _2,d+3. Repeatedly we apply Equations (A.5)–(A.8) and the joint p.m.f. found in the previous step to obtain the joint p.m.f. for random variables when p=3, p=4,… until p=d+2. Then using Equations not shown in this paper, it is possible to obtain the joint p.m.f. for larger p until when the joint p.m.f. of α _M,M, β _M,M and γ _M,M is found.

B. Evaluation of p_{R_l^av,R_f^av}(i, j) (i = 0,1,…,r_l; j = 0,1,…,r_f)

We evaluate the probabilities p_{R_l^av,R_f^av}(i, j) for an OF that next we denote reference OF. Let D_s and W_s be the random variables that denote the number of near and far conversions respectively needed by the OFs selected before the reference OF. Since the SA considered selects randomly the OFs, then if i(i = 1,…N) denotes the order of selection of the OFs, we can express the joint probabilities p _{D_s,W_s}(k,h) (k = 0,1,…;h = 0,1,…) as follows:

p_{D_{s}, W_{s}} (k, h) = \frac{1}{N} \sum_{i = 1}^{N} p_{D_{i}, W_{i}} (k, h)

where p _{D_i,W_i} (k,h) denotes the joint probabilities that k near conversions and h far conversions be needed by the (i-1) OFs selected before the reference OF. When the reference OF is the first to be selected (i = 1), we can simply write:

p_{D_{1}, W_{1}} = {\begin{matrix} 1 k = 0; h = 0 \\ 0 k \neq 0; h \neq 0 \end{matrix}

In the case i ≥ 2, we have the following expression:

p_{D_{i}, w_{i}} (k, h) = \overset{(i - 1) times}{\overset{︷}{p_{D, W} (k, h) \otimes p_{D, W} (k, h) \dots\dots \otimes p_{D, W} (k, h)}},

where ⊗ denotes the convolution operator.

In evaluating the probabilities P _{R^av_l,R^av_f} (i, j) we consider the following cases:

Case (i ≠ 0, j ≠ 0). The number of available LRWCs and FRWCs, when the reference OF is selected, equal i and j respectively, if the previous OFs have required r_l - i and r_f - j near and far conversions respectively.
Case (i = 0, j ≠ 0). Because i = 0, then no LRWCs are available, that is the previous OFs selected have required a number k of near conversions greater than r_l. All of the LRWCs and k-r_l FRWCs have been used to perform the near conversions. Then j FRWCs are available for the reference OF if the previous OF selected have needed r_f - (k-r_l) - jfar conversions.
Case (i ≠ 0, j = 0). Because j = 0, then all of the FRWCs have been used by the previous OFs selected. That occurs when these OFs need a number h of far conversions greater than r_f.
Case (i = 0, j = 0). Because both i and j equal 0, then all the LRWCs and FRWCs have been used when reference OF is selected. That occur when the previous OFs selected have needed both a number k of near conversions greater than r_l and a number of far conversions h greater than r_f -(k-r_l).

According to the cases considered we obtain for p _{R^av_l,R^av_f} (i, j) the following expression:

p_{R_{l}^{av}, R_{f}^{av}} (i, j) = {\begin{matrix} p_{D_{s}, W_{s}} (r_{l} - i, r_{f} - j) i \neq 0; j \neq 0 \\ \sum_{k = r_{l}}^{r_{l} + r_{f} - j} p_{D_{s}, W_{s}} (k, r_{f} - (k - r_{l}) - j) i = 0; j \neq 0 \\ \sum_{h = r_{f}}^{N (M - 1)} p_{D_{s}, W_{s}} (r_{l} - i, h) i \neq 0; j = 0 \\ \sum_{k = r_{l}}^{N (M - 1)} \sum_{h = r_{f} - (k - r_{l})}^{N (M - 1)} p_{D_{s}, W_{s}} (k, h) i = 0; j = 0 \end{matrix}

Acknowledgments

The work described in this paper was carried out with the support of the BONE-project (“Building the Future Optical Network in Europe”), a Network of Excellence funded by the European Commission through the 7th ICT-Framework Programme.

References and links

1. S. Yao, B. Mukherjee, and S. Dixit, “Advances in Photonic Packet Switching: an Overview,” IEEE Commun. Mag. 38, 84–94 (2000). [CrossRef]

2. S. L. Danielsen, P. B. Hansen, and K. E. Stubkjaer, “Wavelength Conversion in Optical Packet Switching,” J. Lightwave Technol. 16, 2095–2108 (1998). [CrossRef]

3. V. Eramo, M. Listanti, and A. Germoni, “Cost Evaluation of Optical Packet Switches Equipped With Limited-Range and Full-Range Converters for Contention Resolution,” J. Lightwave Technol. 26, 390–407 (2008). [CrossRef]

4. H. Li and I. Li-Jin, “Cost-Saving Two-Layer Wavelength Conversion in Optical Switching Network,” J. Lightwave Technol. 24, 705–712 (2006). [CrossRef]

5. V. Eramo, M. Listanti, and A. Germoni, “Cost Evaluation of Optical Packet Switches using both Limited-Range and Full-Range Converters for Contention Resolution,” in proc. IEEE Globecom, December 2007 .

6. C. Guillemot et al., “Transparent Optical Packet Switching: The European ACTS KEOPS Project Approach,” Lasers and Electro-Optics Society 1999 12th Annual Meeting. LEOS ’99. IEEE, vol.2, no., pp.401–402vol.2, 1999.

7. B. Bostica, M. Burzio, P. Gambini, and L. Zucchelli, “Synchronization issues in optical packet switched networks,” Photonic Networks, G. Prati, Sringer-Verlag, 1997.

8. Z. Zhang and Y. Yang, “Distributed Scheduling Algorithms for Wavelength Convertible WDM Optical Interconnects,” IEEE IPDPS 2003, April 2003.

9. Z. Zhang and Y. Yang, “Performance Modelling of Bufferless WDM Packet Switching Networks with Limited Range Wavelength Conversion,” IEEE Trans. Commun. 54, 1473–1480 (2006). [CrossRef]

10. V. Eramo, M. Listanti, and M. Spaziani, “Resource Sharing in Optical Packet Switches With Limited-Range Wavelength Converters,” J. Lightwave Technol. 23, 671–687 (2005). [CrossRef]

11. V. Eramo and M. Listanti, “Packet Loss in a Bufferless WDM Switch Employing Shared Tunable Wavelength Converters,” J. Lightwave Technol. 18, 1818–1833 (2000). [CrossRef]

Performance evaluation of optical packet switches equipped with heterogeneous wavelength converters

Abstract

1. Introduction

2. FLSPN OPS architectures sharing both LRWCs and FRWCs

3. Scheduling algorithms for FLSPN architecture

4. Analytical model

5. Numerical results

6. Conclusions

Appendix

A. Evaluation of the joint probabilities p_α,β,γ(i,j,h)(i = 0,1,…,NM; j = 0,…,M;h = 0,1,…,M - 1)

A.1. Evaluation of the joint p.m.f. of α_p,q,β_p,q and γ_p,q for p = 1 and 1 ≤ q ≤ d+2

A.2. Evaluation of the joint p.m.f. of α_p,q, β_p,q and γ_p,q for 2 ≤ p≤d+1 and 1 ≤q≤p+d+1

A.3. Iterative algorithm for the evaluation of the joint p.m.f. of α,β and γ

B. Evaluation of p_{R_l^av,R_f^av}(i, j) (i = 0,1,…,r_l; j = 0,1,…,r_f)

Acknowledgments

References and links

Cited By

Figures (10)

Equations (23)

Optics Express

Abstract

1. Introduction

2. FLSPN OPS architectures sharing both LRWCs and FRWCs

3. Scheduling algorithms for FLSPN architecture

4. Analytical model

5. Numerical results

6. Conclusions

Appendix

A. Evaluation of the joint probabilities pα,β,γ(i,j,h)(i = 0,1,…,NM; j = 0,…,M;h = 0,1,…,M - 1)

A.1. Evaluation of the joint p.m.f. of αp,q,βp,q and γp,q for p = 1 and 1 ≤ q ≤ d+2

A.2. Evaluation of the joint p.m.f. of αp,q, βp,q and γp,q for 2 ≤ p≤d+1 and 1 ≤q≤p+d+1

A.3. Iterative algorithm for the evaluation of the joint p.m.f. of α,β and γ

B. Evaluation of pRlav,Rfav(i, j) (i = 0,1,…,rl; j = 0,1,…,rf)

Acknowledgments

References and links

Cited By

Figures (10)

Equations (23)

Optics Express

A. Evaluation of the joint probabilities p_α,β,γ(i,j,h)(i = 0,1,…,NM; j = 0,…,M;h = 0,1,…,M - 1)

A.1. Evaluation of the joint p.m.f. of α_p,q,β_p,q and γ_p,q for p = 1 and 1 ≤ q ≤ d+2

A.2. Evaluation of the joint p.m.f. of α_p,q, β_p,q and γ_p,q for 2 ≤ p≤d+1 and 1 ≤q≤p+d+1

B. Evaluation of p_{R_l^av,R_f^av}(i, j) (i = 0,1,…,r_l; j = 0,1,…,r_f)