Channel fragmentation in dynamic spectrum access systems

Ed Coffman, Philippe Robert, Florian Simatos, Shuzo Tarumi, Gil ZussmanACM SIGMETRICS Performance Evaluation Review 2010 · DOI

TL;DR

This paper tackles the problem of spectrum fragmentation in Dynamic Spectrum Access (DSA) systems, where available spectrum is broken into many small, non-contiguous pieces. The authors develop a theoretical model and conduct simulations to show that, surprisingly, even with arbitrarily small fragments, the total number of fragments remains bounded, preventing system collapse. They also explore how different allocation algorithms impact fragmentation, finding that a "Largest-First Scan" algorithm significantly reduces it.

What Problem Does This Paper Address?

Dynamic Spectrum Access (DSA) systems, often powered by Cognitive Radios, aim to improve spectrum utilization by allowing secondary users (SUs) to access "white spaces" – parts of the radio spectrum temporarily unused by primary users. A key technique for SUs is to use non-contiguous channels, meaning their transmission can be spread across multiple, separate frequency bands. While this flexibility is beneficial, it can lead to "spectrum fragmentation," where the available spectrum is broken into many small, disconnected "fragments" or "gaps." This fragmentation can degrade performance and complicate resource allocation. The paper addresses the fundamental question: does this fragmentation process, especially when fragments can be arbitrarily small, lead to an unbounded increase in fragments, ultimately making the system unusable?

Methods

The authors employ a combination of theoretical modeling and experimental simulation.

  • Mathematical Model: They develop a theoretical model of a DSA system operating at capacity. Key assumptions include:
  • A fixed total spectrum size (normalized to [0, 1]).
  • Bandwidth requests with sizes uniformly distributed on (0, α], where α is the maximum request size.
  • Exponentially distributed request durations.
  • No lower bound on fragment size.
  • A system always operating at capacity (i.e., a constant queue of waiting requests). They analyze the number of fragments, gaps, and active channels using Markov chain theory.

  • Simulation Study: Extensive discrete-event simulations were conducted to observe the system's behavior under different fragmentation scenarios and algorithms. This experimental approach helps to uncover unexpected behaviors and validate theoretical findings.

  • Algorithmic Analysis: The paper compares three different algorithms for allocating spectrum fragments to new requests:
  • Linear Scan (LS): Scans the spectrum from one end to the other.
  • Circular Scan (CS): Uses a circular list of gaps, with the scan starting where the previous one left off.
  • Largest-First Scan (LFS): Prioritizes allocating larger available gaps first, aiming to minimize the number of fragments needed for a request.

Datasets

Not discussed in the paper. The study relies on a simulated environment with generated request arrival and departure patterns based on the defined probability model.

Key Insights and Ideas

  • Bounded Fragmentation: The most striking insight is that even when fragments can be arbitrarily small, the total number of fragments and gaps in the system does not grow indefinitely. This is a crucial finding for the practical viability of DSA systems.
  • The 50% Rule: An unexpected reappearance of a "50% rule" is observed, where the number of gaps is approximately half the number of active requests. This rule, known from classical storage allocation, holds even with fragmented files (channels).
  • Fragmentation vs. Request Size: Smaller maximum request sizes (smaller α) lead to significantly higher fragmentation of individual requests. This implies that for practical systems, imposing a minimum fragment size is important.
  • Algorithm Impact: The choice of spectrum allocation algorithm has a substantial impact on fragmentation. The Largest-First Scan (LFS) algorithm dramatically reduces fragmentation compared to Linear Scan and Circular Scan.
  • Normal Distribution: The total number of fragments, under certain conditions and scaling, appears to follow a Normal distribution, which is a useful approximation for performance analysis.

Key Results

  • Theoretical Stability: The paper proves that the total number of fragments and gaps has bounded exponential moments, meaning the system remains stable even with continuous fragmentation.
  • Harris Recurrence: For request sizes larger than 1/2 (α > 1/2), the fragmentation process is shown to be positive Harris recurrent, guaranteeing a unique stationary distribution.
  • Algorithmic Performance: The Largest-First Scan (LFS) algorithm reduces the average number of fragments per channel by a factor of more than 3 compared to Linear Scan (LS) and Circular Scan (CS).
  • 50% Rule Confirmation: The ratio of gaps to requests approaches 1/2 as the maximum request size approaches zero (α → 0).
  • Fragmentation Growth: The average number of fragments per channel grows linearly with 1/α, leading to a quadratic growth in the total number of fragments.

Limitations and Future Work

  • Model Simplifications: The model assumes uniform request size distributions and exponential service times. Future work could explore other distributions and their impact on fragmentation.
  • Independence Assumption: The current model assumes independence of request sizes and durations. More realistic models could relax these assumptions, for example, by allowing residence times to depend on fragmentation.
  • Discrete vs. Continuous: The paper uses a continuous model for spectrum and request sizes. Investigating discrete models, which are more representative of actual OFDM subcarriers, is suggested as a crucial next step.
  • Algorithmic Enhancements: Future research could focus on developing algorithms that better fit fragments into available gaps or incorporate spectrum sensing capabilities into the allocation process.
  • Practical Implementations: Exploring how these theoretical findings translate to real-world DSA systems, including the challenges of implementing these algorithms and models, is a key area for future work.

Summary updated

Abstract

Dynamic Spectrum Access systems exploit temporarily available spectrum ('white spaces') and can spread transmissions over a number of non-contiguous sub-channels. Such methods are highly beneficial in terms of spectrum utilization. However, excessive fragmentation degrades performance and hence off-sets the benefits. Thus, there is a need to study these processes so as to determine how to ensure acceptable levels of fragmentation. Hence, we present experimental and analytical results derived from a mathematical model. We model a system operating at capacity serving requests for bandwidth by assigning a collection of gaps (sub-channels) with no limitations on the fragment size. Our main theoretical result shows that even if fragments can be arbitrarily small, the system does not degrade with time. Namely, the average total number of fragments remains bounded. Within the very difficult class of dynamic fragmentation models (including models of storage fragmentation), this result appears to be the first of its kind. Extensive experimental results describe behavior, at times unexpected, of fragmentation under different algorithms. Our model also applies to dynamic linked-list storage allocation, and provides a novel analysis in that domain. We prove that, interestingly, the 50% rule of the classical (non-fragmented) allocation model carries over to our model. Overall, the paper provides insights into the potential behavior of practical fragmentation algorithms.
BibTeX
@article{coffman2010channel,
  author = {Ed Coffman and Philippe Robert and Florian Simatos and Shuzo Tarumi and Gil Zussman},
  title = {{Channel fragmentation in dynamic spectrum access systems}},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2010},
  doi = {10.1145/1811099.1811077},
}
Figure