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 het-erogeneous 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 Low-Energy Adaptive Clustering Hierarchy
2.4.2 Power-Efficient Gathering in Sensor Information Systems
2.4.3 Threshold-Sensitive 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 ever-increasing 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 (OC-768) on a wavelength. However, the user requirements are of sub-wavelength capacity, typically ranging from 155 Mb/s (OC-3) to 622 Mb/s (OC-12), and rarely in the range of a few gigabits per second. Hence, alternatives for provisioning of sub-wavelength traffic in WDM networks has received significant attention in the recent past. One approach to provisioning sub-wavelength traffic is to divide a wavelength into time slots that would allow multiple traffic to be time multiplexed on the wavelength. transmission speeds in long-haul 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 multi-wavelength multi-time slot or multi-code 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]. All-optical 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 fiber-Bragg gratings. WDM grooming networks can be classified into two categories [3]: dedicated-wavelength grooming (DWG) networks and shared-wavelength 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 almost-full 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 sub-wavelength traffic and therefore require sophisticated routing algorithms based on up-to-datenetwork 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 wavelength-level 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 full-grooming node. As the present day optical technology is not mature enough to make routing decisions at run time, wide-area optical networks are expected to remain circuit-switched in nature for the near future. Operating a circuit-switched wide-area 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 connection-oriented 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 page 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 fixed-path 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 page 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 multi-fiber wavelength-routed 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 (mixed-integer 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 large-scale 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 sub-wavelength traffic in the network to optimize the wavelength utilization. Connection establishment has been extensively studied in the context of wavelength-routed 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 time-slot assignment algorithms for a TDM-based 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 page 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 graph-based model in which every node is replaced by wavelength-nodes, where denotes the number of wavelengths per fiber. A fiber page link between nodes and is replaced by auxiliary links, each connecting a specificwavelength-node of to a specificwavelengthnode of . If a node has full-wavelength conversion, then links between all wavelength-node pairs at node are added. Such a graph model translates a WDM network with nodes, links, and wavelengths per page 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 graph-based model may be employed only as a centralized mechanism to identify paths, hence suited for networks that employ link-state protocols. If the networks employ alternate path routing [19] or least-loaded 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 low-rate traffic to a high-capacity 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 page 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 page 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 4-tuple,(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 page link is defined as a collection of a particular occurrence of time slot across successive frames. Hence, the number of channels in a page link is the same as the number of slots in a frame, . Each channel is also represented by a 4-tuple,
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 two-level network model in which every page link in the network is viewed as multiple channels. A node in a TSN groups the channels with similar characteristics in a page 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 page 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 page 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 page 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 wavelength-level grooming node. If full-wavelength conversion is permitted, but not time slot interchange, then each time slot on the page 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 slot-level grooming node. If both full-wavelength conversion and time slot interchange are permitted, then the entire page link is treated as one trunk with channels, as shown in
Fig. 2. Possible grouping of channels in a page 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 page 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 single-fiber wavelength-routed WDM network employing wavelengths can be modeled as trunks with one channel per trunk. A multi-fiber multi-wavelength wavelength-routed network with fibers and wavelengths with no wavelength conversion can be viewed as trunks with channels per trunk. If full-wavelength conversion is available, then a page 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 page 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 trunk-continuity constraint at a node”i.e., a channel in a trunk on a page 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 full-permutation 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 page link connected to it as a set of trunks each containing channels. Let denote the channels on a page link that fall within trunk at node . Let denote the channels on page 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 sub-trunk. 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 page link can be switched to the successive page 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 sub-trunk 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 sub-trunk on every link. Hence, a connection in a network is represented by a sequence of page link and sub-trunk 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 sub-trunk on a page 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 time-slot-level grooming nodes; and node 4 is a full-grooming node. Wavelength- level grooming nodes view the page link as three wavelength trunks (denoted by , , and ) with six channels in each, time slot-level grooming nodes view a page link as two time slot trunks (denoted by and ) with nine channels in each, and a full-grooming node views a page 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 page link 1-2 (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 page link information to obtain the path information, selection of a path, and assignment of sub-trunks inWDMgrooming networks with heterogeneous grooming capabilities. Each of these steps are described in detail in the following subsections
3.1 Link Information
A page 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 page link that belong to ijxy. Consider the page link 1-2 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 sub-trunk 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 page 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 sub-trunk.
Fig 3.2.3. Link information matrices indicating no of free channels in a sub-trunk.
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 1-2-3-4-5, 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 sub-trunk 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 page link information as shown in Fig. 3.2.3. Applying the operator on these matrices results in the path information matrix for path 1-2-3-4-5 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 sub-trunk on the path the number of ways of assigning a channel is the same as the number of channels in the sub-trunk. 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 sub-trunk 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 1-2-3-4-5 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 non-zero 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. Two-Pass 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 matrix-vector 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 page 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 sub-trunk 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: 1-2-3-4-5 and 1-6-7-5. 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 1-6-7-5 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 destination-based path-selection is employed, then the path 1-6-7-5 would be chosen so as to minimize the blocking at that instant of time. Different metrics such as hop-length, delay, cost, etc. that could be included for page 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 up-to-date 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 link-state 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 matrix-vector 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 1-2-3-4-5.
O(logN +L).The complexity of matrix-vector multiplication of a page 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. Sub-Trunk 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 sub-trunk has to be selected on every page link of the path in order to complete the channel establishment. The sub-trunk 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 page link connects node and then the node selects the output trunk at node , hence the sub-trunk assignment on the page 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 first-fit, best-fit, random, etc. may be employed. In this paper, we illustrate the random sub-trunk assignment. Let denote the trunk that is chosen to accommodate the connection at node . In order to select a sub-trunk on page 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 page link information matrix corresponding
where denotes the transpose of the column vector corresponding to the column of the matrix and the operator denotes the element-wise 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 sub-trunk is allocated on the path. As node 5 is the destination, it selects a trunk for the connection to terminate.We illustrate the random sub-trunk 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 sub-trunk 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 page link 4-5, 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 page link 3-4 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 sub-trunk assignment. Now, the path established for the connection can be written as a set of node-trunk pair assigned at each node on the path or equivalently as a set of page link and sub-trunks pair on the path Any channel belonging to the sub-trunk assigned at a page link can be chosen for establishing the channel as every node has full-permutation switching capability within a trunk. It can be observed that such a trunk selection strategy selects with uniform probability a possible sub-trunk 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 sub-trunk assignments in the path. In order to implement a first-fit sub-trunk 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 sub-trunk (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 full-permutation switching capability. This implies that any channel on a trunk on a page link can be switched to any other channel on any output page 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. All-optical implementation of full-permutation 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 channel-spacechannel switch. The first and the third stages of switching have full-channel interchangers (FCI) that can convert any channel on the trunk on a page 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. Channel-space-channel switching architecture at a node in a TSN.
For example, consider a wavelength-level grooming node in a WDM/TDM network. Assume that the page link has three fibers, three wavelengths per fiber, and two time slots per wavelength. A wavelength-level grooming node would view the page link as three trunks with six channels in each. The channel-space-channel architecture would refer to a time-space-time switch employed for every wavelength for a wavelength-level 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 channel-space-channel switching employed here is a blocking switch. Therefore, the number of channels that could be switched from an input page link t o an output page link could be less than the minimum number of free channels on the links.
Every node maintains a vector for every input and output page 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 page link to . Now, consider a path from node to through .Assume that node employs channel-space-channel switching architecture. The path information vector that is forwarded from node to node , denoted by
(21)
where refers to an element-wise 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 element-wise minimum. Thus, information on a path could be obtained where intermediate nodes need not have full-permutation switching capability. It is worth noting at this point that the FCI at the input and output stages of switching eliminates channel-continuity 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 page link information matrix will be matrix or( vectors) themselves.
3.8. Modeling Trunk-Routing 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 page 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 page link to another. For example, consider a wavelength-routed WDM/TDM network. A wavelength-routing node that does not employ wavelength conversion would switch an entire wavelength
from one page 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 page link to another. Therefore, either all or none of the channels are switched from one page link to another. Such a node in which either all or none of the channels are switched from one page link to another are referred to as trunk-routing nodes. In order to model a trunk-routing 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 page link refers to the page 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 page link to ; and 2) node can receive on trunk from page link and transmit on trunk on page link . Otherwise, it is set to 0. It is to be noted that in the case that trunk from page link is routed to a page 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 element-wise 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 page link 4-5 is routed to another page 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 1-2-3-4-5 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 1-2-3-4-5 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 video-on-demand, the connection request may be initiated by the destination. In destination-initiated communications, the connection establishment may be performed in two ways: 1) three-pass mechanism or 2) two-pass mechanism. In the three-pass 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 two-pass 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 two-pass 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 page 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 1-2-3-4-5.
An element of the PIV computed at a node indicates the number of distinct sub-trunk 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 sub-trunk assignment starts at the source node and proceeds in the forward direction of the path in a way similar to that explained in Section IV-F. 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 trunk-routing 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 cost-effective 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 sub-trunk 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 1-2-3-4-5 at node 1 is obtained as shown in Fig. 11 as [8 8 4]. Similarly, the PIV for the path 1-6-7 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 element-wise operation. When the nodes employ intra-trunk copying facility, the element-wise 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 wavelength-level grooming nodes results in the page 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 full-grooming capability, hence every node views each page link as one trunk, the
MICRON framework can further be reduced to a single metric. The proposed methodology then reduces to the well-known 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 link-state 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, Cost-effective 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 cost-effective traffic grooming in WDM ring networks:
ILP formulations and single-hop 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 sub-wavelength
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 all-optical
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 wavelength-routed 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 time-slot
assignment in time division multiplexed wavelength-routed 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 alternate-path 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 wavelength-routed 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 time-space switched optical networks, IEEE J. Sel. Areas
Commun.: Special Issue on WDM-Based Network Architectures, vol.
20, no. 1, pp. 202“215, Jan. 2002