Nets 128 Camera Ready 1

MMSRP: Multi-wavelength Markov-based Split Reservation Protocol for DWDM Optical Networks Malabika Sengupta

Swapan Kumar Mondal

Debashis Saha

Kalyani Govt. Engg. College Kalyani, West Bengal, India. 913325288537

Kalyani Govt. Engg. College Kalyani, West Bengal, India. 913325941794

IIM Calcutta Kolkata, India. 913324622833

[email protected]

[email protected]

[email protected]

ABSTRACT

Keywords

During wavelength reservation in Wavelength Division Multiplexed (WDM) optical networks, often multiple connection requests unknowingly compete for the same wavelength, even when other free wavelengths are available, resulting in a collision. The Markov model used in Markov Based Reservation Protocol (MBRP), is very effective to reduce such conflicts by intelligently guessing a wavelength in advance. Even then a connection request may be blocked because of the vulnerable period between wavelength probing and actual reservation. To minimize the effect of such vulnerability, splitting the probe process to fork out a partial reservation from an intermediate node is an efficient solution. In Markovselection Split Reservation Protocol (MSRP), the above two strategies are combined, but only one wavelength is guessed during probing. If the attempt with this single wavelength fails, the connection request is blocked. To take care of this limitation, we propose here a new scheme called Multi-wavelength MSRP (MMSRP), where a set of wavelengths (instead of one) is selected by Markov model and continuously updated for possible future use. In case of failure, during reservation in the backward direction, it retries to reserve the next best wavelength through another splitting at the failure point. Thus, MMSRP handles multiple wavelengths sequentially through multiple splitting. Simulation results show that the blocking probability in MMSRP decreases considerably (~25% over MSRP and ~50% over MBRP in some cases) as the number of wavelengths increases. Compared to MSRP, though the average setup time is marginally higher in MMSRP, it appears quite promising for delay-tolerant applications, where blocking is very crucial, in dense WDM networks.

Optical networks, WDM, splitting, Markov model

Categories and Subject Descriptors B.4.4 [Input/Output and Data Communications]: Performance Analysis and Design Aids – Formal models, Simulation.

General Terms Performance. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SAC’10, March 22-26, 2010, Sierre, Switzerland. Copyright 2010 ACM 978-1-60558-638-0/10/03…$10.00.

1.

INTRODUCTION

In Dense Wavelength Division Multiplexed (DWDM) optical networks [1]-[2],[4] without wavelength converters, a dedicated lightpath [5] is first established between the source-destination pair of a connection request (henceforth we refer request to represent connection request) before the actual data transfer starts. Lightpath establishment involves three basic steps: (i) routing, (ii) wavelength selection, and (iii) wavelength reservation [1], [3]-[5]. This work is focused on wavelength selection and reservation. Here we have used fixed shortest path routing, but any other routing may be equally applicable. A judicious selection of wavelength from an available set of wavelengths, reduces the probability of collisions among the concurrent requests. Random-fit and first-fit [2] are two conventional methods for wavelength selection, whereas the recently proposed methods include label prioritization [3], and Markov selection [8],[10]. In label prioritization, the priorities of wavelengths are set depending on the duration of stay in the pool. In Markov method, a particular wavelength is guessed from the available pool of wavelengths well in advance, for each request separately. Thus, other concurrent requests can exclude the already guessed wavelengths and consider the rest, thereby reducing the probability of wavelength conflict. We use this strategy for selection of wavelength in this work. Successful reservation of the selected wavelength throughout the path, is also very crucial because information about wavelength availability is difficult to be guaranteed at any particular place and time in large DWDM networks. To handle this issue, several reservation protocols [3], such as Source Initiated Reservation Protocol (SIRP), Destination Initiated Reservation Protocol (DIRP), Intermediate node Initiated Reservation Protocol (IIRP) [6] and Split Reservation Protocol (SRP) [7] have been reported in literature. Two recent additions to this list are: Markov Based Reservation Protocol (MBRP) [10], and Markov-selection Split Reservation Protocol (MSRP) [8]. In MBRP, selection of wavelength is done using Markov method and reservation is done using DIRP. Here, a wavelength is guessed for a particular request well in advance, so that other requests do not select that guessed wavelength. Thus, wavelength conflict among contemporary requests is reduced. Consequently, MBRP performs better than DIRP [10]. In MSRP, wavelength selection is done using Markov model and reservation of wavelength is done using SRP. Using the concept of splitting [7], blocking is reduced by shortening the vulnerable period. So MSRP performs

better than MBRP [8]. However, a major limitation of MSRP is that, it attempts only one wavelength for reservation and splitting is done only once. If the selected wavelength fails during reservation, the request is blocked. Hence, there is still space for further improvement by extending Markov selection to multiple wavelengths and subsequently incorporating multiple splitting. This concept helps many erstwhile failure cases succeed, thereby reducing the overall blocking of requests. We call this proposed scheme as MMSRP. The paper is organized as follows. Wavelength selection in MMSRP is described in Sections 2 whereas reservation of selected wavelength(s) is discussed in Section 3. Comparative simulation results are discussed in Section 4. Finally, Section 5 concludes the paper.

2. WAVELENGTH SELECTION IN MMSRP Each node of the network maintains three tables: node_table, link_status_table and markov_table. A node_table keeps records of all requests passing through the node. Each record of node_ table contains a few fields. All these fields are mentioned below. Connection_id: identity number of the request, source_id: identity number of source of a route (say R), destination_id: identity number of destination of R, pre_hop_id: identity number of previous node in R, next_hop_id: identity number of next node in R, arrival_time: time when the request arrives at the present node and guessed_wavelength: the wavelength guessed in the present link by the present node. The duration of a record in a node_table is bounded by the estimated sourcedestination round trip time of the concerned request. We assume that each node broadcasts its adjoining link usage information at every T seconds. This link usage information is stored in link_status_table at every node. The records in link_status_table contains the fields: link_id and bit_map. The field bit_map is of size equal to the number of wavelengths used in the network and represents status of usage of all wavelengths of the link. A ‘1’ is placed in the bit_ map when the corresponding wavelength is free and a ‘0’ otherwise. The markov_table contains the information of rate of change of states of the wavelength usage for all the wavelengths in all the links. The records of markov_table contains link_id and rate_map. The rate_map contains rate of change of states of the wavelength usage for all the wavelengths in the corresponding link_id. It is worth mentioning here that, control packets carry information and the nodes use the information carried by the control packets to execute the required tasks. But in this paper, to improve the readability, we sometime describe control packets as performer of some tasks. When a request arrives at source node, the node initiates the control packet PROB and forwards it to the next node towards destination. Henceforth source and destination will be used to represent source node and destination node respectively. PROB includes the following fields: connection_id, source_id, destination_id, route_path, probe_map, future_guess_set and prev_guess_index. The route_path is the ordered list of nodes on the selected route, probe_map is an array indicating the availability of each wavelength in the route. A “1” in probe_map

represents that the corresponding wavelength is free and a “0” otherwise, future_guess_set is an array which contains a set of guessed wavelengths for probable use in future if the request is splitted, prev_guess_index contains the guessed wavelength upto the previous node. Use of future_guess_set and prev_guess_index are discussed in Subsection 2.2. While PROB moves towards destination, each node performs three major tasks discussed in the following subsections.

2.1

Detection of interfering requests

When a request arrives at a node, it is called current request. All other ongoing requests that arrived earlier at that node are called under process requests. Those under process requests, whose pre_hop_id or next_hop_id (available in node_table) matches with next_hop_id of the current request, are called interfering requests. When a PROB arrives at a node, the node detects the interfering requests using node_table. This detection of interfering requests is required to identify and exclude the wavelengths guessed by them to reduce the probability of collision of wavelengths.

2.2

Selection of the guessed wavelength

We assume that each node broadcasts its adjoining link usage information at every T seconds. This is stored in link_status_table. So each node comes to know about the wavelength allocation on all links in the network at times 0T, 1T, …, sT, …, where s is a natural number. However, the information broadcast at sT may not remain correct at an arbitrary time instant between sT and (s+1)T. To overcome this uncertainty, a prediction based on C-T Markov chain [6] is used. Markov parameters are broadcast at every T ′ seconds and stored in markov_table of each node. Usually, T ′ >> T so that the Markov chain remains stable. After receiving a PROB, each node first updates its probe_map field by marking those wavelengths of the present link (the link connecting the present node and the next node of the route) as busy (if any), which are (i) already guessed by interfering requests or (ii) reserved by other requests for future transmission or (iii) reserved and being used for transmission. If no free wavelength is available, PROB fails and the request is blocked. A NACK is generated and sent towards source. NACK releases the entries of this request from node_table at each node till it reaches source. Otherwise, for each free wavelength (if any), the node uses the markov_table to find the probability of getting the wavelength free throughout the path [10]. We extend the concept of guessing [10], using multiple number of wavelengths. If total number of free wavelengths is y, the node selects p (y>p>1) number of wavelengths having higher probabilities of remaining free. These p wavelengths are arranged with respect to probability in descending order as λg1 ,λg2 , …,λgp . Here, p is a predefined number which represents the maximum number of splitting permitted for a request. Obviously, if y<=p, all y wavelengths are selected. From the ordered set, wavelength λg1 is selected as guessed wavelength and wavelengths λg2 to λgp are stored in future_guess_set. When the present node is the source, prev_guess_index of PROB is initialized to λg1. A record is created in node_table of the source and PROB is forwarded to next node. If the present node is any node other than source, the node checks the availability of the wavelength stored in prev_guess_index. If the wavelength is available, a record is created in node_table of the present node and PROB is forwarded to next node; else the node

checks for splitting. When splitting does not occur, prev_guess_index is updated to the wavelength λg1. A record is created in node_table of the present node and the PROB is forwarded to next node.

2.3

Dynamic splitting

MMSRP adaptively splits a probe attempt into two concurrent (upstream and downstream) reservation attempts at some intermediate node selected dynamically. For a request, splitting may occur if both the following conditions are satisfied: (i) PROB has traversed a pre-selected distance (x*d) of the route, where d is the total distance of the route, x is a positive fraction (0<x<1) and (ii) the wavelength at prev_guess_index is not available in present link . The effect of x on blocking probability (bp) for various network conditions, is discussed in [8]. We select the value of x as 0.5, considering moderate to high crisis situation. If the conditions of splitting are satisfied, it splits; otherwise the PROB propagates to the next node.

fields: connection_id and selected_wavelength. RES_BKD includes the fields: connection_id, selected_wavelength and future_guess_set. At the point of splitting prev_guess_index (i.e., λg1) of PROB is assigned to selected_wavelength of both RES_FWD and RES_BKD. The RES_BKD moves towards the source, reserving λg1 (i.e. the wavelength stored at selected_wavelength) and deleting the entries of this request in node_tables on the way. The RES_FWD moves towards destination reserving λg1. Source

sp2

sp1

Destination

PROB RES_BKD

RES_FWD

RES_BKD RES_FWD

3. WAVELENGTH RESERVATION IN MMSRP If splitting does not occur and PROB successfully reaches destination, the destination converts PROB into RES. For that request standard DIRP is used for reserving the wavelength. Table 1 summarizes different control packets used in the scheme. RES includes the following fields: connection_id and selected_wavelength. The content of prev_guess_index of PROB

ACK

Data Transmission

Figure 1. Case of success in MMSRP. Name

Description

PROB

moves from source to destination and contains various probe results moves from splitting point towards destination to reserve a selected_wavelength moves from splitting point towards source to reserve a selected_wavelength moves towards source, caries acknowledgement if RES_FWD reaches destination successfully moves towards source and caries not acknowledgement if RES_BKD or PROB fails moves towards source to release the wavelength reserved so far if RES_FWD fails, also caries not acknowledgement moves towards destination to release the reserved wavelength if RES_BKD fails

RES_FWD RES_BKD ACK NACK REL_BKD REL_FWD

Table 1. Control packets. is assigned to selected_wavelength. The intermediate nodes, on receiving this RES, lock the selected_wavelength as busy and delete the record from the node_table of this request. However, if the selected_wavelength becomes unavailable at any point, RES is converted to REL which moves towards destination and releases the wavelength in the links reserved so far. A NACK is also generated from the point of failure which proceeds towards source deleting all the records in the node_tables of this request. If the RES reaches source successfully, transmission starts. After the transmission is over, the reserved wavelength is released. If splitting occurs, the PROB is converted to RES_FWD. A RES_BKD is also generated at the first splitting point (we call it sp1) as shown in Figure 1 and Figure 2. RES_FWD includes the

However, if RES_BKD fails at some intermediate node due to non-availability of λg1, further splitting may occur (maximum p-1 times). When RES_BKD fails, the node selects next candidate from the future_guess_set, subject to availability. The node checks first the availability of λg2 in the forward link. If λg2 is not available, λg3 is checked for its availability and so on upto λ gp. In case of failure after first splitting, RES_BKD again splits into two new reservation packets RES_FWD and RES_BKD. These RES_FWD and RES_BKD, act like earlier RES_FWD and RES_BKD packets respectively. Both packets now attempt to reserve a new wavelength selected in the same way, say λgx, in both forward and backward directions. RES_FWD on its way also releases the previously reserved wavelengths by previous RES_FWD and RES_BKD. Now, if both RES_FWD and RES_BKD are successful to reserve the same wavelength, data transmission starts after receiving the ACK from destination. If RES_BKD is stuck at an intermediate node and all possible splittings are exhausted, the request is blocked and RES_BKD is converted into NACK which moves towards source. Another REL_FWD is generated from the point of failure which moves towards destination and releases the wavelengths reserved so far by both RES_FWD and RES_BKD. Again, if RES_FWD fails, it is converted into REL_BKD which moves towards source releasing the wavelengths reserved so far. It also acts as a NACK and deletes the entries of this request in node_tables of the path. Figure 1 shows a case of success whereas Figure 2 shows a case of failure. In the figures, sp1 and sp2 indicate the two splitting points (nodes) of a request. Source

sp2

sp1

Destination

70

RES_BKD

RES_FWD

blocking probability ( bp )

PROB

REL_FWD

NACK

REL_FWD

Figure 2. Case of failure in MMSRP.

% gain over M BRP

60 50 40 30 20 10

% gain over M SRP

0 50

SIMULATION RESULTS

We have tested our protocol in simulation environment and the results are produced here. In the simulation model, static shortest path routing is used in a randomly generated DWDM network (without wavelength converters) of 40 nodes and 46 links. Requests arrive following Poisson distribution, and connection holding times are exponentially distributed. The simulation model is event driven. The source and destination of a request are chosen at random. The key performance metric bp is studied exhaustively for different parameters. We define T ratio as the ratio of T ′ to T. Effect of Tratio on bp is studied in [8] and it is reported that for Tratio≈ 300, bp remains minimum. So, for the results presented in this paper, we keep Tratio fixed at 300. We represent the number of wavelength(s) and average arrival rate of request(s) per second in the network as wl and cr, respectively. Here, we have used p=2. Also, we have considered MSRP and MBRP for comparison with the proposed scheme MMSRP. We have studied the characteristics of the schemes for higher values of wl ranging from 300 to 1000 which are suitable for DWDM. However, due to limitation of space, we have presented one representative result for wl= 500. We have also studied the effect of wl on bp for fixed values of cr. One such representative result is presented here for cr=300.

4.1

blocking probability ( bp )

0.1

M BRP 0.08

MSRP

0.06 0.04

M M SRP 0.02

50

100

150

200

250

average arrival rate of requests (cr )

300

Figure 3. Comparison of bp with varying cr for wl = 500.

250

300

M BRP

0.1 0.08

MSRP

0.06 0.04

M MSRP

0.02 0 300

400

500

600

700

800

900

number of wavelengths (wl )

Figure 5. Comparison of bp with wl for cr=300. Figure 5 shows the variation of bp with different values of wl for cr=300. The following points can be observed from the figure. First, MMSRP always performs distinctly better than MSRP and MBRP. Second, the variation of bp with wl is very less. This may be explained considering the two basic reasons of connection blocking, which are: (i) insufficient network resource and (ii) use of outdated information during the attempt of reservation. Here, with the increase of wl more resource become available, whereby the first reason is minimized. But, due to propagation delay, the information used for reservation of wl happens to be outdated. Thus the second reason exists, and blocking takes place due to use of outdated information mainly. Hence, bp does not vary too much with wl.

4.2

0

200

0.12

Blocking probability

The variation of bp with respect to cr is presented in Figure 3 for wl=500. It is evident from the figure that MMSRP performs distinctly better than MSRP and MBRP. In general, for all the schemes, bp increases with increase in cr. The percentage gain of MMSRP over MSRP is in the range of 13% to 25% and around 50% over MBRP (Figure 4).

150

Figure 4. Variation of % gain of MMSRP in bp with cr over MSRP and MBRP for wl=500.

blocking probability ( bp )

4.

100

average arrival rate of requests (cr )

Average setup time

Setup time is the latency in establishing a lightpath corresponding to a request. Since individual setup times may vary from request to request, we calculate the average of all setup times for successful cases (Figure 6). Moreover, setup time of MMSRP remains higher, compared to MSRP and MBRP, throughout the region because MMSRP requires more time as some part of the route is traversed more than once in case of multiple splitting in MMSRP.

[2] C. Murthy and M. Gurusamy, WDM Optical Networks, Concepts, Design and Algorithms. Englewood Cliffs, NJ: Prentice-Hall, 2001.

0.00395

setup time

M M SRP

[3] D. Saha, “A Comparative study of distributed protocols for wavelength reservation in WDM optical networks”, SPIE Opt. Netw. Mag., vol 3, no. 1, pp. 45-52, 2002.

0.00385

[4] H. Zang, J. P. Jue and B. Mukherjee, “Review of routing and wavelength assignment approaches for wavelengthrouted optical WDM networks”, Optical networks, Vol 1, no 1, pp 47-60, Jan. 2000.

M SRP

0.00375

M BRP 0.00365 50

100

150

200

250

300

average arrival rate of requests (cr )

Figure 6. Variation of setup time with cr for wl=500. We have also studied the variation of average number of control packets with different values of cr for a range of values of wl from 300 to 1000. Generally, the average value of control packets used by MMSRP is slightly higher than (or equal to) average value of control packets used by MBRP and MSRP. The increase is limited to around 7% only. This is because the number of control packets used by the schemesare the same for most of the cases, such as success without split, success with single split, failure during probing, and failure during reservation without splitting. Only, for the case of more than one splitting, the number of control packets for MMSRP is more. Thus, the comparison of average control packets is not remarkably noticeable and hence is not presented here.

5.

CONCLUSION

Multiple splitting, combined with multi-wavelength guessing, in

MMSRP reduces blocking probability considerably (around 15%50%) over either MSRP or MBRP. During probing, first splitting is used dynamically and then multiple splitting is used in case of failures. Hence, the average setup time in MMSRP is slightly higher than that in MSRP or MBRP, but the average number of control packets used is not significantly changed. Thus, MMSRP performs better than the current best protocols as far as blocking probability is concerned at higher wavelength regions at the cost of nominal increase in the average setup time. So it may be considered as a better performer in DWDM networks, specially for the applications, where protocol efficiency is of prime importance and the network uses a larger number of wavelengths.

6.

REFERENCES

[1] A.E. Ozdaglar and D.P.Bertsekas, “Routing and Wavelength Assignment in Optical Networks”, IEEE/ACM Trans. On Networking, vol. 11, no. 2, pp. 259-271, April. 2003.

[5] H Zang, J. P. Jue., L Sahashrabuddhe, R Ramamurthy, and B Mukherjee,“ Dynamic Lightpath Establishment in Wavelength-Routed WDM Networks”, IEEE Commun Magazine, pp 100-108, Sept. 2001. [6] K. Lu, J. P. Jue and G. Xiao, “Intermediate-Node Initiated Reservation (IIR): A New Signaling Scheme for Wavelength-Routed Networks,” IEEE JSAC, vol. 21, no. 8, pp 1285-1294, 2003. [7] M. Sengupta, S. K. Mondal and D. Saha “An Adaptive Split Reservation Protocol (SRP) for Dynamicaly Reserving Wavelengths in WDM Optical Networks”, Proc. ICDCN 2008, LNCS 4904, pp 440-451, 2008. [8] M. Sengupta, S. K. Mondal, C. Bose and D. Saha, “A Markov selection Split Reservation Protocol for WDM Optical Networks without Wavelength Conversion”, to appear in Proc., IEEE GLOBECOM, 2008. [9] T. Ozugur, M. Park, and J. Jue, “Label prioritization in GMPLS-centric all-optical networks,” in Proc.ICC, 2003, pp. 1283–1287. [10] W. Lin, R. S. Wolff and B. Mumey, “A Markov-Based Reservation Algorithm for Wavelength Assignment in AllOptical Networks”, IEEE Journal of Light wave Technologies, vol. 25, no. 7, pp 1676-1683, 2007.