Optimized Optical Routing
Optimized Optical Routing using Wavelength Division Multiplexing
Every network of workstations involves a medium of communication in between. The network of workstation requires a particular routing algorithm to route various network packets among the machines. Within networks, workstations or machines are considered as nodes within the network topography. While each machine can have a single communication cable connecting it to the rest of the network there may exist a machine that is part of several networks and may be connected to them via more than one cable. The latter example is similar to that of an optical network connection linking large service providing corporations to their clients. Optical fibers can therefore be used like communication cables however they can be multiplexed using wavelength division multiplexers (WDM) to provide multiple channels within each cable. Each channel within each fiber within the network topography is called a lightpath. A packet-based traffic in the network is assumed, such that a packet travelling from its source to its destination may have to multihop through one or more such lightpaths. A complete virtual topography design including various choices for lightpaths will be considered. Furthermore the lightpath routes and intensity of packet flows through these lightpaths will also be considered. However to make sure the problem does not become NP-hard and also to avoid heuristics, the number of sub-variables associated within each node is assumed not to exceed higher than a set amount. By minimizing the average packet hop distance in our objective function and by relaxing the wavelength-continuity constraints (i.e., assuming wave- length converters at all nodes), we demonstrate that the entire optical network design problem can be considerably simplified and made computationally tractable. Minimizing the average packet hop distance is equivalent to maximizing the total network throughput under balanced flows through the lightpaths. The problem formulation can be used to design a balanced network, such that the utilizations of both transceivers and wavelengths in the network are maximized, thus reducing the cost of the network equipment.
INTRODUCTION
Lightpaths are used to carry information between multiple fiber links across various nodes. Within the physical network there exists an architecture, which utilizes wavelength routing switch (WRS) that convert wavelengths within every node of the router. These wavelength converters help increase compatibility among various equipment that use an array of wavelength among devices with different vendors. Integer Linear Programming is one of the suggested methods of optimizing the lightpaths for finding an optimal network design. The formulation to be used is derived from [2] however from the latter source many non-linearity are witnessed moreover in this case the problem will be scaled down and will be approximated using a linear model using several constraints.
Furthermore the objective function is used to minimize the average packet hop distance. This is equivalent to increasing the network throughput, which is a linear objective function. The optical network architecture can be simplified by considering channel capacity C, number of channels (L) and average packet hop distance (H), and approximating network throughput by:
T = CL/H (1)
As a result by minimizing H the network throughput can then be maximized. Similar to [2] we can use Integer linear programming to minimize H. By simplifying the object function the approach will be able to solve network design problems by increasing network throughput. This sort of optimization is based on the architectures such as MONET, AON etc. [1]. These optical network infrastructures use similar wavelength router architectures in products produced by companies such as Tellium, Ciena, and Nortel.
Optimizing of optical transport networks (OTN) has also been tackled from various approaches. In [4] the problem was further readjusted to reflect more parameters by considering the problem as a Multi Objective Ant Colony Optimization (MOACO) to simultaneously optimize the hop count and number of wavelength conversion for a set of unicast demands, considering wavelength conflicts. This way, a set of optimal solutions, known as Pareto Set, is calculated in one run of the proposed algorithm, without a priori restrictions on some objective. However this MOACO algorithm involves a different approach which is even more complicated than classical routing and wavelength assignment (RWA) which utilizes heuristics. Therefore although MOACO approaches seem to obtain more promising results than heuristics, solving a linearized approach to the problem seems more feasible for the approximation designated for this paper.
SYSTEM DESIGN
Most equations and notations are similar to the specifications of designing wide are optical networks as seen in [2].
Problem Statement
Some specifications of the design include a linear objective function, a constraint to bind the lightpath length, a constraint to bind the number of lightpaths in each node to prevent heuristics resolution and a constraint to bind the maximum loading per channel. Several other generalizations will also be incorporated into the study such as limiting the direction of lightpaths to unidirectional lightpaths, multiple lightpaths between node pairs etc.
As previously pointed out unlike “Some principles for designing a wide-area optical network” this study will approximate the design using strictly linear format objective function and optimization by minimization of the objective function. The design can also be further expanded by analyzing the resource budgeting in the optical network design for minimizing the number of transceivers at each node yet maintaining the required light paths. Furthermore Virtual topology reconfiguration can also be added to the design to reconfigure the network to adapt to changing traffic patterns. However to both optimize the lightpaths and maintain optimal network layer path selection both physical layer and network layer need to be analyzed.
Thus the problem becomes a two level decomposition project. One level deals with network layer which manages the routing of packets based on traffic topology, while the other level of the decomposition problem assures optimal lightpath configuration within the physical link layer.
Nomenclature
s,d : Denote source and destination of a packet, respectively.
i,j : Denote originating and terminating nodes, respectively, in a lightpath.
m , n : Denote endpoints of a physical link that might occur in a lightpath.
N : Number of nodes in the network
W : Maximum number of wavelengths per fiber
Pmn : Physical topology denotes the number of fibers interconnecting node m and node n.
?m,nPmn : Denotes the total number of fiber links in the network
dmn : Fiber distance from node m to node n. This notation is expressed at propagation delay (time unit).
D , Dsd : Delay matrix, delay over the shortest path between nodes s and d.
a : Maximum permissible propagation delay between two nodes. (a, 1 ? a ? ?)
Ti : Number of transmitters at node i
Ri : Number of receivers at node i
?sd : denotes the average rate of traffic flow (packets/s) from node s to node d.
C : Capacity of each channel (bits/s)
? : Maximum loading per channel, 0 < ? < 1 (No queuing delays will be considered
Lij : Denotes the number of lightpaths from node i to node j
sdij : Denotes the traffic flowing from node s to node d. Employing Lij as an intermediate link
pijmn : Denotes the number of lightpaths between nodes i and node j being routed through fiber link mn.
Mathematical Model
Objective function
The objective function minimizes the average packet hop distance in the network. This is a linear objective function since the function is a linear sum of variables while ?sd is a constant for a given traffic. The objective function found in [2] is the minimization of average packet delay over the network and it was non-linear compared to the below objective function.
As a result we are minimizing the average packet hop distance within the network. In other words we are choosing a path that connects two nodes by going through minimum number of nodes and choosing the paths within those nodes that have least amount of traffic flowing through them.
Minimize:
Constraints
Constraints (3) and (4) ensure that the number of light paths exiting from each node is limited by the number of transmitters at each node, the same goes for equation (4) where the number of nodes is limited by the number of receivers.
Constraints (5)-(7) are equations that define the routing of lightpaths from the source to destination.
Constraint (5) defines that the sum of the lightpaths between nodes i and j being routed from the end point to the selected node k is equal to the sum of the lightpaths between nodes i and j being routed from the starting point of the link topography to the node selected node k.
In particular equation (6) denotes the sum of the light paths between nodes i and node j being routed starting from i to the endpoint of the physical layer is no more or less than number of light paths between nodes i and j.
As for constraint (7) has the same definition of constraint (6) except it defines the starting point instead of the end point of the physical layer.
Equation (8) ensures that the number of lightpaths flowing through a fiber link does not exceed the maximum number of links per fiber.
Constraints (9) – (11) define similar constraints to that of constraints (5) – (7) however they define the constraints for virtual topography. In particular constraint (9) defines the traffic flowing in between the nodes are equal to average rate of traffic flow between the subscripts.
Bounded constraints
It is quite difficult to utilize monotonicity theorems to this problem to probe boundedness due to the multivariable nature of the problem. It is also evident to see that the problem is not well constrained since an upper bound on the size of the network is never set. Therefore in order to be able to solve the network and obtain results in a fashionable manner the network size must preset given a static traffic matrix to solve for the particular solution.
(14)
(15)
Since the size of the problem can increase drastically with an increase in number of nodes two additional constraints are added.
Equations (14) and (15) are utilized to ensure bounded packet delays in the network. These equations significantly reduce the solution space of the problem and result in a faster convergence towards an optimal solution.
Equation (14) implements the physical topology as a subset of the virtual topology, every link in the physical topology is also a lightpath in the virtual topology, in addition to which there are lightpaths which span multiple fiber links.
Equation (15) is used to restrict the enumerated p variables to be only among those present in K alternate shortest paths from i to j, where K>1 this prevents long and convoluted lightpaths.
Design Variables and Parameters
Due to the nature of the problem the size of the problem will not be defined too large however a set topography is to be designated and from the specific topography the variables and parameters will take shape and form in terms of a designated value.
Li,j : Denotes the number of lightpaths in between nodes i and j. Depending on the designated network topography the number of lightpaths can vary.
: Denotes the traffic flowing between nodes s and d using the Lij as an intermediate virtual link.
: Denotes the number of lightpaths between nodes i and j being routed through fiber link mn.
?sd : Average rate of traffic flow from node s to node d.
The number of nodes and lightpaths will later be bounded to a set amount to avoid heuristics calculations.
Summary Model – Decomposition Scheme
In summary the average packet hop distance in the network will be minimized using the object function. However minimizing the packet hop distance means modifying many other variables within the system. Primarily the overall system is composed of two sub problems. In other words to optimize such system involves solving a non-hierarchical decomposed problem.
The physical layer is composed of the hardware required for optical transmission using WDM. In order to efficiently use a fiber link there can be several lightpaths within each link. These paths are generated by adding transceivers at each end and varying the number of wavelengths within each transceiver. By varying these in turn the average packet hop distance and utilization per transceiver and wavelength is varied. Packet hop decreases with increase in wavelength and transceivers. However as the number of transceivers and wavelengths is reduced the respective utilization per device increases. The higher the utilization the more efficiently the system is running.
The network layer routes the various packets moving along the nodes. In order to further minimize the packet hop and hence increase the network throughput the packet should travel through the shortest path and least “expensive” path. Expense within this context refers to the network delay and the cost of taking that particular route to get from one node to another. Although the two layers seem transparent to one another, there is an underlying effect that the two layers have on one another. As network utilization increases the network throughput decreases. In other words the traffic is also dependent on the network utilization both transceiver and wavelength utilization.
Thus both layers share the network utilization variable and hence must be accounted for both separately and in parallel. Therefore each layer can be optimized separately via an iterative manner and each output of the system optimization can be the input for the next iterative step input for the other layer.
TOPOLOGY
In order to decrease the number of variables and equations the problem must be more tractable therefore the number of variables can be reduced by pruning the search space. Pruning is based on tracking a limited number of alternate shortest paths, between source–destination pairs, such that the selected routes are within a constant factor of the shortest-path distance between the given source–destination pair. We assume that traffic flow will only use the lightpaths which interconnect nodes present in these alternate paths.
By considering the shortest paths between nodes (CA1) and (IL) this may result in: CA1-UT-CO-NE-IL or CA1-WA-IL. Therefore the enumerated variables for packet routing are as follows:
The above example is based on the NSFNET’s 16 node physical setup. We can further this case by creating a random traffic matrix for several nodes that represent the bidirectional traffic between any of the edges of every node. Since we are considering cases of bidirectional multichannel edges (lightpaths) any two edges can have anywhere from one edge to multiple edges.
Furthermore since the real network topology consists of a large set of nodes we will consider a small set of 14 nodes to be examined.
Generating Traffic behavior
Introduction
Although traffic matrices change very often the standard deviation within the changes are very low [6]. Due to an increase in MTU (maximum transmission unit) of the application layer, larger amounts of data are being transferred from node to node. This causes the client’s chosen path to the source data to not deviate since the path will be occupied transferring the large data packets to the client.
The internet consists of two different types of clients, short bursts and long transmission. During long transmissions clients are usually routed via the same path within the link layer and network layer. Since the long transmission client will be occupying that path chances are short burst clients will utilize a different path to avoid the channel congestion. Thus due to high MTU and large packet transmission the overall traffic topology changes with a small deviation. Thus a particular traffic matrix will be valid for a longer period. To further analyze how long this period lasts would require access to the MCI traffic analysis backbone which was not granted for the purpose of this project. As a result to generate a traffic matrix a different simulation approach to best approximate realistic data was required.
MIMO Wireless communication simulation
Although optical transmission differs from wireless transmission; they are only different in terms of throughput and packet error resolution. However they are similar in terms of channel utilization [7]. As wireless mobile devices move and distant, the number of sub channels between them reduces thus decreasing the throughput between the devices. This behavior can be directly used to portray an optical traffic network. We can collect traffic samples from wireless devices as they move and apply the change in network utilization and number of channels directly to optical lightpath length and the utilization for the wavelength and transceivers.
This will result in a traffic matrix for the behavior for that particular topology. The traffic matrix can then be used to generate a simulation of a series of nodes and edges. The new topology can then be used to withdraw the transceiver and wavelength utilization. Moreover once the optimal number of wavelength and transceivers is found for the current 14 node example the best utilization will be chosen for the wavelength and transceivers which will then be used within the non-hierarchical decomposition problem to solve the best path for the packet to take.
To obtain the traffic data from mobile devices the Common Open Research Emulator (CORE) is used [8]. CORE is an open source software developed by Boeing for network analysis and emulation:
By mobilizing the 14 nodes we can then begin generating a traffic matrix that reduces and increases the number of channels due to MIMO technology. This traffic matrix is then collected from CORE and implemented into a C program for path optimization of finding lowest latency between each node. The C program then outputs an optimized traffic matrix to Matlab for further optimizing the best path and the best choice of transceiver, wavelengths and utilization using the Matlab optimizer (fmincon).
Network Layer Traffic Topology
At this point part of the output from the first layer of the non-hierarchical decomposition problem for the first iteration is completed and requires optimization to find the best path with the best reconfiguration of number of transceivers, wavelengths and their respective utilization.
Numerical Analysis
The traffic matrix being fed into Matlab is placed into a three dimensional matrix using meshgrid command. This allows for traffic matrices to be placed in for an interval of period of time. For one unit of time the matrix looks like:
| p =
Columns 1 through 19 9 9 9 1 1 1 1 2 2 8 8 8 6 6 6 5 5 5 4 Columns 20 through 38 4 4 4 3 3 3 10 10 10 11 11 11 11 11 12 12 12 13 12 Columns 39 through 40 14 14 |
| q =
Columns 1 through 19 1 3 5 12 2 9 4 8 3 5 6 11 7 9 12 1 4 6 1 Columns 20 through 38 8 6 5 2 8 4 2 7 11 10 14 8 12 14 6 11 13 12 1 Columns 39 through 40 5 11 |
| w =
Columns 1 through 11 6.5510 1.6261 1.1900 4.9836 9.5974 3.4039 5.8527 2.2381 7.5127 2.5510 5.0596 Columns 12 through 22 6.9908 8.9090 9.5929 5.4722 1.3862 1.4929 2.5751 8.4072 2.5428 8.1428 2.4352 Columns 23 through 33 9.2926 3.4998 1.9660 2.5108 6.1604 4.7329 3.5166 8.3083 5.8526 5.4972 9.1719 Columns 34 through 40 2.8584 7.5720 7.5373 3.8045 5.6782 0.7585 7.5720 |
Where p is source node, q is the destination node and w is the corresponding weight calculated from CORE for the first time frame. This is only at one time frame, however to linearize and simplify the problem the data is collected over time, each frame yielding a separate data matrix. The matrices are then wound into a meshgrid and fed into Matlab by sparse-ing the variable matrices. Sparse uses the rows of [i,j,s] to generate an m-by-n sparse matrix {sparse(i,j,s,m,n,nzmax)}. The two integer index vectors, i and j, all have the same length, nnz, which is the number of nonzeros in the resulting sparse matrix S. Any elements of s which have duplicate values of i and j are added together.
Thus creating a traffic matrix evaluated over time (which happens to have a small deviation of weights) that represents the network layer traffic graph. For the particular traffic graph studied above we can generate a biograph within Matlab which creates a graph object using the traffic matrix. All non-diagonal and positive entries in the traffic matrix indicate connected nodes; rows represent the source nodes and columns the sink nodes and edges will display their corresponding minimum weight.
Optimized Traffic Biograph
Once the data has been fed from CORE and configured using (meshgrid and sparse) within Matlab the biograph representation of the network layer can then be displayed. The corresponding traffic biograph for the above example is shown below.
With the above configuration from Network layer we can then move on to the second layer of the non-hierarchical decomposition problem of finding the optimized transceivers and wavelengths for maximum utilization that also yields the best routing path between two nodes and also minimizes the average packet hop distance.
Optimizing Physical link layer
The number of variables and equations in the problem formulation increases very quickly as the number of nodes and links increases. The resource utilization characteristics for the 14 node setup above was studied and averaged over several different configurations emulated by the CORE system.
From constraint (6) it can be deduced that we are limiting the Pmn = Pnm = 1. Thus each physical layer can only carry one fiber; however each fiber can have multiple transceivers and wavelengths. From the traffic matrix obtained it can be assumed that the fraction F of traffic obtained over the period of experimentation is uniformly distributed over the range [0,(C/a)] and the remaining traffic is uniformly distributed over [0,(C×?/a)] where C is the lightpath channel capacity, a is the penalty variable for each fiber node (one or greater) and ? represents the average ratio of traffic intensities between node pairs [2]. This model defined by [2] can provide us with varying characteristics of network patterns.
The corresponding network parameters were set to C=1250, a=20, ?=10, F=0.7, w=0.8, 
=2. With Ti and Ri were assumed to be equal for all nodes, and were allowed values between 4 and 8. W was allowed to take values between 1 and 7.
Once again the using CORE the system is simulated this time the physical link layer is emulated with the above parameters. In this scenario we are using OC-192 connection (9.621504 Gbit/s) and not a wireless network to simulate an optical connection since we are utilizing the previously obtained traffic matrix and MIMO wireless mobility is no longer required.
The results from above are collected by varying the number of transceivers and wavelengths to obtain minimum packet hop distance. However minimizing packet hop distance means increasing the wavelengths and transceivers, a very costly solution. Furthermore optimum number of transceivers, receivers and packet hop distance is not alone itself. Since the latter varies the utilization within the physical layer which in turn affects the network layer traffic which in turn changes the traffic matrix. Thus a tradeoff exists to have an optimum amount of transceivers, wavelengths, maximized utilization, yet not affect the network layer traffic.
Iterative Optimization
Once the corresponding number of physical devices required is found from above method the data is required to be fed into Matlab in correspondence with node optimization using C program to find the best trade off configuration for the network. This iterative scheme needs to be done several times until the solution converges.
Interesting enough it seems however that the shared variable between the physical link layer and the network layer is the utilization. In terms of minimizing hardware equipment utilization must be running at 100% capacity. However this configuration yielded in a drastic change in the resulting traffic matrix outputted by the ‘Matlab + C’ optimizer. All that is required is to keep utilization between 95~98% (from experimental results) to keep traffic matrix unchanged and to find the shortest path from any starting node to any node.
CONCLUSION
Results
After iterating twice within the decomposed problem, it becomes evident that to solve the problem, one of the layers needs to become a ‘redundant’ layer to further simplify the system. As it seems all that is required is to make sure utilization does not reach 100%. This will allow C path optimizer to easily find the shortest path from any starting node to any node and not have the physical layer interrupt the network layer.
Furthermore the optimized physical layer has yielded in having 6 transceivers and 4 wavelengths will yield a ~100% utilization thus decreasing any of the two hardware will ensure shortest path resolution within the network layer.
Fig. 5 plots the average packet hop distance for optimal virtual topologies for different number of transceivers per node, and different number of wavelengths in the system. The average hop distance in the network is a function of the number of lightpaths set up in the network, which directly depends on the number of transceivers and wavelengths supported. As expected, the average hop distance decreases with a balanced increase in the number of transceivers and wavelengths in the network [2]. Increasing transceivers without adding extra wavelengths marginally improves the quality of the solution. For more than six transceivers, and more than four wavelengths, the performance improvement in hop distance is marginal for the network in Fig. 2 for the current choice of network traffic. Given a different network topology, and a different traffic matrix, these results would be different. Fig. 6 plots the transceiver utilization for different values of the number of wavelengths in the system, and number of transceivers at a node. Fig. 7 plots the wavelength utilization for the same set of experiments. As one would expect, Fig. 6 quantitatively demonstrates that the transceiver utilization decreases as the number of wavelengths is reduced and/or the number of transceivers is increased. Similarly, Fig. 7 demonstrates that the wavelength utilization decreases when the number of wavelengths is increased and/or the number of transceivers is reduced. These results confirm our original hypothesis that it is necessary to obtain the correct balance between transceivers and wavelengths in the system in order to have high utilizations of both these expensive resources.
Network Layer
Following the results from the physical layer, we can keep the utilization under 100% thus yielding in the same traffic matrix as output by CORE after Matlab reconfiguration via the biograph. Furthermore starting from any node the best (shortest/fastest) path can be calculated to any node within the network layer.
As an example, following Fig 3, using the Matlab + C optimizer we can find the shortest path from node 1 (per say) to any node within the topology outputted by the project:
Optimal Results: --------------------------- Distance from 1 to 1: 0 Path: 1 Distance from 1 to 2: 9.59744 Path: 1 2 Distance from 1 to 3: 5.02997 Path: 1 9 3 Distance from 1 to 4: 5.85268 Path: 1 4 Distance from 1 to 5: 4.59383 Path: 1 9 5 Distance from 1 to 6: 7.16892 Path: 1 9 5 6 Distance from 1 to 7: 7.64234 Path: 1 9 7 Distance from 1 to 8: 8.3955 Path: 1 4 8 Distance from 1 to 9: 3.40386 Path: 1 9 Distance from 1 to 10: 16.0722 Path: 1 12 11 10 Distance from 1 to 11: 12.5556 Path: 1 12 11 Distance from 1 to 12: 4.98364 Path: 1 12 Distance from 1 to 13: 12.5209 Path: 1 12 13 Distance from 1 to 14: 20.8639 Path: 1 12 11 14
The C code is located within the appendix.
Solution
Thus it is evident both via optimizers and graphically that to improve network layer and physical layer performance the best tradeoff for minimized packet hop distance (maximum overall system throughput) utilization must below 100% and never to reach 100%. As for the 14 node configuration the choice of six transceivers and four wavelengths is a very good one since it yields an average hop distance of one, with close to but not reaching ~100% utilization.
CONTRIBUTION
Due to the nature of this project, it became very hard to apply several principles of optimal design (such as monotonicity principles) since dealing with internet networks means dealing with a world of discrete possibilities. Unfortunately within discrete systems many principles will lead to heuristics and stochastic processes. Thus one of the primary aspects of this project was to make sure the function is linear to further simplify the problem statement. Furthermore since we are dealing with routing algorithms and discrete packets, implementation of a continuous function optimizer found within the iSight software was not feasible. Thus I wrote my own optimizer within C which communicates with the Matlab (fmincon) optimizer via a data.txt file which stores traffic matrices. This aided me to solve the network layer shortest path problem. Moreover since I was unable to obtain the CPLEX templates and software (due to the author’s restriction) used by various computer science departments I created my own simulation network within CORE to obtain results. I then emulated the same network seen in real life and made sure it behaved accordingly and collected my observations from CORE. The observations were then analyzed and optimized via Matlab + C (my own written code found in the appendix) to find the most optimal solution to this discrete problem.
ACKNOWLEDGEMENTS
Special thanks go to the Computer Sciences department and the Physics and Optics department at the University of Illinois for aiding me in the selection of the interesting routing topic within optical networks. Also this project would not have taken off without the help of the Boeing Communication and systems branch who provided me with the CORE software. Furthermore great help was obtained from the authors of the reference defined below.