Design of logical topologies for wavelength-routed optical networks pdf

We say that a logical topology has on logical link of the logical topology. A logical topology is said to be hop-bound limited if there The various parameters included in the mixed-integer linear is a restriction on the maximum number of hops a lightpath is program are the number of wavelengths the fiber supports, sym- allowed to take. A logical topology is said to be wavelength lim- metry and asymmetry restrictions, multiplicity restrictions, and ited if there is a restriction on the maximum number of wave- hop bound constraints.

We shall see above information in compact form: , later that these are important parameters in logical topology de-. If the first two arguments are sign. The third argument denotes that the are given.

The fourth argu- wavelength assignment for the logical links, such that the re- ment denotes that the logical topology has at most edges sources of the network subject to the given constraints are used between any node pair. The fifth argument is the hop-bound optimally. The last the physical topology shown in Fig. Using the notation of wavelengths the fiber supports is one, and the maximum hop stated above Fig. It is reasonable to construct logical topology on the physical topology of figure Fig.

This between the various parameters. Previous Work care that a lightpath is assigned the same wavelength on every In this section, we position our work in relation to three recent hop wavelength continuity constraints. Many parameters ex- papers, [2], [3], and [1], on the problem of designing optimal plained in Section II-A could be passed to the ILP to yield the logical topologies. A more detailed reference on this topic has desired logical topology which minimizes congestion.

Since the been listed in [2]. The objective ical topology reflects the traffic intensities between the nodes. The authors subdivide the problem into easier. We also see that the relaxation of the ILP yields lower four subproblems. They are: 1 determining a logical topology bounds on the congestion and provides a performance reference logical links ; 2 routing the logical links over physical links; for any topology design heuristic algorithm.

The number of con- 3 assigning wavelengths to the routes; and 4 routing packet straints in our formulation grows as number of — pairs traffic on the logical topology. The authors only consider sub- number of edges number of wavelengths. Though large, problems 1 and 4. Simulated annealing which is NP-hard this problem formulation could be useful for moderate-sized has been used to solve subproblem 1 and flow deviation to networks. For larger networks, we develop heuristic algorithms solve subproblem 4.

The drawbacks of the above approach are which use as inputs the solutions obtained by relaxing the in- as follows. Lower Bounds on Congestion rather, it considers subproblems one and four independently.

Congestion as defined earlier is the maximum offered load In [3] the authors formulated the logical topology design on any logical link. Congestion may be viewed as a function problem as a linear program when the nodes were equipped of the various parameters of the network such as the traffic with wavelength changers.

The objective of the formulation matrix, number of wavelengths the fiber can support, resources was to minimize the average hop length of a logical link, with at each node number of transmitters and receivers , the hop the hope that the number of wavelength changers used could be lengths of the logical links, the multiplicity restrictions on the reduced and therefore this formulation could be approximated logical topology, the multiplicity restrictions on the physical to the formulation with no wavelength changers.

Our linear formulation helps us investigate if the traffic matrix is balanced this is because the objective the lower bounds on congestion for different values of the function does not include any traffic variables , 2 that it works above parameters.

In [1] congestion as a function of the traffic well only if the physical topology is dense in the number of matrix, resources at each node, and propagation delay has been edges, and 3 that it only works when the network size number studied.

Note that if the physical topology is sparse it has We do not consider the propagation delay [1] as it makes few edges then the number of wavelength changers used the formulation nonlinear. We compare the bounds obtained could increase fewer alternate routes and the resulting logical previously with the bounds obtained by inclusion of the above topology would not reflect the traffic intensities between the mentioned parameters.

This in turn would increase the amount of packet traffic carried on a per-wavelength basis. The wavelength continuity F. Outline of the Paper constraint of [2] could not be introduced in [3] as this would In Section II we give a precise formulation of the logical make the problem nonlinear. In but the number of wavelengths the fiber supports is not a Section III we introduce different constraints for the various constraint.

The drawback in this approach is that the physical cases. We introduce the aggregate formulation in Section III-C topology becomes irrelevant for designing a logical topology. In Section IV D. Contribution of This Work we give examples to show the interrelationship between the In this paper, we take care of all the drawbacks and short- various parameters.

In Section IV-C we prove that under comings listed above. We present an exact linear formulation certain conditions we can use equality logical link constraints [integer 0—1 linear program, or ILP] for designing a logical instead of inequality logical link constraints without affecting topology with no wavelength changers.

This formulation when congestion. In Section V we explain the rounding heuristics solved provides an optimal solution for the logical topology de- and the wavelength assignment heuristics that are to be used sign problem. To the best of our knowledge, this is the first on the solutions obtained by solving the MILP with the integer time a linear formulation has been stated which provides an constraints being relaxed relaxed problem. This yields upper bounds on congestion and on source—destination pair.

Numerical values are listed in the b denotes the total offered traffic on logical tables for two different traffic matrices. Objective mixed integer linear program MILP. This formulation yields a logical topology. We shall see in Section III how we can modify the constraints to account for any desired logical topology.

We use the following notation. The perscripts; motivation for choosing this objective is that the electronic pro- cessing switching speed requirement is proportional to the , originating and terminating node of a logical link congestion. If the switching speeds at the nodes are limited, then lightpath ; minimizing congestion would be appropriate as it would enable th multiple logical link between nodes terminating a the traffic carried per wavelength to increase.

In the examples logical link; we have solved, we have noticed that if there is heavy traffic , endpoints of a physical link; between some source—destination pair, then there is a logical wavelength number, when used as a superscript. This happens because of the objective function, i. Parameters would tend to be an edge in the logical topology. If this number of nodes in the network; is not the case, then the traffic from node to node may have to span many logical links before being delivered to its destina- is the traffic matrix, i.

Constraints If then there is a fiber link between nodes 1 Logical link degree constraints: and , otherwise is 0; maximum hop matrix.

If intermediate wavelength routing nodes have to be configured for establishing a logical link between node and node for all then the hop length of that logical link is. Let ; and number of wavelengths the fiber can support; Remark: The above constraint ensures that the number of , number of transmitters and receivers, respectively, logical links originating out-degree and terminating in-de- at node.

Variables ceivers at each node are equal and are the same for every node. We also set , that is, no multiple logical link or directed edge , in the log- multiple logical links allowed. Let color be chosen for node for the traffic between nodes and. This implies that. Then the above constraint would force for all for all and and.

If in the MILP the integer constraints are replaced by their continuous coun- Remark: We are summing over all possible logical links terparts, i. By this we are assured that there is no wavelength clash at physical , the resulting LP is called the LP-relax- link , i.

Since our formulation is a minimization physical link will be assigned the same wavelength. Multiplicity in Physical Topology if To account for the multiple fibers in the physical topology, if , for all and we can modify the constraints of Section II as shown below.

We have to modify the variable to , where Variables and. The conservation of wavelength con- Remark: The above equation ensures that a wavelength is straints would have to suitably modified to take this additional conserved at every node for a logical link.

We call this factor into account. Symmetry Constraints flow conservation equations in multicommodity flow problems.

Let logical link use wavelength. Then by conservation We have the following set of constraints to impose the sym- of wavelength constraints there is a path in the physical topology metry restrictions. And also that the routing and wavelength as- Remark: This ensures that the variable can have a signment for the lightpaths associated with the logical links be- nonzero value if there exists a logical link tween node and node traverse the same set of physical links.

The traffic on logical link between the source—des- and are assigned corresponding wavelengths if th logical link tination pair is upper-bounded by the total flow of traffic from node to node is assigned wavelength then th logical between.

This is usually referred to as a disaggregate formulation Remark: The above two equations ensure that the load on [6]. We can get a more tractable aggregate MILP formulation any logical link is no greater than the maximum load , by identifying a commodity with each source, rather than each which is being minimized.

Then, in the aggregate MILP formulation, the logical link degree constraints and the wave- length continuity constraints remain the same; only the traffic constraints have to be modified. The modified traffic constraints are as follows. But there is no restriction on the number of wavelengths We note that the above is superfluous in the MILP but usu- and on the number of hops taken by a lightpath. We In [1], various logical topologies are given which are of the solve the LP and get a lower bound, say,.

Iteratively, we type. We note that the logical link con- can then set and solve the LP-relaxation straints are equality constraints. This forces the restriction that to get an improved lower bound. We will refer to every node should use all its transmitters and receivers even these bounds as the iterative LP-relaxation lower bounds.

It is to though it may not be required. We shall give examples to show be noted that the LP-relaxation lower bounds in [1] are obtained the surprising result that by using inequality degree constraints, when there is no restriction on the number of wavelengths, and we get lower congestion than that obtained by using equality the hop length. We could then use the lower bound of [1] as an degree constraints. By using equality logical link constraints, a priori lower bound on in our LP-relaxed problem.

Due to the regular nature of IV. This metric restriction, multiplicity, wavelength and hop-bound behavior tends to increase congestion. We shall derive the condi- constraints affect congestion.

In the notation for the logical tions under which we can use equality degree constraints instead topology, if some of the arguments are dropped, then those of inequality degree constraints, without affecting congestion. It is interesting to note that if we drop the last two arguments, that is, and A.

We use the notation to denote the gestion. The traffic matrix between the nodes is given in optimal congestion value obtained by solving the MILP. The Table I. On solving the MILP we obtained the logical topology first argument inside the parenthesis is the logical topology shown in Fig.

But desired and the second argument is the traffic matrix to be if we had solved the MILP with equality degree constraints routed on the logical topology. These are the parameters passed then the congestion value obtained is 1. That is to the MILP. For example refer to Fig. The above example is the congestion obtained by solving the MILP, with the shows that equality constraints may at times increase con- restriction that the logical topology is -regular symmetric, has gestion.

Hence it is important to know when we can use equality constraints without affecting conges- Fig. The two theorems given below give us a criterion for im- posing equality constraints. Given below are examples when we consider symmetric Theorem 1: Consider a undirected graph with maximum de- logical topologies.

Consider the traffic matrix given in gree and let its underlying simple graph have minimum de- Table II. In this case. The gree. Let be the minimum congestion achieved for a given logical topology corresponding to this is shown in Fig.

Then we and the logical topology is can always construct a regular graph which achieves the same shown in Fig.

Multiplicity Constraints Proof: In the undirected graph, we add edges between de- We can also construct examples where multiplicity con- ficient degree nodes. We can always do this whenever straints affect the congestion value. Assume the traffic. We stop adding edges to deficient degree nodes when matrix shown in Table III is to be routed.

We note that we are left with at most one deficient degree node. We note that , in Fig. View 10 excerpts, cites results, background and methods. Logical topology design for linear and ring optical networks. IEEE J. View 2 excerpts, cites background. A modified heuristic approach of logical topology design in WDM optical networks. View 1 excerpt, cites background. Some principles for designing a wide-area optical network. Highly Influential.

View 5 excerpts, references background and results. Lightnets: Topologies for High-speed Optical Networks. An inherent problem of conventional point to point WAN architectures is that they cannot translate optical transmis- sion bandwidth into comparable user available throughput due to the limiting … Expand. Routing and wavelength assignment in all-optical networks.

Topological design of the wavelength-division optical network. Lightwave networks based on de Bruijn graphs. A heuristic wavelength assignment algorithm for multihop WDM networks with wavelength routing and wavelength reuse. The authors present a heuristic algorithm for effectively assigning a limited number of wavelengths among the access stations of a multihop network wherein the physical medium consists of optical … Expand. Algorithms for routing in a linear lightwave network.

The conference on Computer Communications. Routing algorithms are proposed for setting up calls on a circuit-switched basis in linear lightwave networks LLN , i. We study the node architecture for a WDM mesh network with traffic-grooming capability.

A mathematical formulation of the traffic-grooming problem is presented in this study and several fast heuristics are also proposed and evaluated. Rouskas - Optical Networks , In the past few years, there has been growing interest in wide area "All Optical Networks" with wavelength division multiplexing WDM , using wavelength routing.

Due to the huge bandwidth inherent in optical fiber, and the use of WDM to match user and network bandwidths, the wavelength Due to the huge bandwidth inherent in optical fiber, and the use of WDM to match user and network bandwidths, the wavelength routing architecture is an attractive candidate for future backbone transport networks. Virtual topology design aims at combining the best of optical switching and electronic routing abilities.

Designing a virtual topology on a physical network consists of deciding the lightpaths to be set up in terms of their source and destination nodes and wavelength assignment. In this survey we first describe the context and motivations of the virtual topology design Design of logical topologies: A linear formulation for wavelength-routed optical networks with no wavelength changers by Rajesh M.

Krishnaswamy, Kumar N. Abstract—We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers. We present a general linear formulation which considers routing traffic demands, and routing and as-signing wavelengths to lightpaths, as a combined optimization Abstract - Cited by 71 0 self - Add to MetaCart Abstract—We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers.

We present a general linear formulation which considers routing traffic demands, and routing and as-signing wavelengths to lightpaths, as a combined optimization problem. The objective is to minimize congestion. We show by examples how equality and inequality logical degree constraints have a bearing on congestion. We prove that, under certain conditions, having equality degree constraints with mul-tiple edges allowed in the design of logical topologies does not affect congestion.

This helps in reducing the dimensionality of the search space and hence speeds up the search for an optimal solution of the linear formulation.

We solve the linear formulation for small examples and show the tradeoff between congestion, number of wavelengths available and the maximum number of hops a lightpath is allowed to take. For large networks, we solve the linear formulation by relaxing the integer constraints. We develop topology design algorithms for large networks based on rounding the solutions obtained by solving the relaxed problem.

Since the whole problem is linearizable, the solution obtained by relaxation of the integer constraints yields a lower bound on congestion. This is useful in comparing the efficiency of our heuristic algorithms. Following Bienstock and Gunluk, , we introduce a cutting plane which helps in obtaining better lower bounds on congestion and also enables us to reduce the previously obtained upper bounds on congestion. Index Terms—All-optical networks, linear program, network planning, topology design.

Citation Context We consider the problem of designing a virtual topology to minimize electronic routing, that is, grooming traffic, in wavelength routed optical rings. The full virtual topology design problem is NP-hard even in the restricted case where the physical topology is a ring, and various heuristics have be Abstract - Cited by 68 19 self - Add to MetaCart We consider the problem of designing a virtual topology to minimize electronic routing, that is, grooming traffic, in wavelength routed optical rings.

The full virtual topology design problem is NP-hard even in the restricted case where the physical topology is a ring, and various heuristics have been proposed in the literature for obtaining good solutions, usually for different classes of problem instances. We present a new framework which can be used to evaluate the performance of heuristics and which requires significantly less computation than evaluating the optimal solution.