RWA Optical network design problem,
ILP formulations and solution techniques
For Optical network design problems
By
Zein ElAbedin Mohamed Wali
B.Sc. in Electronics and Communications Engineering – Cairo University
A Thesis Submitted to the
Faculty of Engineering at Cairo University
in Partial Fulfillment of the
Requirements for the Degree of
Master of Science
in
Engineering Mathematics and Physics Department
Supervised by
Dr. Abd ElKarim Shaban Omr
Assoc. Professor, Faculty of Engineering, Cairo University
Dr. Khaled Mohamed Fouad Elsayed
Assoc. Professor, Faculty of Engineering, Cairo University
Faculty of Engineering, Cairo University
Giza, Egypt
2005
TABLE OF CONTENTS
LIST OF ABBREVIATIONS AND ACRONYMS iv
LIST OF FIGURES v
1. Introduction & Terminology 1
1.1. Introduction: 1
1.2. Multiplexing techniques: 3
1.3. Optical WDM networks: 4
1.4. RWA problem: 6
1.4.1. Wavelength conversion: 8
1.5. Multicasting: 11
1.6. Thesis Organization (incomplete): 13
2. Survey of literature 14
2.1. Technical Classification for RWA: 14
2.2. Functional Classification for static RWA: 15
2.2.1. Functional elements of routing algorithms: 16
2.2.2. Functional elements of Wavelength Assignment algorithms: 17
2.3. General Notations: 17
2.4. Different Approaches for static RWA: 18
2.4.1. Min-RWA, link-based, no conversion, unique requests, single fiber: 18
2.4.2. Min-RWA, link-based, no conversion, multiple requests, single fiber: 21
2.4.3. Min-RWA, link-based, full-wavelength conversion, unique requests, single fiber: 23
2.4.4. Max-RWA, path-based, no conversion, multiple requests, single-fiber: 24
2.4.5. Max-RWA, path-based, no conversion, multiple requests, single-fiber(2): 26
2.4.6. Max-RWA, link-based, no conversion, multiple requests, single-fiber: 29
2.4.7. Max-RWA, link-based, no conversion, multiple requests, single-fiber: 31
2.4.8. Max-RWA, path-based, no conversion, multiple requests, mutli-fiber: 33
2.4.9. Greedy Heuristic Approach: 36
2.4.10. Min-RWA, path-based, full conversion, unique requests, single-fiber: 39
2.4.11. Min-RWA, path-based, no conversion, unique requests, single-fiber: 42
2.4.12. Min-RWA, path-based, sparse conversion, unique requests, single-fiber: 43
2.4.13. Min-RWA, path-based, sparse conversion, multiple requests, multi-fiber: 47
2.4.14. Tabu Search Heuristic Approach: 53
2.5. Technical classification for MC-RWA: 56
2.6. Different Approaches for static MC-RWA (incomplete): 57
2.5.1. Heuristic Approach, single-session, full-splitting capability: 57
2.5.2. Heuristic Approach, single-session, sparse-splitting capability: 58
2.7. Motivation: 61
3. Proposed Approach 62
3.1. Comparison: 62
3.2. Proposal: 63
3.2.1 Handling multiple-fibers: 63
3.2.2 Model (ILP formulation): 64
3.2.3. Solution uniqueness and Shortest paths preference: 68
3.3. Network growing problem: 69
3.4. Total Unimodularilty Property: 72
3.5. Proposed Solution Technique "TU-Based integrality relaxation": 73
4. Experimental Results 78
4.2. Performance evaluation: 78
4.3. Test setup: 79
4.4. Performance metrics: 79
4.5. Direct Model implementation: 79
REFERENCES 83
LIST OF ABBREVIATIONS AND ACRONYMS
|ATM |Asynchronous Transfer Mode |
|B & B |Branch and Bound technique for solving ILP problems |
|DLE |Dynamic LightPath Establishment |
|EDP |Edge Disjoint Paths |
|FDM |Frequency-Division Multiplexing |
|FSC-OXC |Fiber-Switch Capable OXC |
|Gbps |Gega bits per Second |
|GRWA |Grooming, Routing and Wavelength Assignment |
|ILP |Integer Program / Programming |
|IP |Internet Protocol |
|K-SP |K Shortest Path |
|LP |Linear Program / Programming |
|LSC-OXC |Lambda-Switch Capable OXC |
|MCNF |Multi-Commodity Network Flow |
|MC-OXCs |Multicast capable OXC |
|MC-RWA |Multicast RWA |
|MILP |Mixed Integer Program / Programming |
|MG-OXC |Multi-Granularity OXC |
|nm |Nano-meter |
|OTN |Optical Transportation Networks |
|OXC |Optical Cross-Connects |
|RWA |Routing and Wavelength Assignment |
|SD |Source-Destination |
|SDM |Space-Division Multiplexing |
|SLE |Static LightPath Establishment |
|SP |Shortest Path |
|Tbps |Tera Bits per second |
|TDM |Time-Division Multiplexing |
|TU |Total Unimodularilty / Total Unimodular |
|WDM |Wavelength-Division Multiplexing |
|WRON |Wavelength Routed Optical Networks |
|WWW |World Wide Web |
LIST OF FIGURES
Figure 1: The low-attenuation regions of an optical fiber. 2
Figure 2: fiber section illustrating different connections carried on different wavelengths 4
Figure 3: A wavelength routed WDM network 5
Figure 4: A 3x3 optical cross-connect (OXC) with two wavelengths per fiber 6
Figure 5: An NxN WDM optical Cross-connect with k-wavelengths 6
Figure 6: An example of WRON with 4 lightpaths using 2 wavelengths 7
Figure 7: conceptual RWA problem with two wavelengths per fiber 8
Figure 8: Wavelength-continuity constraint in a WRON, (a) without converter, (b) with converter 9
Figure 9: Wavelength conversion 10
Figure 10: A WRON with 4 requests and a wavelength converter 11
Figure 11: (a) power splitter, (b) combiner 12
Figure 12: functional classification of Routing & Wavelength Assignment algorithms. 16
Figure 13: An optical network with eight routed lighptahs 21
Figure 14: Auxiliary graph for the Wavelength-assignment sub-problem 21
Figure 15: illustration of the search phase of Routing sub-problem 24
Figure 16: illustration of model formulation of section 2.4.4 26
Figure 17: illustration of the model of section 2.4.5. 29
Figure 18: Maximum coverage greedy algorithm 35
Figure 19: flow chart of the algorithm used for RWA based on maximum coverage problem 36
Figure 20: Greedy algorithm for EDP 38
Figure 21: flow chart of the RWA heuristic based on greedy EDP algorithm 39
Figure 22: Piecewise linear cost functions for link l. 41
Figure 23: a combined MG-OXC node and its logically separated form: (a) MG-OXC node, (b) FSC-OXC and LSC-OXC nodes. 48
Figure 24: Langrangean relaxation with heuristics (LRH) 52
Figure 25: Algorithm Tabu-RWA(), as adopted from [28] 55
Figure 26: An example of multicasting routing and wavelength assignment. Node 2 is considered with the 4 combinations of wavelength conversion and splitting capabilities. 57
Figure 27: Multicasting tree construction heuristic algorithm, as adopted from [32] 58
Figure 28: An example multicasting forest in a NSFNET-like network with sparse splitting 59
Figure 29: Multicasting "forest" construction heuristic algorithm, as adopted from [32] 60
Figure 30: WRON with 2 links each of 2 fibers 63
Figure 31: same WRON viewed as multi-graph 63
Figure 32: pseudo-code to calculate needed multi-fibers in network growing problem 71
Figure 33: flow chart diagram for accommodating the network growing problem. 71
Chapter 1
1. Introduction & Terminology
1. Introduction:
"Life in our increasingly information-dependent society requires that we have access to information at our finger tips when we need it, where we need it, and in whatever format we need it" as quoted from Professor's Biswanath Mukherjee book [1] , greatly emphasis our need for high-speed networks that can provide us with the required information access.
Today's applications require more and more bandwidth usage, such as: Voice over IP, video conferencing, java applications, World Wide Web (WWW) browsing, etc. Not only that, but The next decade may bring to the home and office multiple connections of high-definition television, video mail, and digital audio, as well as full Internet connections via user-friendly graphic user interfaces. Moreover these applications vary from business critical applications, transactions or medical applications to even internet games.
As more users start to use data networks, and as their usage patterns evolve to include more bandwidth-intensive networking applications, there emerges an acute need for very high bandwidth transport network facilities whose capabilities greatly exceed our current high-speed networks, such as those of current Internet and Asynchronous transfer Mode (ATM) networks.
It is widely believed that the emerging fiber optic technology that supports the development of Optical Transportation Networks (OTNs) [2] can be considered as the promising solution for the above needs. In fact, Optical networks are considered to be the Next-Generation Networking Paradigm, and to be a replacement of the current implementation of the Internet, as "Optical Internet"[3] .
Fiber Optics possesses many characteristics that make it an excellent physical medium for high-speed networking [4] . This can be illustrated using the following figure (Figure 1) that shows the two low-attenuation regions of optical fiber. It can be seen that usable bandwidth region is spitted over two similar regions around a wavelength of 1300 and 1550 respectively, with an attenuation as low as 0.2 dB per kilometer. Combined, these two regions provide a theoretical upper bound of 50 THz of bandwidth.
[pic]
Figure 1: The low-attenuation regions of an optical fiber, as adopted from [4].
In addition, the small size and thickness of fiber allows more fiber to occupy the same physical space as copper, a property that is desirable when installing local networks in buildings. Fiber is flexible, difficult to break, reliable in corrosive environments, and deployable at short notice (which makes it particularly favorable for military communications systems). Also, fiber transmission is immune to electromagnetic interference and does not cause interference. Last, fiber is made from one of the cheapest and most readily available substances on earth, sand. This makes fiber environmentally sound; and unlike copper, its use will not deplete natural resources.
Thus, the general fiber characteristics can be summarized as follows:
1. huge bandwidth (nearly 50 terabits per second (Tbps)
2. low signal attenuation (as low as 0.2 dB/km)
3. low signal distortion (immune to electromagnetic interference)
4. low power requirement
5. low material usage
6. small space requirement, and
7. low cost.
For all the above qualities, the optical fiber networks best fits to be the solution for the high-speed networks. In the same time, it raises the challenge of the design of such networks and the optimizations problems to effectively benefit from its resources.
2. Multiplexing techniques:
As previously mentioned, a single fiber has a potential bandwidth of nearly 50 Tbps, on the other hand the maximum rate at which an end user – which can be a workstation or a gateway that interfaces with lower-speed subnetworks - can access the network is limited by electronic speed (to a few Gbps). This raises the issue of optimal optical communication network design that saves the network cost, and improves its performance by efficiently using the fiber's huge bandwidth and introducing concurrency among multiple user transmissions.
In optical networks, this concurrency may be provided by different multiplexing techniques [5] :
• Space-division multiplexing (SDM):
partitions the physical space to increase transport bandwidth, e.g., bundling a set of fibers into a single cable, or using several cables within a network link. It is also referred to as "multi-fiber" case in literature. Also, it is usually combined with any of the other multiplexing techniques.
• Frequency/Wavelength-division multiplexing (FDM/WDM):
partitions the available frequency spectrum into a set of independent channels. The use of FDM within an optical network is termed (dense) wavelength-division multiplexing (DWDM or WDM) which enables a given fiber to carry traffic on many distinct wavelengths.
• Time-division multiplexing (TDM):
divides the bandwidth’s time domain into repeated time-slots of fixed length. Using TDM, multiple signals can share a given wavelength if they are non-overlapping in time.
• Code-division multiplexing (CDM):
divides the available channels (frequency, time, spatial) by assigning a different orthogonal code to each connection.
Optical TDM and CDM are somewhat futuristic technologies [1] . The optical TDM bit rate is the aggregate rate over all TDM channels in the system, while the optical CDM chip rate may be much higher than each user's data rate. As a result, both the TDM bit rate and the CDM chip rate may be much higher than electronic processing speed, i.e., some part of the end user's network interface must operate at a rate higher than electronic speed. Thus, TDM and CDM are relatively less attractive than WDM, since WDM – unlike TDM or CDM- has no such requirement.
Specifically, WDM is the current favorite multiplexing technology for the optical communication networks since all the end-user equipment needs to operate only at the bit rate of a WDM channel, which can be chosen arbitrarily, e.g., peak electronic processing speed. Hence our main focus will be based on WDM routed network or simply WRON's.
3. Optical WDM networks:
To take full advantage of the potential of fiber, the use of wavelength division multiplexing (WDM) technology has become the option of choice. With WDM, a number of distinct wavelengths are used to implement separate channels. An optical fiber can carry several channels in parallel, each on a particular wavelength (see below Figure 2).
[pic]
Figure 2: fiber section illustrating different connections carried on different wavelengths
The number of wavelengths that each fiber can carry simultaneously is limited by the physical characteristics of the fiber and the state of the optical technology used to combine these wavelengths onto the fiber and isolate them off the fiber. With currently available commercial technology, a few tens of wavelengths can be supported within the low-loss window at 1550 nm (see Figure 1), but this number is expected to grow rapidly in the next few years. Therefore, optical fiber links employing WDM technology have the potential of delivering an aggregate throughput in the order of Terabits per second, enough to satisfy the ever-growing demand for more bandwidth per user on a sustained, long-term basis.[6]
Unfortunately, due to the mismatch between aggregate fiber capacity and peak electronic processing speeds, simply upgrading existing point-to-point fiber links to WDM creates the well-known electro-optic bottleneck [2]: rather than achieving the multiterabit-per-second throughput of the fiber, one has to settle for the multigigabit-per-second throughput that can be expected of the electronic devices where the optical signals terminate. Overcoming the electro-optic bottleneck, therefore, involves the design of properly structured architectures to interconnect the fiber links.
An optical WDM Routed network (WRON) is a network with optical fiber transmission links and with an architecture that is designed to exploit the unique features of fibers and WDM. Such networks offer the promise of an all-optical information highway capable of supporting a wide range of applications that involve the transport of massive amounts of data and/or require very fast response times. Such applications include video on demand and teleconferencing, telemedicine applications, multimedia document distribution, remote supercomputer visualization, and many more to come. Consequently, optical WDM networks have been a subject of extensive research both theoretically and experimentally.
The architecture for wide-area WDM networks that is widely expected to form the basis for a future all-optical infrastructure is built on the concept of wavelength routing. A wavelength routing network, shown in Figure 3, consists of two types of nodes:
• Optical Cross-Connects (OXCs): which connect the fibers in the network, and
• Edge nodes: which provide the interface between non-optical end systems (such as IP routers, ATM switches, or supercomputers) and the optical core.
Access nodes provide the terminating points (sources and destinations) for the optical signal paths. Each node (at its access station) is equipped with a set of transmitters and receivers, both of which may be wavelength tunable.
It should be noted that the communication paths may continue outside the optical part of the network in electrical form.
[pic]
Figure 3: A wavelength routed WDM network
The services that a wavelength routed network offers to end systems attached to edge nodes are in the form of logical connections implemented using lightpaths [27]. A lightpath is the basic mechanism of communication in a wavelength-routed network. Each lightpath (also referred to as (-channel), is a clear optical path –alternatively referred to as an all-optical communication channel -between two edge nodes, it bypasses electronic packet processing at intermediate nodes and is realized by finding a physical path and allocating a free wavelength on each link of that path. The end-nodes of the lightpath have access to it via transmitters and receivers that are tuned to the wavelength on which the lightpath operates.
Examples of lightpaths are shown in Figure 3 as red and green directed lines.
Information transmitted on a lightpath does not undergo any conversion to and from electrical form within the optical network, and thus, the architecture of the optical network nodes can be very simple because they do not need to do any signal processing. Furthermore, since a lightpath behaves as a literally transparent "clear channel" between the source and destination edge node, there is nothing in the signal path to limit the throughput of the fibers.
The OXCs provide the switching and routing functions for supporting the logical connections between edge nodes. An OXC takes in an optical signal at each of the wavelengths at an input port, and can switch it to a particular output port, independent of the other wavelengths. An OXC with N input and N output ports capable of handling W wavelengths per port can be thought of as W independent N x N switches. These switches have to be preceded by a wavelength demultiplexer and followed by a wavelength multiplexer to implement an OXC, as shown in Figure 4.
[pic]
Figure 4: A 3x3 optical cross-connect (OXC) with two wavelengths per fiber
Thus, an OXC can cross-connect the different wavelengths from the input to the output, where the connection pattern of each wavelength is independent of the others. By appropriately configuring the OXCs along the physical path, a logical connection (lightpath) may be established between any pair of edge nodes [26] . This can be illustrated though the following WDM OXC shown as a routing block (see Figure 5).
[pic]
Figure 5: An NxN WDM optical Cross-connect with k-wavelengths
4. RWA problem:
The Wavelength routed networks presented here above, raise a challenging network design problem. To illustrate this design problem, let us consider an N-node network, if each node is equipped with N-1 transceivers [transmitters (lasers) and receivers (filters)] and if there are enough wavelengths on all fiber links, then every node pair could be connected by an all-optical lightpath, and there is no networking problem to solve. However, it should be noted that the network size (N) should be scalable, transceivers are expensive so that each node may be equipped with only a few of them, and technological constraints dictate that the number of WDM channels that can be supported in a fiber be limited to W (whose value is a few tens today, but is expected to improve with time and technological breakthroughs). Thus, only a limited number of lightpaths may be set up on the network [1] .
Under such a network setting, a challenging networking problem is that, given a set of lightpaths that need to be established on the network, and given a constraint on the number of wavelengths, determine the routes over which these lightpaths should be set up and also determine the wavelengths that should be assigned to these lightpaths so that the maximum number of lightpaths may be established or alternatively minimize the total number of wavelengths used to establish all the given lightpaths.
While shortest-path routes may be most preferable, note that this choice may have to be sometimes sacrificed, in order to allow more lightpaths to be set up. Thus, one may allow several alternate routes for lightpaths to be established. Lightpaths that cannot be set up due to constraints on routes and wavelengths are said to be blocked, so the corresponding network optimization problem is to minimize this blocking probability or to reduce the total network cost respectively.
An example of such network with assigned lightpaths between different end-nodes is illustrated in the figure below (Figure 6 ). [7]
[pic]
Figure 6: An example of WRON with 4 lightpaths using 2 wavelengths
A unique feature of optical WDM networks is the tight coupling between routing and wavelength selection. As can be seen in Figure 6, a lightpath is implemented by selecting a path of physical links between the source and destination edge nodes, and reserving a particular wavelength on each of these links for the lightpath. Thus, in establishing an optical connection we must deal with both routing (selecting a suitable path) and wavelength assignment (allocating an available wavelength for the connection). The resulting problem is referred to as the Routing and Wavelength Assignment (RWA) problem [7] , and is significantly more difficult than the routing problem in electronic networks.
The additional complexity arises from the fact that routing and wavelength assignments are subject to the following two constraints:
1. Wavelength continuity constraint:
A lightpath must use the same wavelength on all the links along its path from source to destination edge node. This constraint is illustrated in Figure 6 by representing each lightpath (using a certain wavelength) with a certain style along all the links in its path. In other words, the same lightpath is drawn with a continuous style (either dotted or solid) along all the links in its path
2. Distinct wavelength constraint:
All lightpaths using the same link (fiber) must be allocated distinct wavelengths. In Figure 6 this constraint is illustrated by the fact that any 2 lightpaths sharing any link are drawn with different styles (assigned different wavelengths).in other words, the lightpaths with the same drawing style never share the same link.
The effect of the wavelength continuity constraint can be represented by replicating the network into as many copies as the number of wavelengths. For example, such a concept is illustrated in Figure 7 where the RWA problem is assumed to have two wavelengths. If wavelength i is selected for a lightpath, the source and destination edge node communicate over the i-th copy of the network. Thus, finding a path for a connection may potentially involve solving W routing problems for a network with W wavelengths, one for each copy of the network.
[pic]
Figure 7: conceptual RWA problem with two wavelengths per fiber
1. Wavelength conversion:
The wavelength continuity constraint may be relaxed if the optical cross connects (OXCs) are equipped with wavelength converters [8] . A wavelength converter is a single input/output device that converts the wavelength of an optical signal arriving at its input port to a different wavelength as the signal departs from its output port, but otherwise leaves the optical signal unchanged.[6]
In OXCs without a wavelength conversion capability, an incoming signal at port Pi on wavelength ( can be optically switched to any port Pj, but must leave the OXC on the same wavelength (. With wavelength converters, this signal could be optically switched to any port pj on some other wavelength ('. That is, wavelength conversion allows a lightpath to use different wavelengths along different physical links.
The wavelength-continuity constraint distinguishes the wavelength-continuous network from a circuit-switched network which blocks calls only when there is no capacity along any of the links in the path assigned to the call. To further illustrate this point, consider the portion of the network in Figure 8, two lightpaths have been established in the network: 1) between node 1 and node 2 on wavelength (1 and 2) between node 2 and node 3 on wavelength (2. Now, suppose a lightpath between node 1 and node 3 must be set up. If there are only two wavelengths available in the network, establishing such a lightpath from node 1 to node 3 is now impossible even though there is a free wavelength on each of the links along the path from node 1 to node 3. This is because the available wavelengths on the two links are different. Thus, a wavelength-continuous network may suffer from higher blocking as compared to a circuit-switched network.[8]
[pic]
Figure 8: Wavelength-continuity constraint in a WRON, (a) without converter, (b) with converter
Different levels of wavelength conversion capability are possible. Figure 9 illustrates the differences for a single input and single output port situation; the case for multiple ports is more complicated but similar.
[pic]
Figure 9: Wavelength conversion
The different cases are:
• Full wavelength conversion capability implies that any input wavelength may be converted to any other wavelength.
• Limited wavelength conversion capability denotes that each input wavelength may be converted to any of a specific set of wavelengths, which is not the set of all wavelengths for at least one input wavelength.
• Fixed wavelength conversion capability forms a special case of the limited wavelength conversion case, where each input wavelength can be converted to exactly one other wavelength.
As a matter of fact, if each wavelength is "converted" only to itself, then we have no conversion.
The advantage of full wavelength conversion is that it removes the wavelength continuity constraint, making it possible to establish a lightpath as long as each link along the path from source to destination has a free wavelength (which could be different for different links). As a result, the RWA problem reduces to the classical routing problem that is, finding a suitable path for each connection in the network. Referring to Figure 7, full wavelength conversion collapses the W copies of the network into a single copy on which the routing problem is solved.
On the other hand, with limited conversion, the RWA problem becomes more complex than with no conversion. To see why, note that employing limited conversion at the OXCs introduces links between some of the network copies of Figure 7. For example, if wavelength (1 can be converted to wavelength (2 but not to wavelength (3, then links must be introduced from each OXC in copy 1 of the network to the corresponding OXC in copy 2, but not to the corresponding OXC in copy 3. When selecting a path for the connection, at each OXC there is the option of remaining at the same network copy or moving to another one, depending on the conversion capability of the OXC. Since the number of alternatives increases exponentially with the number of OXCs that need to be traversed, the complexity of the RWA problem increases accordingly.
In general, wavelength conversion (full or limited) increases the routing choices for a given lightpath (i.e., makes more efficient use of wavelengths), resulting in better performance. Since converter devices increase network cost, a possible middle ground is to use sparse conversion, that is, to employ converters in some, but not all, OXCs in the network. In this case, a lightpath must use the same wavelength along each link in a segment of its path between OXCs equipped with converters, but it may use a different wavelength along the links of another such segment. It has been shown that by implementing full conversion at a relatively small fraction of the OXCs in the network is sufficient to achieve almost all the benefits of conversion [9]
To summarize, the figure below (Figure 10) gives a sample WDM routed network with 4 requests and a wavelength-converting capable node. The requests from node 1 to node 4 and one connection request from node 2 to node 4 can use the same wavelength for their lightpaths as they don't share any links. The 2nd request from node 2 to node 4 must use a different wavelength for its lightpath, as the (1 has been already used. The last connection request from node 2 to node 5 has been assigned a lightpath passing over node 1. Since the wavelength (1 has been already used over the fiber from node 1 to node 5, it should use another wavelength (2, but due to the existence of a wavelength converter in node 1, it could use wavelength (1 one the fiber from node 2 to 1 and to be converted to (2 from node 1 to 5.
[pic]
Figure 10: A WRON with 4 requests and a wavelength converter
5. Multicasting:
In the previous sections we presented the concept of lightpath as the basic mechanism of communication in a wavelength-routed network. In [22] , the concept of a lightpath was generalized into that of a light-tree, which, like a lightpath, is a clear channel originating at given source node and implemented with a single wavelength. But unlike a lightpath, a light-tree has multiple destination nodes; hence it is a point-to-multipoint channel. The physical links implementing a light-tree form a tree rooted at the source node, rather than a path in the physical topology, hence the name.
The study in [22] focused on the RWA problem for static traffic (traffic based on connection requests known in advance, the different types of traffic will be discussed in the next chapter in details). It was demonstrated that by extending the lightpath concept to a light-tree, the network performance (in terms of average packet hops) can be improved while the network cost (in terms of the number of optical transmitters / receivers required) decreases.
Light-trees are implemented by employing optical devices known as power splitters at the OXCs [4] . The figure below (Figure 11) shows a power splitter and a combiner.
[pic]
Figure 11: (a) power splitter, (b) combiner
A power splitter has the ability to split an incoming signal, arriving at some wavelength (, into up to m outgoing signals, m >= 2; m is referred to as the fan-out of the power splitter. Each of these m signals is then independently switched to a different output port of the OXC. Note that due to the splitting operation and associated losses, the optical signals resulting from the splitting of the original incoming signal must be amplified before leaving the OXC. Also, to ensure the quality of each outgoing signal, the fan-out m of the power splitter may have to be limited to a small number.
If the OXC is also capable of wavelength conversion, each of the m outgoing signal may be shifted, independently of the others, to a wavelength different than the incoming wavelength (. Otherwise, all m outgoing signals must be on the same wavelength (.
The main feature of light-trees is the inherent capability for performing multicasting in the optical domain (as opposed to performing multicasting at a higher layer, e.g., the network layer, which requires electro-optic conversion). Such wavelength routed light-trees are useful for transporting high-bandwidth, real-time applications such as high-definition TV (HDTV). Therefore, OXCs equipped with power splitters will be referred to as multicast capable OXCs (MC-OXCs). Note that, just like with converter devices, incorporating power splitters within an OXC is expected to increase the network cost because of the large amount of power amplification and the difficulty of fabrication.
With the availability of MC-OXCs and the existence of multicast traffic demands, the problem of establishing light-trees to satisfy these demands arises. We will call this problem the multicast routing and wavelength assignment (MC-RWA) problem. MC-RWA bears many similarities to the RWA problem discussed in section 1.4 above. Specifically, the tight coupling between routing and wavelength assignment remains, and even becomes stronger: in the absence of wavelength conversion the same wavelength must be used by the multicast connection not just along the links of a single path but along the links of the whole light-tree. Since the construction of optimal trees for routing multicast connections is by itself a hard problem, the combined MC-RWA problem becomes even harder.
As we already know, optimal solutions for the point-to-point RWA problems are not practically obtainable, and with a more general construct (the light-tree) and hence a much larger search space, this is going to be even more true for the MC-RWA problems.
The benefits of multicasting in wavelength routed optical networks were first demonstrated in [32] . These benefits as proved in the reference paper can be summarized in the following points:
• Using light-trees (spanning the source and destination nodes) rather than individual parallel lightpaths (each connecting the source to an individual destination) requires fewer wavelengths and consumes a significantly lower amount of bandwidth.
• Using light-trees increase the logical connectivity of the network by employing more receivers than transmitters, and in the same time the hop distance is decreased.
• Light-trees not only can provide improved performance for unicast traffic, but naturally better support multicast traffic and broadcast traffic because of their inherent point-to-multipoint nature.
• Moreover, optical multicasting (which is used to implement a light-tree) has some improved characteristics over electronic multicasting since “splitting light” is conceptually easier than copying a packet in electronic buffer.
6. Thesis Organization (incomplete):
Chapter 2
2. Survey of literature
This chapter is dedicated to the discussion of the previous work in our research area. It should be noted that the optical network design is a very rich and dynamic research area that leads to many research points for different cases or under varying assumptions.
1. Technical Classification for RWA:
To start with, we will first present a technical classification of the RWA problem under consideration and then discuss the different contributions. The classification is based on different aspects of the problem under consideration:
1. Traffic type:
The traffic type determines different class of problems, which can be either [7] :
1. Static:
Where the entire set of traffic connections is well known in advance and will not change (at least for the current configuration time). The problem is then to set up lightpaths fro these connections in a global fashion.
2. Incremental:
In this case, connection requests arrive sequentially, a lightpath is established for each connection, and the lightpath remains in the network indefinitely.
3. Dynamic
In opposition to the previous case, a lightpath is set up for each connection request as it arrives, and then is released when after some finite amount of time.
The RWA problem for static traffic is known as Static Lightpath Establishment (SLE) problem or Static-RWA problem. The RWA problem for both incremental and dynamic cases is known as Dynamic Lightpath Establishment (DLE) problem or Dynamic-RWA problem. As the dynamic traffic case is based on stochastic models and leads to dynamic programming methods [6] , it is considered out of the scope of the current work and shall be considered for future work.
2. Wavelength-conversion capability:
As discussed in the previous chapter, there are different levels of wavelength conversion capabilities. The full wavelength conversion case reduces the RWA problem to classical routing problem and thus has been less attractive to research. Some research work focused on the case of no wavelength conversion capability and others studies the case of limited conversion and a limited number of wavelength conversion capable optical switches. Wavelength capability in the networks (rather than on each switch as explained in the previous chapter) can be considered in different levels:
• Full-wavelength conversion
• Sparse wavelength conversion
• No wavelength conversion
According to whether all the network, only a limited subset of the nodes, or none of the node are equipped with wavelength converters, respectively
3. Objective function:
The main two objective functions used in literature are: minimizing the number of used wavelengths to establish a given set of connection requests, referred to as Min-RWA problem. Or, alternatively, maximizing the number of established connection requests for a given number of wavelengths
4. Fiber multiplicity:
Studies have differentiated between the case where each physical link is composed of a single fiber link or multiple ones. The interest in multi-fiber networks is motivated by the economic advantage of installing bundles of fiber on network links for the purpose of future grows [10] .
5. Requests multiplicity:
Some research work, assumed only a single connection request between any Source-destination (S-D) pair, while other studied the more general case where the same S-D air can request multiple connections.
6. formulation structure:
The mathematical modeling of different formulations may approach the problem from different views, one such aspect is the significance of the variables used in the modeling. The major two classes are the use of variable to reflect link flows (referred to as link-flow based formulation), or variables that reflect path flows (referred to as path-flow based formulation). The advantage of using a link-flow based formulation over a path-flow based formulation is that the former has fewer variables. In fact, the number of links grows quadratically with the number of nodes in the network, whereas the number of paths may grow exponentially with the number of nodes [10] .
In this study, we survey the different formulation, and solution approaches for the static traffic RWA problem (or SLE problem), for the general Mesh topology case while varying the rest of assumptions of the problems (wavelength conversion capability, fiber multiplicity, requests multiplicity, and objective function).
2. Functional Classification for static RWA:
A special study has focused on the static RWA problem's different algorithms and solution approaches [11] . It provided a novel classification based on the functional aspects of each algorithm. Based on this classification different comparisons has been carried out to highlight the different challenges and trade-offs or advantages and disadvantages of each category.
Generally, the RWA problem is partitioned into two sub-problems; routing sub-problem and wavelength assignment sub-problem. The authors further divide each sub-problem into two components (1) search and (2) selection functions. Figure 12 gives example algorithms for solving each functional element described in the routing and wavelength assignment problems, respectively.
[pic]
Figure 12: functional classification of Routing & Wavelength Assignment algorithms.
We will further discuss the different functional elements of each problem algorithms.
1. Functional elements of routing algorithms:
The search space for the routing problem exponentially increases with the number of network nodes and links. Thus, it is impractical to take into account all the possible source destination pairs. For this reason, the routing functionality is usually divided into two components; search and selection.
1. Search function:
The search function is usually performed by well-known techniques as shortest-path (SP) algorithm and its variations. The different search functions are:
• Shortest Path (SP): Shortest Path algorithms find the shortest route from a given source to a destination in a graph. The route is a path whose cost is less than any other route from the source to the destination. The cost function is most commonly the number of hops in the path. The shortest path algorithm generates one route and it is independent of other selections.
• K-shortest Path (K-SP): K-shortest path algorithms find more than one (of number that equals k, hence the naming) route for each source-destination pair. Those K alternative paths provide the flexibility in route selection [25] . However, the routing problem is transformed into a selection problem, where routes are selected to satisfy the required objective function of the model.
2 Selection function:
The selection function varies from the following:
• Sequential selection: this technique is considered to be the simplest method. Usually a greedy algorithm is employed. The main disadvantage of such techniques is not guaranteeing the optimality of the solution, since the selection is made in sequence and individually. Such algorithms algorithm depends on two main sub-components, namely; selection order and selection rule.
The selection order is the selection sequence of lightpaths to be routed (or to be assigned) and the selection rule is a decision criterion to choose one of the available candidates.
• Combinatorial selection: this selection technique is considered to be more complex than the previous alternative. In the same time the main advantage of it is that it considers the inter-dependency of lightpath routing that sequential approaches can not take into consideration (but approximated by an appropriate ordering scheme).
For an optimal solution, a Mixed Integer Linear Program (MILP) can be used. This technique is the most complex in terms of computational complexity.
For a heuristic solution, a random algorithm may be used. In this approach, routing algorithm is repeatedly performed for different set of routes and the objective function is satisfied by the appropriate choice of the set of routes at each step.
2. Functional elements of Wavelength Assignment algorithms:
Again, the Wavelength assignment problem can also be defined in terms of search and selection functions.
1. Search function:
The search function simple since any available wavelength can be assigned along the selected route.
2 Selection function:
This problem is concerned with selecting a certain wavelength among the available wavelength in such a way to achieve the minimum used number of wavelength or in other words, maximize the wavelength utilization. Selection is further classified into sequential and combinatorial approaches as for the routing case. It should be noted that the wavelength assignment problem is mapped to a graph-coloring problem and is known to be NP-complete. [1] , [12]
• Sequential selection: As previously, this technique is less complex than the combinatorial case. In the same time optimality is not guaranteed as the inter-dependencies between the selections is not considered.
• Combinatorial selection: This selection technique is considered to be more complex than the previous alternative. Again, the main advantage of it is that it considers the inter-dependency of lightpath assignment that sequential approaches can not take into consideration (but approximated by an appropriate ordering scheme).
There are different algorithms for heuristic solutions. Many are special purpose algorithms specialized for this problem.[12]
3. General Notations:
In this section, we will introduce the notations that will be used throughout this chapter to form a common base for discussion and comparison between the different approaches. We will model the network as a graph G(V,E) with vertex set V and nodes or edges E :
o N: denotes the number of nodes in the network, N=|V|.
o L: denotes the number of links in the network, L=|E|.
o L': denotes the number of links in the network that are used in the pre-selected candidate paths
o W: denotes the number of wavelengths in each of the network links.
o R: denotes the number of source-destination SD pairs.
o P': denotes the number of candidate paths for each connection request.
o P: denotes the total number of paths calculated in the network, which is equal to P'*R.
4. Different Approaches for static RWA:
In this section we will present different solution approaches for the static RWA problem. The different solution approaches will be referred to according to their objective function, formulation, and fiber and requests multiplicity. The functional specification of each approach will be discussed in details for each approach.
1. Min-RWA, link-based, no conversion, unique requests, single fiber:
This approach first appeared in [13] and published by one of the authors in his book [1] , and was referred to in the review paper [7] . This approach depends on decomposing the RWA problem into 2 sub-problems, namely:
1. Routing sub-problem: where the objective is to find paths (lightpaths) to satisfy the given connection requests
2. Wavelength assignment sub-problem: where the objective is the assign each of the lightpaths a different wavelengths respecting the wavelength continuity constraint.
Each of these 2 sub-problems is itself an NP-Complete problem. In this approach, they are solved separately and in sequence.
1. Routing sub-problem:
The routing sub-problem is solved by formulating it as a mixed-integer linear program MILP model based on the similarity with a well-known problem of Multi-commodity network flow problem (MCNF) [29].
Let us first present the Routing sub-problem formulation with the discussion of its constraints and then discuss the solution approach. As, referred to in the title of this approach the model has the following characteristics and assumptions:
• Min-RWA
• Link-based model
• No wavelength conversion
• Unique Requests
• Single-fiber links
• Wavelength continuity constraint is not explicit in this model since it is considered in the Wavelength assignment sub-problem.
The formulation is as follows:
Objective Function: Minimize [pic] (1.1)
Such that [pic][pic] [pic] (1.2)
Flow conservation constraints:
[pic] [pic] if s=j (1.3)
[pic] if d=j
0 otherwise
Integrality constraints:
[pic] = 0,1 (1.4)
[pic] = 0,1 (1.5)
Where
[pic]denote the traffic (in terms of a lightpath) from any source s to any destination d.
(the authors consider at most one lightpath from any source to any destination;
hence[pic]=1 if there is a lightpath between s to d [pic]=0 otherwise.)
[pic] denote the flow variables (in terms of lightpaths) that is flowing from source s to
destination d on link ij.
In the above model, equation (1.1) simply states the objective is to minimize the introduced Fmax variable. This variable is constraints by equation (1.2) to be larger than the sum of flows between all the SD pairs on any link. The main constraints of the model in (1.3) formulate the "flow balance" or "flow conservation" equations; the sum of the outgoing flows subtracted from the sum of all incoming flows in any node equals the traffic consumed in the node. The traffic consumed may be either positive if the node is the source, negative if it is a sink node, or zero it is neither source nor sink of that connection. These flow balance equations are repeated for every connection request (SD pair).
Since the traffic demands [pic] between any SD pair are inputs to the models, equation (1.4) simply states that they can only be given in 0/1 format. On the other hand, equation (1.5) constrains the model's flow variables to only integer 0/1 quantities.
The general form of the MILP can easily overwhelm the capabilities of today’s computing facilities, even for moderate-sized networks. This is mainly because of the large number of variables and constraints in the model and due to the integrality constraints in the model.
A solution technique has been provided to overcome the above two problems. First, to reduce the number of variables in the model, only the non-zero connection requests ([pic]) will be considered. This can eliminate all of the equations (1.4). Also, this approach will reduce the number of variables in the constraints of equation (1.3).
Further reduction of the number of variables was achieved by assuming that a particular lightpath will not pass through all the ij links. By determining the links which have a good probability of being in the path through which a lightpath may pass, only those links with corresponding [pic] variables for that particular SD pair are considered.
Second, to overcome the problem of extensive computations due to the integrality constraints, a new technique called "randomized rounding" technique [14] , has been developed. As part of this technique, the integrality constraints have been relaxed, and thus eliminating all instances of equation (1.5). After solving the proposed relaxed LP model (using a general-purpose LP solver [15] ) the technique then proceeds by "stripping" paths that has been selected by the MILP solver. This is accomplished by extracting and converting the fractional flows provided by the LP solution to integer flows forming a set of alternate paths for each request. Each one of those alternate paths may be used to route the connection. A single path is then randomly chosen for each connection. It should be noted that using this technique the search space of the routing sub-problem has been reduced using the fractional values of the flow variables obtained by the solver.
2. Wavelength assignment sub-problem:
Once a path has been chosen for each lightpath, the number of lightpaths traversing any physical fiber link defines the congestion on that link. Now, it is needed to assign wavelengths to each lightpath such that any two lightpaths that pass through the same physical link are assigned different wavelengths.
This Wavelength assignment sub-problem is solved by reformulating the wavelength assignment problem as a "Graph coloring" problem and solving it using graph coloring algorithms. Assigning wavelength to lightpaths, so as to minimize the number of wavelengths under the wavelength-continuity constraint is be reduced to graph coloring problem, which can be shown in the following steps:
1. Construct an auxiliary graph G' (V', E'), so that each lightpath in the system is represented by a node in graph G. There is an undirected edge between two nodes in graph G' if the corresponding lightpaths pass through a common physical fiber link.
2. Color the nodes of the graph G' such that no two adjacent nodes have the same color.
This formulation of the wavelength assignment problem is best represented by the following two figures. First, Figure 13 shows a WRON with eight connection requested that has been assigned eight lightpaths after solving the routing sub-problem.
[pic]
Figure 13: An optical network with eight routed lighptahs
Second, Figure 14 shows the auxiliary graph constructed as part of the wavelength assignment sub-problem solution.
[pic]
Figure 14: Auxiliary graph for the Wavelength-assignment sub-problem
This problem can be solved using efficient sequential graph coloring algorithms. The "smallest-last" coloring algorithm [12] was employed in this approach. The algorithm depends on ordering the vertices to be colored according to the descending order of their degrees and try to color them in sequence to minimize the total number of colors used.
2. Min-RWA, link-based, no conversion, multiple requests, single fiber:
This approach is a generalization of the previous one, where each SD pair can request more than a single connection request [7] . Again, the RWA problem is decomposed into 2 sub-problems Routing, and Wavelength Assignment respectively.
1. Routing sub-problem:
The routing sub-problem in this approach follows the same formulation as the previous one, with little change to accommodate the case of multiple connection requests between the same SD pair.
As, referred to in the title of this approach the model has the following characteristics and assumptions, which are mostly inherited from the previous approach:
• Min-RWA.
• Link-based model.
• No wavelength conversion.
• Multiple Requests
• Single-fiber links
• Wavelength continuity constraint is not explicit in this model since it is considered in the Wavelength assignment sub-problem.
The formulation is as follows:
Objective Function: Minimize [pic] (2.1)
Such that [pic] [pic] (2.2)
Flow conservation constraints:
[pic] [pic] if s=j (2.3)
[pic] if d=j
0 otherwise
Traffic demand constraints:
[pic] [pic] (2.4)
Capacity constraints:
[pic] [pic] (2.5)
Integrality constraints:
[pic] = 0, 1 [pic] (2.6)
where
[pic]denote the traffic (in terms connection requests) from any source s to
any destination d on any wavelength w.(assuming that two or more lightpaths
may be set up between the same source-destination pair, if necessary, but each of
them must employ a distinct wavelength; hence [pic]=0,1 )
[pic] denote the number of connections needed between source s and destination d.
[pic]denote the flow variables (in terms of lightpaths) that is flowing from source s to
destination d on link ij and wavelength w. [pic][pic] since a wavelength on a link
can be assigned to only one path ( wavelength-capacity constraint)
In the above model, equation (2.1) simply states the objective is to minimize the introduced Fmax variable. This variable is constrainted by equation (2.2) to be larger than the sum of flows over all wavelengths over all connections on any link ij. The flow balance constraints of the model in (2.3) ensures that the sum of the outgoing flows subtracted from the sum of all incoming flows in any node equals the traffic consumed in the node. The traffic consumed may be either positive if the node is the source, negative if it is a sink node, or zero if it is neither source nor sink of that connection. These flow balance equations are repeated for every connection request (SD pair) and for every available wavelength W.
Equation (2.4), forms the traffic demand constraints, which ensures that different lightpaths (with different wavelengths) has been established to satisfy the number of connection requests between the SD pair; [pic].
The capacity constraints in equation (2.5), states that the same wavelength can only be assigned once to any lighpath between any SD pair on the same link ij.
Furthermore, equation (2.6) constrains the model's flow variables to only integer 0/1 quantities.
From the above presented formulation and the discussion on the previous model, it is easily concluded that this model has a larger number of variables and constraints. It might not be suitable to use the same developed techniques for the previous approach to solve this problem in hand.
2. Wavelength assignment sub-problem:
Independently from the routing problem, once each connection requests (irrelatively if it was for the same SD pair or not) has been assigned a lightpath, the wavelength assignment problem can still be solved in the same method as in the previous approach.
Note:
It should be noted that the assumption made in this approach, that multiple connection requests between the same SD pair must use different wavelength is a limitation on the problem itself. Furthermore this assumption is not necessary, different connection requests between the same SD pair can be carried out by link-disjoint paths (path that don't share any links) whenever possible and thus assigned the same wavelength.
3. Min-RWA, link-based, full-wavelength conversion, unique requests, single fiber:
This approach is a special version of the above two approaches where the network is assumed to be composed of full-wavelength conversion capable nodes [7] . As previously mentioned in Chapter 1, this case reduces the RWA problem to the classical routing problem (in circuit-switched telephone networks). Thus the problem is completely solved by solving the routing sub-problem, and the wavelength assignment sub-problem is not an issue. In other words, once lightpaths has been established for each connection requests, any wavelength available on any link may be used. Note that a single lightpath in such a wavelength-convertible network can possibly use different wavelengths along each of the links in its path.
Furthermore, the routing problem is formulated using the same ILP model and constrains as the 1st presented approach. Thus, we will not repeat them in this section.
This approach as a variation of the above approaches still inherits most of its characteristics and assumptions:
• Min-RWA.
• Link-based model.
• Full-wavelength conversion
• Unique Requests;
• Single-fiber links
• The wavelength continuity constraints are eliminated
Note:
This problem is not of much commercial importance, since in most cases full wavelength conversion in the network is not preferred and may not even be necessary due to high costs and limited performance gains.
4. Max-RWA, path-based, no conversion, multiple requests, single-fiber:
This approach was first published in [17]. This approach handles the problem in a different method than the previously presented approaches. If we consider the same decomposing of the RWA problem into Routing and wavelength assignment problems, the solution becomes:
1. Routing sub-problem:
In this formulation the routing problem itself is decomposed into:
• The calculation of different paths for each connection request, and then
• A selection for the optimal path for each one according to the imposed constraints and the objective function.
Referring to the functional classification of static RWA problems (in section 2.2, and in [11] ), where the routing problem is subdivided into search and selection, in this formulation the search component of the routing sub-problem is first calculated by finding a set of alternative paths for each connection.
As will be formulated in the model, for each connection request between any source s and destination d, a physical path [pic] is calculated. This concept is illustrated in Figure 15 below. The figure shows a set of different SD pair connection requests (the number of connection requests is R as conforming to our notation), and for each request, a set of paths are calculated.
[pic]
Figure 15: illustration of the search phase of Routing sub-problem
2. Wavelength assignment sub-problem:
Contradicting to the previous approaches, the selection component of the routing problem along with the wavelength assignment is formulated as an ILP and is solved for optimality. The solution of this ILP determines which paths of the candidate paths for each request are used and a wavelength is assigned for each of them.
The basic characteristics of this approach as will be mapped to its ILP can be given as follows, only different aspects will be commented:
• Max-RWA
• Path-based model
• No wavelength conversion;
• Multiple requests
• Single-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
The formulation is as follows:
Objective Function: Maximize [pic] (4.1)
Capacity constraint: [pic] (4.2)
Traffic demands: [pic] (4.3)
[pic] i=1,….,R
Integrality constraints:
[pic] , integer i=1,….,R (4.4)
[pic] , integer i= 1,….,P, j=1,…..,W (4.5)
where
R: denote the number of source-destination (s-d) pairs.
L: denote the number of links.
W: denote the number of wavelengths per link
[pic]= {mi}, i=1,2….,R : number of connections established for source-destination pair i
T: offered load (total number of connection requests to be routed).
ρ={ ρ i}; i=1,2,…,R: fraction of the load to be established for source-destination pair i (thus,[pic]= number of connections to be set up for source-destination pair i)
A={aij}: PxN (path- s-d pair incidence) matrix in which aij = 1 if path i is between source-destination j, and aij =0 otherwise.
B={bij}: PxM (path-edge incidence) matrix in which bij = 1 if link j is on path i, and bij =0 otherwise.
C={cij}: PxW (path-wavelength assignment) matrix in which cij = 1 if wavelength j is assigned to path i, and cij =0 otherwise.
As previously, equation (4.1) states that the objective is to maximize the sum of satisfied connections. The capacity constraints in (4.2) specify that a certain edge can not accommodate more than one connection on the same wavelength. The traffic demands constraints in (4.3) ensures that the sum of the assigned paths with their respective wavelengths to a certain SD pair must be at least satisfy the requested number of connections for it,[pic]. The 2nd equation of this constraint is there to separate the variables [pic] from the actual demanded number of connections[pic].
Since the number of connection requested for each SD pair is [pic], which is an input to the model, equation (4.4) simply states that they can only integers. On the other hand, equation (4.5) constrains the model's assignment variables to only integer 0/1 quantities.
To further illustrate the model and the definition and relation between the different matrices involved in it, the following diagram (see Figure 16) is presented. The diagram is an extension of the previous one (Figure 15), the same components, namely the set of traffic connections and their candidate paths as defined by the A matrix are shown. Also, the relation between each candidate path and the set of link sin the networks are shown and are defined by the B matrix in the model (note that only one candidate path relation with links is drawn for simplicity).
[pic]
Figure 16: illustration of model formulation of section 2.4.4
We should note that this formulation was presented for the purpose of providing tight bounds on the solution of any RWA algorithms. Thus the above model has not been implemented.
5. Max-RWA, path-based, no conversion, multiple requests, single-fiber(2):
This approach was published also in [17], as an alternative to the previous formulation. Again, using the same decomposing of the RWA problem into Routing and wavelength assignment problems:
1. Routing sub-problem:
It is repeated exactly as the same previous approach.
2. Wavelength assignment sub-problem:
As opposite to the previous the previous approach, the RWA sub-problem with the optimal selection of candidate paths for connection requests is formulated based on the concept of "Graph coloring" problems [12] . As discussed in the wavelength assignment sub-problem of the 1st presented approach, an auxiliary G'(V', E') graph is created, where each node corresponds to a lightpath and two nodes are adjacent if and only if the corresponding two lightpaths share a common physical link. This means a set of lightpaths can be assigned a common wavelength only if the corresponding nodes in G' form and independent sets (set of nodes that are disconnected).
The basic characteristics of this approach as will be mapped to its ILP can be given as follows, only different aspects will be commented:
• Max-RWA;
• Path-based model;
• No wavelength conversion;
• Multiple requests:
• Single-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
The formulation this time is somehow different than the previous one. Instead of having the C matrix to indicate the assignment between paths and wavelengths, this relation has been broker over two steps:
• Let [pic]={fi} be the vector of path-flows variables, where fi denotes whether the corresponding path carries a flow or not (0/1 indicator)
• Let [pic]= {wi} be the vector holding the indicator variables that determines if wavelength i is used or not. The length of this vector is assumed to be the maximal number of independent sets in the auxiliary graph G' and is denotes "I"
• D={dij}: PxI (path-independent set incidence) matrix, where,
Dij = 1, if path i, belongs to independent set j
0, otherwise
The formulation is as follows:
Objective Function: Maximize [pic] (5.1)
Such that:
Wavelength constraint: [pic] (5.2)
Traffic demand constraints:
[pic] (5.3)
[pic] i=1,….,R
[pic] (5.4)
Integrality constraints:
[pic] , integer i=1,….,I (5.5)
where
R,W, [pic],[pic], P, A as previous problem
I: the number of maximal independent sets in G'.
[pic]= {wi}, i=1,2….,L : variables to indicate whether or not that wavelength indexed I
is used or not. (whether an indepenedt set is assigned this wavelength or not).
D={dij}: PxI (path-independent set incidence) matrix in which dij = 1 if independent
set j contains path i, and dij =0 otherwise.
[pic]={fi} the vector of path-flows.
Same as the previous model the objective function in equation (5.1) has not changed. On the other hand the wavelength constraint in equation (5.2) ensures that the number of assigned wavelengths does not exceed the physical number of wavelengths per fiber.
The traffic demands constraints in (5.3) ensure that a number of paths have been selected to carry the traffic of connection requests. Again, the 2nd equation of this constraint is there to separate the variables [pic] from the actual demanded number of connections[pic].
The new constraint in equation (5.4) ensures that every path that has been selected (assigned a flow) is assigned a wavelength.
The last constraint (5.5) only states that each wavelength must be fully used or not used at all hence each [pic]is either 0/1.
To further illustrate the model and the definition and relation between the different matrices involved in it, relative to the previous modeling, the following diagram (see Figure 17) is presented.
The diagram is an extension of the previous one (Figure 16), the same components, namely the set of traffic connections and their candidate paths as defined by the A matrix are shown. Also, the relation between each candidate path and the set of path-flow variables is indicated by the fact that only a group of the candidate paths is selected to carry the traffic, then each flow variable is assigned an appropriate wavelength through the D matrix.
[pic]
Figure 17: illustration of the model of section 2.4.5.
Along with the previous model, this formulation was presented for the purpose of providing tight bounds on the solution of any RWA algorithms. Thus the above model has not been implemented.
6. Max-RWA, link-based, no conversion, multiple requests, single-fiber:
This approach was published in [18]. This approach is similar to the previous ones but the main difference is that the model variables reflect link-flows rather than path-flows.
The approach presented by the authors addresses the RWA problem from a different angle, instead of decomposing the problem into two sub-problems; the problem is formulated as a single ILP model. This model is close to the 1st approach presented, with the difference that the model incorporates the Wavelength assignment problem too.
Let us first present the main characteristics and assumptions of the model:
• Max-RWA
• Link-based model
• No wavelength conversion
• Multiple Requests
• Single-fiber links
• Wavelength continuity constraint is explicit in this model as the ILP addresses the combined RWA problem.
The formulation is as follows:
Objective Function: Maximize [pic] (6.1)
Such that:
Traffic demand constraints:
[pic] [pic] (6.2)
Wavelength continuity:
[pic] [pic] (6.3)
Physical Links:
[pic] [pic] (6.4)
Capacity continuity:
[pic] [pic] (6.5)
Flow conservation:
[pic] (6.6)
=[pic]
Where
Parameters:
s and d denote the originating and terminating node of a lightpath.
i and j denote the endpoints of a physical link
k: denotes the wavelength number from 0 to W-1.
q: used as subscript or superscript denotes the qth lightpath between a source-destination pair.
N: the number of nodes in the network.
W: the number of wavelengths a fiber can support.
[pic]= {[pic]} the traffic matrix, i.e [pic]is the number of connections that are to be established between node s and node d.
[pic]denotes the existence of a link in the physical topology. If [pic]=1 then there is a fiber link between node i and j, otherwise [pic]=0.
Variables:
[pic]=1, if there exists a qth lightpath between (s,d), else [pic]=0.
[pic]=1, if there exists a qth lightpath between node s and node d uses wavelength k, else [pic]=0.
[pic]=1, if there exists a qth lightpath between node s and node d uses wavelength k and is routed over physical link (i,j), else [pic]=0.
Since it is a Max-RWA problem, the objective function in equation (6.1) is to maximize the sum of satisfied connections over all the SD pairs over all the lightpaths for each. The traffic demand constraints in (6.2) ensures that the number of connections established is at most[pic]. The wavelength continuity constraint in (6.3) ensures that is a lightpath is exists then only one lightpath is assigned to it among the W possible wavelengths.
Equation (6.4), the physical constraints, ensures that only those [pic]could be non-zero for which the corresponding [pic]variables are non zero. This means that any established path must be established through a flow over the links between different i,j nodes.
The wavelength capacity constraints (or wavelength clash constraint), in equation (6.5) above, enforces that no two lightpaths traversing through the physical link (l,m) will have the same wavelength assigned to them.
The flow balance or flow conservation equations, in (6.6) (similar to the more simple version in the 1st presented approach) ensures that the same wavelength is reserved at every node for a lightpath[pic].
It should be noted, that due to the fact the both the Routing and Wavelength assignment sub-problems are considered simultaneously, the ILP model is rather more complex than the previous ones.
Solution of the LP-relaxation yields fractional flows which when appropriately rounded up to a 0 or 1 yield an integer solution. For example when solving the LP-relaxation of the above ILP we obtain variables[pic], [pic] and [pic]which contain the fractional flow information, where [pic]=0.5 would imply that 0.5 units of flow of the qth connection of source–destination pair (s,d) using color k flows on physical link (i,j).
The algorithm used rounds variables obtained by solving the above ILP. Note that by rounding variable of type[pic], [pic] and [pic]we obtain a wavelength and a path to a connection of an SD pair. This algorithm terminates when it can no longer round variables without violating wavelength continuity constraints.
7. Max-RWA, link-based, no conversion, multiple requests, single-fiber:
This approach was published also in [18], as an alternative to the previous formulation. The main difference in this approach is its way of interpreting the WRON, a WRON with W wavelengths being supported on a fiber is considered a network with W multiple-fiber links between the nodes with each fiber supporting just one wavelength. Each of the links labeled q ( {0, 1, 2, …. W-1}
Similar to the previous approach, this approach addresses the RWA problem as a unit; the problem is formulated as a single ILP model incorporating both the routing and wavelength assignment problem.
Let us first present the main characteristics and assumptions of the model:
• Max-RWA;
• Link-based model;
• No wavelength conversion;
• Multiple Requests:
• Single-fiber links:
• Wavelength continuity constraint is explicit in this model as the ILP addresses the combined RWA problem.
The formulation is as follows:
Objective Function: Maximize [pic] (7.1)
Such that:
Traffic demand constraints:
[pic] [pic] (7.2)
Capacity continuity:
[pic] [pic] (7.3)
Flow conservation:
[pic] [pic] (7.4)
Where
Parameters:
s and d denote the originating and terminating node of a lightpath.
i and j denote the endpoints of a physical link
k: denotes the wavelength number from 0 to W-1.
q: used as subscript or superscript denotes the qth lightpath between a source-destination pair.
N: the number of nodes in the network.
W: the number of wavelengths a fiber can support.
[pic]= {[pic]} the traffic matrix, i.e [pic]is the number of connections that are to be established between node s and node d.
[pic] =1 denotes the existence of the qth multiple link of the physical link (i,j), otherwise[pic]=0. q ( {0, 1, 2, …. W-1}
Variables:
[pic] denotes the number of lightpaths established between node s and node d. it takes positive integral values.
[pic]=1, if a lightpath is set up between node s and node d using the qth multiple link of edge (i,j) , else [pic]=0
Again as a Max-RWA problem, the objective function in equation (7.1) is to maximize the sum of satisfied connections over all the SD pairs. The traffic demand constraints in (7.2) ensures that the number of established lightpaths from origin node s and destination node d are equal and is at most the requirement[pic], for source destination pair (s,d).
Equation (7.3) ensures that at most one lighpath traverses the qth copy of the link (i,j).
The flow balance equation in (7.4) in the same time ensures that at a node "wavelength is conserved", i.e., the same wavelength is used on the incoming and outgoing links of a lightpath.
Similar to the previous approach, this ILP model is solved in two steps, first solving the LP-relaxed version, then using a rounding algorithm to obtain integral routes and their assigned wavelengths.
8. Max-RWA, path-based, no conversion, multiple requests, mutli-fiber:
This approach was developed recently to address the problem of multi-fiber links in the WRON [10] .
This approach handles the problem in a different method than the previous presented approaches. If we consider the same decomposing of the RWA problem into Routing and wavelength assignment problems, the difference will be clear:
1. Routing sub-problem:
In this formulation the routing problem itself is decomposed into:
• The calculation of different paths for each connection request, and then
• A selection for the optimal path for each one according to the imposed constraints and the objective function.
Referring to the functional classification of static RWA problems (in section 2.2, and in [11] ), where the routing problem is subdivided into search and selection, in this formulation the search component of the routing sub-problem is first calculated by finding a set of alternative paths for each connection.
As will be formulated in the model, for each connection request between any source s and destination d, a physical path [pic] is calculated. This concept has been illustrated before in Figure 15. The figure shows a set of different SD pair connection requests (the number of connection requests is R as conforming to our notation), and for each request, a set of paths are calculated.
2. Wavelength assignment sub-problem:
Contradicting to the previous approaches, the selection component of the routing problem along with the wavelength assignment is formulated as an ILP and is solved for optimality. The solution of this ILP determines which paths of the candidate paths for each request are used and a wavelength is assigned for each of them.
The basic characteristics of this approach as will be mapped to its ILP can be given as follows, only different aspects will be commented:
• Max-RWA
• Path-based model
• No wavelength conversion
• Multiple requests
• Multiple-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
The formulation is as follows
Objective Function: Maximize [pic] (8.1)
Such that:
Capacity constraint: [pic] [pic] (8.2)
Traffic demand constraint: [pic] [pic] (8.3)
Integrality constraints:
[pic] , integer [pic] (8.4)
where
[pic] denote the number of fibers deployed on link[pic].
[pic] is the set of wavelengths a fiber can support.
[pic] denote the set of paths in the network. P(s,d) (or respectively P (e)) denote the
subset of paths in the network that use link ( respectively join nodes s and d).
[pic] denote the number of connection requests between nodes s and d.
[pic] denote the number of lightpaths successfully routed over physical path
[pic]and assigned wavelength [pic].
Note:
a connection request is realized by finding a physical path [pic]and a wavelength [pic]that is assigned to every link on p. The pair (p,w) is called a lightpath.
The objective function in equation (8.1) (different from the above models) is to maximize the number of lightpaths successfully established.
The wavelength-capacity constraint (or alternatively referred to as wavelength clash constraint) in equation (8.2) differently stated is the constraint that ensures that the number of lightpaths routed over any link e and assigned the same wavelength w does not exceed the number of fibers Ke deployed on that link.
Equation (8.3) ensures that the number of lightpaths established for a pair (s, d) of nodes does not exceed the traffic demand for that pair.
The integrality and non-negativity constraints of flow variables are stated in equation (8.4). It should be noted that the number of connection requests between any SD pair[pic], is assumed to be integer.
It is worth noting that wavelength continuity is implicitly guaranteed because wavelengths are assigned to entire paths rather than to links.
The RWA problem in this approach, which is now the optimal solution of the above presented ILP model, is solved using a Greedy algorithm. The authors proved that any instance of the above problem for single wavelength is an instance of the "maximum coverage" problem.
Maximum Coverage:
This problem can be formulated as follows; given a universal set U of elements, an integer k, and a collection S of subsets over the elements (that satisfy some structural constraints), the maximum coverage problem is to select k subsets from S such that the total number of elements covered is maximized. It is worth mentioning that, in some applications of the maximum coverage problem, the subsets in S may be implicitly defined rather than explicitly given.
The authors used a simple greedy algorithm that was introduced and analyzed by Hochbaum and Pathria in [16] for the maximum coverage problem. This greedy algorithm is as follows (Figure 18):
[pic]
Figure 18: Maximum coverage greedy algorithm
Their work proceeded by proving that any instance of the RWA problem is also an instance of the maximum coverage problem and thus the above greedy algorithm may be used to provide solutions that are guaranteed to be within a factor of (1-1/e) of the optimal solution.
The proof, mainly specifies the abstracted sets used in the maximum coverage problem. The universal set U of elements is considered to be the (multi-)set of connection requests. In particular the U contains [pic] copies of the pair (s,d) of nodes. A subset Si of U is the set of paths that can be realized simultaneously using the same wavelength wi .Thus with each iteration of the greedy algorithm an RWA problem as formulated above but with one wavelength wi available is solved and the set of connection requests that can be satisfied Si is returned.
The above flow is best described with the below flow chart diagram in Figure 19
[pic]
Figure 19: flow chart of the algorithm used for RWA based on maximum coverage problem
9. Greedy Heuristic Approach:
This solution approach is different than the previous approaches. It addresses the problem from a different point of view; this solution is based on a well known problem in graph theory: the “maximum Edge Disjoint Path” problem (EDP) [19].
This problem is defined as follows:
Maximum Edge Disjoint Paths problem:
In this problem a graph and a set of source-destination pairs are given and the requirement is to find Edge disjoint paths for as many of the pairs as possible. It is easy to see that the maximum edge disjoint paths (EDP) problem is a combinatorial optimization problem and is known to be NP-hard [20] .
The use of this problem and its developed solutions is the core of this approach. The important observation is the fact that lightpaths that are assigned the same wavelength will not traverse the same physical link, i.e., these paths are "edge-disjoint"[1]. Hence, this approach is to use a greedy algorithm for the maximum Edge Disjoint Paths problems to calculate all edge-disjoint paths that satisfy the maximum number of connection requests, those paths will all use the same wavelength. Then iterate again, by using a new wavelength as long as the connection requests are not all satisfied. In such a manner, the overall heuristic approach solves the RWA problem, by satisfying the given connection requests (or lightpaths) with the objective of minimizing the total used number of wavelengths.
This heuristic approach is most close to the presented approach in (section 2.4.8) published in [10] . The main difference is that; at each iteration of the heuristic algorithm, it calls a greedy algorithm for the EDP problem, rather than solving the RWA problem for a single wavelength in the previous approach.
First, the greedy algorithm used to solve the EDP problem is presented in the flow chart diagram below (Figure 20). The Greedy algorithm for EDP problem will be abstracted as a building block in the next diagram. In brief, the operation of the greedy algorithm for EDP problem is to select a random connection request and calculate a path for it. Then delete all the edges shared in this path and pick another request and try to satisfy it using the remaining edges of the network and so on, until no requests can be satisfied.
It should be noted that this algorithm is based on a heuristic approximation (to reduce down the search space) by only accepting paths that are length upper bounded by the value: [pic], where L is the total number of links in the network, [pic]is the graph G diameter, which is defined as: the longest shortest path between any vertices in the graph.
[pic]
Figure 20: Greedy algorithm for EDP
Second, the next flow chart diagram, presented in Figure 21, shows the main heuristic to solve the RWA problem. At each iteration, the algorithm tries to find (through the use of the greedy algorithm for EDP problem) the maximum possible number of connection requests that can be satisfied using the same wavelength (since they are all satisfied by edge-disjoint paths). Then when not all the connection requests has been satisfied the number of wavelengths used is increased and a new iteration is started. The algorithm continues until all the connection requests have been satisfied, with the minimum possible number of wavelengths used.
The authors, also showed using the same framework, the max-RWA problem may e solved, that is maximizing the number of connection requests (or lightpaths) satisfied using a limited number of wavelengths W per fiber. This can be achieved, by terminating the algorithm, not only when all the connection requests have been satisfied, but when the number of wavelengths used has reached W.
[pic]
Figure 21: flow chart of the RWA heuristic based on greedy EDP algorithm
10. Min-RWA, path-based, full conversion, unique requests, single-fiber:
This approach was provided, among different formulations in [6] . This approach is most similar to the first presented one in section (2.4.4, reference [17]) in its use of pre-calculated candidate paths for each connection request. On the other hand, it addresses the case of a network with full wavelength conversion capable nodes as presented in section 2.4.3. The main difference is the formulation of the objective function used.
As previously mentioned in section 2.4.3, this case reduces the RWA problem to the classical routing problem (in circuit-switched telephone networks). For such network with full wavelength conversion capability, there is no distinction between available wavelengths, i.e the wavelength continuity constraint need not to be satisfied along the lightpaths and the number of wavelengths on each link merely specifies a capacity constraint on the total number of lightpaths that can cross that link.
Thus the problem reduces to only Routing problem [23] , the routing problem itself is simplified by calculating some candidate paths for each connection request (as has been shown in Figure 16). As will be formulated in the model, for each connection request between any source s and destination d, a physical path [pic] , [pic] is calculated
This approach focuses on these main characteristics and assumptions:
• Min-RWA
• Path-based model
• full wavelength conversion;
• unique requests
• Single-fiber links
• The wavelength continuity constraints are eliminated
The formulation is as follows:
Objective Function: Minimize [pic] (10.1)
[pic] (10.2)
Capacity constraint: [pic] [pic] (10.3)
Traffic demands: [pic] i=1,….,R (10.4)
Integrality constraints:
[pic] ,non-negative integer [pic] (10.5)
where
R: denote the number of source-destination (s-d) pairs.
L: denote the number of links.
W: denote the number of wavelengths per link
[pic]= {mi}, i=1,2….,R : number of connections to be established for source-destination pair i
[pic]: denote the flow on path [pic] for some connection requests[pic].
[pic]: denote the total flow on a certain link [pic].
The overall cost function in equation (10.1) is given by the sum of link cost functions and each of the link cost functions depends on the amount of flow on the link which is determined according to equation (10.2). This link cost function is the main difference in this approach and will be presented below.
The capacity constraint given in equation (10.3) ensures that the number of flowing path on any link (each assigned a different wavelength) doesn't exceed the number of available wavelengths. On the other hand, the traffic demand constraint in (10.4) represents the requirement that the demand of each OD pair be satisfied by the resulting path flows. Finally, the integrality of the path flow variables is stated in equation (10.5).
The cost function,[pic], presented in the model has two key features that impact significantly on the nature of the optimal solution:
a) The cost function of every link is convex, monotonically increasing, and piecewise linear. Thus, the marginal cost for routing a new lightpath over a given link is larger than the marginal cost for routing the preceding lightpaths on the same link.
b) The breakpoints of each piecewise linear link cost function occur at the integer points (Figure 22).The cost for flow larger than W is (, thereby imposing a link capacity constraint.
Because of feature a), the resulting optimal solution of the associated linear program, favors choosing paths with underutilized links, and tends to leave room for future lightpaths. Because of feature b), the resulting optimal solution tends to be integer, as we will explain shortly, thereby obviating the need for time-consuming integer programming techniques.
[pic]
Figure 22: Piecewise linear cost functions for link l.
The solution approach for the above formulation was based on the specific use of the piecewise linear objective function. The use of piecewise linear objective functions with integer break points has some important consequences. First, the corresponding relaxed linear programming model, where the integer constraints are replaced by the relaxed constraints, can be solved by efficient commercial or special purpose simplex methods with fast running times. Second, even if we relax the integer constraints, it appears that an integer optimal solution can still be obtained in most cases of interest.
Using a simplex code, commercial optimization package CPLEX [24] , the author's research indicates that for most of the cases, the relaxed problem, in any of the given formulations, has an integer optimal solution (assuming it has a feasible solution). The reason is that, because of the structure of the piecewise linear cost function, extreme points of the relaxed constraint polyhedron appear to be integer in the majority of cases. Intuitively, the extreme points of the constraint set tend to correspond to the corner points of the piecewise linear objective function, which take integer values. Note that, as can be seen from simple examples, other types of link cost functions (e.g.: linear, or smooth and convex), such as those commonly used in optimal data network routing, typically result in fractional optimal solutions for the relaxed versions of these formulations.
Finally, it has been mentioned that even in the cases where the solution to the relaxed problem may be fractional, the number of fractional variables in the solution typically turn out to be insignificant relative to the number of integer variables. As a result, it may be possible to round the fractional portion of the solution to integer with the use of simple heuristics.
11. Min-RWA, path-based, no conversion, unique requests, single-fiber:
This approach was also provided in [6] . This approach is quite similar to the one presented in section 2.4.8, (reference [10] ) as will be obvious in the ILP model. The difference is in the objective function used both in its sense (Min-RWA versus Max-RWA) and in the formulation itself.
This approach inherits most of its aspects from the previous one, except of assuming in no wavelength conversion capability available in the network, as listed in its characteristics below:
• Min-RWA
• Path-based model
• No wavelength conversion
• unique requests
• Single-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
As will be formulated in the model, for each connection request between any source s and destination d, a physical path [pic] , [pic] is calculated. To accommodate the different wavelength assignment for the lightpaths, the path-flow variables has been modified to reflect such change. Thus, the new path-flow variables are [pic]. The variable[pic]= 1 , if wavelength w is used by path p, and 0 otherwise.
The formulation is as follows:
Objective Function: Minimize [pic] (11.1)
[pic] (11.2)
Capacity constraint: [pic] [pic] (11.3)
Traffic demands: [pic] i=1,….,R (11.4)
Integrality constraints:
[pic] =0,1 [pic] (11.5)
where
R: denote the number of source-destination (s-d) pairs.
L: denote the number of links.
W: denote the number of wavelengths per link
[pic]= {mi}, i=1,2….,R : number of connections to be established for source-destination pair i.
[pic]: denote the path-flow variables, where [pic]= 1 , if wavelength w is used by path p, and 0 otherwise.
[pic]: denote the total flow on a certain link [pic].
The objective function in equation (11.1) is used again as in the previous approach , namely it is given by the sum of link cost functions and each of the link cost functions depends on the amount of flow on the link which is determined according to equation (11.2).
The capacity constraint given in equation (11.3) ensures that each wavelength on each link can be used at most once. While, the traffic demand constraint in (11.4) ensures that the demand of each OD pair is satisfied. Finally, the integrality of the path flow variables is stated in equation (11.5).
As in the previous model, the solution of this model is based on exploiting the advantages of the piecewise linear objective function used in the formulation. In a similar manner, the authors argue that for most of the cases, the relaxed problem, in any of the given formulations, has an integer optimal solution (assuming it has a feasible solution).
12. Min-RWA, path-based, sparse conversion, unique requests, single-fiber:
In addition to the previous two approaches this one was also presented in [6] . This approach is still similar to the two previous ones, but as referred to in the title; it is a new way to compromise between the two previous assumptions of either full wavelength conversion, or no wavelength conversion capability available.
Thus, as shall be presented in the formulation, this approach considers networks with "sparse wavelength conversion". In other words, only a fraction of the network nodes are equipped with wavelength converters. For these networks, we have the additional freedom of switching wavelength channels along the lightpaths at the nodes with converters.
Mostly common with the previous approaches presented in the same work, the characteristics of this approach can be listed as follows:
• Min-RWA
• Path-based model
• Sparse wavelength conversion
• unique requests
• Single-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links, but due to considering sparse wavelength conversion capable nodes in the networks, different flow conservation constraints are presented and differ according to the node capability.
The authors in the corresponding formulation of this approach on hand, introduced more granularity in the optimization variables in order to distinguish between nodes that have converters and those who do not. More precisely, the problem is formulated in terms of path-link-wavelength variables: [pic]. The variable [pic]=1 , if wavelength w is used on link l by path p and is zero otherwise.
In what follows, we write [pic] if links [pic] and [pic]are successive links of path [pic]. Also, [pic]represents the first link along the path [pic].
The formulation is as follows:
Objective Function: Minimize [pic] (12.1)
[pic] (12.2)
Capacity constraint: [pic] [pic] (12.3)
Traffic demands: [pic] i=1,….,R (12.4)
Flow conservation:
[pic] [pic] (12.5)
[pic] [pic] (12.6)
Integrality constraints:
[pic] =0,1 [pic] (12.7)
where
R: denote the number of source-destination (s-d) pairs.
L: denote the number of links.
W: denote the number of wavelengths per link
[pic]= {mi}, i=1,2….,R : number of connections to be established for source-destination pair i.
[pic]: denote the path-link-wavelength flow variables, where [pic]=1 , if wavelength w is used on link l by path p and is zero otherwise.
[pic]: denote the total flow on a certain link [pic].
The same group of constraints is used again with some differences. The objective function in equation (12.1) is used again as piecewise linear function. Only the sum of the link flows on the links in equation (12.2) is changed to reflect the use of the new path-link-wavelength flow variables.
The capacity constraint and traffic demand constraints are unchanged and are presented in equations (12.3) and equation (12.4) respectively.
The new set of constraints introduced for this case are the flow conservation constraints in equation (12.5) and equation (12.6). These constraints take different forms depending on whether or not there is a wavelength converter at that node. The flow conservation for nodes with wavelength converter is presented in equation (12.5) , where only the total number of lightpaths (assigned different wavelengths) should be preserved in that node. Equation (12.6) represents the case of nodes without wavelength converters, and thus every lightpath with its assigned lighpath should be preserved along this node. Finally, the integrality of the path flow variables is stated in equation (12.7).
This formulation introduces networks with sparse wavelength conversion, which is interesting in practice because practical considerations prohibit using wavelength converters at all the routing nodes.
To overcome the problem of the above formulation, where more constraints have been used, the authors introduce a modified formulation with fewer constraints. The modification depends on using the penalty function. Basically, the authors eliminate the conservation of flow constraints at nodes with no wavelength converters and add to the cost function a penalty term that prescribes a high cost to assignments which violate these constraints. Associated with the penalty term in the cost function is a penalty parameter ( that determines the degree of penalty and, as a result, the extent to which this alternative penalized problem approximates the original. As ( increases, the approximation becomes more accurate. Using[pic], which represents the total flow on link l, in the cost function[pic], we arrive at the following penalized cost function:
[pic] (12.8)
Classical optimization results, state that the relaxed version of problem of the above approach with objective function as shown in equation (12.8) admits an exact penalty, meaning that when the relaxed problem is feasible and the scalar (>0 is large enough, the corresponding penalized problem has the same solutions as the original relaxed problem. Hence, if our problem is feasible, we can find the RWA using the alternative formulation with the penalty function, provided that we choose the penalty parameter ( sufficiently large.
Suppose now that we add conservation of flow constraints at nodes with no converters, pretending there are wavelength converters at these nodes. The optimal solution of the problem does not change, since it already satisfies these constraints. We thus arrive at penalized formulation shown below, together with the integrality constraints.
Objective Function:
[pic](12.8)
Capacity constraint: [pic] [pic] (12.3)
Traffic demands: [pic] i=1,….,R (12.4)
Flow conservation:
[pic] [pic] (12.5)
The penalized problem has multiple advantages of the original formulation as can be listed below:
• The advantage that it may have a feasible solution even when the original problem is infeasible. In particular, if the original problem is feasible and has some optimal solutions, the penalized formulation has the same optimal solutions (assuming ( is large enough).
• If the original problem is infeasible, i.e., there is no possible RWA to satisfy the requests for a network with a given limited number of converters, the penalized problem may still have an optimal solution that involves wavelength conversions at some of the nodes where there are actually no converters. This solution is helpful during a network design process; because it indicates the best placement of extra converters in order to satisfy the given light-path request set.
• The exact penalty formulation can also be used within several other network design contexts. In particular, it can be used for reconfiguration purposes, in order to adapt to changes in traffic demands or network topology. Given a small change in the current operating conditions of the network, we would ideally like to maintain the RWA for the existing lightpaths as much as possible. This can be achieved by introducing a penalty in the cost function that penalizes changes from the current assignment scheme. Then the algorithm tries to find the best assignment suitable for the new conditions in the network without deviating much from the previous assignment.
From the use of the penalized objective function, the problem is modified as if it addresses the problem of RWA problem of a network with full wavelength converters. Thus it becomes much simpler to solve this new formulation. The same solution techniques introduced for the above two approaches can be used with this modified formulation.
13. Min-RWA, path-based, sparse conversion, multiple requests, multi-fiber:
This work was presented in [30] The aim of the authors was to solve the RWA problem in multi-granularity WDM networks.
These networks include nodes with multi-granularity switching capabilities. In particular examples of multi-granularity optical cross-connects (MG-OXC) include:
• Lambda-Switch Capable OXC (LSC-OXC): capable of switching on a single lambda
• Waveband-Switch Capable OXC: capable of switching a waveband (i.e. multiple lambdas)
• Fiber-Switch Capable OXC (FSC-OXC): capable of switching an entire fiber.
Multi-granularity optical cross-connect MG-OXC is considered having the capability of any of the above or any combination of them.
The authors consider in particular WDM networks, with fiber-switch capable (FSC-OXC) and lambda switch capable (LSC-OXC) devices. It is worth mentioning that, as shown in Figure 23, an MG-OXC node is logically identical to an individual FSC-OXC node in conjunction with an external separated LSC-OXC node. As a consequence the authors adopt the separated node form.
The RWA problem for such multi-granularity switching nodes is referred to by RWA+. It is formulated as a linear integer problem stated as follows. Given a physical topology (with FSC-OXCs and LSC-OXCs) and available wavelengths on each link, and requested lightpath demands between all source-destination pairs, determine the routes and wavelengths of lightpaths, such that the maximum number of lightpaths on the most congested link is minimized, subject to the wavelength continuity constraint. For ease of illustration, the number of available wavelengths on each link is assumed the same.
[pic]
Figure 23: a combined MG-OXC node and its logically separated form: (a) MG-OXC node, (b) FSC-OXC and LSC-OXC nodes.
Due to the existence of FSC nodes, a graph transformation is first required. For each FSC node with input (and output) fibers, it is replaced by a bipartite sub-graph with phantom nodes connecting to input fibers, and another phantom nodes connecting to output fibers. Besides, there are additional phantom links connecting the phantom nodes. These phantom links describe possible configuration combinations in-side an FSC node.
As previously, the characteristics of this approach can be listed as follows:
• Min-RWA
• Path-based model
• Sparse wavelength conversion
• Multiple requests
• multi-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
The formulation is as follows:
Objective Function: Minimize [pic] (13.1)
Subject to:
[pic] [pic] (13.2)
Traffic demands: [pic] [pic] (13.3)
Capacity constraints:
[pic] [pic] (13.4)
FSC nodes constraints:
[pic] [pic] (13.5)
[pic] [pic](13.6)
[pic] [pic](13.7)
Integrality constraints:
[pic] [pic] (13.8)
[pic] (13.9)
[pic] [pic] (13.10)
LSC nodes constraints:
[pic] [pic] (13.11)
The notation used in the formulation can be summarized as follows:
Input values:
[pic]set of FSC nodes in the network;
[pic]set of LSC nodes in the network;
[pic]set of physical optical links;
[pic]set of phantom links within FSC nodes;
[pic]set of phantom input nodes for node n;
[pic]set of phantom output nodes for node n;
[pic]set of available wavelengths on each link; (assumed to be the same for simplicity);
[pic]set of source-destination (SD) pairs requesting light-path setup;
[pic]the set of SD pairs where node is the source node;
[pic]candidate path set for SD pair ;
[pic]lightpath demand for SD pair ;
[pic] =1 if path includes link; =0, otherwise;
[pic]=1 if link l is incident to node v; =0, otherwise;
Decision variables:
[pic] most congested link utilization (lightpath number/ W).
[pic]=1 if lightpath p uses wavelength w; =0, otherwise;
[pic] =1 if phantom link l is selected; =0, otherwise;
The objective function is to minimize the highest utilization ([pic]), namely, the utilization on the most congested fiber link with the maximum number of lightpaths passing through. Constraint (13.2) requires that the number of wavelengths used on every link be less than that of the most congested link. Constraint (13.3) is the traffic demand constraint, and restricts the lightpaths demands of all SD pairs to be satisfied. The capacity constraint in equation (13.4) indicates that for each link, there can be at most one lightpath using each wave-length. Constraints (13.4) and (13.8) jointly correspond to the wavelength continuity constraint.
In particular, due to FSC nodes, Constraints (13.6), (13.7), and (13.10) delineate the possible configurations of FSC nodes, through the value of the decision variable [pic]. Constraint (13.5) states that paths can only pass through the phantom links determined by (13.6), (13.7) and (13.10).
Constraint (13.11) is a redundant constraint to constraints (13.4) and (13.5). It is only added fro optimization purposes.
The solution approach for this work relies on the Lagrangean relaxation (LR) method, which has been successfully employed to solve complex mathematical problems by means of constraint relaxation and problem decomposition [31] . Particularly for solving linear integer problems, unlike the traditional linear programming approach that relaxes integer into non-integer constraints, the LR method generally leaves integer constraints in the constraint sets while relaxing complex constraints such that the relaxed problem can be decomposed into independent manageable sub-problems.
Essentially, the original primal problem is first simplified and transformed into a dual problem after some constraints are relaxed. If the objective of the primal problem is a minimization (maximization) function, the solution to the dual problem is a lower (upper) bound to the original problem.
The dual problem can be constructed as follows; constraints (13.2), (13.4), and (13.5) are first relaxed from the constraint set. As shown in the first line of (13.12), the three expressions corresponding to the three constraints are respectively multiplied by Lagrangean multipliers s, q, and r, and then summed with the original objective function. Using the above process the problem (P) is transformed into a dual problem Dual(P), with objective function given in (13.12) and subject to constraints (13.3), (13.6) , and (13.11) where [pic]is the non-negative Lagrangean multiplier vector.
[pic]
[pic](13.12)
With the above transformation, the current problem is to determine the Lagrangean multiplier vector values. This is accomplished using a Lagrangean Relaxation with Heuristics (LRH) algorithm. The algorithm is shown in Figure 24. The algorithm repeatedly computes upper and lower bounds on the problem using two different heuristics and updating the bounds with the multiplier vector accordingly.
The algorithm starts by initializing all the multipliers, upper and lower bounds, and the quiescence_age variables. The quiescence age is an indication of the improvement of the solution as shall be clear. The algorithm runs for a number of total iterations; at each iteration, a lower bound solution is calculated by solving the dual problem. As long as quiescence age does not pass the quiescence threshold value, it is incremented and the Lagrangean multiplier values are updated. On the other hand, is the quiescence age passes the threshold it is re-initialized, and an upper bound is calculated by solving a heuristic for the original problem. Through the above process, the multiplier values are updated and upper and lower bound difference is reduced.
[pic]
Figure 24: Langrangean relaxation with heuristics (LRH)
1. Lower Bound calculations:
The dual problem, as a relaxation to the original problem always calculates a lower bound on the solution of the original one. Thus, a heuristics to solve the dual problem has been employed.
A closer look at the objective function of equation (13.12) of the dual problem, we realize that decision variable [pic], decision variable [pic], and decision variable [pic]are all separated. In this manner, the dual problem can be decomposed into three independent sub-problems: S1, S2, and S3. Specifically, we have:
[pic] (13.13)
Where:
Sub-problem S1 is given by:
[pic], subject to constraint (13.9).
Sub-problem S2 is given by:
[pic], subject to constraint (13.3).
Sub-problem S3 is given by:
[pic], subject to constraints (13.6), (13.7), and (13.10).
Then, each of these sub-problems can be solved independently using an appropriate heuristic algorithm and integrated again to form the solution of the dual problem.
2. Upper Bound calculations:
The upper bound is computed by solving the original problem with a special heuristic. The heuristic solved the combined original problem based on cost values previously obtained from the Lagrangean multiplier. The algorithm repeadtly applies the Dijkstra's shortest path algorithm to in a an effort to satisfy the lightpath demands of all the SD pairs.
The algorithm terminates when all the lightpath demand are all satisfied or there is no remaining resources (infeasible problem) in the network.
14. Tabu Search Heuristic Approach:
This solution approach recently presented in [28] is a heuristics based approach. It relies on the tabu search framework.
Although this approach depends on no ILP model, we will provide below in our discussion the main characteristics of the approach. This will provide a common base for comparison between different approaches. The approach mainly addresses the Max-RWA problem, where the objective is to maximize the number of satisfied connection requests.
In the same time, the approach handles multiple connection requests between the same source-destination nodes. On the other hand, the approach doesn't address the networks with multifiber links.
These characteristics can be summarized as follows:
• Max-RWA
• Path-based approach
• No wavelength conversion
• multiple requests
• Single-fiber links
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
Before, we present the algorithm, let us first present the notations used in this work. In the following, we will use the following notation. Let G = (V,E) be a graph with a set V of nodes and a set E of edges. A path µ in G from node a ( V to node b ( V is a sequence µ = (a = a1, a2, . . . , b = an) of nodes connected by the edges (a1, a2), (a2, a3), etc. The length of path µ equals n−1, i.e., the number of nodes in the sequence, minus one.
The authors use PATHS(G) to denote the set of paths in G, PATHS(a, b,G) to denote the set of paths from a to b in G, and SHORTEST-PATHS(a, b,G) to denote the set of shortest paths from a to b in G. two paths µ = (a1, a2, . . . , an) and µ' = (a'1, a'2, . . . , a'p) are said to be adjacent, and noted µ1 ∩ µ2' = (, if there exist integers i(1 ≤ i ≤ n − 1) and j(1 ≤ j ≤ p − 1) such that ai = a'j and ai+1 = a'j+1.
An RWA problem instance is defined by: the topology of the network, the traffic requirements (set of demands to be satisfied), and the number of wavelengths. The network is represented by a non-oriented graph G = (V,E) with nodes in V representing stations and edges in E representing bi-directional links. Demands are numbered from 1 to R, with origin(i) and destination(i) representing the origin and the destination of demand i, and multiplicity(i) the traffic requirement from origin(i) to destination(i). Finally, the number of wavelengths is denoted by W.
A lightpath is represented by a couple (µ, w) defined by a path µ in the network and a wavelength w : (µ, w) ( PATHS(G) ×{1, . . . , W}. A potential solution of the RWA problem is a set S of lightpaths, with S = S1 ( S2 ( . . . ( SR, each Si representing the set of ightpaths to satisfy demand i : Si ( PATHS(origin(i), destination(i),G)×{1, . . . , W}. To be a feasible solution, S must satisfy the two following constraints:
• |Si| ≤ multiplicity(i), (i(1 ≤ i ≤ R) (13.1)
• (µ1, w) ( S, (µ2, w) ( S, µ1 ( µ2 => µ1 ∩ µ2 = ( (13.2)
Constraint (13.1) imposes that each set Si does not contain more lightpaths than required by demand i. Constraint (13.2) forbids two adjacent lightpaths µ1 and µ2 to use a same wavelength. The goal of the RWA problem is to satisfy a maximum number of demands, i.e., to find a solution S with a maximum |S|. Finally, notice that (i=1...R multiplicity(i) represents an upper bound of |S|.
To solve the RWA problem based on the tabu search framework, the authors propose the tabu-RWA() algorithm described in Figure 25. This algorithm has two main steps. During Step 1, a set of paths is selected in the graph. Then Step 2 uses paths selected during Step 1 to build a solution of the problem.
During Step 1, the algorithm builds the sets of paths (Pi)i=1...R. For each demand i, the set of shortest paths from origin(i) to destination(i) is built, and these paths are introduced into set Pi. Let now P denote the union of sets Pi : P =( i=1...D Pi. Then, for each pair of paths {µ, µ'} in P, paths µ and µ' are determined is they are adjacent or not.
[pic]
Figure 25: Algorithm Tabu-RWA(), as adopted from [28]
During Step 2, Tabu-RWA builds a solution by using the paths selected during Step 1. Tabu-RWA is based upon neighborhood search; therefore, a solution S is initialized and then iteratively transformed, and the best solution found is returned at the end. The current solution S is initially an empty set of lightpaths. Then, on each iteration, the current solution S is modified by inserting a lightpath (µ, w) into it. At the same time, any lightpath (µ', λ) in S such that µ’ is adjacent to µ is removed from S; therefore, the new so obtained solution S satisfies constraint (13.2).
CAND represents the set of candidate lightpaths that can be inserted into S. CAND is defined as CAND = CD × {1, . . . , W} − S where CD = {i = 1. . . R : |(Pi ×{1, . . . , L}) ∩ S| < multiplicity(i)}.Notice, the new solution S also respects constraint (13.1), due to the way set CD is defined.
In order to avoid to be trapped in local optima, Tabu-RWA uses a tabu strategy: after each iteration, the lightpath (µ, w) which is inserted into S is made tabu for a fixed number lg of iterations (where lg is a parameter of the procedure). It means that, during that period, if (µ, w) is removed from S, it will not be allowed to be reintroduced into S. Because the problem is to maximize |S|, the ”best” candidate (µ,w) in CAND to be inserted into S is therefore the one that minimizes the number |{(µ', w) ( S : µ ∩ µ' ( (}| of lightpaths that will be removed from S.
On each iteration, the Tabu-RWA algorithm chooses the best non-tabu candidate. The procedure stops after a maximum number of iterations specified by parameter maxIter. The search also stops if |S| = (i=1...R multiplicity(i) because, in this case, S is proven to be optimal. Finally, the procedure returns the best solution found S*.
In addition, the authors also proved a complexity analysis of the algorithm. They proved that the overall complexity of a tabu iteration is O(|P|2).
5. Technical classification for MC-RWA:
The Multicast-Routing and wavelength Assignment problem (MC-RWA) was first presented in the previous chapter, in this section we present the different problem's assumptions or variations and then discuss the different contributions for this problem. As the problem's name implies, the problem inherits the same technical classification of the parent RWA problem. In addition, one more feature is the node's splitting capability.
1. Splitting capability:
Different research approaches have different assumptions on the availability of splitting capability for different nodes in the network (whether or not equipped with MC-OXC). Mostly treated like the wavelength conversion capability, the splitting capability can have different levels:
• Full splitting capability
• Sparse splitting capability
• No splitting capability
According to whether all the network, only a limited subset of the nodes, or none of the node are equipped with splitting capable OXC's, respectively. In most cases, the splitting capability assumptions are combined with the wavelength conversion capability. This generated interesting cases for study.
These different cases are demonstrated in the following example. Figure 26 shows a part of a network, where node S is the source of a multicasting request, and nodes 1 through 4 are some of the destinations of the session. There are four possible cases depending on whether or not node 2 is capable of wavelength conversion and/or splitting.
[pic]
Figure 26: An example of multicasting routing and wavelength assignment. Node 2 is considered with the 4 combinations of wavelength conversion and splitting capabilities.
The first two cases where node 2 has and does not have the wavelength conversion capability are shown in Figure 26 (a) and (b), respectively. In both cases, it is assumed that node 2 has the splitting capability and thus can multicast to nodes 3 and 4. Note that, whether or not node 2 has the wavelength conversion capability does not affect the multicasting tree (at least its structure) but does affect how wavelengths can be assigned on each link in the multicasting tree.
The other two cases which are similar to the first two except that node 2 does not have the splitting capability are shown in Figure 26 (c) and (d), respectively. In both cases, since node 2 can only forward one copy (e.g. to node 3), a separate path from S to node 4 is needed. Accordingly, more bandwidth (in terms of the number of channels) will be consumed, when compared to the first two cases.
2. Session multiplicity:
Different research approaches can be compared according to their support of single or multiple multicast sessions. A multicast session is a request where the same single source requests to cast to different destinations.
Again, in this study, we survey the different formulation, and solution approaches for the static traffic MC-RWA problem, for the general Mesh topology case while varying the rest of assumptions of the problems (splitting capability, wavelength conversion capability, fiber multiplicity, requests multiplicity, and objective function).
6. Different Approaches for static MC-RWA (incomplete):
As for the RWA problem, in this section we will present different solution approaches for the static MC-RWA problem. The different solution approaches will be referred to according to their objective function, formulation, and fiber and requests multiplicity.
1. Heuristic Approach, single-session, full-splitting capability:
This solution approach as presented in [32] is a heuristics based approach. The approach aims to construct light-trees (as previously defined in the previous chapter) under static traffic assumption.
It should be noted that this approach addresses the problem under the assumption that every node in the network has the splitting capability. Moreover, only one multicasting session is addressed by this approach. A multicast session is a request where the same single source requested to cast to different destinations.
This approach also relies on decomposing the MC-RWA problem into two main sub-problems:
• Routing sub-problem
• Wavelength Assignment sub-problem
1. Routing sub-problem:
This problem is first solved using a proposed heuristic algorithm. This algorithm is based on shortest-path heuristic.
[pic]
Figure 27: Multicasting tree construction heuristic algorithm, as adopted from [32]
As shown above, at each iteration the algorithm adds more destinations to the currently constructed tree. As mentioned earlier this approach assumes that every node in the network has the splitting capability, and thus can have as many immediate children in the multicasting tree as needed.
2. Wavelength Assignment sub-problem:
Since, only one multicast tree is constructed, a single wavelength is to be used over all the links it spans. Hence, the wavelength assignment causes no problem for this case.
The above approach based on the unpractical assumptions of only one multicast session requested and full splitting capability in the network does not provide realistic solution to the problem. On the other hand, it is the base for more practical solutions and complex algorithms as shall be seen in the next section.
2. Heuristic Approach, single-session, sparse-splitting capability:
This solution approach was also presented in [32] as a heuristics based approach. Similarly this approach aims to construct different light-trees (as previously defined in the previous chapter) under static traffic assumption. The objective is to construct these trees using the minimum possible number of wavelengths.
The main difference is that in this approach the case where different nodes may posses the splitting capability or not is considered, referred to as "sparse-splitting capability". In this case only a few nodes have the splitting capability, and those who do not have the splitting capability will not be able to have more than one immediate child in a multicasting tree. Accordingly, in order to reach all the destinations in a multicasting session, a multicasting "forest" consisting of one or more multicasting trees rooted at a common source needs to be constructed.
This case can be further illustrated based on the following example. The example network is shown in Figure 28, where node 1 is the source of a multicasting session, and nodes 2-9 are the destinations, of which nodes 3,4 and 6 do not have the splitting capability. When shortest path (in terms of hop counts) routing is used to construct the multicasting tree, it is possible that node 9 is considered last, and thus, it cannot be included in the multicasting tree since both of its neighbors, nodes 4 and 6 cannot do splitting. In this case, a second multicasting tree has to be constructed which overlaps with part of the current one (i.e. on links 1-2-4). Therefore, for this multicasting session, two multicasting trees are needed.
[pic]
Figure 28: An example multicasting forest in a NSFNET-like network with sparse splitting
This approach also relies on decomposing the MC-RWA problem into two main sub-problems:
• Routing sub-problem
• Wavelength Assignment sub-problem
1. Routing sub-problem:
This problem is first solved using a proposed heuristic algorithm. This algorithm is a more general one than the previous tree-construction algorithm. The basic idea of the algorithm that can be used to construct a multicasting forest for a given multicasting session is as follows. The algorithm first tends to include as many destinations as possible in one multicasting tree. If there is any node that cannot be included, the algorithm is recursively called to construct the second multicasting tree (and the third, and so on, if necessary).
Specifically, let V be the set of nodes that includes the source and other nodes which are already in the current tree, and which are either leaf nodes or have the splitting capability or both. Essentially, V contains the set of nodes through which the multicasting tree can grow. On the contrary, let V' be the set of non-leaf nodes that do not have the splitting capability through which the multicasting tree cannot grow. In addition, let UV be the set of destinations that have not been included in any multicasting tree of the current session.
To account for the lack of the splitting capability at some nodes (other than the source), we need to ensure that once such a node becomes an intermediate node in the multicasting tree, it is excluded from set V if it already exists in V and put to V'.
The following is the pseudo-code of the multicasting forest construction algorithm for a given multicasting session.
[pic]
Figure 29: Multicasting "forest" construction heuristic algorithm, as adopted from [32]
Note that using the above algorithm, the path between the source and each of the destinations used in the multicasting tree may not always be the shortest path between them.
2. Wavelength Assignment sub-problem:
In this section_ we describe how wavelengths are assigned and in particular_ how many wavelengths are needed for a
The authors consider the wavelength assignment problem, for assigning wavelengths to the constructed multicasting forest in three cases corresponding to no, sparse and full wavelength conversion. In the case of full wavelength conversion, any wavelength can be assigned on each link, while in the case of no wavelength conversion; the same wavelength has to be assigned to each subtree.
The authors propose a solution for wavelength assignment for the more general case of sparse wavelength conversion. They explain that it can be performed independently on each segment, which is a collection of links, as follows. In each subtree, they remove all the intermediate (i.e. non-leaf) nodes which have the wavelength conversion capability but keep the associated links. In this way, a subtree may be partitioned into several segments, each of which requires the same wavelength to be assigned on all its links since there is no wavelength conversion capability within a segment.
For example, in the multicasting forest shown in Figure 28, there are three subtrees (trees sharing the same root branch, which contain for example, leaf nodes 5 and 7, leaf node 9, and leaf node 8, respectively). Among the intermediate nodes, only node 2 is capable of wavelength conversion. After node 2 is removed, we will have 3 segments (1-2,2-5, 2-4-7) from the first subtree, 2 segments (1-2,2-4-9) from the second subtree, and only 1 segment (1-3-6-8) from the third subtree.
The authors adopted the "First-Fit" algorithm to perform wavelength assignment within each segment for its simplicity, although other heuristics may also be used.
7. Motivation:
As seen from the approached presented above, the following aspects can be inferred:
• Only few models addressed the Min-RWA problem.
• Mostly all the approaches presented ILP models, but relied on approximation or heuristic algorithms to solve the problem especially for large size networks.
• No model addressed the Min-RWA problem with multi-fiber links case.
From the above reasons we were motivated to propose a new intuitive approach to address the Min-RWA problem and that can be general enough to incorporate most of the different cases such as: muti-fiber links, and multiple-requests. Hoping that, with this approach, we can provide guaranteed optimal solutions without the need to rely on heuristics, even for large size networks.
Chapter 3
3. Proposed Approach
This chapter is mainly concerned with the discussion of the proposals made to the research area of interest, namely the static RWA problem. A proposed model will be presented. In addition an arising problem in network design is considered for discussion and a solution based on our framework is provided.
1. Comparison:
In this section, we will compare the different approaches presented in the survey chapter. The different approaches fall mainly into one of the three following categories:
1. Link-Based approaches:
These are the approaches similar to the ones presented in sections 2.4.1 and 2.4.2 (reference [13]), 2.4.6 and 2.4.7 (reference [18]).
The main advantage of such approaches is the fact that it covers all the search space of the problem (in terms of possible paths for each SD pair). This advantage comes with an extra cost, as it leads to a large number of variables and constraints in the model making the model hardly tractable. Moreover, the problem is often decomposed into two sub-problems; Routing sub-problem and Wavelength-assignment sub-problem (as in [13] ), which generally leads to sub-optimal solutions.
2. Path-based approaches:
These are the approaches similar to the ones presented in sections 2.4.4 and 2.4.5 (reference [13] ), 2.4.8 (reference [10] ), and 2.4.10, 2.4.11, 2.4.12 (reference [18]) and 2.4.13 (reference [30] ).
These approaches represent the compromise of the difficulties encountered in the precedent approaches. The search space is reduced by considering a limited set of candidate paths (note that the total number of paths grow exponentially in the number of network links in the network). This reduces the number of variables and constraints in the model, but may lead to sub-optimally if the number of candidate paths is below a certain threshold.
3. Heuristic approaches:
A number of approaches falling into this category has been presented in sections; 2.4.8 (reference [10] ), 2.4.9 (reference [19]), and 2.4.14 (reference [28]).
In these approaches the solution quality is traded for the techniques' complexity. In the approach presented in 2.4.8, the solution is guaranteed to be within tight bounds of the optimality.
2. Proposal:
As can be seen from the variety of approaches for the problem, the contribution to such an active area of research is a complicated task. It is not easy to outperform the presented approaches in theory and/or practice. In what follows, we will present the different proposed points to our static RWA problem.
1. Handling multiple-fibers:
As a part of our proposed approach, we propose an intuitive idea of handling the multiple-fibers case in the RWA problem. This idea is can be incorporated in any path-based formulation without any need for modifications in the model itself, which makes it independent on the specific path-based formulation in use. The reason behind such independence is the fact that the idea is a slight modification made in the search phase of Routing sub-problem (reference to section 2.4). In other words, we only modify the way the candidate paths are pre-calculated.
The simple idea is to consider the network as modeled as an undirected multi-graph instead of a simple undirected graph. With this in mind, each fiber copy of the same physical link is considered individually. This way when searching for a path between any source-destination nodes, different fibers (even for the same physical link) may belong to different paths.
To illustrate this idea, consider a simple network with only two links and for simplicity each having two fibers per link. A connection is requested between node 0 to node 2. Such a case could be handled by finding the path 0 ( 1 ( 2 and this path could be assigned wavelengths either on the 1st group of fibers or the 2nd. This case is shown in the figure below (Figure 30)
[pic]
Figure 30: WRON with 2 links each of 2 fibers
Our proposed idea is to consider this network graph as a multi-graph, thus each link is decomposed to two separate links. And in the search phase of the routing sub-problems, those tow different links could be used to form two different candidate paths (Figure 31). Moreover, they are link-disjoint paths.
[pic]
Figure 31: same WRON viewed as multi-graph
We should note that this view point of the network model as an undirected multi-graph for handling multiple-fibers is quiet different from the view of the network as layered copies of the same physical network according to the number of wavelengths in each link. Each handles a different level of modeling in the network, in the first each link if considered having different copies according to the fiber multiplicity, and in the other the whole network is considered as layered copies according to the number of wavelengths in each link. In fact, both viewpoints can be combined together, were each layer of the network can have multiple copies of the links according the fiber multiplicity.
2. Model (ILP formulation):
Our proposed model is based on the same set of constraints appearing in the presented model in section 2.4.4 (reference [17]).
The main differences between the basic approach and the one we propose are:
• Addressing the multiple-fiber case: based on our proposed idea in the section above, which merely changes in the candidate paths pre-calculation (the search phase of the routing-sub-problem)
• Addressing the Min-RWA Problem: we have changed the objective function to reflect our new objective of min-RWA, which is to minimize the number of used wavelengths to satisfy the given lighpath requests.
Following the same main characteristic of the approach of section 2.4.4, ours also may be decomposed to both:
1. Routing sub-problem:
2. Wavelength assignment:
It should be noted that the search phase of the routing problem has been changed to consider the multiple-fiber case as discussed in the above section.
Again, the selection phase of the routing problem along with the wavelength assignment is formulated as an ILP and is solved for optimality. The solution of this ILP determines which paths of the candidate paths for each request are used and a wavelength is assigned for each of them.
The proposed model also shares most of the characteristics:
• Min-RWA:
This is a variation made by modifying the objective function
• Path-based model:
As inherited from the model
• No wavelength conversion:
As inherited from the model
• Multiple requests:
As inherited from the model
• Multiple-fiber links:
In contrast with the basic approach, our proposed addresses the RWA problem with multiple-fiber links, based on the above presented idea.
• Wavelength continuity constraint is implicitly guaranteed because wavelengths are assigned to entire paths rather than to individual links.
The objective function is based on the same idea of the approach proposed in section 2.4.9 in the previous chapter (reference [20] ). This idea is to minimize the total number of wavelengths used, by maximizing the wavelength re-use, as much as possible, as long as the capacity constraints are not violated.
The ILP model of this approach is presented as follows:
Objective Function: Minimize [pic] (3.1)
Capacity constraint: [pic] (3.2)
Traffic demands: [pic] (3.3)
Integrality constraints:
[pic] , integer i=1,….,R (3.4)
[pic] , integer i= 1,….,P, j=1,…..,W (3.5)
where
R: denote the number of source-destination (s-d) pairs.
L: denote the number of links.
W: denote the number of wavelengths per link
[pic]= {mi}, i=1,2….,R : number of connections to be established for source-destination pair i
A={aij}: PxR (path- s-d pair incidence) matrix in which aij = 1 if path i is between source-destination j, and aij =0 otherwise.
B={bij}: PxL (path-edge incidence) matrix in which bij = 1 if link j is on path i, and bij =0 otherwise.
C={cij}: PxW (path-wavelength assignment) matrix in which cij = 1 if wavelength j is assigned to path i, and cij =0 otherwise.
G={Gi}: 1xW weighting matrix.
The objective function as shown in equation (3.1) states that the objective is to minimize the weighted sum of the Path-Wavelength assignment variables. This in fact aims to minimize the total number of wavelengths used in the network. The logic behind this is in the assigned weights: since low index wavelengths are given lower weights, the objective forces the assignment of paths to the smallest possible set of low index wavelengths this is achieved by re-using the same low index wavelengths whenever possible (whenever it doesn’t conflict with the capacity constraints).
The capacity constraints in equation (3.2), traffic demand constraints in equation (3.3) and integrality constraints in equations (3.4) and (3.5) are all unchanged.
Parameters:
For the proposed formulation, some parameters may be used to refine the quality of the solution:
• The number of candidate paths: the larger the number of candidate paths, the closer we get to the optimal solution, however, it shouldn't be increased much as it increases the number of variables. The proper choice of this parameter reduces the number of variables/constraints especially when there are some links that are never used by any of the paths.
• The number of assumed wavelengths: the increase of the number of available wavelengths (from which we try to use as minimum as possible) ensures feasibility, reducing this numbers may result in an infeasible solution. The upper bound choice of this parameter is to equal the number of connection requests, a better choice can greatly reduce the number of variables of the formulation.
• The criteria of searching for candidate paths: The criterion to search for the set of candidate paths between the required SD pairs in the routing sub-problem can be selected from among the following:
o Link-disjoint paths (were paths must differ in all the links they traverse)
o Link-distinct paths (were paths must differ in at least one link)
Only the set of Link-disjoint paths is considered in this work for the following reasons:
• The set of link-disjoint path is most suitable to this specific problem on hand, because if a certain link is congested, then we are sure this link is not shared between the set of candidate paths (furthermore, at most only one candidate path will use it), which gives the freedom of avoiding congested links.
• In general for any network the total number of link-disjoint paths between any SD pair is not large.
• For a low number of candidate path such as two or three we can obtain the required optimum value for the number of wavelengths
• It greatly enhances the "survivability" or fault tolerance of the network, by establishing connections on link-disjoint paths, ensures that with link failure, not all the connections between any SD pair are lost.
Weighting matrix considerations:
There are a few considerations to take into account, when making the appropriate choice for the weights of the weighting matrix used above. The selected weights must satisfy the following requirements:
1. All weight must be integer, to maintain the required integrality of the variables.
2. Weights must be linear, so that additional cost is added as more different wavelengths are used.
3. Weights must be chosen to be monotonically increasing in such a way that extra cost is added when a new wavelength is used in the system.
4. Weights must not be dramatically large as to maintain the model's stability.
To satisfy the above requirements, we may propose different choices for the weighting matrix. First, we may choose to assign the same weights to all the assignment variables of the same wavelength. Second, we select increasing costs for the assignment variables of increasing index wavelengths.
One such choice, to ensure that a new wavelength is used is only used when all the previous wavelengths can not be used due to constraint violation, is to choose the weight of each new assigned wavelength to be greater than the upper bound value of the case when all the previous wavelengths are assigned. Since for each wavelength a total number of paths P can be assigned to it. The weight choice can be as follow:
G={Gi}: 1xW weighting matrix, Gi = Pi
It can be easily seen that such choice, requires very large weight values even for moderate number of paths and wavelengths.
Another choice can be made based on the following facts:
• Assuming that all the P paths can be assigned the same wavelength is an extreme and unpractical case.
• The path-wavelength assignment variables selection are further constrained by the traffic demand constraint, for each demand.
To explain the second point, let us focus on the traffic demand constraint. Re-writing this constraint in summation form:
[pic]
In general, the number of path-wavelength assignment variables (representing the different path-wavelength combinations) is greater than the number of connection requests [pic]for each SD pair j (or else the problem would turn out to be infeasible).
Only a number equal to [pic]variables would be set (assigned the value of one) and the others must be unset (assigned zero value)
Lemma 1:
For the previously proposed model, at optimality, the traffic demand must be satisfied at equality.
Moreover, using any monotonically increasing weights for the increasing index wavelengths will ensure that the minimum number of wavelengths is used.
Proof:
We will base our proof on contradiction. Let us assume that optimality has been reached and the minimum possible objective function value is calculated. Also assume that more than [pic] assignment variables are set.
Consider unsetting the extra number of assignment variables (above the traffic demand [pic]) we can proof that this can be done without violating any of the constraints:
Observing the available constraints in the model, namely:
• The traffic demand constraint:
[pic]
This means that this constraint is satisfied at inequality. By unsetting those extra assignment variables the right hand side will be decreased and this constraint can be still satisfied at equality.
• The capacity constraint:
[pic]
for those extra assignment variables, this constraint was satisfied at equality. Again, by unsetting them this constraint can be still satisfied but this time at equality.
Thus, the extra assignment variables can be unset without violating any constraints, reaching a lower value for the objective function. This is a violation of our previous assumption of optimality.
At this point we have proved that an exact number of assignment variables equal to [pic]is set. To prove the second part of the lemma, we only need to show that assignments are always made to the lower index wavelengths as long as the capacity constraint is not violated.
Notice that for each traffic demand, the extra path-wavelength assignment variables must be unset. As long as the capacity constraint is not violated, all the assignment variables are equally weighted in the traffic demand constraint. The optimizer must select those assignments to the higher index wavelengths in their order of decreasing weights to be unset so as to minimize the total objective function value. Otherwise, if any other choice is made we will reach a contradiction as in the previous argument.
Based on the above lemma, any monotonically increasing weights for the increasing index wavelengths such that:
[pic] (3.6)
[pic]
(notice the strict inequalities) is sufficient to ensure the correct performance of our model.
3. Solution uniqueness and Shortest paths preference:
Another feature in our proposed model is the possibility to favor shorter paths in the selection process. This means that whenever two paths could be equally selected to reach the same optimal value for the objective, the shorter one can be favored to be selected. More precisely, even if the two paths are of same length, the path of lower index in the pre-calculated K-Shortest path list is favored.
This is a quiet desirable feature in communication networks in general, since shorter path directly maps to lower delays, lower possibilities of interference and lower probability of failure. An example illustrating this feature is shown in Figure 32. Assuming there are 3 connection requests (in terms of lightpaths) from node 0 to node 3, from node 1 to node 3 and from node 1 to node 2.
|[pic] |[pic] |
|(a) |(b) |
|[pic] |Requests: |
| |0 to 3 |
| |1 to 3 |
| |1 to 2 |
Figure 32: two optimal solutions for an example RWA problem
This feature can be fairly easy accomplished through a proper choice of the weights in the weighting matrix used in the objective function of our proposed model. This is possible since we have proved in the lemma 1 above, that we have the freedom to choose any weights satisfying the simple condition of (3.6).
Our proposed weights can be then set as follows:
2. Network growing problem:
In addition to the above proposed model, in this section we discuss a new arising problem and present a solution based on the above model as a framework.
A new practical problem that arises in the domain of optical networks design as an extension of targeted problem of RWA is the case where the available resources of the network can not satisfy the connection requests and it required to "grow" the network in order to accommodate the requests.
As in the RWA problem, this problem can be formulated as follows:
• Given the network topology, and a list of connection requests.
• When the current network topology and resources does not satisfy the demanded requests, it is required to obtain the minimum set of modifications (in terms of additional resources) on the current network topology in order to satisfy the connection requests.
The terms network "growth" and network "modification" are rather vague in the above discussion. In what follows, we present our suggestion of a solution for the problem. This can be expressed in terms of our definition of the possible modification on the current network topology. The assumption made to incorporate this problem in our framework, is that the suggested modifications are only the addition of fibers to already existing links and we will not consider the addition of totally new links between originally un-connected nodes.
This assumption is of reasonable practical value due to its economical advantage; in practice it is of less cost to add more fibers (in a bundle) to already existing links rather than to construct new links. Moreover, multi-fiber links networks are gaining a lot of interest recently [10] .
In our proposed model the number of available wavelengths for use is a parameter to the model. The problem under consideration arises when this number can not accommodate the requests.
Following theses steps we can find the required solution problem:
1. The problem is first solved as previously.
2. If the problem is found to be feasible, then we have reached optimality and the minimum number of wavelengths is reported.
3. Otherwise, the problem is infeasible; this means that the available number of wavelengths is not sufficient. This is the network growing problem case. In this case we Re-solve the problem with a larger number of wavelengths (we typically used the maximum possible number, the worst case one, which is equal to the number of connection requests).
4. The modified problem must be feasible (since we used the maximum possible number of wavelengths), we then calculate the required modifications to the network topology as follows:
After the 2nd run, we calculate the required number of wavelengths used for each link, if this number exceeds the constrained number we started with and that can not be carried on by any (if available) multiple fibers between the same nodes, a suggestion is made to add a mutli-fiber link between these two nodes (please note that the number of links to be added is proportional to the number of waves needed, since each link can carry a specified number of waves as stated in the model). All other non-congested links are left unchanged.
The above can be further explained using the following pseudo code (Figure 33):
/*Values obtained from the 2nd run */
W = the number of available wavelengths per link.
W(L) = the needed number of wavelengths on link L
For each node pairs (i,j)
For each link Lij (between the nodes (i,j)
If (W (Lij) < W ) freeWaves = freeWaves + W-W(Lij)
EndFor
For each link Lij (between the nodes (i,j)
If ((W (Lij) > W ) && ( freeWaves < W(Lij) – W) )
Fibers to add = ceil ((W(lij)-W-freeWaves)/W)
EndFor
EndFor
Figure 33: pseudo-code to calculate needed multi-fibers in network growing problem
The complete flow to accommodate the network growing problem in our framework, is presented by the following flow chart diagram (Figure 34).
[pic]
Figure 34: flow chart diagram for accommodating the network growing problem.
3. Total Unimodularilty Property:
Some problems have special structure that allows an ILP to be solved exactly under its relaxation as an LP. This is significant because LP problems can be solved much more quickly than ILP problems. One way of thinking about such problems is that the constraint matrix has a structure that in effect traps the optimal solution onto discrete values if the RHS constants are themselves integer. The relevant mathematical property is called Total Unimodularilty (TU).
Theorem 1:
"Let A be a totally unimodular matrix and b be an integral vector then the polyhedron P:={x|Ax = Quiescence_Threshold
Then quiescence_age:=0;
Run (P)_heuristic;
If ub ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- different approaches to problem solving
- 3rd grade word problem worksheets
- research problem examples
- math word problem worksheets pdf
- word problem practice worksheets
- online shopping problem and solution
- optical antibiotic ointment
- icd 10 optical codes
- optical icd 10 codes
- optical diagnosis codes
- v codes for optical billing
- v codes optical glasses