polling_qsys_klimited.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_API_POLLING_POLLING_QSYS_KLIMITED_H
#define LINE_API_POLLING_POLLING_QSYS_KLIMITED_H
 
/**
 * @file
 * @ingroup api_polling
 * Approximate mean waiting times of a cyclic k-limited polling system.
 *
 * Templated port of matlab/src/api/polling/polling_qsys_klimited.m. Queue i
 * is served K_i-limited: a visit ends after K_i services or when the queue
 * empties, whichever comes first. The approximation is Fuhrmann's relation
 * for symmetric k-limited systems (Fuhrmann 1985; Haverkort eq. 9.27; Takagi
 * 1988 eq. 27), applied queue by queue:
 *
 *   E[W_i] + b_i = (1-rho) / (1 - rho - lambda_i R/K_i) * (E[W_i^E] + b_i),
 *
 * with E[W_i^E] the exact exhaustive mean waiting time of the same system and
 * R the mean total switchover time per cycle. In the symmetric case it is
 * exact for K=1 and as K grows to infinity. Stability requires
 * rho + lambda_i R/K_i < 1 at every queue.
 */
 
#include <cstddef>
#include <string>
#include <vector>
 
#include "line/api/polling/polling_qsys_1limited.h"
#include "line/api/polling/polling_qsys_exhaustive.h"
#include "line/num/number.h"
#include "line/util/error.h"
 
namespace line {
namespace polling {
 
/**
 * @param m  per-queue first two moments of arrivals, service and switchover
 * @param K  one positive limit, or one per queue
 */
template <class T>
std::vector<T> polling_qsys_klimited(const PollingMoments<T>& m, std::vector<long> K) {
    m.validate("polling_qsys_klimited");
    const std::size_t n = m.size();
    if (K.size() == 1) K.assign(n, K[0]);
    bool bad = K.size() != n;
    for (long k : K) bad = bad || k < 1;
    if (bad)
        throw InputError(ErrorKind{"Argument"},
                         "polling_qsys_klimited: K must be a positive integer, or one positive integer per queue.");
    const T zero = num_traits<T>::from_int(0), one = num_traits<T>::from_int(1);
    T rho = zero, R = zero;
    for (std::size_t i = 0; i < n; ++i) {
        rho += m.lambda[i] * m.b[i];
        R += m.r[i];
    }
    std::vector<T> den(n);
    for (std::size_t i = 0; i < n; ++i) {
        den[i] = one - rho - m.lambda[i] * R / num_traits<T>::from_int(K[i]);
        if (den[i] <= zero)
            throw NumericError(ErrorKind{"Instability"},
                               "polling_qsys_klimited: The k-limited polling system is unstable: "
                               "rho + lambda_i*R/K_i >= 1 at some queue.");
    }
    const std::vector<T> WE = polling_qsys_exhaustive(m);
    std::vector<T> W(n);
    for (std::size_t i = 0; i < n; ++i) W[i] = (one - rho) / den[i] * (WE[i] + m.b[i]) - m.b[i];
    return W;
}
 
/** Scalar-K convenience overload. */
template <class T>
std::vector<T> polling_qsys_klimited(const PollingMoments<T>& m, long K) {
    return polling_qsys_klimited(m, std::vector<long>{K});
}
 
}  // namespace polling
}  // namespace line
 
#endif  // LINE_API_POLLING_POLLING_QSYS_KLIMITED_H