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)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)