Tropic NetworksIntroductionMDP Algorithm OverviewThe MDP ModelSimulation ResultsConclusionReferencesUsing OPNET to Evaluate Diverse Routing Algorithms Peter Pieda and John Spicer Tropic Networks 135 Michael Cowpland Drv., Kanata, On. K2M 2E9 E-mail: [email protected] Abstract In optical networks, it is essential to handle network failures such that network disruption is minimized. Existing SONET Standards require network restoration within 50 ms. Traditionally, two diverse paths are provisioned: a primary/working path and a secondary/protection path (i.e. two sides of an optical ring network). As we move from simple (i.e. ring) to complicated (i.e. mesh) optical networks, determining two diverse paths becomes increasingly difficult. To provide two diverse paths, Maximally Disjoint Path (MDP) algorithms are used. In this paper, we evaluate the characteristics of MDP, specifically including (i) brief description of MDP algorithms, (ii) detailed model description, and (iii) performance on arbitrary test networks. Introduction Optical networks are comprised of optical fiber links and network nodes that connect these links together. Many optical networks have topologies combining long-haul point-to-point links and SONET (Synchronous Optical NETwork) optical rings. In optical networks, it is essential to handle network resource failures, i.e. failed links and nodes, such that network disruption is minimized. Existing SONET standards require network restoration within 50 ms on recognition of network failure (normally 10ms). One approach to meet this requirement is to provision or install two physical paths. Traditionally, two diverse paths are provisioned: a primary/working path and a secondary/protection path. Two diverse paths are paths that share the least network resources. Completely diverse paths ensure that the same network failure will not affect both paths. For example in a SONET ring, one side of the ring could be the primary path and the other side the protection path. Therefore, when a fault occurs on the primary path, traffic is quickly switched to the protection path. There are several different configuration used in SONET rings to achieve this: UPSR, BLSR and others [2]. As we move from simple (i.e. ring) traditional networks to complicated (i.e. mesh) Metro-Optical networks, determining two diverse paths becomes increasingly difficult. To provide two diverse paths, two components are used: (1) Maximally Disjoint Path (MDP) algorithms and (2) routing algorithms. Two maximally disjoint paths are two paths that are diverse as possible, given the network topology. The MDP algorithm transforms the network to encourage disjoint paths and discourage shared network resources. Paths are then determined individually using a Shortest Path First (SPF) routing algorithm. These two functional blocks were modeled in the OPNETOPNET simulation environment. The main goal of this paper is to describe our approach for modeling MDP using OPNET. Based on the MDP algorithms described in [1], we developed a procedure whereby two or more optimally diverse paths can be calculated from an arbitrary network topology of links and nodes. Additionally, as new research in routing and diverse routing algorithms become available, this model can be used to facilitate their evaluation. This paper is organized as follows. In section II we give a brief description of the Maximally Disjoint algorithm and in section III we describe our OPNET implementation of the MDP. In section IV, we illustrate the working of MDP on some example networks and present simulation results. Concluding remarks are offered in section VI. MDP Algorithm Overview In this section we give a brief overview of the Maximally Disjoint Path algorithms [1], describing the network transformations, and discuss the multiple path operation of MDP. The MDP algorithms describe several methods of network transformation so that a SPF routing algorithm can determine paths that are optimally diverse. Two of these methods are an edge disjoint transformation and a node disjoint transformation. A B C ZD111427A B C ZD111427A B C ZD1+a4271+a 1+a-1 -1 -1A B C ZD1+a4271+a 1+a-1 -1 -1 Figure 1: Edge Transformation The edge disjoint transformation splits each intermediate bi-directional link into two unidirectional links. The first link, directed forward, is set to a high cost (a) to discourage its use, and the second link, directed backwards, is set to the negative 1original value, to encourage disjoint paths. The high cost a value is set usually set to the sum of all the links costs times some constant, [1] suggests 4. See figure 1 for an example of this transformation. The original network has the best path: A-B-C-Z. The intermediate links, AB-BC-CZ, are transformed. For multiple paths, the algorithm is executed iteratively for the number of paths. The previously determined paths resources are transformed for the next iteration. For the edge disjoint transformation, if multiple paths use a link, that link incurs multiple costs. This makes that link less likely to be used again for another path. The node disjoint transformation only splits intermediate nodes once, with additional path adding a cost to the forward directed link (b). The node disjoint transformation splits each intermediate node into two nodes. All links (excluding primary path links) that are connected to this node are split into two unidirectional links of original cost. The incoming directed links attach to the first node and the outgoing directed links attach to the second node. There are two links (unidirectional) inserted between the two nodes: a forward link of high cost (b) and a backward link of 0 cost. The high cost b value is set in the same manner as for the edge disjoint a value. In figure 2, the same example network transformed for node disjoint path determination. The MDP Model We used OPNET to develop a simulation model for the MDP algorithms. Within a simple node model we implemented the edge and node disjoint transformations and the necessary SPF routing algorithm in a modular fashion. Each class function encompasses one step in the general algorithm. To simulate link failures, we modeled a simple link failure control model. Figure 2: Edge Transformation A B C ZD111427A B C ZD111427AB’ZD114271B’’ C’ C’’4bb00AB’ZD114271B’’ C’ C’’4bb00 To analyze the MDP functionality, a simple node model was