International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Simulation and Analysis of Blocking Probability Using RWA Algorithm for All- Optical Networks

Mohammed Shadab, Piruthiviraj.P, Dr. Preeta Sharan
  1. Student, Department of Electronics and Communication Engineering, The Oxford College of Engineering, Bangalore, India
  2. Assistant Professor, Department of Electronics and Communication Engineering, The Oxford College of Engineering, Bangalore, India
  3. Professor, Department of Electronics and Communication Engineering, The Oxford College of Engineering, Bangalore, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Routing and Wavelength Assignment (RWA) is one of the key tasks for the optical network, due to its information transparency and wavelength reuse characteristics. This paper presents heuristic algorithm that can be used for routing and wavelength assignment for All-Optical WDM networks under dynamic arising of calls. We have considered All-Optical Networks (AON) without wavelength conversion and dynamic RWA scheme which is based on the distributed Dijkstra's routing algorithm and first-fit wavelength reservation with a set of 64 wavelengths in random topology and for 500 calls the Call Blocking Ratio (CBR) is 0.55 and simulation time is 5 sec.For different arrival of calls the performance is analysed in terms of blocking probability as well as the simulation time of the heuristic algorithm and has been studied through simulation.

Keywords
RWA; Blocking probability; All-Optical Networks;

INTRODUCTION
All Optical Networks [1-5] have become an efficient mean to fulfil the tremendous demand of bandwidth due to skyrocketed increase of internet users. In this regard, dynamic Routing and wavelength assignment (RWA) plays an important role for highly variable traffic pattern of Optical network.
The objective of dynamic RWA is to select the best combination of a route and a wavelength of each connection, such that the numbers of blocked connections are minimized.
In wavelength-routed WDM networks, a connection is realized by a lightpath. In order to establish a connection between a source–destination pair, a wavelength continuous route needs to be found between the node pair. An algorithm used for selecting routes and wavelengths to establish lightpath is known as a Routing and Wavelength assignment (RWA) algorithm. Many problems in wavelength-routed WDM networks have RWA as a sub-problem. Therefore, it is mandatory to use a good routing and wavelength assignment algorithm to establish lightpaths in an efficient manner. Wavelength assignment is a unique feature in wavelength-routednetworks that distinguishes from conventional networks [6]. In the absence of wavelength converters, a lightpath must occupy the same wavelength on all the fiber links through which it traverses; this property is known as wavelength continuity constraint.
Two lightpaths cannot be assigned the same wavelength on any fiber.However, two lightpaths can use the same wavelength if they use distinct set of links. This is known as wavelength reuse.
Depending on whether lightpath requests are known initially and fixed over time or not, routing and wavelength assignment schemes can be classified into two categories: static and dynamic.
In static RWA, all the lightpath requests between end-node pairs are known initially. This is the case for large transport networks in which the planning of the network is made based on an aggregate demand pattern and its forecast future values. Therefore, individual requests are accommodated on provisioned routes during network planning. If the bandwidth requirements for individual connection requests are much less than the bandwidth of a single lightpath, it is possible to use lightpaths to carry electronically multiplexed streams of traffic from many different users. In these networks, the number of lightpaths between end-node pairs may remain fixed over time with only rare changes in lightpath allocations to follow slowly changing mean traffic requirements time.
In dynamic RWA, lightpath requests between end-nodes are assumed to arrive at random times and have random holding times. That is, lightpath requests are established on demand. This is the case for data communication networks in which connections require large bandwidths or lightpaths are used for multiplexed packet based traffic. In such networks, end-nodes may correspond to individual workstations or IP routers. Therefore, lightpath requirements may vary frequently over time. For this reason, routing is done individually for each lightpath request to efficiently use network resources.

II. LITERATURE REVIEW
AshwinSridharan and Kumar N. Sivarajan [6] have proposed two analytical techniques of low complexity, the Independence Model and the Correlation Model, for the study of wavelength routed networks with arbitrary topology and traffic patterns. Both models involve only simple computations and can be used for fast calculations of blocking probabilities. Through computations we have shown that the Independence Model gives good estimates when the network is well connected and the Correlation Model is accurate even for sparse networks under fixed routing. The simplicity of our models can be exploited when computing blocking probabilities in reasonably large networks with a large number of wavelengths as shown in this paper for the ARPA-2 and 12-node ring networks with 64 wavelengths. The Correlation Model, however, is not insensitive to the direction in which we proceed along a route when we compute the blocking and may lead to incorrect results under highly skewed traffic patterns. They have also extended the Independence Model to study Fixed Alternate Routing and Least Loaded Routing and found it to give good results in the region of interest, i.e., low blocking probability.
Amit Wason, R.S. Kaler [7] developed a low complexity mathematical model which does not require any simulation statistics. It has low implementation complexity and the computation used is quite efficient. This model also suggests an optimum path as a solution to routing problem. The model also suggests the appropriate number of wave- lengths which should be free in a network to have the least blocking probability. This model can be implemented on different network topologies.The model is also used to evaluate the blocking performance of NSFNet topology and hence used to improve its performance. We can go for the compromise between the path length and number of free wavelength for the best results in terms of blocking probability. The computation efficiency of the model is very high as it completes the simulation within 1 s with computer with Intel Pentium IV and 512MB RAM.

III. ROUTING AND WAVELENGTH ASSIGNMENT

3.1. Algorithm
Formally, the RWA problem can be stated as follows: given a set of lightpaths that need to be established within the network, and given a constraint on the number of wavelengths (fiber capacity constraint), determine the routes over which these lightpaths should be set up and also determine the wavelengths which should be assigned to these lightpaths so that the maximum number of lightpaths is established [7]. While the shortest path routes (according to distance, available resources, or by some other criteria) may often be preferable, this choice may sometimes have to be sacrificed in order to allow more lightpaths to be set up. In general, good RWA algorithms allow several alternate routes for each lightpath that needs to be established. Lightpath sessions that cannot be set up due to constraints on routes and wavelengths are said to be blocked. That is why it is very important to implement the routing algorithm which will find the shortest path route according to several criteria, but also several alternate routes in case that resource on the shortest path are already reserved. RWA of lightpaths in optical networks is usually done in two steps. The first step tries to find a route between the node pair, and the second assigns wavelengths for links of the route. The literature suggests different solutions, with separate or simultaneous handling of these steps. One approach is to route all connections first, and then assign wavelengths to them as a separate step. With this strategy, it is possible to have no available wavelengths for the found route. Another approach is to combine the steps so that routing is tied to a particular wavelength. This latter approach is typically accomplished by starting with a particular wavelength and reducing the network topology to only those links on which this wavelength is available. The routing algorithm is then run on this pruned topology. If a suitable route cannot be found, another wavelength is chosen and the process is run through again for the matching topology. In this paper we have used former method to implement the algorithm to reduce the simulation time.

3.2 Routing algorithm
Fixed routing is the simplest while adaptive routing yields the best performance. Alternate routing offers a trade-off between complexity and performance. We briefly discuss fixed routing approaches later in this work.

3.1.1. Fixed routing
The most straightforward approach to routing a connection is to always choose the same fixed route for a given source-destination pair. One example of such an approach is fixed shortest-path routing. The shortest-path route for each source-destination pair is calculated off-line using standard shortest-path algorithms, such as Dijkstra’s algorithm or the Bellman-Ford algorithm, and any connection between the specified pair of nodes is established using the pre-determined route.

3.2. Wavelength Assignment algorithm
In WDM All-Optical Networks, there are three main constraints related with wavelength assignment. In WCC, the same wavelength should be used on all links along the selected route. In DWAC, two light paths cannot be assigned the same wavelength on any fiber and in NWCC; different wavelengths can be used on the links along the selected route but the nodes should have wavelength conversion capability.
image
Figure 1: shows an Architectural diagram of the wavelength assignment algorithm.In general, if there are multiple feasible wavelengths between a source node and a destination node, then a wavelength assignment algorithm is required to select a wavelength for a given lightpath. The wavelength selection may be performed either after a route has been determined, or in parallel with finding a route. Since the same wavelength must be used on all links in a lightpath, it is important that wavelengths are chosen in a way which attempts to reduce blocking for subsequent connections. A review of wavelength-assignment approaches can be found in [15].
One example of a simple, but effective, wavelength-assignment heuristic is first-fit. In first-fit, the wavelengths are indexed, and a lightpath will attempt to select the wavelength with the lowest index before attempting to select a wavelength with a higher index. By selecting wavelengths in this manner, existing connections will be packed into a smaller number of total wavelengths, leaving a larger number of wavelengths available for longer lightpaths. Another approach for choosing between different wavelengths is to simply select one of the wavelengths at random. In general, first-fit will outperform random wavelength assignment when full knowledge of the network state is available [7]. However, if the wavelength selection is done in a distributed manner, with only limited or outdated information, then random wavelength assignment may outperform first-fit assignment. The reason for this behaviour is that, in a first-fit approach, if multiple connections are attempting to set up a lightpath simultaneously, then it may be more likely that they will choose the same wavelength, leading to one or more connections being blocked.

3.2.1. First-Fit wavelength assignment
In first-fit, the wavelengths are indexed, and a lightpath will attempt to select the wavelength with the lowest index before attempting to select a wavelength with a higher index. By selecting wavelengths in this manner, existing connections will be packed into a smaller number of total wavelengths, leaving a larger number of wavelengths available for longer lightpaths. Another approach for choosing between different wavelengths is to simply select one of the wavelengths at random. In general, first-fit will outperform random wavelength assignment when full knowledge of the network state is available [7].First-fit does not require global knowledge about the network. No storage is needed to keep the network states and no communication overhead is needed. The computational overhead is small and the complexity is low. Moreover, the performance in terms of blocking probability and fairness is among the best. Therefore, first-fit is preferred in practice [1], [2], [5], [6], [8] and [10]. This scheme performs well in terms of blocking probability and fairness, and is preferred in practice because of its small computational overhead and low complexity. Similar to Random, First-Fit does not introduce any communication overhead because no global knowledge is required.

IV. PROBLEM FORMULATION
As the WDM technology matures and the demand for bandwidth increases, dynamic provisioning of lightpaths at the WDM layer becomes an important and challenging problem. Any distributed algorithm for routing dynamic traffic should be simple, efficient, and also scalable. Our proposed algorithm also measures the performance evaluation considering call blocking ratio and CPU time.
Next Generation WDM based Network basically focuses on the Routing and Wavelength Assignment (RWA) problem in wavelength-routed optical WDM networks. Most of the attention is devoted to such networks operating under the Wavelength- continuity constraints, in which light paths are set up for connection request between node pairs, and a single light path must occupy the same Wavelength on all of the links that it spans. In setting up a light path, a route must be selected and a Wavelength must be assigned to the light path. If no Wavelength is available for this light path on the selected route, then the connection request is blocked. In our proposed work Wavelength is assigned dynamically depending on the bandwidth factor.
We examine the RWA problem and review various routing approaches and Wavelength assignment approaches proposed in the literature. Finally we have proposed a new RWA algorithm, which works well under dynamic traffic by reducing number of call blockages, and wedemonstrated its performance through simulation. In this paper, we have developed a new routing and wavelengthassignment algorithm for WDM-all Optical network in random topology. Also a study has been made on behaviour of blockage problem without wavelength converter for dynamic number of calls and then comparison between different numbers of calls arising.

V . PROBLEM STATEMENT
image

VI. SIMULATION RESULTS
The figures 2, 3 and 4 show the CBR for 50, 500 and 1000 calls respectively.
image
image
The figures 5, 6 and 7shows the simulation time for 50, 500 and 1000 calls respectively.
image
In Figures 8 and 9 shows the proposed and simulated random network. Which consist of 14 number of nodes connected randomly.
image
Table 1 shows the comparison between different parameters like CBR and Simulation time in sec for different number of calls.

VII. CONCLUSION
Comparing the Call blocking ratio and simulation time on the basis of number of calls arrived we found that: For the 50 calls the CBR is zero as wavelengths are 64 and time taken for simulation is 0.7 sec.Similarly for 500 calls the CBR was 0.55 and time taken for simulation is 5 sec. And with 1000 calls the CBR was 0.65 and simulation time taken was 15 sec.
The analysis shows that for the 1000 calls the CBR was slightly increased by 0.10 even though number of calls is doubled which shows that improvement in CBR for large number of call arrival.

References
  1. B. Mukherjee, D.Banerjee,S.Ramamurthy and A. Mukherjee, IEEE/ ACM TRANS ON Networking, 4(5), 684-96;1996
  2. Richard A. Barry and Pierre A. Humblet, IEEE Journal on selected area of communication, 14(5), 858-867;1996
  3. Hazing, J.P.Jue,L.Sahsrabubbhe, R.Ramamurthy and B. Mukherjee, IEEE Comm. Magazine, 39(9), 100-107;2001
  4. J.Spath , Computer Network, 32, 519-538;2000
  5. AshwinSridharan and Kumar N .Sivarajan, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 2,APRIL 2004
  6. Amit Wason, R.S. KalerOptik 122, pp631–634, 2011
  7. VladicaTintor*, Jovan RadunovićMultihop Routing and Wavelength Assignment Algorithm for Optical WDM Networks, International Journal of Networks and Communications; 2(1): 1-10;2012
  8. H. Zang, J. P. Jue, B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches forWavelength-Routed Optical WDM Networks”, Optical Networks Magazine, Vol. 1, No. 1, January. 47-60;2000
  9. C. Chen and S. Banerjee, “A New Model for Optimal Routing and Wavelength assignment in Wavelength Division Multiplexed Optical Networks.” In Proc. IEEE INFOCOM’96, pages 164–171;1996
  10. Xuehong Sun', Yunheo Lit, IoannisLambadarist and Yiqiang Q. Zhao’, Performance Analysis of First-Fit wavelength Assignment Algorithm in Optical Networks, 7th International Conference on Telecommunications – ConTEL SBN: 953-184-0524. June 11-13, 2003,
  11. HUI ZANG, JASON P. JUE, BISWANATH MUKHERJEE, Review of Routing and Wavelength Assignment Approaches for Wavelength- Routed Optical WDM Networks, 2000 SPIE/Baltzer Science Publishers 1388 6916/2000