Definition
The general objective of the RWA problem is to maximize the number of established connections. Each connection request must be given a route and wavelength. The wavelength must be consistent for the entire path, unless the usage of wavelength converters is assumed. Two connections requests can share the same optical link, provided a different wavelength is used.
The RWA problem can be formally defined in an integer linear program (ILP). The ILP formulation given here is taken from.
Maximize:
subject to
is the number of source-destination pairs, while is the number of connections established for each source-destination pair. is the number of links and is the number of wavelengths. is the set of paths to route connections. is a matrix which shows which source-destination pairs are activate, is a matrix which shows which links are activate, and is a route and wavelength assignment matrix.
Note that the above formulation assumes that the traffic demands are known a priori. This type of problem is known as Static Lightpath Establishment (SLE). The above formulation also does not consider the signal quality.
It has been shown that the SLE RWA problem is NP-complete in. The proof involves a reduction to the -graph colorability problem. In other words, solving the SLE RWA problem is as complex as finding the chromatic number of a general graph. Given that dynamic RWA is more complex than static RWA, it must be the case that dynamic RWA is also NP-complete.
Another NP-complete proof is given in. This proof involves a reduction to the Multi-commodity Flow Problem.
The RWA problem is further complicated by the need to consider signal quality. Many of the optical impairments are nonlinear, so a standard shortest path algorithm can't be used to solve them optimally even if we know the exact state of the network. This is usually not a safe assumption, so solutions need to be efficient using only limited network information.
Read more about this topic: Routing And Wavelength Assignment
Famous quotes containing the word definition:
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)