Banner image placeholder
Banner image
Site avatar
Alex Carrega
Ph.D. IT & Network Engineer

Curriculum vitae



+39 348-74.85.497


TNT Lab @ UniGe

CNIT

via Opera Pia 13, 16154 Genoa, Italy



A Stochastic Knapsack Model for Energy Efficient Management of Multi-Server Queues


Conference paper


Raffaele Bolla, Roberto Bruschi, Alessandro Carrega, Franco Davoli, Chiara Lombardo, Beatrice Siccardi
2024 7th International Balkan Conference on Communications and Networking (BalkanCom), 2024, pp. 224-229


Cite

Cite

APA   Click to copy
Bolla, R., Bruschi, R., Carrega, A., Davoli, F., Lombardo, C., & Siccardi, B. (2024). A Stochastic Knapsack Model for Energy Efficient Management of Multi-Server Queues. In 2024 7th International Balkan Conference on Communications and Networking (BalkanCom) (pp. 224–229). https://doi.org/10.1109/BalkanCom61808.2024.10557204


Chicago/Turabian   Click to copy
Bolla, Raffaele, Roberto Bruschi, Alessandro Carrega, Franco Davoli, Chiara Lombardo, and Beatrice Siccardi. “A Stochastic Knapsack Model for Energy Efficient Management of Multi-Server Queues.” In 2024 7th International Balkan Conference on Communications and Networking (BalkanCom), 224–229, 2024.


MLA   Click to copy
Bolla, Raffaele, et al. “A Stochastic Knapsack Model for Energy Efficient Management of Multi-Server Queues.” 2024 7th International Balkan Conference on Communications and Networking (BalkanCom), 2024, pp. 224–29, doi:10.1109/BalkanCom61808.2024.10557204.


BibTeX   Click to copy

@inproceedings{bolla2024a,
  title = {A Stochastic Knapsack Model for Energy Efficient Management of Multi-Server Queues},
  year = {2024},
  pages = {224-229},
  doi = {10.1109/BalkanCom61808.2024.10557204},
  author = {Bolla, Raffaele and Bruschi, Roberto and Carrega, Alessandro and Davoli, Franco and Lombardo, Chiara and Siccardi, Beatrice},
  booktitle = {2024 7th International Balkan Conference on Communications and Networking (BalkanCom)}
}

🔬 Stochastic Knapsack Modeling for Energy-Efficient Multi-Server Queues: Balancing Processing Capacity, Packet Delay, and Flow Admission

The increasing deployment of virtualized network functions and computational services at the network edge introduces significant challenges for energy-efficient resource management.

Modern edge infrastructures must process multiple heterogeneous traffic flows characterized by bursty packet arrivals, different statistical properties, and distinct Quality of Service (QoS) requirements.

Traditional static resource provisioning can result in unnecessary energy consumption when computing resources remain active despite fluctuating traffic demands.

Our research proposes an analytical modeling and control framework that combines multi-server queueing theory, stochastic knapsack models, and admission control to dynamically manage processing capacity while satisfying performance constraints.

The fundamental objective is to activate the minimum number of processing cores required to serve incoming traffic, while balancing packet-level delay requirements and flow-level blocking probabilities.

⚙️ Multi-Class, Multi-Scale Traffic Model

The proposed framework separates system dynamics into two distinct time scales.

🔹 Packet-Level Dynamics

Packets are generated in bursts and processed by multiple parallel computing resources.

The system is modeled using an Mˣ/D/C queue, where:

• Mˣ represents Poisson batch arrivals with random batch sizes.

• D denotes deterministic packet processing times.

• C represents the number of simultaneously active processing cores.

• An infinite queue buffers packets waiting for processing.

The model enables analytical estimation of queue occupancy and average packet waiting time.

🔹 Flow-Level Dynamics

Traffic flows are modeled through a birth–death stochastic process.

Flow arrivals follow a Poisson process, while flow durations are exponentially distributed.

These dynamics evolve on a slower time scale than packet arrivals and processing operations, allowing a time-scale decomposition of the overall system.

The resulting state space is represented through a Stochastic Knapsack model, where admission decisions depend on available resources and QoS constraints.

📐 Analytical Optimization Framework

The framework addresses two complementary optimization problems.

1. Packet-Level Optimization

Determine the minimum number of active processing cores needed to satisfy the maximum acceptable average waiting time for each traffic class.

The model uses analytical queueing expressions and Little's theorem to characterize the relationship between offered traffic, processing capacity, queue occupancy, and waiting time.

2. Flow-Level Optimization

Determine admissible combinations of traffic flows while controlling blocking probabilities.

The admissible states form a feasibility region defined by packet-level performance constraints.

For Complete Partitioning, resource allocation is optimized by minimizing a weighted sum of class-specific blocking probabilities, expressed using the Erlang B formula.

🔀 Complete Partitioning vs. Complete Sharing

Two Call Admission Control (CAC) strategies are evaluated.

🔹 Complete Partitioning (CP)

Each traffic class receives a dedicated queue and a partition of the available processing resources.

The allocation is optimized according to the corresponding delay constraints and class-specific blocking probabilities.

This approach provides differentiated resource allocation for heterogeneous traffic classes.

🔹 Complete Sharing (CS)

All traffic classes use a common queue and share the available processing resources.

The paper analyzes this approach under the assumption that packets from different classes have identical processing times.

The aggregate traffic process is characterized using the combined arrival intensity and batch-size statistics.

🧪 Numerical Evaluation

The analytical framework is evaluated using numerical experiments involving two traffic classes with different workload characteristics.

The reference configuration includes:

• Maximum available processing cores: 24.

• Class 1 batch arrival rate: 20 Mbatches/s.

• Class 2 batch arrival rate: 3.5 Mbatches/s.

• Average batch sizes: 2.3 and 1.9 packets/batch.

• Packet processing times: 10 ns and 100 ns, respectively, in the reference parameter configuration.

• Average waiting-time limits: 50 ns and 100 ns, respectively.

The analysis examines how varying traffic loads affect the minimum number of active cores, packet waiting times, resource allocation, and estimated energy savings.

📊 Key Numerical Findings

✅ Dynamic Processing Capacity: The minimum number of active cores generally increases in a stepwise manner as incoming workload grows.

✅ Delay-Constrained Resource Management: The proposed framework determines the minimum processing capacity required to satisfy class-specific average waiting-time constraints.

✅ Energy-Aware Operation: Deactivating unnecessary processing cores during low-load periods reduces the estimated energy requirements.

✅ Flow-Level Admission Control: The stochastic knapsack formulation supports admission decisions subject to packet-level QoS constraints and class-specific blocking considerations.

✅ Resource Allocation Comparison: Complete Partitioning provides greater energy-saving opportunities than Complete Sharing under the evaluated assumptions.

✅ Main Result: In the numerical comparison with equal packet processing times, Complete Partitioning achieves approximately 2.5 times the energy savings obtained with Complete Sharing.

✅ QoS–Energy Trade-off: The framework explicitly connects energy-efficient processing capacity allocation with waiting-time constraints and flow-blocking objectives.

🎯 Key Research Contribution

A multi-scale analytical framework that combines Mˣ/D/C queueing theory, stochastic knapsack admission control, and dynamic processor activation to support energy-efficient management of heterogeneous traffic flows in virtualized networking and edge computing infrastructures.

The study demonstrates how processing resources can be activated according to workload requirements while retaining explicit control over packet waiting times and flow admission.

The proposed methodology provides a mathematical foundation for future energy-aware resource management in Multi-Access Edge Computing (MEC), virtualized network functions, and emerging 6G architectures.

Scientific clarification: The findings are based on analytical modeling and numerical evaluation. The approximately 2.5× advantage refers to the integrated energy-saving comparison reported for the evaluated CP and CS configurations, not to a universal performance guarantee. The paper does not report experimental power measurements from a physical testbed.

🌱⚡ What If Game Theory and Mathematics Could Make Edge Computing Greener? ☁️🚀

Imagine an edge computing infrastructure where multiple applications compete for processing resources, generating unpredictable bursts of network traffic while demanding different levels of performance.

Keeping every processing core permanently active guarantees available computing capacity, but it also leads to unnecessary energy consumption during periods of reduced workload.

What if we could activate only the processing resources actually needed, without violating application performance requirements?

Our research investigates this challenge through a Stochastic Knapsack Model for Energy-Efficient Management of Multi-Server Queues.

The central idea is to dynamically control the number of active CPU cores according to incoming traffic and Quality of Service (QoS) requirements.

⚡ Dynamic Core Activation: Activate additional processing cores when traffic increases and deactivate unnecessary resources when demand decreases.

📦 Bursty Traffic Modeling: Represent multiple traffic flows generating packets in batches, each characterized by different statistical properties and performance requirements.

🧮 Queueing Theory: Use an Mˣ/D/C multi-server queueing model to estimate packet waiting times and determine the processing capacity required to meet QoS constraints.

🎯 Stochastic Knapsack: Determine which flows can be admitted while respecting resource limitations and controlling the probability of rejecting new requests.

🔀 Intelligent Resource Allocation: Compare two strategies for distributing processing resources among traffic classes.

The first strategy, Complete Partitioning (CP), assigns dedicated processing resources and separate queues to different traffic classes.

The second, Complete Sharing (CS), combines traffic classes into a shared queue served by a common pool of processing cores.

📊 What did we discover?

✅ The proposed approach dynamically adjusts processing capacity while satisfying the modeled packet waiting-time constraints.

✅ Processing-core activation follows workload variations, reducing unnecessary resource usage under lighter traffic conditions.

✅ Complete Partitioning provides greater opportunities for energy savings in the evaluated scenario.

✅ CP achieves approximately 2.5 times greater energy savings than CS in the paper's numerical comparison.

✅ The model explicitly considers the trade-off between packet delay, flow blocking probability, and processing-resource utilization.

Our manga-inspired infographic illustrates how intelligent resource allocation can transform energy-hungry edge computing infrastructures into more adaptive and sustainable systems.

🎯 The message: Greener networks do not necessarily require more powerful hardware. They require smarter decisions about which resources should remain active and when.

The reported results come from analytical modeling and numerical evaluation, rather than measurements on a physical edge computing testbed.

Our manga-inspired infographic illustrates how intelligent resource allocation can transform energy-hungry edge computing infrastructures into more adaptive and sustainable systems.


Share

Text Only Owlstown
QR Code
Translate to