fluid_mfq_admits.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_SOLVERS_FLUID_FLUID_MFQ_ADMITS_H
#define LINE_SOLVERS_FLUID_FLUID_MFQ_ADMITS_H
 
/**
 * @file
 * @ingroup line_solvers
 * Port of `fluid_mfq_admits.m` and `fluid_is_single_queue.m`: can the
 * `mfq` fluid method (and its alias `aoi`) run as itself on this model?
 *
 * The Markovian fluid queue answers ONE open station, Source -> Queue -> Sink.
 * Off that shape `mfq` RESOLVES to `matrix` (`SolverFLD.resolveMethod`), which
 * is the fallback the analyzer has always taken: stating it before the gate is
 * what makes the gate check, and the result report, the method that answers.
 * One predicate, two callers (`fluid_resolve_method` and the `mfq` arm of
 * `fluid_dispatch`), as in MATLAB and native python.
 *
 * Three arms, tried in the analyzer's own order:
 *  - the age-of-information shape (`aoi_is_aoi`);
 *  - the priority branch, taken when the classes carry distinct priorities: a
 *    class-independent finite positive service rate, a MAP {D0,D1} arrival for
 *    every open class, at least one of them modulated;
 *  - the plain branch, stated for ONE open class.
 * Closed classes are refused by the feature set rather than here.
 *
 * The topology test is NODE-level, as the reference's is: a Delay or Router
 * node does not disqualify the model, only a second Source, Queue or Sink
 * does. That differs from `mfq_is_single_queue`, the topology the solver
 * itself builds, which is stricter; a model admitted here and refused there is
 * answered by `matrix` in the dispatch, exactly as before.
 */
 
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <set>
#include <string>
#include <vector>
 
#include "line/lang/qn/network_struct.h"
#include "line/solvers/fluid/fluid_aoi.h"
 
namespace line {
namespace fluid {
 
/** The single-queue topology the reference reads, in 0-based indices. */
struct FluidSingleQueue {
    bool ok = false;
    std::string error;           ///< the reference's errorMsg when !ok
    std::size_t source = 0;      ///< 0-based station index of the Source
    std::size_t queue = 0;       ///< 0-based station index of the Queue
};
 
/** Port of `fluid_is_single_queue.m`. */
template <class T>
FluidSingleQueue fluid_is_single_queue(const qn::NetworkStruct<T>& sn) {
    FluidSingleQueue t;
    const std::size_t K = sn.nclasses;
    bool any_open = false;
    for (std::size_t r = 0; r < K; ++r)
        if (!std::isfinite(sn.classes[r].population)) any_open = true;
    if (!any_open) {
        t.error = "Not an open model - all classes are closed";
        return t;
    }
    std::size_t nsrc = 0, nq = 0, nsink = 0, qnode = 0, srcnode = 0;
    for (std::size_t ind = 0; ind < sn.nodes.size(); ++ind) {
        const qn::NodeType nt = sn.nodes[ind].nodetype;
        if (nt == qn::NodeType::Source) { ++nsrc; srcnode = ind + 1; }
        else if (nt == qn::NodeType::Queue) { ++nq; qnode = ind + 1; }
        else if (nt == qn::NodeType::Sink) ++nsink;
    }
    if (nsrc == 0) { t.error = "No source node found"; return t; }
    if (nsrc > 1) { t.error = "Multiple source nodes found (" + std::to_string(nsrc) + ")"; return t; }
    if (nsink == 0) { t.error = "No sink node found"; return t; }
    if (nsink > 1) { t.error = "Multiple sink nodes found (" + std::to_string(nsink) + ")"; return t; }
    if (nq == 0) { t.error = "No queue node found"; return t; }
    if (nq > 1) {
        t.error = "Multiple queue nodes found (" + std::to_string(nq) +
                  ") - MFQ supports single queue only";
        return t;
    }
    const std::size_t sst = sn.nodes[srcnode - 1].station;  // 1-based, 0 = not a station
    const std::size_t qst = sn.nodes[qnode - 1].station;
    if (sst == 0 || qst == 0) {
        t.error = "MFQ requires source and queue to be stations";
        return t;
    }
    const double c = sn.stations[qst - 1].nservers;
    if (c > 1 && std::isfinite(c)) {
        t.error = "Multi-server queue (c=" + std::to_string(static_cast<long long>(c)) +
                  ") not supported - MFQ requires c=1 or c=Inf";
        return t;
    }
    // No self-loop at the queue. rt is over the STATEFUL nodes; the reference
    // indexes it with the station index, which coincides on this shape.
    const auto it = std::lower_bound(sn.stateful_nodes.begin(), sn.stateful_nodes.end(), qnode);
    if (it != sn.stateful_nodes.end() && *it == qnode) {
        const std::size_t isf = static_cast<std::size_t>(it - sn.stateful_nodes.begin());
        for (std::size_t k = 0; k < K; ++k) {
            const std::size_t idx = isf * K + k;
            if (idx < sn.rt.rows() && idx < sn.rt.cols() &&
                num_traits<T>::to_double(sn.rt(idx, idx)) > 0) {
                t.error = "Self-loop detected at queue - violates independence assumption";
                return t;
            }
        }
    }
    t.source = sst - 1;
    t.queue = qst - 1;
    t.ok = true;
    return t;
}
 
/** Verdict of `fluid_mfq_admits`. */
struct FluidMfqAdmits {
    bool ok = false;
    std::string reason;   ///< the refusal, empty when ok
    bool is_aoi = false;  ///< the age-of-information arm is the one that runs
};
 
/** Port of `fluid_mfq_admits.m`. */
template <class T>
FluidMfqAdmits fluid_mfq_admits(const qn::NetworkStruct<T>& sn) {
    FluidMfqAdmits a;
    if (aoi_is_aoi(sn).ok) {
        a.ok = true;
        a.is_aoi = true;
        return a;
    }
    const FluidSingleQueue top = fluid_is_single_queue(sn);
    if (!top.ok) {
        a.reason = "The 'mfq' method is a single-queue fluid model (Source -> Queue -> Sink, "
                   "one or infinitely many servers): " + top.error + ".";
        return a;
    }
    std::vector<std::size_t> open;
    for (std::size_t r = 0; r < sn.nclasses; ++r)
        if (!std::isfinite(sn.classes[r].population)) open.push_back(r);
    // the same test the analyzer switches on: distinct priorities over ALL classes
    std::set<double> prios;
    for (std::size_t r = 0; r < sn.nclasses; ++r) prios.insert(static_cast<double>(sn.classes[r].prio));
    if (prios.size() > 1) {
        const char* rate_msg = "The priority branch of 'mfq' needs a finite positive service rate "
                               "for every open class.";
        if (open.empty()) { a.reason = rate_msg; return a; }
        std::vector<double> mu;
        for (std::size_t k : open) mu.push_back(num_traits<T>::to_double(sn.rates(top.queue, k)));
        for (double m : mu)
            if (!std::isfinite(m) || m <= 0) { a.reason = rate_msg; return a; }
        const double fine_tol = 1e-8;  // GlobalConstants.FineTol
        for (double m : mu)
            if (std::fabs(m - mu[0]) > fine_tol * std::max(1.0, mu[0])) {
                a.reason = "The priority branch of 'mfq' is a fluid priority queue drained at one "
                           "rate, so it needs a class-independent service rate.";
                return a;
            }
        std::size_t nph = 1;
        for (std::size_t k : open) {
            const lang::Distrib<T>& arr = sn.service[top.source][k];
            const std::size_t n = arr.D0.rows();
            if (n == 0 || arr.D1.rows() != n) {
                a.reason = "The priority branch of 'mfq' needs a MAP {D0,D1} arrival process for "
                           "class " + std::to_string(k + 1) + ".";
                return a;
            }
            nph *= n;
        }
        if (nph < 2) {
            a.reason = "The priority branch of 'mfq' needs at least one Markov-modulated "
                       "(multi-phase) arrival process: with exponential arrivals its fluid model "
                       "degenerates.";
            return a;
        }
        a.ok = true;
        return a;
    }
    if (open.size() != 1) {
        a.reason = "The 'mfq' method reads the arrival and service processes of one open class "
                   "and this model has " + std::to_string(open.size()) +
                   "; several classes are served only by its priority branch (distinct class "
                   "priorities).";
        return a;
    }
    a.ok = true;
    return a;
}
 
}  // namespace fluid
}  // namespace line
 
#endif  // LINE_SOLVERS_FLUID_FLUID_MFQ_ADMITS_H