lossn_links.h

Go to the documentation of this file.

#ifndef LINE_API_LOSSN_LOSSN_LINKS_H
#define LINE_API_LOSSN_LOSSN_LINKS_H
 
/**
 * @file lossn_links.h
 * @ingroup api_lossn
 * @brief Per-link blocking and occupancy of a loss network.
 *
 * Templated port of matlab/src/api/lossn/lossn_links.m.
 *
 * Returns, for every link j and route r with A(j,r) > 0, the probability that
 * link j alone cannot accept a route-r call, E(j,r) = P(fewer than A(j,r) free
 * units on link j), together with the mean occupancy of each link,
 * Occ_j = sum_r A(j,r) E[n_r]. Under the product form the link blocking is a
 * ratio of normalizing constants, E(j,r) = 1 - G(C - A(j,r) e_j)/G(C), which
 * the exact methods evaluate directly. The route loss satisfies
 * Loss_r >= max_j E(j,r), with equality only when no two links block
 * route r in different states.
 *
 * Methods:
 *  - 'exact' (also 'manjunath', 'ms'): one Manjunath-Sikdar evaluation per
 *    distinct (link, requirement) pair; needs integral A and C.
 *  - 'rec': as exact with MDD-rec, also for fractional A and C.
 *  - 'erlangfp': the Erlang fixed-point blocking matrix (independence
 *    approximation).
 *  - 'asy': the Kelly limit, E(j,r) = 1 - (1-a_j)^A(j,r).
 *  - 'mci': the importance-sampling estimator of lossn_mci (the options carry
 *    the sample count and the seed).
 *
 * ARITHMETIC. The fixed point, the fluid limit and the Monte Carlo estimator
 * are all transcendental, so the header is gated on
 * num_traits<T>::has_transcendental.
 *
 * Reference: K. W. Ross, "Multiservice Loss Models for Broadband
 * Telecommunication Networks", Springer, 1995, Sec. 5.1-5.3.
 *
 * @see lossn_revsens, lossn_mci, lossn_asy, lossn_erlangfp
 */
 
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
 
#include "line/api/lossn/lossn_asy.h"
#include "line/api/lossn/lossn_erlangfp.h"
#include "line/api/lossn/lossn_manjunath.h"
#include "line/api/lossn/lossn_mci.h"
#include "line/api/lossn/lossn_rec.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
 
namespace line {
namespace lossn {
 
/** Result of lossn_links. */
template <class T>
struct LossnLinksResult {
    Matrix<T> E;          ///< (J x R) blocking of route r by link j alone; 0 where A(j,r) = 0
    std::vector<T> Occ;   ///< (J) mean number of busy units on link j
    std::vector<T> Loss;  ///< (R) route loss probability, as the chosen method gives it
    std::vector<T> QLen;  ///< (R) mean number of route-r calls in progress
};
 
namespace detail {
 
/** Lowercased copy, as MATLAB's lower(method). */
inline std::string lossn_lower(std::string s) {
    for (char& c : s) c = static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
    return s;
}
 
/** Distinct positive entries of row j of A, sorted ascending (MATLAB unique). */
template <class T>
std::vector<T> lossn_row_levels(const Matrix<T>& A, std::size_t j) {
    const T zero = num_traits<T>::from_int(0);
    std::vector<T> v;
    for (std::size_t r = 0; r < A.cols(); ++r)
        if (A(j, r) > zero) v.push_back(A(j, r));
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    return v;
}
 
}  // namespace detail
 
/**
 * @brief Per-link blocking and occupancy of a loss network.
 *
 * @param nu     offered load of route r (R)
 * @param A      capacity requirement of link j for route r (J x R)
 * @param C      capacity of link j (J)
 * @param method 'exact' (default), 'rec', 'erlangfp', 'asy' or 'mci'
 * @param mciopt options for 'mci' (samples, alpha, gamma)
 * @param seed   seed of the 'mci' generator
 */
template <class T>
LossnLinksResult<T> lossn_links(const std::vector<T>& nu, const Matrix<T>& A, const std::vector<T>& C,
                                const std::string& method = "exact",
                                const LossnMciOptions<T>& mciopt = LossnMciOptions<T>(),
                                std::uint64_t seed = 0) {
    static_assert(num_traits<T>::has_transcendental,
                  "lossn_links requires transcendental arithmetic");
    using std::expm1;
    using std::log1p;
    const std::size_t R = nu.size();
    const std::size_t J = C.size();
    if (A.rows() != J || A.cols() != R)
        throw InputError("lossn_links: A must be " + std::to_string(J) + "x" + std::to_string(R) +
                         " (J x R).");
    const T zero = num_traits<T>::from_int(0), one = num_traits<T>::from_int(1);
    const std::string m = detail::lossn_lower(method.empty() ? std::string("exact") : method);
 
    LossnLinksResult<T> out;
    out.E = Matrix<T>(J, R, zero);
    if (m == "exact" || m == "manjunath" || m == "ms" || m == "rec") {
        const bool rec = (m == "rec");
        // lG of the network at capacity Cv; the exact G under rec
        T G = zero;
        double lG = 0.0;
        if (rec) {
            const LossnRecResult<T> r0 = lossn_rec(nu, A, C);
            out.QLen = r0.QLen;
            out.Loss = r0.Loss;
            G = r0.G;
            lG = r0.lG;
        } else {
            const LossnManjunathResult<T> r0 = lossn_manjunath(nu, A, C);
            out.QLen = r0.QLen;
            out.Loss = r0.Loss;
            lG = r0.lG;
        }
        for (std::size_t j = 0; j < J; ++j) {
            for (const T& a : detail::lossn_row_levels(A, j)) {
                T e = one;
                if (!(T(C[j] - a) < zero)) {
                    std::vector<T> Cs = C;
                    Cs[j] = T(C[j] - a);
                    if (rec) {
                        // 1 - G(Cs)/G(C), which is -expm1(lGs - lG) without the
                        // round trip through a double logarithm
                        e = T(one - lossn_rec(nu, A, Cs).G / G);
                    } else {
                        const double lGs = lossn_manjunath(nu, A, Cs).lG;
                        e = num_traits<T>::from_double(-std::expm1(lGs - lG));
                    }
                    if (e < zero) e = zero;
                    if (e > one) e = one;
                }
                for (std::size_t r = 0; r < R; ++r)
                    if (A(j, r) == a) out.E(j, r) = e;
            }
        }
    } else if (m == "erlangfp") {
        const ErlangFpResult<T> r0 = lossn_erlangfp(nu, A, C);
        out.QLen = r0.QLen;
        out.Loss = r0.Loss;
        out.E = r0.E;
    } else if (m == "asy") {
        const LossnAsyResult<T> r0 = lossn_asy(nu, A, C);
        out.QLen = r0.QLen;
        out.Loss = r0.Loss;
        for (std::size_t j = 0; j < J; ++j)
            for (std::size_t r = 0; r < R; ++r)
                if (A(j, r) > zero)
                    out.E(j, r) = r0.a[j] >= one ? one : T(-expm1(T(A(j, r) * log1p(T(-r0.a[j])))));
    } else if (m == "mci") {
        const LossnMciResult<T> r0 = lossn_mci(nu, A, C, mciopt, seed);
        out.QLen = r0.QLen;
        out.Loss = r0.Loss;
        out.E = r0.linkLossPoint;
    } else {
        throw InputError("lossn_links: Unknown method '" + method +
                         "'; use exact, rec, erlangfp, asy or mci.");
    }
    out.Occ.assign(J, zero);
    for (std::size_t j = 0; j < J; ++j)
        for (std::size_t r = 0; r < R; ++r) out.Occ[j] += T(A(j, r) * out.QLen[r]);
    return out;
}
 
}  // namespace lossn
}  // namespace line
 
#endif  // LINE_API_LOSSN_LOSSN_LINKS_H