sleela_bestof.c
impl/core/sleela_bestof.c · 383 line(s) · c
/* ==========================================================================
* sleela_bestof.c -- Best-of selection engine (transparent, honest).
*
* Scoring is deliberately simple and inspectable. For each candidate we keep a
* running measured summary (mean RTT, jitter, loss) and derive a carrier
* certainty in [0..1000] permille the same spirit as QOS.md: a clean, on-time,
* low-jitter reply raises certainty; a loss or a large deviation lowers it.
*
* The final score blends four weighted, normalized terms:
* data : lower mean RTT + lower loss + lower jitter is better
* decisions : higher carrier certainty is better
* costs : lower cost is better (subtracted)
* versions : higher version fitness (>= min_version) is better
* A candidate with no measurements is "unproven": it scores from its static
* fitness only, with a certainty of 0, so a measured-good route beats an
* unmeasured one. Nothing is assumed good.
* ========================================================================== */
#include "sleela_bestof.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SL_BESTOF_NAME 64
#define SL_BESTOF_ROUTE 192
/* Reference ceilings used only to normalize measured values into [0..1000].
* They are scaling constants, not guarantees or limits on the transport. */
#define SL_BESTOF_RTT_CEIL_US 1000000L /* 1s: RTT at/above this scores ~0 */
#define SL_BESTOF_JITTER_CEIL_US 500000L /* 0.5s jitter reference */
#define SL_BESTOF_SCORE_MIN (-1000000000LL)
typedef struct {
int used;
char name[SL_BESTOF_NAME];
char route[SL_BESTOF_ROUTE];
int timeout_ms, payload_len, min_gap_ms;
int flags, version, cost, replays;
/* internet QoS architecture (SL_BESTOF_ARCH_*) + its parameter + state */
int arch, arch_param, arch_state;
/* measured accumulators */
int64_t sent, received;
int64_t sum_us; /* sum of matched RTTs (us) */
int64_t last_us; /* previous matched RTT for jitter */
int64_t sum_jitter_us; /* sum of |rtt - last| across matches */
int64_t jitter_count;
} SLBestCandidate;
struct SLBestOf {
int w_data, w_decisions, w_costs, w_versions, w_architecture;
int min_version;
int cost_budget; /* 0 == unbounded */
SLBestCandidate c[SL_BESTOF_CANDIDATES];
int ncandidates;
};
SLBestOf* slbestof_new(void) {
SLBestOf* b = (SLBestOf*)calloc(1, sizeof(SLBestOf));
if (!b) return NULL;
b->w_data = 45;
b->w_decisions = 25;
b->w_costs = 10;
b->w_versions = 5;
b->w_architecture = 15;
b->min_version = 0;
b->cost_budget = 0;
return b;
}
int slbestof_weight(SLBestOf* b, int axis, int weight) {
if (!b) return -1;
if (weight < 0) weight = 0;
if (weight > 100) weight = 100;
switch (axis) {
case SL_BESTOF_AXIS_DATA: b->w_data = weight; return 0;
case SL_BESTOF_AXIS_DECISIONS: b->w_decisions = weight; return 0;
case SL_BESTOF_AXIS_COSTS: b->w_costs = weight; return 0;
case SL_BESTOF_AXIS_VERSIONS: b->w_versions = weight; return 0;
case SL_BESTOF_AXIS_ARCHITECTURE: b->w_architecture = weight; return 0;
default: return -1;
}
}
void slbestof_min_version(SLBestOf* b, int min_version) {
if (b) b->min_version = min_version;
}
void slbestof_cost_budget(SLBestOf* b, int cost_budget) {
if (b) b->cost_budget = cost_budget < 0 ? 0 : cost_budget;
}
int slbestof_add_candidate(SLBestOf* b, const char* name, const char* route,
int timeout_ms, int payload_len, int min_gap_ms,
int flags, int version, int cost, int replays) {
if (!b || b->ncandidates >= SL_BESTOF_CANDIDATES) return -1;
SLBestCandidate* cn = &b->c[b->ncandidates];
memset(cn, 0, sizeof(*cn));
cn->used = 1;
snprintf(cn->name, sizeof(cn->name), "%s", name ? name : "candidate");
snprintf(cn->route, sizeof(cn->route), "%s", route ? route : "");
cn->timeout_ms = timeout_ms;
cn->payload_len = payload_len;
cn->min_gap_ms = min_gap_ms;
cn->flags = flags;
cn->version = version;
cn->cost = cost < 0 ? 0 : cost;
cn->replays = replays < 1 ? 1 : replays;
cn->last_us = -1;
/* Default architecture: best-effort, requested (memset already zeroed). */
cn->arch = SL_BESTOF_ARCH_BESTEFFORT;
cn->arch_param = 0;
cn->arch_state = SL_BESTOF_ARCH_REQUESTED;
return b->ncandidates++;
}
static int valid_idx(const SLBestOf* b, int idx) {
return b && idx >= 0 && idx < b->ncandidates && b->c[idx].used;
}
int slbestof_candidate_arch(SLBestOf* b, int idx, int architecture,
int arch_param, int realized) {
if (!valid_idx(b, idx)) return -1;
if (architecture < SL_BESTOF_ARCH_BESTEFFORT || architecture > SL_BESTOF_ARCH_MPLS)
return -1;
SLBestCandidate* cn = &b->c[idx];
cn->arch = architecture;
cn->arch_param = arch_param;
cn->arch_state = (realized < SL_BESTOF_ARCH_REQUESTED || realized > SL_BESTOF_ARCH_DENIED)
? SL_BESTOF_ARCH_REQUESTED : realized;
return 0;
}
int slbestof_arch_realized(SLBestOf* b, int idx, int realized) {
if (!valid_idx(b, idx)) return -1;
if (realized < SL_BESTOF_ARCH_REQUESTED || realized > SL_BESTOF_ARCH_DENIED) return -1;
b->c[idx].arch_state = realized;
return 0;
}
int slbestof_arch(const SLBestOf* b, int idx) {
return valid_idx(b, idx) ? b->c[idx].arch : -1;
}
int slbestof_arch_param(const SLBestOf* b, int idx) {
return valid_idx(b, idx) ? b->c[idx].arch_param : -1;
}
int slbestof_arch_state(const SLBestOf* b, int idx) {
return valid_idx(b, idx) ? b->c[idx].arch_state : -1;
}
/* The architecture-fitness term in [0..1000]: how much the candidate's QoS
* architecture, as actually realized, should raise its score. Best-effort is a
* neutral baseline; a REALIZED DiffServ/IntServ/MPLS path earns a bonus scaled
* by how strong that architecture's guarantee is; a merely REQUESTED path earns
* a small credit; a DENIED reservation is penalized below best-effort. Honest:
* the bonus is gated on realization, never on the mere request. */
static int64_t arch_fitness(const SLBestCandidate* cn) {
int64_t base;
switch (cn->arch) {
case SL_BESTOF_ARCH_INTSERV: base = 1000; break; /* end-to-end reservation */
case SL_BESTOF_ARCH_MPLS: base = 800; break; /* traffic-engineered path */
case SL_BESTOF_ARCH_DIFFSERV:base = 600; break; /* per-hop class marking */
default: base = 400; break; /* best-effort baseline */
}
if (cn->arch == SL_BESTOF_ARCH_BESTEFFORT) return base; /* state N/A */
switch (cn->arch_state) {
case SL_BESTOF_ARCH_REALIZED: return base; /* full credit */
case SL_BESTOF_ARCH_DENIED: return 200; /* below best-effort */
default: /* REQUESTED */ return 400 + (base - 400) / 4; /* partial */
}
}
int slbestof_record(SLBestOf* b, int idx, int64_t rtt_us) {
if (!valid_idx(b, idx)) return -1;
SLBestCandidate* cn = &b->c[idx];
cn->sent++;
if (rtt_us < 0) return 0; /* honest loss: counted, no RTT */
cn->received++;
cn->sum_us += rtt_us;
if (cn->last_us >= 0) {
int64_t d = rtt_us - cn->last_us;
if (d < 0) d = -d;
cn->sum_jitter_us += d;
cn->jitter_count++;
}
cn->last_us = rtt_us;
return 0;
}
int64_t slbestof_mean_us(const SLBestOf* b, int idx) {
if (!valid_idx(b, idx)) return -1;
const SLBestCandidate* cn = &b->c[idx];
return cn->received > 0 ? cn->sum_us / cn->received : -1;
}
int64_t slbestof_loss_permille(const SLBestOf* b, int idx) {
if (!valid_idx(b, idx)) return -1;
const SLBestCandidate* cn = &b->c[idx];
if (cn->sent == 0) return 0;
int64_t lost = cn->sent - cn->received;
if (lost < 0) lost = 0;
return (lost * 1000) / cn->sent;
}
int64_t slbestof_jitter_us(const SLBestOf* b, int idx) {
if (!valid_idx(b, idx)) return -1;
const SLBestCandidate* cn = &b->c[idx];
return cn->jitter_count > 0 ? cn->sum_jitter_us / cn->jitter_count : 0;
}
/* Certainty in [0..1000]: driven by delivered fraction, dampened by jitter.
* No measurement -> 0 (unproven), consistent with "never assumed good". */
int slbestof_certainty_permille(const SLBestOf* b, int idx) {
if (!valid_idx(b, idx)) return 0;
const SLBestCandidate* cn = &b->c[idx];
if (cn->sent == 0) return 0;
int64_t delivered = (cn->received * 1000) / cn->sent; /* 0..1000 */
int64_t jitter = slbestof_jitter_us(b, idx);
/* Reduce certainty by up to ~300 permille as jitter approaches the ceiling. */
int64_t jitter_penalty = (jitter * 300) / SL_BESTOF_JITTER_CEIL_US;
if (jitter_penalty > 300) jitter_penalty = 300;
int64_t c = delivered - jitter_penalty;
if (c < 0) c = 0;
if (c > 1000) c = 1000;
return (int)c;
}
/* Normalize a measured RTT to a [0..1000] "goodness" (lower RTT -> higher). */
static int64_t rtt_goodness(int64_t mean_us) {
if (mean_us < 0) return 0; /* unmeasured */
if (mean_us >= SL_BESTOF_RTT_CEIL_US) return 0;
return 1000 - (mean_us * 1000) / SL_BESTOF_RTT_CEIL_US;
}
int64_t slbestof_score(SLBestOf* b, int idx) {
if (!valid_idx(b, idx)) return SL_BESTOF_SCORE_MIN;
const SLBestCandidate* cn = &b->c[idx];
int64_t mean = slbestof_mean_us(b, idx);
int64_t loss = slbestof_loss_permille(b, idx);
int64_t data_term = 0;
if (cn->received > 0) {
int64_t good = rtt_goodness(mean); /* 0..1000 */
int64_t deliver = 1000 - loss; /* 0..1000 */
data_term = (good + deliver) / 2; /* 0..1000 */
} /* else unproven: data_term stays 0 */
int64_t decisions_term = slbestof_certainty_permille(b, idx); /* 0..1000 */
/* Cost term: 0 cost -> 1000, rising cost -> lower. Normalized against the
* budget when set, else against a soft reference of 1000. */
int64_t ref = b->cost_budget > 0 ? b->cost_budget : 1000;
int64_t cost_norm = (cn->cost * 1000) / (ref > 0 ? ref : 1000);
if (cost_norm > 1000) cost_norm = 1000;
int64_t costs_term = 1000 - cost_norm; /* 0..1000 (higher=cheaper) */
/* Version fitness: at/above min_version scores by how far above; a small
* bonus per version over the floor, capped. */
int64_t versions_term = 0;
if (cn->version >= b->min_version) {
int64_t over = cn->version - b->min_version;
versions_term = 500 + (over * 100);
if (versions_term > 1000) versions_term = 1000;
}
/* Architecture fitness: how the candidate's realized QoS architecture
* (DiffServ/IntServ/MPLS/best-effort) should raise its score. */
int64_t architecture_term = arch_fitness(cn);
return (int64_t)b->w_data * data_term
+ (int64_t)b->w_decisions * decisions_term
+ (int64_t)b->w_costs * costs_term
+ (int64_t)b->w_versions * versions_term
+ (int64_t)b->w_architecture * architecture_term;
}
int slbestof_best(SLBestOf* b) {
if (!b) return -1;
int best = -1;
int64_t best_score = SL_BESTOF_SCORE_MIN;
for (int i = 0; i < b->ncandidates; i++) {
const SLBestCandidate* cn = &b->c[i];
if (!cn->used) continue;
if (cn->version < b->min_version) continue; /* version gate */
if (b->cost_budget > 0 && cn->cost > b->cost_budget) continue; /* budget */
int64_t s = slbestof_score(b, i);
if (s > best_score) { best_score = s; best = i; }
}
return best;
}
static void flags_string(int flags, char* out, size_t cap) {
out[0] = 0;
size_t n = 0;
const struct { int bit; const char* name; } names[] = {
{SL_BESTOF_FLAG_CRYPTO, "crypto"}, {SL_BESTOF_FLAG_RETRY, "retry"},
{SL_BESTOF_FLAG_PACING, "pacing"}, {SL_BESTOF_FLAG_DSCP, "dscp"},
{SL_BESTOF_FLAG_REPLAY, "replay"},
};
for (size_t i = 0; i < sizeof(names)/sizeof(names[0]); i++) {
if (flags & names[i].bit) {
int w = snprintf(out + n, cap - n, "%s%s", n ? "," : "", names[i].name);
if (w > 0) n += (size_t)w;
if (n >= cap) break;
}
}
if (n == 0) snprintf(out, cap, "none");
}
/* Render a candidate's architecture as "arch(param):state", e.g.
* "diffserv(46):realized", "intserv(2000):requested", "mpls(17):realized",
* or "best-effort". */
static void arch_string(const SLBestCandidate* cn, char* out, size_t cap) {
const char* a;
const char* param_label;
switch (cn->arch) {
case SL_BESTOF_ARCH_DIFFSERV: a = "diffserv"; param_label = "dscp"; break;
case SL_BESTOF_ARCH_INTSERV: a = "intserv"; param_label = "kbps"; break;
case SL_BESTOF_ARCH_MPLS: a = "mpls"; param_label = "label"; break;
default: snprintf(out, cap, "best-effort"); return;
}
const char* st = cn->arch_state == SL_BESTOF_ARCH_REALIZED ? "realized"
: cn->arch_state == SL_BESTOF_ARCH_DENIED ? "denied"
: "requested";
snprintf(out, cap, "%s(%s=%d):%s", a, param_label, cn->arch_param, st);
}
int slbestof_choice(SLBestOf* b, char* out, size_t cap) {
if (!out || cap == 0) return 0;
out[0] = 0;
int idx = slbestof_best(b);
if (idx < 0) { snprintf(out, cap, "(no qualifying candidate)"); return (int)strlen(out); }
const SLBestCandidate* cn = &b->c[idx];
char fl[64], ar[64];
flags_string(cn->flags, fl, sizeof(fl));
arch_string(cn, ar, sizeof(ar));
int w = snprintf(out, cap,
"%s %s arch=%s timeout=%dms payload=%dB gap=%dms flags=[%s] version=%d replays=%d "
"mean=%lldus loss=%lldpermille certainty=%d score=%lld",
cn->name, cn->route, ar, cn->timeout_ms, cn->payload_len, cn->min_gap_ms, fl,
cn->version, cn->replays,
(long long)slbestof_mean_us(b, idx),
(long long)slbestof_loss_permille(b, idx),
slbestof_certainty_permille(b, idx),
(long long)slbestof_score(b, idx));
if (w < 0) { out[0] = 0; return 0; }
return ((size_t)w < cap) ? w : (int)(cap - 1);
}
int slbestof_report(SLBestOf* b, char* out, size_t cap) {
if (!out || cap == 0) return 0;
out[0] = 0;
size_t n = 0;
int w = snprintf(out, cap,
"best-of weights[data=%d decisions=%d costs=%d versions=%d architecture=%d] "
"min-version=%d cost-budget=%d candidates=%d\n",
b ? b->w_data : 0, b ? b->w_decisions : 0, b ? b->w_costs : 0,
b ? b->w_versions : 0, b ? b->w_architecture : 0,
b ? b->min_version : 0, b ? b->cost_budget : 0,
b ? b->ncandidates : 0);
if (w > 0) n += (size_t)w;
if (!b) return (int)n;
int best = slbestof_best(b);
for (int i = 0; i < b->ncandidates && n < cap; i++) {
const SLBestCandidate* cn = &b->c[i];
if (!cn->used) continue;
char fl[64], ar[64];
flags_string(cn->flags, fl, sizeof(fl));
arch_string(cn, ar, sizeof(ar));
w = snprintf(out + n, cap - n,
" %c %s %s arch=%s v%d cost=%d flags=[%s] mean=%lldus loss=%lldpermille "
"certainty=%d score=%lld\n",
i == best ? '*' : ' ', cn->name, cn->route, ar, cn->version, cn->cost, fl,
(long long)slbestof_mean_us(b, i),
(long long)slbestof_loss_permille(b, i),
slbestof_certainty_permille(b, i),
(long long)slbestof_score(b, i));
if (w > 0) n += (size_t)w;
}
return ((size_t)n < cap) ? (int)n : (int)(cap - 1);
}
void slbestof_close(SLBestOf* b) {
free(b);
}