Optimization in Action: The Train of a Single Color

Let's explain the routing wavelength assignment (RWA) problem.

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.

Imagine planning a train trip across multiple cities. Each track can only accommodate one train of a particular color at a time. Your challenge is to find a path with open tracks and choose one train color that can carry you all the way to your destination.

This is similar to the concept of routing and wavelength assignment in network optimization. Here's how it works:

1. Find Your Route : Identify a series of tracks (or paths) that can take you from start to finish with enough capacity for your train.
2. Pick Your Color: Choose a train color that is available for the entire journey. The catch? You have to stick with this color from start to finish, no switching allowed!
3. Using the Same Track : Just like trains can share tracks as long as they are of different colors, multiple connection requests can share the same optical link as long as they use different wavelengths. Imagine two trains, a red train and a blue train, both traveling between the same stations on the same track. As long as they are different colors, they can use the track simultaneously without interfering with each other.

As you can see, the optimization is a fascinating dance of resource management and efficiency.

Summary

• Stations are like points in the network where connections start and end.
• Tracks are the routes connections take between these points.
• Train colors are the wavelengths used for these connections.
• Multiple trains can use the same track if they are different colors (wavelengths).
• The aim is to have as many trains as possible traveling without conflicts, maximizing the network’s efficiency.

Example:

• Case A: both demands can be addressed since they don't use mutual path and use only one wavelength.
• Case B: Just one of the demands can be addressed since they use mutual path and only one wavelength is available.
• Case C: both demands can be addressed since althought they use mutual path and but they can use different wavelengths.

Let's skip to the good part called modeling and coding:

Model:

Data

• A graph with know topology
• A set of potential demands are known (the send-receive nodes)
• A set of wavelengths to be assigned to each demand if addressed

Math model

• There should be a path between send and receive of each demand if accepted (the send and receive nodes should be in the path, the rest of the nodes can be excluded from the path if needed as far as the connected path is acheived)

for l in demands:
  aa= [(demands[l][0],demands[l][1],accepted[l])]
  bb = [(i,i,select[i,l].Not()) for i in nodes ]
  cc = [(i,j,v) for (i,j,L),v in U.items() if L ==l]
  model.Add(select[demands[l][0],l]==accepted[l])
  model.Add(select[demands[l][1],l]==accepted[l])
  model.AddCircuit(cc+aa+ bb)        

aa creates a link between send and receive

bb makes sure to exclude non selected nodes from the path

cc a connected path

• If two demands share a link (between node i and j) in their paths then they should be assigned to different wavelengths

First we need to know if any two demands l1,l2 share the same link

for (i,j,l1),v in U.items():
  for (m,n,l2),vv in U.items():
    con1 = (i,j) == (m,n) and l1>l2 and i>j
    if con1:
      model.Add(Z[i,j,l1,l2] <= v + U[j,i,l1])
      model.Add(Z[i,j,l1,l2] <= vv+ U[n,m,l2])
      model.Add(Z[i,j,l1,l2] >= vv + v + U[n,m,l2] + U[j,i,l1] -1)        

• Each demand should be assigned to only one wavelength if accepted

for l in demands:
  expressions = [lambdas[l,wl] for wl in wl_set]
  model.Add(sum(expressions) == accepted[l])        

• If a demand is not accepted then no node can be selected to be in its path

for (i,l),v in select.items():
  model.Add(v<=accepted[l])        

Another Example

Here are the key points explaining why optimization is needed:

• Resource Utilization: Optimization ensures efficient use of available wavelengths and network resources, minimizing waste and maximizing the network's capacity.
• Blocking Probability Reduction: By optimizing the assignment, the likelihood of call blocking due to unavailable paths or wavelengths is reduced, improving the network's quality of service.
• Scalability: As the network grows, optimized RWA helps in handling increased demand without a proportional increase in infrastructure costs.
• Cost Efficiency: Optimal RWA can lower operational costs by minimizing the need for additional hardware, such as optical amplifiers and switches, by effectively utilizing existing resources.
• Network Performance: Improved routing and wavelength allocation can enhance overall network performance, including latency, throughput, and reliability.
• Load Balancing: Optimization helps in distributing network traffic evenly, preventing congestion and bottlenecks on certain paths while underutilizing others.
• Flexibility and Adaptability: An optimized RWA strategy can adapt more readily to changes in traffic patterns and network topology, ensuring long-term network resilience.
• Minimized Interference: By carefully selecting wavelengths, optimization can reduce interference and crosstalk, leading to clearer signal transmission and fewer errors.
• Energy Efficiency: Optimal routing and wavelength use can lead to energy savings by minimizing the need for active network components and reducing heat generation.
• Future-Proofing: A well-optimized RWA framework can accommodate future technological advancements and increases in demand, ensuring the network remains viable and competitive.

Reference :

https://hal.science/hal-01062321/document

https://www.eclipseclp.org/ELearning/wave2/slides.pdf from Helmut Simonis

The code is available upon the request