MICRON A Framework for Connection Establishment in Optical Networks project and implimentation report
project topics Active In SP Posts: 2,492 Joined: Mar 2010 
02042010, 10:48 PM
MICRON A Framework for Connection Establishment in Optical Networks Submitted By G. Bala Satish Jitendra kumar Gond Pankaj Kumar Pandey Under the guidance of Mr.Asim Mukerjee Department of Electronics & Communication Engineering MNNIT Allahabad Abstract Traffic grooming in optical network has gained significance due to prevailing sub wavelength requirement of end users. Optical networks get upgraded to the latest technology slowly with time with only a subset of nodes being upgraded to the latest technology. The networks are thus comprised of nodes employing heterogeneous switching architectures. In this paper, we develop a framework called Methodology for Information Collection and Routing in Optical Networks (MICRON) for connection establishment in optical grooming networks with heterogeneous switching architectures. Contents Sl no. Chapter Page no Certificate i Abstract ii Acknowledgement iii 1 2 3 4 5 Introduction Wireless Sensor Network 2.1 Introduction 2.2 Routing Protocols 2.2.1 Conventional Protocols 2.2.2 Existing Protocols 2.3 Flat routing Protocols 2.4 Hierarchical routing protocols 2.4.1 LowEnergy Adaptive Clustering Hierarchy 2.4.2 PowerEfficient Gathering in Sensor Information Systems 2.4.3 ThresholdSensitive Energy Efficient Protocols 2.5 Algorithms used for Protocols 2.5.1 Kruskal's algorithm 2.5.2 Dijkstra's algorithm Methodology 3.1 Cluster Head Election 3.2 Cluster Head election constraints 3.2.1 Energy method Results Conclusions Appendix References 01 Chapter 1 Introduction OPTICAL communication employing wavelength division multiplexing (WDM) has emerged as a viable solution for satisfying the everincreasing quest for bandwidth due to emerging Internet applications. WDM divides the available fiber bandwidth into multiple wavelengths each of which operates at peak electronic speed. Present day networks have a transmission capacity of 40 Gb/s (OC768) on a wavelength. However, the user requirements are of subwavelength capacity, typically ranging from 155 Mb/s (OC3) to 622 Mb/s (OC12), and rarely in the range of a few gigabits per second. Hence, alternatives for provisioning of subwavelength traffic in WDM networks has received significant attention in the recent past. One approach to provisioning subwavelength traffic is to divide a wavelength into time slots that would allow multiple traffic to be time multiplexed on the wavelength. transmission speeds in longhaul networks requires stringent synchronization across the network. Hence, Code Division Multiple Access (CDMA) approaches may be employed to share a wavelength bandwidth across multiple users. The resulting multiwavelength multitime slot or multicode network is referred to as a WDM grooming network. Wavelength converter (WC) is a device that converts an optical signal from one wavelength to another. Similarly, a time slot interchanger (TSI) is a device that converts an optical signal from one time slot to another. The optical version of TSI is realized using fiber delay lines [1], [2]. Alloptical implementations of WC and TSI are expensive, and hence cannot be implemented at all nodes in the network. CDMA code converters can be implemented using passive components such as fiberBragg gratings. WDM grooming networks can be classified into two categories [3]: dedicatedwavelength grooming (DWG) networks and sharedwavelength grooming (SWG) networks. In DWG networks, a lightpath between two nodes is shared only by the traffic between them. In SWG networks, the lightpath can be shared by traffic from other nodes as well. The performance of SWG networks depends on efficient merging of fractional wavelength requirements into full or almostfull wavelength requirements. Such merging of smaller capacity requirements into higher capacity lightpaths is called traffic grooming. Traffic grooming in SWG networks can be performed in a static or dynamic manner. In static grooming, the sourceâ€œdestination pairs whose traffic requirements will be combined are predetermined. In dynamic grooming, connections of different sourceâ€œdestination pairs are combined based on the existing lightpaths at the time of a request arrival. In this paper, we consider dynamic grooming in SWG networks. The performance of SWG networks depends on efficient grooming of subwavelength traffic and therefore require sophisticated routing algorithms based on uptodatenetwork information. Nodes in a SWG network can have different levels of grooming capability. For example, a node might employ TSI but not WC. Such nodes are referred to as wavelengthlevel grooming nodes as channels can be switched only within a wavelength. Similarly some other nodes might implement WC but not TSI, referred to as time slot level grooming nodes. A node employing both TSI and WC are referred to as fullgrooming node. As the present day optical technology is not mature enough to make routing decisions at run time, widearea optical networks are expected to remain circuitswitched in nature for the near future. Operating a circuitswitched widearea network involves establishing connections of a certain bandwidth between two nodes in the network. It is well understood that networks in future would comprise of nodes with heterogeneous switching architectures. One of the reasons is that upgrading of existing switch architectures to the latest optical technology takes both time and money. Financial constraints limit the network upgrade procedure to enhancing the capability of only a few nodes or increasing the capacity of only a few links depending on the traffic flowing through them. The networks are thus heterogeneous in nature as they constantly evolve with time. Hence, it is important to address the issue of connection establishment in such heterogeneous networks. Connection establishment in a connectionoriented network consists of two steps: path selection and channel assignment. Path selection refers to selecting a path from source to destination based on certain criteria. Channel assignment refers to assigning one or more channels, depending on the requirement of the request, on every link of the chosen path. Path selection may be carried out in several ways. If a sourceâ€œdestination pair has one preselected path, then it is referred to as fixedpath approach. If a path is selected depending on the network status from a preselected set of candidate paths, then it is referred to as dynamic path selection. The set of candidate paths remain the same at all times and do not change with the network status. If the candidate paths are chosen based on the network status, the path selection process is referred to as exhaustive routing. Channel assignment refers to allocation of specific resources on every link of a chosen path, for example: 1) fiber, wavelength,and time slot assignment on the links in a WDM grooming network; and 2) fiber and wavelength assignment in a multifiber wavelengthrouted network. Irrespective of the path selection or channel assignment strategy employed in the network, obtaining information along a path to assess the availability of resources to establish the connection becomes the fundamental requirement. Information collection in optical grooming networks involve identifying availability of resources on the links along with the grooming capability of intermediate nodes on a specific path to identify capacity availability on the path. The connection establishment problem is typically modelled as an optimization (mixedinteger linear programming) problem when the set of connections to be established are known a priori. Typically heuristic approaches are employed as the solution times for the optimization problem may be prohibitively high for largescale networks. The objective in such formulations is to reduce the network cost while being able to accommodate all the connections. Some earlier work concentrate on specific network topologies, such as rings [4]â€œ[7], while others are developed for arbitrary (or mesh) topologies [8]â€œ[11]. In [12], the authors consider the problem of rerouting the existing subwavelength traffic in the network to optimize the wavelength utilization. Connection establishment has been extensively studied in the context of wavelengthrouted WDM networks under dynamic traffic scenarios [13]â€œ[15]. Under dynamic traffic scenarios, the objective is to compute a path and a channel assignment for a given request based on the current network status. Connection establishment in WDM grooming networks has been addressed in [16]â€œ[18]. In [16], the authors develop a family of routing, wavelength and timeslot assignment algorithms for a TDMbased wavelength routing network. The nodes are assumed to have switching capability at the granularity of a time slot. The nodes, however, do not have time slot interchangers or wavelength converters. If denotes the number ofwavelengths per link and denotes the number of time slots per wavelength, then the routing, wavelength, and time slot assignment problem is similar to routing and wavelength assignment problem in a wavelength routed network with wavelengths per link. In [17] and [18], the authors develop a graphbased model in which every node is replaced by wavelengthnodes, where denotes the number of wavelengths per fiber. A fiber link between nodes and is replaced by auxiliary links, each connecting a specificwavelengthnode of to a specificwavelengthnode of . If a node has fullwavelength conversion, then links between all wavelengthnode pairs at node are added. Such a graph model translates a WDM network with nodes, links, and wavelengths per link to a graph with nodes and links. If the nodes employ wavelength conversion, then additional links are required. The maximum number of additional links required is , when all the nodes have wavelength conversion. It is worth noting that when all the nodes have wavelength conversion, the network may be simply viewed as nodes connected by links with indistinguishable channels in each link. However, the graph model does not automatically allow such a reduction in network representation. In addition, such a graphbased model may be employed only as a centralized mechanism to identify paths, hence suited for networks that employ linkstate protocols. If the networks employ alternate path routing [19] or leastloaded path routing [20], [21] the availability of capacity on a path may be computed by probing (sending messages along) the desired paths. Earlier works on routing in traffic grooming networks simply consider a wavelength routed network where some nodes may employ wavelength conversion. However, given that multiplexing of lowrate traffic to a highcapacity lightpath may be accomplished in several dimensions, e.g., WDM, TDM,n CDMA, it is conceivable that nodes might employ switching capabilities only in some dimensions. The research in this paper addresses the problem of efficient representation of link and node information in a traffic grooming network with heterogeneous switching architectures. In this paper, we develop a framework for connection establishment called MICRON (Methodology for Information Collection and Routing in Optical Networks) in WDM grooming networks, specifically emphasizing on what and how information is collected on the links, the aggregation strategy to obtain information on a path considering different grooming capabilities of the intermediate nodes, and mechanisms for path selection and channel assignment. Several routing and channel assignment strategies may be developed from the framework developed in this paper. The remainder of the paper is organized as follows. Section II explains the assumptions on the network model, node architecture, and notations employed. Section III describes an example network. Section IV introduces the framework and illustrates different path selection and channel assignment schemes on the example network. Section V concludes the paper. Chapter 2 NETWORK MODEL 2.1 Introduction Consider an optical grooming network with nodes employing heterogeneous switching architecture. The nodes in the network are connected using links. Let N denote the number of nodes And L denote the number of links in the network. Each link is assumed to carry F fibers, each fiber carrying W wavelengths. Each wavelength is divided into frames which are further subdivided into T time slots. Every slot within a frame is denoted by a 4tuple,(l,f,w,t) , where ,1<l<L ,1<f<F,1<w<W,and1<t<T.For example, the tuple (1,1,2,1) (read from right to left) denotes first time slot in a frame on the second wavelength of the first fiber on the first link. A channel on a link is defined as a collection of a particular occurrence of time slot across successive frames. Hence, the number of channels in a link is the same as the number of slots in a frame, . Each channel is also represented by a 4tuple, 2.2 A. Node Architecture A WDM grooming network with heterogeneous network architecture is modeled as a trunk switched network (TSN). The TSN model was introduced in [22] to enable modeling of multiwavelength optical networks and evaluate them for blocking probability. The MICRON framework is developed for the TSN model, therefore we describe the TSN model in detail. A TSN is a twolevel network model in which every link in the network is viewed as multiple channels. A node in a TSN groups the channels with similar characteristics in a link into groups called trunks. The definition of a trunk at a node depends on the switching resources available at a node.We illustrate the notion of trunks with an example. Consider a WDM grooming network where every link has four fibers, three wavelengths per fiber and two time slots per frame ( , , ). Fig. 1 shows the channels on a link. The shapes represent the time slots and the shades represent wavelengths. If time slot interchange and wavelength conversion are not permitted, a node views link as trunks where each wavelength and time slot combination forms a trunk. Every trunk has channels as shown in Fig. 2(a). If time slot interchange is permitted, but not wavelength conversion, a node views link as trunks, where each wavelength forms a trunk. Every trunk has channels as shown in Fig. 2(b). A node with such a capability is referred to as a wavelengthlevel grooming node. If fullwavelength conversion is permitted, but not time slot interchange, then each time slot on the link forms a trunk. Every trunk has channels as shown in Fig. 2©. A node with such a capability is referred to as a time slotlevel grooming node. If both fullwavelength conversion and time slot interchange are permitted, then the entire link is treated as one trunk with channels, as shown in Fig. 2. Possible grouping of channels in a link as trunks. (a) Each wavelength and time slot combination is a trunk; (b) each wavelength is a trunk; © each time slot is a trunk; and (d) the link is a trunk Fig. 3. Node architecture in a trunk switched network Fig. 2(d). A node with such a capability is referred to as a full grooming node. A singlefiber wavelengthrouted WDM network employing wavelengths can be modeled as trunks with one channel per trunk. A multifiber multiwavelength wavelengthrouted network with fibers and wavelengths with no wavelength conversion can be viewed as trunks with channels per trunk. If fullwavelength conversion is available, then a link can be viewed as a single trunk with channels. Fig. 3 shows the node architecture in a TSN. The node in the figure is assumed to have three links attached to it and views each link as a set of trunks. The trunks are first demultiplexed from the link. The trunks from different links are then sent to their respective trunk switches where the channels are switched. We impose trunkcontinuity constraint at a nodeâ€i.e., a channel in a trunk on a link may be switched only to a channel that falls within the same trunk on another link. Such a restriction stems from an architectural point of view. The complexity of a full permutation switching over all channels across all links is prohibitively large. Therefore, switch designs for the near future are likely to be based on simple architectures that would switch channels within restricted groups. A TSN is said to be homogeneous if the collection of channels that constitute a trunk at a node is the same for all the nodes in the network. Otherwise, it is said to be heterogeneous. In this paper, it is assumed that a fullpermutation switch is employed for every trunk in a node, i.e., a free channel of a trunk at the input of the switch can be switched to any free channel of the Fig. 4. Example network showing two paths from node 1 to node 5. same trunk at its output. We assume that switching channels across fibers is available at all nodes as it requires only space switching. We, therefore consider only wavelength and timeslots as trunks in this paper. A node in the network views a link connected to it as a set of trunks each containing channels. Let denote the channels on a link that fall within trunk at node . Let denote the channels on link that fall within trunk at node and trunk at node , i.e., . The group of channels that fall within a set is referred to as a subtrunk. Calls arriving in the network request for a connection to be established from a source to destination. The connection establishment involves selection of a path and assignment of channels on the path such that the channel on one link can be switched to the successive link on the path by the node connecting the links. In a TSN, connection establishment consists of three steps: 1) selecting a path; 2) assigning a subtrunk on every link, or equivalently assigning a trunk at every node; and 3) assigning one or more channels depending on the call requirement on every subtrunk on every link. Hence, a connection in a network is represented by a sequence of link and subtrunk pairs, or equivalently as a sequence of node and trunk pairs. If every node in the network employs full permutation switching for every trunk, then any channel that falls within the selected subtrunk on a link can be chosen for establishing a connection. 2.2. EXAMPLE NETWORK Consider the example network shown in Fig. 4 illustrating two paths from node 1 to 5. Let the nodes be connected using three fibers each carrying three wavelengths and two time slots per wavelength. Also assume that nodes 1, 3, 6, and 7 are wavelength level grooming nodes; nodes 2 and 5 are timeslotlevel grooming nodes; and node 4 is a fullgrooming node. Wavelength level grooming nodes view the link as three wavelength trunks (denoted by , , and ) with six channels in each, time slotlevel grooming nodes view a link as two time slot trunks (denoted by and ) with nine channels in each, and a fullgrooming node views a link as one trunk (denoted by ) with 18 channels. Fig. 5 shows the expanded view of the network indicating the different trunks at the nodes. For example, consider trunk W1 of node 1 and trunk T1 of node 2. The number of channels in the link 12 (denoted by ) that belongs to both the trunks is 3. The channels are ( l12,1,1,1), (l12 ,2,1,1) and (l12,3,1,1), each channel belonging to a distinct fiber. The arrow connecting trunkW1of node 1 to trunk T1 of node 2 indicates the number of free channels that belong to both the trunk definitions. A value of 3 indicates that all the channels belonging to both the trunk definitions are free. Assume that the network is observed at some instant of time during its operation and the channel occupancy in the links are known. Let Availability denote the availability of the channel: denoted by 0 if occupied by a connection, 1 if the channel is free. Chapter 3 MICRON FRAMEWORK The MICRON framework developed in this paper addresses in detail the information representation on a link, aggregation of link information to obtain the path information, selection of a path, and assignment of subtrunks inWDMgrooming networks with heterogeneous grooming capabilities. Each of these steps are described in detail in the following subsections 3.1 Link Information A link connecting nodes I and j is represented by a matrix Fig 3.1.1 Each element lxy denotes a certain property about the channels in the link that belong to ijxy. Consider the link 12 in the example network shown in Fig. 4. Node 1 views each wavelength as a trunk, and hence has 3 trunks. Node 2 views each time slot as a trunk, and hence has 2 trunks. Therefore L12, is a 3Ãƒâ€”2 matrix . The matrix can denote different properties of the channels. We discuss two specific examples in this paper. Case 1: Connectivity: In this case, every element lxy of the matrix Lij is denoted by 1 if the total number of free channels that belong to ijxy has a capacity of at least B. The matrix is defined as Where 1=x=Ki and 1=y=Kj . The matrix representation for different links are shown in Fig. 7 that correspond to the network state shown in Fig. 5. Note that the matrices obtained using the available subtrunk capacity also contains the information of the matrices representing connectivity information. Depending on the level of information required, different matrix representations may be employed 3.2. Path Information The information about a certain path from a node to that are not physically connected by a fiber is obtained by combining the link information along the path. The matrix representation for a path is defined in a manner similar to that of a link. A path matrix from node i to k through j is obtained as a matrix multiplication of individual path segments Pij and Pik as Fig . 3.2.1 Expanded view of the network with channel occupancy information Fig 3.2.2. Link information matrices indicating if there is at least one free channel in a subtrunk. Fig 3.2.3. Link information matrices indicating no of free channels in a subtrunk. We employ a generalized version of matrix multiplication to compute the path matrix. An element Pxy ij(the superscript denotes the matrix to which the element belongs to) is obtained as Fig 3.2.4 Operations on matrix elements The operators and , denoted as a tuple ( , ) may be defined in different combinations so that several meaningful results are obtained. It may be observed that when is integer multiplication and is integer addition, the above equation denotes the traditional matrix multiplication. To illustrate the significance of different operators, we take the two example matrix representations of links and apply two different set of operators to obtain different information from the network. Case 1: Arithmetic Operators: In this case, we consider integer multiplication and integer addition as the operators for and , respectively. Consider the matrix representation shown in Fig. 3.2.6. Applying the operator on the path 12345, we obtain the path information matrix as Fig 3.2.6 Path information matrix showing no of trunk assignments An element of the above matrix denotes the number of distinct subtrunk selections available from trunk of node 1 to trunk of node 5. For example, there are four paths that can start at trunk W1 of node 1 and end at trunk T1 of node 5. These four trunk assignments on the path are represented as a set of tuples containing node numbers and trunk identifier on that node. The four possible trunk assignments on the path, denoted by P1 through P4are The existence of trunk assignment for other trunk pairs can be easily verified from Fig. 3.1.1. Consider the link information as shown in Fig. 3.2.3. Applying the operator on these matrices results in the path information matrix for path 12345 as Fig 3.2.7 Path information matrix showing no of free channels An element Pxy of the above matrix denotes the number of possible channel assignment combinations on the path that start at a certain trunk x at node 1 and end at a trunk y at node 5. On every subtrunk on the path the number of ways of assigning a channel is the same as the number of channels in the subtrunk. Hence, the number of possible channel assignments on a specific trunk assignment on the path is the product of the number of free channels on the assigned subtrunk on every link. The number of possible channel assignments on the four possible trunk assignments P1 through P4 that start the connection at trunk at node 1 and end at trunk T1 at node 5 are 192, 72, 192, and 48, respectively, adding up to 504 possible ways of channel assignment Case 2: Selection Operators: In this case, we assume that the operator indicates the minimum of the two operands while the operator indicates the maximum of the two operands. Applying this set of operation to the matrix representation in Fig.3.2.6, we obtain the matrix representation for the path 12345 as Fig. 3.2.8 Matrix indicating existence of channel allocation scheme The elements of this matrix indicate the existence of a channel allocation scheme for call requiring one channel capacity that would start at trunk x at node 1 and end at trunk y at node 5. The matrix in 3.2.8 may be obtained from the matrix in 3.2.6 or 3.2.7 by replacing every nonzero element in the matrix by 1. Applying this set of operation to the matrix representation in Fig. 3.2.7, we obtain the maximum capacity that can be routed from node 1 to node 5 without splitting the connection. The matrix representation for the path is obtained as Fig 3.2.9 Matrix indicating maximum capacity data that can be sent without splitting. 3.3. TwoPass Approach to Connection Establishment When a call arrives at a node, a request for connection establishment is sent along a set of candidate paths. The connection establishment is carried out in two passes: Forward pass and Reverse pass . During the forward pass, the connection request is forwarded to the nodes along the path with a vector, called the path information vector (PIV). The path information vector at a node k for a path with source i and destination k, denoted by Vik is of dimension 1Ãƒâ€”Kk. Vik is obtained as a product of the path information vector at the source node and the information matrix of the path connecting nodes i and k Eqn no 3.3.1 where denotes the path information matrix at the source node which is always set as a unit row vector. Assume that the path from node i to k passes through node j . Rewriting the above equation gives the relationship between the PIV vectors at node j and node k The matrixvector multiplication employed above is similar to the generalized matrix multiplication proposed earlier in the paper with the operator tuple(,) . The elements of PIV at a node indicates specific properties about paths that end at a certain trunk. For example, if the link information matrix represented in Fig. 6 and operator(Ãƒâ€”,+) are employed, then the resulting PIV at each node indicates the number of possible trunk assignments on the path that would terminate the connection on a certain trunk at that node. During the forward pass of the connection establishment, an intermediate node j on the path from source i may forward either the path information matrix Pij to its neighboring node or the path information vector Vij . Forwarding the latter has the advantage of minimizing the amount of information forwarded. Note that the reduction in information exchange will be significant when the number of trunks at a node is large. Hence, we assume that only the path information vector is forwarded to the successive node along the path and will be employed to assign a subtrunk on the reverse pass. 3.4. Path Selection The path information vector may be used to select a suitable path for a given source destination pair. For example, consider the two paths from node 1 to 5: 12345 and 1675. Employing the matrix information represented in Fig. 6 and operator (,), we obtain the path information vector for the two paths as With these matrices known at the destination, one could employ different comparison algorithms to select a path. For example, the total number of trunk assignments possible on a path is obtained by summing all the elements of the matrix. A path that has the maximum value for this metric can be chosen for establishing the connection. If the matrix representation in Fig. 7 and operator (max,min) are employed, the path information vector for the two paths are obtained as It can be observed that the path 1675 can route a call for three channel capacity request without splitting, while the other path cannot. Hence, if traffic requirements in the network are diverse and destinationbased pathselection is employed, then the path 1675 would be chosen so as to minimize the blocking at that instant of time. Different metrics such as hoplength, delay, cost, etc. that could be included for link state vector and possible path selection schemes for WDM grooming networks are discussed in [24]. The path information vector can also be extended to include multiple metrics in order to select a path. The abovemechanism to select a path may be employed in networks where alternate path [19] or least loaded path [20], [21] routing algorithms are employed, where every sourceâ€œdestination pair has a set of alternate paths. In alternate path routing, the paths are probed one by one sequentially for available capacity and the first available path. In the latter, all the paths are probed for available capacity and the least loaded path is chosen. In both these approaches, a node in the network need not be aware of the grooming capabilities at other nodes. 3.5. Path Computation If paths have to be computed based on the uptodate network status, then the Dijkstraâ„¢s shortest path algorithm may be extended to operate on the PIV and some additional metrics such as hop length, cost, etc. These metrics may be collected at the nodes through a linkstate protocol [23]. The centralized version of the working of Dijkstraâ„¢s algorithm using the path information vector (employing available capacity) and hop length is shown in Fig. 8. Steps 1 through 4 are initialization steps. In step 5, a selected node is marked. The neighbors of the nodes are updated with the new available capacity vector and path length values in steps 9 through 14. The vectors are updated if the new path has: 1) a shorter path length (step 10); or 2) if the path lengths are same, then the path is replaced with a probability 1/Cj , where Cj denotes the number of Fig. 3.5.1. Steps involved in path computation using Dijkstraâ„¢s algorithm operating on the path information vector and hop length. The algorithm attempts to select the shortest path among those that are available, referred to as the Available Shortest Path (ASP) algorithm paths encountered so far with the same hop length. A function that maps a vector to a scalar is employed to compare the PIVs. With such an approach, the routing algorithm makes a collective decision regarding all the trunks at a node. One such approach is to compare the maximum value of an element in the path information vector. If the maximum available capacity of a trunk exceeds the capacity of the request, then the connection can be established on that path. Steps 9 through 14 select the shortest path among the set of available paths. Step 15 identifies if there are any unmarked nodes left. If no such nodes are present, then the algorithm terminates. Otherwise, steps 16 through 23 select a node for marking. A node is selected must have an available path from the source and its path length must be the smallest among all such nodes. Step 24 initializes the selected node i as and proceeds with updating its neighbors. The algorithm in Fig. 8 is similar to the Dijkstraâ„¢s algorithm for a scalar metric, except that at every step of the algorithm a matrixvector multiplication is carried out. The complexity of the Dijkstraâ„¢s shortest path algorithm for a scalar metric is Fig. 3.5.1. Path information vector computed at the nodes along the path 12345. O(logN +L).The complexity of matrixvector multiplication of a link connecting two nodes with Kand Kâ„¢trunks isO(KKâ„¢) . Let KKâ„¢indicate the average over all links the product of the number of trunks at the nodes connected by a link. The complexity of the algorithm in Fig. 8 is O(KKâ„¢(NlogN + L)). 3.6. SubTrunk Assignment At the end of the forward pass, the destination node has the path information vector for the different probed paths and selects a path based on a certain path selection algorithm. Once a path is chosen, a subtrunk has to be selected on every link of the path in order to complete the channel establishment. The subtrunk assignment is carried out as follows: 1) the destination node first selects the trunk at its node where the connection would terminate; and 2) every node along the path selects the output trunk at its previous node. If a link connects node and then the node selects the output trunk at node , hence the subtrunk assignment on the link . Consider the information matrix represented in Fig. 6 and operator . The path information vectors obtained at different nodes are shown in Fig. 9. The trunk assignment to end the connection at the destination node may be made using the path information vector. Several trunk selection schemes such as firstfit, bestfit, random, etc. may be employed. In this paper, we illustrate the random subtrunk assignment. Let denote the trunk that is chosen to accommodate the connection at node . In order to select a subtrunk on link , a ratio vector is computed at node . The vector, denoted by , is obtained as the product of the vector at the path information vector previous node, and the column vector of the link information matrix corresponding where denotes the transpose of the column vector corresponding to the column of the matrix and the operator denotes the elementwise operation on the row vectors. Again, one could define different operators depending on the construction of the information matrix. Since the input trunk at node is decided, the choices of output trunk at node is also dictated by the channel occupancy of the channels that fall within . The output channel at node can be selected in various ways using the ratio vector. During the reverse pass, a subtrunk is allocated on the path. As node 5 is the destination, it selects a trunk for the connection to terminate.We illustrate the random subtrunk assignment here. We assume that the operator denotes integer multiplication. The PIV at node 5 indicates that there are 20 possible subtrun assignments with each trunk being able to terminate 10 each. Hence, one of the two is chosen with equal probability. In general, if subtrunk assignments are possible on the path that would terminate the connection at the destination node at trunk then the trunk is chosen with a probability ,where denotes the number of trunks at the destination node In the example considered here, one of the two trunks is selecte with equal probability. Assume that the trunk chosen The node also selects the output trunk at its previous node. In order to select this, the ratio vector is computed a In this case, as only one output trunk is available, it is selected. Hence, on link 45, a channel that belongs to trunk of node 4 and trunk of Node 5 is selected. Node 5 confirms the selection of output trunk to Node 4 during the reverse pass in the network. As the trunk assignment for the connection at node 4 is decided by node 5, node 4 chooses the output trunk at node 3 by computing a similar ratio vector a(18) vector denotes the selection ratio for the three output trunks at Node 3. Note that although there are 5 possible paths that could end at trunk at Node 3, there are no free channels on link 34 that fall within trunk of Node 3 and trunk of Node 4. This information is reflected in the selection ratio vector as a zero entry corresponding to the ratio for trunk W3. Hence, trunk W1 or W2 is selected with equal probability. Assume that trunk W2 is selected in this case. At Node 3, the vector is computed as(19) Node 3 selects the output trunk at Node 2 in the ratio of 2:3, i.e, trunk is selected with a probability of 0.4 while trunk is selected with a probability of 0.6. Assume that trunk is chosen. At Node 2, the vector is computed as (20) One of the trunks or is chosen with equal probability. Assume that is chosen. This selection is sent to node 1 completing the subtrunk assignment. Now, the path established for the connection can be written as a set of nodetrunk pair assigned at each node on the path or equivalently as a set of link and subtrunks pair on the path Any channel belonging to the subtrunk assigned at a link can be chosen for establishing the channel as every node has fullpermutation switching capability within a trunk. It can be observed that such a trunk selection strategy selects with uniform probability a possible subtrunk assignment on the path. For example, if we employ information matrix shown in (7), operator , operator set to multiplication, and random channel assignment within a chosen trunk on a link, then the resulting channel assignment algorithm selects a channel uniformly from the set of all possible channel assignments possible on the path. Several other trunk selection approaches can be employed, such as selecting the trunk that has the minimum or maximum value in the selection ratio vector, which would have effect similar to packing or spreading the connections across the available subtrunk assignments in the path. In order to implement a firstfit subtrunk assignment, the first available trunk is chosen from the ratio vector. The framework may then be used to implement and evaluate the performance of the different path selection and subtrunk (hence, channel) assignment schemes on different network architectures. . 3.7. Modeling Blocking Trunk Switches The framework assumes that the trunk switch employed at every node has fullpermutation switching capability. This implies that any channel on a trunk on a link can be switched to any other channel on any output link but within the same trunk. In such a scenario, a connection cannot be accommodated on a trunk only due to lack of capacity on the trunk and not due to switching. Alloptical implementation of fullpermutation switches would require a large number of stages of switching, and hence may not be practical due to power and synchronization issues. Hence, simpler but blocking switching architectures that involves fewer stages of switching may be considered for implementation. For example, consider the node architecture shown in Fig. 10. The node is assumed to have three incoming and outgoing links. Different trunks are demultiplexed from the link. The trunks from different links are then switched using a channelspacechannel switch. The first and the third stages of switching have fullchannel interchangers (FCI) that can convert any channel on the trunk on a link to any other channel on the same trunk on the same link. The FCI stages at the input and the output of the node allows the node to operate in an autonomous manner. Connections are assigned channels on the links. These channels are mapped by the FCI to channels within the node. The node could rearrange the connections for switching at the input and output of the switch as long as the channels allocated to the connections on the links (before the first FCI stage and after the last FCI stage) are retained. Fig. 10. Channelspacechannel switching architecture at a node in a TSN. For example, consider a wavelengthlevel grooming node in a WDM/TDM network. Assume that the link has three fibers, three wavelengths per fiber, and two time slots per wavelength. A wavelengthlevel grooming node would view the link as three trunks with six channels in each. The channelspacechannel architecture would refer to a timespacetime switch employed for every wavelength for a wavelengthlevel grooming node. Consider a channel that belongs to an input link, say (l,f,w,t)in . At a wavelength level grooming node, the channel is mapped in the first stage of switching to another channel, say (l,f,w,t)1 , where lin and win=w1 . The space switch maps the channel (l,f,w,t)1 to another channel (l,f,w,t)2 , where l1l2 ,f1=f2 ,w1=w2 , and t1=t2. The last stage of FCI maps the channel(l,f,w,t)2 to (l,f,w,t)out where l2 =lout and w2=wout . It is to be noted that the channelspacechannel switching employed here is a blocking switch. Therefore, the number of channels that could be switched from an input link t o an output link could be less than the minimum number of free channels on the links. Every node maintains a vector for every input and output link pair at the node, referred to as switching constraint vector. This vector at a node has a dimension 1Ãƒâ€”ki , denoted by . Every element in this vector denotes the number of channels that could be switched from input link to . Now, consider a path from node to through .Assume that node employs channelspacechannel switching architecture. The path information vector that is forwarded from node to node , denoted by (21) where refers to an elementwise operator on the two vectors. This operator could be chosen in many ways depending on the information collected on the path. For example, if the available capacity is stored in the matrices and the operator set is employed to identify the maximum capacity that could be routed on the path without splitting the connection, then the operator can be made to be elementwise minimum. Thus, information on a path could be obtained where intermediate nodes need not have fullpermutation switching capability. It is worth noting at this point that the FCI at the input and output stages of switching eliminates channelcontinuity constraint within a trunk. Therefore, it is sufficient to carry information about the number of channels that could be switched by the node. However, if the FCI stages are not present, then exact information on which channels can be switched must also be considered. In such a case, the elements in the switching constraint vector and the link information matrix will be matrix or( vectors) themselves. 3.8. Modeling TrunkRouting Networks The framework for connection establishment assumes that switches employed for every trunk at a node has the capability of switching individual channels across different links but within the same trunk. In other words, different channels on a trunk at a link can be switched to channels on different links but in the same trunk. However, some switches may have further restricted switching capability in which an entire trunk is switched from one link to another. For example, consider a wavelengthrouted WDM/TDM network. A wavelengthrouting node that does not employ wavelength conversion would switch an entire wavelength from one link to another. Another example of such a nswitching node is a photonic slot routing node [25] that would switch all the wavelengths in a time slot from one link to another. Therefore, either all or none of the channels are switched from one link to another. Such a node in which either all or none of the channels are switched from one link to another are referred to as trunkrouting nodes. In order to model a trunkrouting node, we employ switching constraint vector. The individual elements are computed depending on whether node is a source, destination, or an intermediate node. If node is a source, then the input link refers to the link through which the local traffic is inserted. In such a case, the information corresponding to a trunk in the switching constraint vector is set to 1 if the node is allowed to transmit on the corresponding trunk, otherwise set to 0. If node is the destination node, then the elements of the switching constraint vector are set to 1 if the node is allowed to receive on the specific trunk. If node is an intermediate node, then the value corresponding to trunk is set to 1 under any of the following conditions: 1) trunk is routed from link to ; and 2) node can receive on trunk from link and transmit on trunk on link . Otherwise, it is set to 0. It is to be noted that in the case that trunk from link is routed to a link other than , the value is set to 0. The switching constraint vector is maintained at a node and need not be exchanged with other nodes in the network. Upon receiving a connection establishment request, the node computes its path information vector as described in the earlier section. Before forwarding it to the neighboring node in the network, the path information vector and the switching constraint vector are combined using elementwise multiplication. The resultant vector denotes the updated path information vector that also takes into account the switching capability at a node. Consider the example network shown in Fig. 5. Assume that node 5 is photonic slot routing node and that the trunk T1 on link 45 is routed to another link (not shown in figure). Therefore, node 5 cannot receive information on trunk T1. Assume that node 5 is receiving information on trunk T2. This information is available at node 5 as the switching constraint vector, denoted by [0 1]. Consider the path information vector obtained on the path 12345 at Node 5 using connectivity information and employing the operator set . The path information vector [10 10] indicates that there are 10 possible trunk assignments that would end on trunk T1 and T2 each. When this information is combined with the switching constraint vector at node 5, we Fig. 11. Path information vector obtained along the path 12345 at different nodes when the request is initiated by node 5. Obtain the resultant vector as [0 10] indicating that there are no possible trunk assignments that could end on trunk at node 5. 3.9. Destination Initiated Connection Establishment The sections thus far assumed that the connection request is initiated by the source node. However, in some scenarios, such as videoondemand, the connection request may be initiated by the destination. In destinationinitiated communications, the connection establishment may be performed in two ways: 1) threepass mechanism or 2) twopass mechanism. In the threepass mechanism, the receiver sends a connection request to the source during the first pass. In the second pass, the source node initiates a connection request to the destined receiver. In the third phase, the channel establishment is performed on the reverse path. The connection establishment in such a case could be performed as described in the previous subsections. In the twopass mechanism, the path information from the source to destination is captured when the connection request is sent by the receiver to the source as the first phase. In the second phase, the source decides a path and the channel assignment is performed along the path from the source to destination. It is to be noted that the path information collected in the first pass is for a directed path from the source to destination, although the connection request is sent from the destination to the source. Consider a path from node I to node k passing through node j . Let V* jk denote the path information vector at node j for the path from node j to k . The superscript of * denotes that this vector is computed at node j . Let Pij denote the path information matrix from node I to j node . The path information vector at node I from node i to node k , denoted byV*ik , is computed as We illustrate the twopass mechanism here with an example. Consider the network in Fig. 4. Assume that node 5 initiates a connection request. Node 5 initializes its PIV as . Assume that the link information matrices represent the connectivity information and arithmetic operator (+, Ãƒâ€” ) set is used for computing the PIVs. The PIVs computed at various nodes as the request traverses from node 5 to node 1 are shown in Fig. 11.V*15 denotes the PIV for the path 12345. An element of the PIV computed at a node indicates the number of distinct subtrunk assignments possible on the path from that node to the destination. More than one request may be sent from the destination along a candidate set of paths and the source node may select a path depending on the path selection algorithm employed in the network. Once the path is selected Fig. 12. Example network where node 0 is the source of a multicast connection that is destined to nodes 5 and 7. ig. 13. Expanded view of the network where node 0 is the source of a multicast connection that is destined to nodes 5 and 7. The subtrunk assignment starts at the source node and proceeds in the forward direction of the path in a way similar to that explained in Section IVF. The selection ratio vector at node for a path from node to node through node is obtained as where Lij (x i) is the row vector corresponding to the row of x I of the matrix . The techniques described in earlier sections to account for blocking nature of the switch at a node and trunkrouting nodes may be combined with the above PIV computation of destination initiated requests as well. 3.10. Multicast Tree Establishment Multicast connection establishment is accomplished using the destination initiated request approach mentioned above. Consider the network shown in Fig. 12 in which node 0 is the multicast source and nodes 5 and 7 are the destination. Fig. 13 shows the expanded view of the network. The multicast tree that needs to be established spans all the links and requires node 1 to route the incoming traffic along two paths. In order to facilitate multicast connections, the incoming signal must be copied and transmitted along two different paths. In order to provide a costeffective solution, the copying may be restricted within a trunk. In such a case, the trunk in which the connection terminates at node 1 must reach all the destinations. In MICRON, such a multicast path is established in three steps: 1) the multicast request is forwarded along the tree; 2) the path information vector on the reverse path is obtained; and 3) the subtrunk assignment is made along the forward path. In Step 1, node 0 sends the request along the tree to nodes 5 and 7. Node 1 is aware of the branching, and hence will merge the two path information vectors for the two destinations. The PIV for the path 12345 at node 1 is obtained as shown in Fig. 11 as [8 8 4]. Similarly, the PIV for the path 167 at node 1 is obtained as [1 0 1]. It has to be noted that as the PIV is computed at node 1, the vectors along different paths will be of the same dimension (same number of columns, corresponding to the number of trunks at node 1) although the destination nodes may have different switch architectures. From the PIVs it is clear that node 5 may be reached from node 1 by starting on any of the trunks. However, node 7 may be reached only if the connection at node 1 is routed along trunk or The tree information vector (TIV) at node 1, denoted by is obtained by combining the path information vectors as where represents an elementwise operation. When the nodes employ intratrunk copying facility, the elementwise operator must satisfy one property: if any of the element is zero, the result must be zero. There is more than one operator that may satisfy this constraint. In this example, we use integer multiplication. The TIV at node 1 is obtained as [8 0 4]. The TIV at node 0 is computed as The TIV at node 1 indicates that the multicast tree may be established starting at either trunk. However, the selection of a trunk will affect the selection ratio vector computed at node 1. For example, if trunk T1 is selected at node 0, the selection ratio vector at node 1 will beR*1{5,7} = [8 0 0], thus forcing the multicast connection to be established through trunk W1 at node 1. Similarly, if trunk T2 is chosen at node 0, the multicast connection will be established using trunk W3 at node 1. The techniques for modeling blocking switches and trunkrouting switches may be combined with the multicast connection establishment techniques as well. 3.11. Reductions to Simpler Networks The MICRON framework applied to a WDM grooming network where all the nodes in the network are wavelengthlevel grooming nodes results in the link information matrix being a diagonal matrix. In such a scenario, the matrix can be reduced to a vector, thus simplifying the operations to be performed to obtain path information. Such a reduction of the MICRON framework has been adopted in [26] and [27]. In the case of networks where all nodes are equipped with fullgrooming capability, hence every node views each link as one trunk, the MICRON framework can further be reduced to a single metric. The proposed methodology then reduces to the wellknown information aggregation methods established in traditional networks. The framework may be easily extended with other metrics such as delay, cost, etc. to implement a plethora of routing and channel assignment algorithms based on the information collected using linkstate protocols in WDM grooming networks with heterogeneous grooming capability. Chapter 4 CONCLUSION In this paper, we develop a framework for connection establishment in a WDM grooming network with heterogeneous switching architectures.We illustrate with examples the various information that could be collected from the links and various operators that could be used to obtain information along a path. The information collected may be used to select a path dynamically depending on the network status. We complete the framework by providing a generic channel assignment procedure that could be employed to implement different channel assignment schemes. REFERENCES [1] D. K. Hunter and D. G. Smith, New architectures for optical TDM switching, J. Lightw. Technol., vol. 11, no. 3, pp. 495â€œ511, Mar. 1993. [2] H. F. Jordan, D. Lee, K. Y. Lee, and S. V. Ramanan, Serial array time slot interchangers and optical implementations, IEEE Trans. Comput., vol. 43, no. 11, pp. 1309â€œ1318, Nov. 1994. [3] J. Yates, J. Lacey, and D. Everitt, Blocking in multiwavelength TDM networks, in Proc. 4th Int. Conf. Telecommunication Systems, Modeling, and Analysis, Nashville, TN, Mar. 1996, pp. 535â€œ541. [4] A. L. Chiu and E. H. Modiano, Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks, J. Lightw. Technol., vol. 18, no. 1, pp. 2â€œ12, Jan. 2000. [5] O. Gerstel, R. Ramaswami, and G. H. Sasaki, Costeffective traffic grooming in WDM rings, IEEE/ACM Trans. Networking, vol. 8, no. 5, pp. 618â€œ630, Oct. 2000. [6] J. Wang, W. Cho, V. R. Vemuri, and B. Mukherjee, Improved approaches for costeffective traffic grooming in WDM ring networks: ILP formulations and singlehop and multihop connections, J. Lightw. Technol., vol. 19, no. 11, pp. 1645â€œ1653, Nov. 2001. [7] A. Jarray and B. Jaumard, Exact ILP solution for the grooming problem in WDM ring networks, in Proc. IEEE Int. Conf. Communications (ICC), Seoul, Korea, May 2005, vol. 3, pp. 1708â€œ1712. [8] H. Huang and J. A. Copeland, Hybrid wavelength and subwavelength routed optical networks, in Proc. IEEE GLOBECOM, San Antonio, TX, Nov. 2001, vol. 4, pp. 25â€œ29. [9] P. Prathombutr, J. Stach, and E. K. Park, An algorithm for traffic grooming in WDM optical mesh networks, in Proc. IEEE Int. Conf. Computer Communications and Networks (ICCCN), Dallas, TX, Oct. 2003, pp. 405â€œ411. [10] J. Hu and B. Leida, Traffic grooming, routing and wavelength assignment in optical WDM mesh networks, in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 495â€œ501. [11] C. Xin, C. Qiao, and S. Dixit, Traffic grooming in meshWDMoptical networksâ€Performance analysis, IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1658â€œ1669, Nov. 2004. [12] W. Yao and B. Ramamurthy, Rerouting schemes for dynamic traffic grooming in optical WDM mesh networks, in Proc. IEEE GLOBECOM, Dallas, TX, Nov.â€œDec. 2004, vol. 3, pp. 1793â€œ1797. [13] A. Mokhtar and M. Azizoglu, Adaptive wavelength routing alloptical networks, IEEE Trans. Networking, vol. 6, no. 2, pp. 197â€œ206, Apr. 1998. [14] H. Zang, J. Jue, L. Sahasrabuddhe, R. Ramamurthy, and B. Mukherjee, Dynamic lightpath establishment in wavelengthrouted WDM networks, IEEE Commun. Mag., vol. 39, no. 9, pp. 100â€œ108, Sep. 2001. [15] G. Li and R. Simha, On the wavelength assignment problem in multifiber WDM star and ring networks, IEEE/ACM Trans. Networking, vol. 9, no. 1, pp. 60â€œ68, Feb. 2001. [16] B. Wen and K. M. Sivalingam, Routing, wavelength and timeslot assignment in time division multiplexed wavelengthrouted optical WDM networks, in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 1442â€œ1450. [17] K. Zhu, H. Zhu, and B. Mukherjee, Traffic engineering in multigranularity heterogeneous WDM mesh networks through dynamic traffic grooming, IEEE Network, vol. 17, no. 2, pp. 8â€œ15, Mar.â€œApr. 2003. [18] H. Zhu, K. Zang, K. Zhu, and B. Mukherjee, A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks, IEEE/ACM Trans. Networking, vol. 11, no. 2, pp. 285â€œ299, Apr. 2003. [19] L. Li and A. K. Somani, Fiber requirement in multifiber WDM networks with alternatepath routing, in Proc. Int. Conf. Computer Communications and Networks (ICCCNâ„¢99), Boston, MA, Oct. 1999, pp. 338â€œ343. [20] E. Karasan and E. Ayanoglu, Effects of wavelength routing and selection algorithms on wavelength conversion gain in WDM optical networks, IEEE/ACM Trans. Networking, vol. 6, no. 2, pp. 186â€œ196, Apr. 1998. [21] C.F. Hsu, T.L. Liu, and N.F. Huang, Performance of adaptive routing strategies in wavelengthrouted networks, in Proc. IEEE Int. Conf. Performance, Computing, and Communications, Phoenix, AZ, Apr. 2001, pp. 163â€œ170. [22] R. Srinivasan and A. K. Somani, A generalized framework for analyzing timespace switched optical networks, IEEE J. Sel. Areas Commun.: Special Issue on WDMBased Network Architectures, vol. 20, no. 1, pp. 202â€œ215, Jan. 2002 Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



