The Repacking Efficiency for Bandwidth Packing Problem

Jianxin Chen, Yuhang Yang, Lei ZhouIEICE Trans. Information and Systems 2007 · DOI

TL;DR

This paper tackles the Bandwidth Packing Problem (BPP) in centralized networks (CNs), focusing on maximizing bandwidth utilization. The authors propose several "repacking" algorithms, enhancements to the Next Fit (NF) approach, and demonstrate through simulations that these repacking schemes significantly improve efficiency, especially when small call demands dominate the network.

What Problem Does This Paper Address?

In communication networks, efficiently allocating limited bandwidth is crucial. Centralized networks (CNs), where a central unit (CU) manages bandwidth for connected terminals, face a specific challenge: the Bandwidth Packing Problem (BPP). The goal is to maximize the total profit by assigning appropriate routes to calls, but in CNs, this translates to maximizing bandwidth utilization within the CU. While existing algorithms like Next Fit (NF) exist, their performance is often suboptimal. This paper investigates how to improve NF's efficiency in CNs by introducing a "repacking" scheme, which aims to re-optimize bandwidth allocation within a given packing window (PW) when a new call cannot be accommodated. The core question is: how much can repacking improve the efficiency, and how does it perform under different call demand distributions?

Methods

The authors formulate the BPP in the context of a CN, aiming to maximize bandwidth utilization while maintaining online properties (computation complexity within the packing window). They introduce a "repacking scheme" as an enhancement to the Next Fit (NF) algorithm. When a new call arrives and the current available bandwidth is insufficient, instead of simply rejecting the call, the repacking scheme attempts to rearrange already allocated calls to make space.

They propose four NF-based repacking algorithms:

  • Algorithm 1: Next Fit with the Top Call Repacking (NFTCR): The simplest approach, it only considers repacking the most recently allocated call if it allows the new call to fit.
  • Algorithm 2: Next Fit with the First Call Repacking (NFFCR): This algorithm searches from the top down for the first call that, if removed, would allow the new call to be packed.
  • Algorithm 3: Next Fit with the Best Call Repacking (NFBCR): This algorithm aims to minimize wasted bandwidth by finding the best call to repack (i.e., the one that frees up just enough bandwidth) among those that meet the repacking condition.
  • Algorithm 4: Next Fit with the Optimal Repacking (NFOR): This is the most sophisticated, treating the repacking problem as a knapsack problem and solving it using dynamic programming to find the absolute optimal repacking solution for a given set of calls.

The performance of these algorithms is evaluated through simulations, considering various call demand distributions.

Datasets

Not discussed in the paper. The authors generated synthetic call demand data for their simulations, using uniform, exponential, binomial, and Poisson distributions.

Key Insights and Ideas

  • Repacking is effective: The repacking scheme, even in its simplest forms, offers significant improvements over the basic Next Fit algorithm for bandwidth packing in centralized networks.
  • Small demands are key: Repacking schemes are most beneficial when small call demands are prevalent. This is because repacking is more likely to succeed when there are many smaller items (calls) that can be rearranged to accommodate a new one, rather than a few large items.
  • Distribution matters: The distribution of call demands significantly impacts repacking efficiency. Exponential distributions, which tend to have a higher proportion of small demands, yield the best results, while binomial distributions show less improvement.
  • Trade-off between complexity and efficiency: While the optimal repacking algorithm (NFOR) offers the highest efficiency, its computational complexity is considerably higher than simpler methods like NFTCR, NFFCR, and NFBCR. The simpler algorithms achieve good performance with much lower computational overhead.

Key Results

  • Uniform Distribution: Repacking algorithms showed an average performance improvement of about 15% over NF. NFTCR provided a minimal improvement of around 13%, while NFOR achieved up to 17%.
  • Exponential Distribution: This distribution yielded the highest repacking efficiency, with improvements reaching up to 21%.
  • Poisson Distribution: Repacking efficiency was less pronounced, with improvements being minimal (less than 3% for some cases). This is attributed to the decreasing probability of large call demands in Poisson distributions, leading to fewer repacking opportunities.
  • Complexity vs. Performance: Simpler algorithms like NFTCR, NFFCR, and NFBCR achieved performance close to NFOR but with significantly lower computational complexity, making them more practical for real-time applications. Table 1 shows that the computation time for NF, NFTCR, NFFCR, and NFBCR are generally comparable and much lower than NFOR.

Limitations and Future Work

  • Limited to CNs: The study focuses specifically on centralized network architectures. Its applicability to distributed or other network topologies is not explored.
  • Assumptions: The paper assumes a fixed packing window duration and that the CU has infinite buffers. Real-world scenarios might have dynamic window sizes or buffer limitations.
  • Call Demand Distributions: While several distributions were tested, the paper acknowledges that real-world internet traffic can be tri-modal, which was not explicitly modeled.
  • Future Work: The authors suggest further investigation into the impact of different call demand distributions and the potential for more advanced repacking algorithms. They also hint at the need to consider the energy constraints in specific network types like ad hoc or wireless sensor networks, where complex algorithms might not be feasible.

Summary updated

BibTeX
@article{chen2007repacking,
  author = {Jianxin Chen and Yuhang Yang and Lei Zhou},
  title = {{The Repacking Efficiency for Bandwidth Packing Problem}},
  journal = {IEICE Trans. Information and Systems},
  year = {2007},
  doi = {10.1093/ietisy/e90-d.7.1011},
}
Figure