Optical WDM Networks With Limited Wavelength Conversion

An important optical network architecture is the wavelength division multiplexed (WDM) network that supports lightpaths. WDM is basically frequency division multiplexing in the optical frequency range, where carrier frequencies are referred to as wavelengths. Lightpaths are end-to-end connections made up of connected WDM channels. A network node is said to have wavelength conversion capability if it can shift the wavelengths of optical signals. The advantage of wavelength conversion is that it allows networks to support more lightpaths, but its disadvantage is that it can be expensive and/or difficult to implement. This research is on limited wavelength conversion that allows network nodes to perform some but not necessarily all wavelength shifts. Limited conversion means less complex and costly hardware than full conversion, yet better channel utilization than no conversion. Network architectures and algorithms will be studied by initially focusing on special important network topologies such as the star and ring, and then eventually covering general network topologies. These will be analytically evaluated by worst case analysis that leads to guaranteed performance results, and also by probabilistic methods.

Below are the project's

  1. People
  2. Results and Publications
  3. Significant Educational, Commercial and Societal Impact
  4. Sponsor

1. People

Contact Person: Galen H. Sasaki, Principal Investigator.

Graduate Research Assistants

2. Results and Publications

The project is to investigate WDM networks that support lightpaths. Thus, these networks are essentially circuit switched networks, where the lightpaths are the circuits. In addition, we are investigating networks with limited wavelength conversion. Limited conversion means that wavelengths may be shifted to other wavelengths but there may be restrictions. Note that limited conversion is a generalization of no conversion and full conversion.

Limited wavelength conversion can model real restrictions on conversion devices. For example, wavelength conversion by four wave mixing leads to wavelength shifting within a range of wavelengths. If the wavelength conversion is done by (optical-electrical-optical) O-E-O components then the limitation may be due to constraints on the fan-out/fan-in of the components. At any rate, we are interested in quantifying how wavelength shifting is related to efficient utilization of optical bandwidth in a fiber.

We provided a measure of wavelength conversion called the channel degree (or wavelength degree). If a network node has a channel degree d then a wavelength may shift to any one of a pre-defined set of wavelengths, where the set has size at most d. Thus, if a node had no wavelength conversion then its value of d = 1 because the wavelength passes through without being shifted. If a node has full wavelength conversion capability then its value of d = W, where W is the number of wavelengths.

Our aim was to study how wavelength conversion is related to the bandwidth efficiency of a network. In addition, we were able to identify network architectures that had small amounts of wavelength conversion but were very bandwidth efficient. Our objective was to derive mathematical results, and in particular guarantees on performance. This lead us to use non-statistical traffic models so that we could derive such performance guarantees. The traffic models have a parameter Rmax, which is the maximum traffic load on each fiber-link. More specifically, the amount of offered lightpaths to any link at any time is assumed to be at most Rmax. Note that an offered lightpath may be blocked from being set up in the network if the network has no free wavelengths or cannot crossconnect free wavelengths due to limitations on wavelength conversion.

We had two traffic models: off-line and dynamic. Off-line corresponds to the scenario when the network is initially empty and then all the lightpath traffic arrives at one time. Dynamic means that lightpaths may arrive and depart at arbitrary times. A network is said to be nonblocking for off-line traffic if it does not block any offered lightpaths for any such traffic. Similarly, a network is nonblocking for dynamic traffic if it does not block any offered lightpaths for any such traffic. In the case of dynamic traffic, we refer to a nonblocking network to be wide sense nonblocking if it does not rearrange any existing lightpaths. Note that if a network is nonblocking for off-line traffic then it is nonblocking for dynamic traffic with the same Rmax if it is allowed to rearrange its existing lightpaths to make way for a new one. Such networks are referred to as rearrangeably nonblocking for dynamic traffic.

Note that dynamic traffic is a more realistic model of traffic. In addition, wide sense nonblocking networks are more practical because in real telecommunication networks, connections are rarely rearranged. The exceptions are usually for maintanence, e.g., replacing a faulty switch or link. However, we consider rearrangeably nonblocking networks because they use significantly less resources, as we shall see. Therefore, rearrangement of connections may be become practical when users are very cost sensitive, as it can be with Internet users.

Note that any network that has less than Rmax wavelengths may suffer lightpath blocking and cannot be nonblocking. Also note that a network with full conversion at every node and exactly Rmax wavelengths will be nonblocking for both off-line and dynamic traffic. Thus, full conversion at every node achieves the highest bandwidth utilization. A theoretical issue that we addressed is how efficent can a network be with a small channel degree. In particular, if a network has a small channel degree, how much larger does the number of wavelengths W have to be over Rmax and still remain nonblocking.

Next we present our nonblocking network results for off-line traffic. The network topologies we focused on are rings because telecommunication fiber layouts are often rings for SONET. Then we present our results for dynamic traffic. Finally, we explain the other results of this project.

2.1. OFF-LINE TRAFFIC

R. Ramaswami and G. Sasaki, "Multiwavelength optical networks with limited wavelength conversion," IEEE/ACM Transactions Networking, vol. 6, no. 6, pp. 744-754, Dec. 1998. Also appeared in Infocom 1997.

Summary: We investigated nonblocking networks for off-line traffic with an emphasis on ring topologies. The off-line lightpath traffic were assumed to have pre-compted routes. Thus, arriving lightpaths only require a wavelength assignment, i.e., the wavelengths they should use along the route.

We found ring network architectures that were very bandwidth efficient and required very little channel degree. One of the architectures had channel degree d=2 at two nodes and no conversion at all other nodes. It is nonblocking if the number of wavelengths W = Rmax, i.e., it has the highest bandwidth efficiency. There is another architecture with channel degree d=5 at one node and no conversion at all other nodes. It is also nonblocking if W = Rmax.

For a ring network, we were able to show that if the channel degree d = 1 at all nodes then a nonblocking network requires W > Rmax. This provides a lower bound on the amount of wavelengths required for a nonblocking network with very limited wavelength conversion. We found a ring network that showed that the bound is tight. The ring network has no conversion at all other nodes except one, which also has d = 1. The ring network is nonblocking if W = Rmax + 1.

We also have some results for networks with other topologies. For a star topology, there is a nonblocking network with channel degree d = 1 and W = Rmax. For arbitrary topology networks, there is a nonblocking network with channel degree d = 1 and W = Rmax as long as the lightpaths have length at most 2 hops. If the lightpaths have no restrictions on their path lengths then we have a nonblocking network with a mix of full conversion nodes and nodes with d = 1. However, each node with d = 1 must have all of its neighbors be full conversion nodes.

2.2. DYNAMIC TRAFFIC

O. Gerstel, S. Kutten, R. Ramaswami, and G. Sasaki, "Worst-case analysis of dynamic wavelength allocation in optical networks," IEEE/ACM Transactions Networking, vol. 7, no. 6, pp. 8333-8456, Dec. 1999.

Summary: We investigated dynamic traffic for wide-sense nonblocking networks with limited or no wavelength conversion. The lightpath traffic was assumed to have pre-computed routes. We will first present results for networks with no conversion, and then present results for networks with limited conversion.

For no conversion networks, our results are for ring and tree topologies. For ring networks, we showed that a wide-sense nonblocking network requires at least (1/2)Rmax log N wavelengths, where log is log base 2 and N is the number of nodes. Note that the wavelength requirement (i.e., bandwidth inefficiency) increases with the number of nodes. We also showed that for a ring with no conversion, a nonblocking network requires approximately Rmax logN + Rmax wavelengths. This result assumes a particular strategy to assign lightpaths to wavelengths which may not work well for "typical" traffic. A particular strategy that does work well for typical traffic is first fit, which is to use the lowest numbered available wavelength. We showed that for first fit the number of wavelengths for a nonblocking network is approximately 2.52Rmaxlog N + 5Rmax wavelengths. Thus, in the worst case, it is a constant factor from the lower bound.

We also have similar results for tree topologies, excluding the first fit results.

Turning back to ring networks, we found wide-sense nonblocking networks that have wavelength requirements that do not grow with N at the expense ov a small amount of wavelength conversion. The network architecture has channel degree d = 2 and the required number of wavelengths is Rmax log (log Rmax) + 4 Rmax. Note that the wavelength requirement is growing slightly faster than O(Rmax).

For general topologies, we have results for networks with a sufficiently large number of wavelengths W and channel degree d. The channel degree d may be large but fixed (i.e., not growing) with Rmax or N. In addition, for the network, W is O(Rmax). In particular, there is a constant a such that W = a x Rmax. Thus, the wavelength conversion is limited in the sense that d is O(1) with respect to W and Rmax.

The network is wide-sense nonblocking. The allowable wavelength shifting at nodes has a pattern that is defined using "expander" graphs. Thus, the channel degree d is O(1) with respect to W and Rmax, and W is O(Rmax). Note that this is an improvement over the other ring architectures, which have their wavelength requirements growing faster than O(Rmax) or growing with N. However, d is a big constant, and so the result is only of theoretical importance for now.

We also considered dynamic traffic that never departs, which we refer to as incremental traffic. This models lightpaths that carry high capacity traffic, which are likely to have long durations. For this traffic, We found ring networks that are wide-sense nonblocking and have wavelength requirements W = max{0, Rmax-d}. Note that as d increases, the bandwidth efficiency gets better. In fact, when d = Rmax then W = Rmax, which makes sense because the network has full wavelength conversion. When d= 1 then W = 2 Rmax - 1.

Finally, note that the wide-sense nonblocking ring networks above that have limited wavelength conversion have wavelength requirements that are much larger than Rmax. This should be compared to the wavelength requirements for the nonblocking ring networks for off-line traffic. The requirements are Rmax, which is necessary for any nonblocking network. These networks are also rearrangeably nonblocking for dynamic traffic. This illustrates that rearrangement could considerably improve bandwidth efficiency.

2.3. OTHER RESULTS

T. Lin and G. Sasaki, "Nonblocking WDM networks with fixed-tuned transmitters and tunable receivers," Proc. 37th Annual Allerton Conference on Communication, Control, and Computing, Monticello IL, Sept. 1999, 400-401. Postscript.

Summary: The networks considered have limited wavelength conversion in the following sense. The receivers are tunable but the transmitters are fixed-tuned. In practical systems, tunable transmitters are more difficult to build or expensive and so it is reasonable to investigate systems that have fixed-tuned transmitters.

The networks we considered were rearrangebly nonblocking networks with fixed-tuned transmitters and tunable receivers. Wavelength shifting at an intermediate node may be accomplished by a receiver-transmitter pair that receives a signal at an arbitrary wavelength, and regenerates it at the wavelength of the fixed-tuned transmitter. For grid topology networks, if there is just a single transmitter-receiver pair per node then the number of required wavelengths is at least (N-6)/5, where N is the number of nodes. On the other hand, if there are two transmitter-receiver pairs per node then the number of required wavelengths is at most 2 sqrt(N). Thus, there is a significant reduction of wavelengths by slightly increasing the number of transmitters and receivers per node.

G. Sasaki, C.-F. Su, D. Blight, "Simple layout algorithms to maintain network connectivity under faults," Proc. 38th Annual Allerton Conf. on Communication, Control and Computing, Sept., 2000. PDF.

Summary: A problem of survivable layout of an IP network topology on a WDM network is considered. The problem is to layout the IP network so that any fiber-link cut will still leave the network connected. Simple layout algorithms are given that perform much better than simple shortest path routing, but have comparable time complexities.

R. Kandula and G. Sasaki, "Grooming of dynamic tributary traffic in WDM rings with rearrangements," 39th Allerton Conference, Monticello IL, Oct. 2001. PDF.

Summary: We considered the problem of setting-up traffic connections, when the traffic is tributary traffic, i.e., sub-wavelength traffic. The traffic is assumed to be dynamic, i.e., arrives and leaves at arbitrary times. Thus, it is similar to dynamic lightpath traffic, because it has bounds on offered traffic per link, but it also has bounds on the amount of traffic that can terminate at any node.

We studied a particular WDM architecture for ring networks that allows lightpaths to pass through optically. These networks reduce the number of transponders in the network which are a significant contributor to cost. In fact for certain network sizes and uniform traffic, the architecture can lead to a 44% reduction in transponders compared to networks that do not allow optical pass through.

By using bridge-and-roll we show that existing connections can migrate gracefully to make way for new ones, and have the architecture perform as well as a network that does not allow optical pass through. We provide bounds on the number of bridge-and-roll needed per new connection.

3. Significant Educational, Commercial and Societal Impact Derived From The Project

Patent #6,108,311 "Multichannel ring and star networks with limited channel conversion." Inventors: R. Ramaswami and G. Sasaki, Aug. 22, 2000.

4. Sponsor

This work was supported by the National Science Foundation under project number #9612846. The project was conducted in the Department of Electrical Engineering, University of Hawaii. Its duration was from May 15, 1997 to April 31, 2000 but with a no cost extension until April 31, 2002. A link to the project description at NSF can be found here