Spectrum Assignment in EON

Methods and algorithms for efficient spectrum allocation in elastic networks.

The Challenge: Optical Spectrum as Prime Real Estate

Imagine the available optical spectrum in a fiber as a valuable, finite stretch of undeveloped land. When a request for a new connection arrives (like a developer wanting to build a new supermarket), the network operator, acting as the city planner, must decide not only which roads to take to get to the location (this is Routing), but also exactly which plot of land along that route to build on. This second, critical decision is known as Spectrum Assignment (SA).

In an , this "land" is divided into many small, uniform plots called frequency slots. A connection request (the supermarket) requires a specific number of adjacent plots (a contiguous block of slots) to build upon. The Spectrum Assignment algorithm's job is to efficiently allocate these plots, ensuring that no two supermarkets are built on top of each other and that the overall land use is as efficient as possible for future development.

The Primary Obstacle: Spectrum Fragmentation

The most significant challenge in Spectrum Assignment is Spectrum Fragmentation. In a dynamic network, connections are constantly being established and torn down. When a connection is terminated, it releases its block of frequency slots, creating a gap of available spectrum. Over time, this process of allocation and de-allocation leaves behind a patchwork of small, scattered, and often unusable free blocks.

This is analogous to fragmentation on a computer's hard drive, where after creating and deleting many files, the free space is broken up into many small, non-contiguous chunks. In optical networks, this means that even if the total amount of free spectrum on a link is large, it may not be possible to serve a new connection request because no single block of slots is large enough.

Consequences of Fragmentation

Poorly managed spectrum assignment leads to high fragmentation, which in turn leads to a higher blocking probability. A connection is "blocked" if the network cannot find a suitable path and/or spectrum block to serve it, even though the network is not at full capacity. For a network operator, a high blocking probability translates directly to lost revenue and dissatisfied customers.

Spectrum Assignment Heuristics: Simple Rules for a Complex Problem

...signment for every possible future request is an incredibly complex () problem. Therefore, network controllers rely on heuristics (simple, fast, rule-of-thumb algorithms that provide a good-enough solution quickly).

Imagine the spectrum on a fiber link is a long street with numbered plots from 0 to 319. A new request arrives needing 4 adjacent plots. The network has several free blocks: plots 10-15 (6 plots), 40-43 (4 plots), and 90-95 (6 plots). Which block should the algorithm choose?

Common Allocation Strategies

First-Fit (FF)

The Rule: Scan the spectrum starting from the lowest frequency (slot 0) upwards and allocate the first available contiguous block of slots that is large enough to accommodate the request.

In our example: The algorithm would scan, find the free block at plots 10-15, see that it is large enough $(6 > 4)$ , and allocate plots 10, 11, 12, and 13 to the new connection.

Implications: FF is very simple and fast to implement. Over time, it tends to pack connections tightly at the lower end of the spectrum, leaving larger contiguous blocks free at the higher end, which can be beneficial for future high-bandwidth requests. Many studies show it performs surprisingly well in reducing overall blocking.

Last-Fit (LF)

The Rule: The opposite of First-Fit. Scan the spectrum starting from the highest frequency downwards and allocate the first block that is large enough.

In our example: The algorithm would scan from the top, find the free block at 90-95, and allocate plots 92, 93, 94, and 95 (or 90-93).

Implications: This strategy packs connections at the high-frequency end of the spectrum, leaving space at the bottom. It performs similarly to FF, but the choice might be influenced by physical characteristics of optical amplifiers, which sometimes have better performance profiles at one end of the spectrum.

Random-Fit (RF)

The Rule: Identify all available contiguous blocks that are large enough for the request, and then choose one of them at random.

In our example: The algorithm would identify blocks $10-15$ , $40-43$ , and $90-95$ as candidates and randomly select one to place the 4-slot connection.

Implications: By spreading the allocated channels more evenly across the spectrum, RF can theoretically lead to more severe fragmentation over time, creating many small, unusable gaps everywhere instead of consolidating free space. It generally performs worse than First-Fit.

Exact-Fit

The Rule: Search for a free block that has exactly the same size as the request. Only if such a perfect-sized block is not found does it consider allocating from a larger block.

In our example: The algorithm would first search for a 4-slot block. It would find the block at 40-43 and immediately select it, leaving the larger blocks (10-15 and 90-95) untouched for potentially larger future requests.

Implications: This is an intuitive strategy aimed at preserving large contiguous blocks. It can be very effective but may be slightly more complex to implement than simple First-Fit.

Advanced Considerations

Beyond simple heuristics, a real-world Spectrum Assignment system must consider additional constraints imposed by optical physics.

Modulation Format Awareness

The number of slots a connection requires is not fixed; it depends on the chosen modulation format, which in turn depends on the length of the path.

Consider a 100 Gbps connection request:

For a short path (e.g., San Francisco to Los Angeles, ~600 km), it might be possible to use 16-QAM modulation. This requires, for example, 3 frequency slots.
For a long, cross-country path (e.g., New York to Los Angeles, ~4000 km), 16-QAM would be too noisy. The system must use a more robust format like BPSK, which might require 8 frequency slots to deliver the same 100 Gbps.

Therefore, a truly intelligent SA algorithm cannot simply search for "a free block." It must first determine the required modulation format based on the path length and then search for a free block that is wide enough to accommodate the number of slots required by that specific format.

Spectrum Defragmentation

What happens when fragmentation inevitably becomes a problem? The ultimate solution is spectrum defragmentation. This involves actively re-arranging existing connections in the network, moving them to different parts of the spectrum to consolidate small free blocks into larger, more usable ones. This is akin to defragmenting a hard drive.

This is a highly complex process, as it must ideally be done without interrupting live traffic ("hitless defragmentation"), which requires briefly rerouting connections or using sophisticated techniques to shift a channel's frequency without dropping data. It remains an active and challenging area of research in optical networking.