🥮 mooncakes.io
    Sign in

    moon-netcalculus

    Deterministic network calculus: traffic contracts, min-plus curves, feed-forward bounds and capacity planning

    network-calculus
    min-plus
    traffic-envelope
    delay-bounds
    Download zip
    Version
    0.1.2
    License
    MIT
    Repository
    Last updated
    7 hours ago
    Downloads
    5

    No dependencies

    #moon-netcalculus

    CI mooncakes.io

    MoonBit 确定性网络演算库。把突发量与长期速率、节点服务能力、共享路径转成可复查的缓存和延迟上界；从观测记录定位契约违例，再反解满足预算的服务容量。

    核心代码由 MoonBit 实现，只依赖 moonbitlang/core。这是基于公开数学定义的独立实现，不宣称发明网络演算，也不宣称全网没有同类工具。与 MoonBit 相邻项目的关系和有限查重结论见 SOURCES.md。

    #三个不同的完整工作流

    使用者与问题输入 → 分析 → 输出可运行程序
    平台设计者：服务链需要多少容量和缓冲区流量突发/速率、各节点速率/时延、预算 → 服务串联、最坏界、容量反解 → 可行配置或明确不可行原因examples/capacity
    监控/数据管道开发者：实际流量是否满足声明的契约有序时间与工作量记录、流量契约 → 所有事件区间核验、最坏反例、固定速率下最小观测突发 → 违例记录与只对观测成立的包络examples/trace_contract
    网络/实时系统工具作者：共享链路会怎样影响目标流有向节点、严格服务曲线、各流路径 → 拓扑检查、交叉流量聚合、剩余服务、逐跳传播 → 各跳及端到端上界examples/feed_forward

    这些程序使用合成数据，不包含客户数据或实测设备性能。

    #已实现能力

    • 令牌桶到达包络与速率—时延服务曲线；全时域 backlog、虚延迟、输出突发和利用率。
    • 到达聚合、服务串联、任意复用下的剩余严格服务；速率相等和零流量边界明确处理。
    • 延迟/缓存预算判定，以及满足目标的最小单节点服务速率；超载、不可行和数值溢出分别报错。
    • 有限离散曲线的 min-plus 卷积、窗口反卷积、次可加闭包、和/最小/最大、垂直及水平偏差。
    • 流量契约的完整事件区间检查、同时刻合并突发的反例、固定速率下最小观测突发、多个窗口的经验包络。
    • 多流前馈网络分析；未知节点、重复 ID、重入和循环路由拒绝；同节点使用一致输入快照。
    • 七类 JSON 请求、未知/重复字段拒绝、大小与计算规模限制；相同 CLI 在四个后端实际运行。

    #环境与运行

    需要 MoonBit CLI，当前源码要求 moonc >= 0.10.16：已在本机用 moonc v0.10.16+b1a0e846e（moon 0.1.20261016）与官方 stable v0.10.17+d971670cd（moon 0.1.20261023）跑通下面全部命令，两版都是 check/build/test 46/46 × 四后端；v0.10.14+7d59c7ec9 会因源码使用 Int32 而编译失败（该类型在更早的编译器里不存在）。JS 后端需要 Node.js，native 后端需要系统 C 编译器。Python 3.9+ 仅用于独立验证，不参与库或 CLI 的计算。

    在项目根目录执行：

    moon version --all
moon check --deny-warn --target all
moon build --target all
moon test --deny-warn --target all
moon run examples/capacity --target wasm-gc
moon run examples/trace_contract --target wasm-gc
moon run examples/feed_forward --target wasm-gc

    容量示例第一行输出 backlog=126、delay=18；反解得到最小容量 12，将延迟上界降至 13。流量示例先报告违例，拟合突发量 6 后通过观测记录的复查。

    已发布到 Mooncakes：niuniu513-ask/moon-netcalculus@0.1.2，包页面 https://mooncakes.io/docs/niuniu513-ask/moon-netcalculus。

    moon add niuniu513-ask/moon-netcalculus@0.1.2

    在另一个包的 moon.pkg 中导入：

    import {
      "niuniu513-ask/moon-netcalculus" @nc,
    }

    fn main raise {
      let a = @nc.token_bucket(10.0, 2.0)
      let s = @nc.rate_latency(5.0, 3.0)
      let report = @nc.bounds(a, s)
      println(report.delay) // 5
    }

    也可以把本目录作为工作区模块直接引用，跳过下载。生成的 pkg.generated.mbti 列出完整公开接口；scripts/verify_consumer.py 在全新源码副本中只通过公共接口运行，不访问远程注册表。

    #JSON 命令行

    bash（含 Windows 上的 Git Bash）可以直接用单引号把整条 JSON 作为一个参数传入：

    moon run cmd/main --target native -- '{"op":"bound","arrival":{"burst":10,"rate":2},"service":{"capacity":5,"latency":3}}'

    {"ok":true,"result":{"backlog":16,"delay":5,"output":{"burst":16,"rate":2},"utilization":0.4}}

    Windows PowerShell 5.1 会剥掉单引号字符串里的内层双引号，同一条命令只会得到 malformed or too deeply nested JSON（本机未装 PowerShell 7，未验证其行为）。在 PowerShell 5.1 里请改用 cmd /c 并转义内层双引号：

    $req = '{"op":"bound","arrival":{"burst":10,"rate":2},"service":{"capacity":5,"latency":3}}'
cmd /c ('moon run cmd/main --target native -- "' + $req.Replace('"','\"') + '"')

    CLI 只接受一个 JSON 参数，不读标准输入。

    --target 可选 wasm、wasm-gc、js、native。CLI 输出单行 JSON；业务失败通过 ok:false 和 code 表达，进程退出码不代表业务成功。可运行的请求文件在 examples/requests/，完整协议见 docs/protocol.md。

    #验证与复现

    moon fmt --check
moon info
python scripts/verify.py
python scripts/verify_consumer.py

    第一份脚本对四个后端分别进行逐步流体服务器计算、曲线分解穷举、事件区间穷举和协议/拓扑错误检查。第二份脚本把必要源码复制到 _build/consumer/，生成一个独立包，通过公共接口运行；不访问远程或发布任何内容。CI 在 GitHub Actions 上执行同样的格式与接口检查、四后端检查/构建/测试、三个示例和上述两份脚本；最近一次 main 推送的运行结果见 Actions 记录。

    #数学与工程边界

    • 单位由调用者保持一致，例如 kB 与 ms；rate 和 capacity 都应为 kB/ms。输入没有隐式单位转换。
    • 全时域解析界依赖有效到达包络与服务曲线。剩余服务要求节点提供严格服务曲线，逐包延迟解释要求流内 FIFO。它们是模型条件，不是从少量观测自动证明的事实。
    • 当前是流体模型，不计包长、调度实现、协议开销、丢包、反馈控制或循环网络。不能把输出当成真实设备的无条件时延保证。
    • Curve 表示 0..H 整数网格；离散卷积不是任意连续曲线的精确卷积。窗口结果带 finite_window_only。服务窗口不足时 delay_upper_ticks 为 null，不会填入虚假的有限上界。
    • 反卷积只在已知窗口内取上确界，可能非单调；它返回 WindowDeconvolution，不能直接当作未来输出包络。解析 bounds(...).output 才是在相应模型假设下的全时域包络。
    • check_contract/fit_burst/empirical_envelope 只说明观测记录，空记录是空观察，不证明未来符合。默认绝对容差为 1e-9，可以显式设为零。
    • 使用 IEEE-754 Double，并检查非有限输入/中间结果；没有有理数或向外舍入证明。近边界规划应保留工程余量，不应把浮点输出称为形式化数值证书。
    • 规模上限：曲线 512 ticks、记录 512 条、窗口 128 个、网络 64 节点/64 流、路径 64 跳、聚合/串联 128 项；JSON 上限 1,048,576 个 UTF-16 code units、深度 32。受操作系统参数长度限制，CLI 可传入的实际请求可能更短，嵌入式 process_json 不受命令行长度限制。

    推导与算法复杂度见 docs/mathematics.md。MIT 许可证见 LICENSE，来源和非移植关系见 SOURCES.md。

    CalculusError

    source
    pub suberror CalculusError {
      Invalid(String)
      Unbounded(String)
      Infeasible(String)
      Limit(String)
      Numerical(String)
    } derive(
    Debug    )

    All rates, bursts, times and capacities use caller-selected consistent units.

    CalculusError::to_repr

    source

    Admission

    source
    pub(all) struct Admission {
      admitted : Bool
      delay_ok : Bool
      buffer_ok : Bool
      metrics : AnalyticBounds
    } derive(ToJson, 
    Debug    )

    Admission::to_json

    source
    fn Admission::to_json(Admission) -> Json

    Admission::to_repr

    source

    AnalyticBounds

    source
    pub(all) struct AnalyticBounds {
      backlog : Double
      delay : Double
      output : TokenBucket
      utilization : Double
    } derive(ToJson, 
    Debug    )

    AnalyticBounds::to_json

    source

    AnalyticBounds::to_repr

    source

    BurstFit

    source
    pub(all) struct BurstFit {
      envelope : TokenBucket
      witness : ContractWitness?
      scope : String
    } derive(ToJson, 
    Debug    )

    BurstFit::to_json

    source
    fn BurstFit::to_json(BurstFit) -> Json

    BurstFit::to_repr

    source

    CapacityPlan

    source
    pub(all) struct CapacityPlan {
      minimum_capacity : Double
      necessary_buffer : Double
      delay_limit : Double
      latency : Double
    } derive(ToJson, 
    Debug    )

    CapacityPlan::to_json

    source

    CapacityPlan::to_repr

    source

    ContractReport

    source
    pub(all) struct ContractReport {
      conforms : Bool
      violating_intervals : Int
      worst : ContractWitness?
      checked_intervals : Int
      events : Int
      tolerance : Double
      scope : String
    } derive(ToJson, 
    Debug    )

    ContractReport::to_json

    source

    ContractReport::to_repr

    source

    ContractWitness

    source
    pub(all) struct ContractWitness {
      first : Int
      last : Int
      start : Double
      end : Double
      amount : Double
      allowance : Double
      excess : Double
    } derive(ToJson, 
    Debug    )

    ContractWitness::to_json

    source

    ContractWitness::to_repr

    source

    Curve

    source
    pub struct Curve {
      values : Array[Double]
    } derive(
    Debug    )

    A nondecreasing, finite, discrete-time curve on integers 0..H. Construction copies data, as does samples(), so callers cannot mutate it.

    Curve::horizon

    source
    fn Curve::horizon(self : Curve) -> Int

    Curve::sample

    source
    fn Curve::sample(self : Curve, tick : Int) -> Double raise CalculusError

    Curve::samples

    source
    fn Curve::samples(self : Curve) -> Array[Double]

    Curve::to_repr

    source

    EnvelopeSample

    source
    pub(all) struct EnvelopeSample {
      window : Double
      amount : Double
      first : Int?
      last : Int?
    } derive(ToJson, 
    Debug    )

    EnvelopeSample::to_json

    source

    EnvelopeSample::to_repr

    source

    Flow

    source
    pub(all) struct Flow {
      id : String
      arrival : TokenBucket
      route : Array[String]
    } derive(ToJson, 
    Debug    )

    Flow::to_json

    source
    fn Flow::to_json(Flow) -> Json

    Flow::to_repr

    source

    FlowBound

    source
    pub(all) struct FlowBound {
      id : String
      hops : Array[HopBound]
      end_to_end : AnalyticBounds
      sum_hop_delay : Double
      maximum_hop_backlog : Double
      exit_envelope : TokenBucket
    } derive(ToJson, 
    Debug    )

    FlowBound::to_json

    source
    fn FlowBound::to_json(FlowBound) -> Json

    FlowBound::to_repr

    source

    HopBound

    source
    pub(all) struct HopBound {
      server : String
      input : TokenBucket
      cross : TokenBucket
      service : RateLatency
      metrics : AnalyticBounds
    } derive(ToJson, 
    Debug    )

    HopBound::to_json

    source
    fn HopBound::to_json(HopBound) -> Json

    HopBound::to_repr

    source

    NetworkReport

    source
    pub(all) struct NetworkReport {
      server_order : Array[String]
      flows : Array[FlowBound]
      analysis_method : String
      assumptions : Array[String]
    } derive(ToJson, 
    Debug    )

    NetworkReport::to_json

    source

    NetworkReport::to_repr

    source

    RateLatency

    source
    pub(all) struct RateLatency {
      capacity : Double
      latency : Double
    } derive(Eq, ToJson, 
    Debug    )

    RateLatency::at

    source
    fn RateLatency::at(self : RateLatency, t : Double) -> Double raise CalculusError

    RateLatency::equal

    source
    fn RateLatency::equal(RateLatency, RateLatency) -> Bool

    RateLatency::not_equal

    source
    fn RateLatency::not_equal(x : RateLatency, y : RateLatency) -> Bool

    RateLatency::to_json

    source
    fn RateLatency::to_json(RateLatency) -> Json

    RateLatency::to_repr

    source

    Server

    source
    pub(all) struct Server {
      id : String
      service : RateLatency
    } derive(ToJson, 
    Debug    )

    Server::to_json

    source
    fn Server::to_json(Server) -> Json

    Server::to_repr

    source

    TokenBucket

    source
    pub(all) struct TokenBucket {
      burst : Double
      rate : Double
    } derive(Eq, ToJson, 
    Debug    )

    TokenBucket::at

    source
    fn TokenBucket::at(self : TokenBucket, t : Double) -> Double raise CalculusError

    α(0)=0; α(t)=b+rt for t>0, including its right-hand jump b.

    TokenBucket::equal

    source
    fn TokenBucket::equal(TokenBucket, TokenBucket) -> Bool

    TokenBucket::not_equal

    source
    fn TokenBucket::not_equal(x : TokenBucket, y : TokenBucket) -> Bool

    TokenBucket::to_json

    source
    fn TokenBucket::to_json(TokenBucket) -> Json

    TokenBucket::to_repr

    source

    TrafficEvent

    source
    pub(all) struct TrafficEvent {
      at : Double
      amount : Double
    } derive(ToJson, 
    Debug    )

    TrafficEvent::to_json

    source

    TrafficEvent::to_repr

    source

    WindowBounds

    source
    pub(all) struct WindowBounds {
      backlog : Double
      backlog_tick : Int
      resolved_delay_max_ticks : Int
      delay_upper_ticks : Int?
      censored_samples : Int
      horizon : Int
      scope : String
    } derive(
    Debug    )

    WindowBounds::to_json

    source
    fn WindowBounds::to_json(self : WindowBounds) -> Json

    WindowBounds::to_repr

    source

    WindowDeconvolution

    source
    pub(all) struct WindowDeconvolution {
      values : Array[Double]
      maximizing_shift : Array[Int]
      horizon : Int
      scope : String
    } derive(ToJson, 
    Debug    )

    WindowDeconvolution::to_json

    source

    WindowDeconvolution::to_repr

    source

    admit

    source
    fn admit(a : TokenBucket, s : RateLatency, delay_limit : Double, buffer_limit : Double) -> Admission raise CalculusError

    aggregate

    source
    fn aggregate(arrivals : Array[TokenBucket]) -> TokenBucket raise CalculusError

    Sum of arrival envelopes; no statistical independence is assumed.

    analyze_network

    source
    fn analyze_network(servers : Array[Server], flows : Array[Flow]) -> NetworkReport raise CalculusError

    Topological feed-forward analysis using aggregate cross-traffic envelopes, strict blind-multiplexing leftovers and conservative per-hop propagation. Delays describe virtual delay, or per-flow FIFO delay. No routing is chosen.

    bounds

    source

    Infinite-horizon fluid bounds, conditional on an arrival envelope and a deterministic service curve. A delay interpretation requires FIFO. Equality r=R is stable for these deterministic envelopes.

    check_contract

    source
    fn check_contract(events : Array[TrafficEvent], contract : TokenBucket, tolerance? : Double) -> ContractReport raise CalculusError

    Observed packet/batch envelope: sum(i..j) <= b+r*(t_j-t_i). These closed event spans deliberately account for an instantaneous burst. Passing this finite trace does not prove a future traffic guarantee.

    convolve

    source
    fn convolve(a : Curve, b : Curve) -> Curve raise CalculusError

    Exact discrete min-plus convolution on the shared finite prefix.

    curve

    source
    fn curve(values : Array[Double]) -> Curve raise CalculusError

    curve_max

    source
    fn curve_max(a : Curve, b : Curve) -> Curve raise CalculusError

    curve_min

    source
    fn curve_min(a : Curve, b : Curve) -> Curve raise CalculusError

    curve_sum

    source
    fn curve_sum(a : Curve, b : Curve) -> Curve raise CalculusError

    empirical_envelope

    source
    fn empirical_envelope(events : Array[TrafficEvent], windows : Array[Double]) -> Array[EnvelopeSample] raise CalculusError

    Empirical maximum amount over all closed event spans of length <= window. In particular window=0 includes all batches with the same timestamp.

    fit_burst

    source
    fn fit_burst(events : Array[TrafficEvent], rate : Double) -> BurstFit raise CalculusError

    Minimum burst for a caller-specified rate on the OBSERVED records. The caller supplies rate; this is not an asymptotic-rate estimator.

    leftover

    source
    fn leftover(s : RateLatency, cross : TokenBucket) -> RateLatency raise CalculusError

    Blind/arbitrary multiplexing leftover. Requires a STRICT server service curve and a valid aggregate envelope for all cross traffic at this node.

    process_json

    source
    fn process_json(input : String) -> String

    Machine-readable response: {ok:true,result:...} or {ok:false,code:invalid|unbounded|infeasible|limit|numerical,message:...}. JSON is bounded to 1 MiB UTF-16 units and depth 32; duplicate fields fail.

    rate_latency

    source
    fn rate_latency(capacity : Double, latency : Double) -> RateLatency raise CalculusError

    required_capacity

    source
    fn required_capacity(a : TokenBucket, latency : Double, delay_limit : Double, buffer_limit : Double) -> CapacityPlan raise CalculusError

    Analytic inverse for a single fluid server. A zero minimum describes idle traffic, not a constructible positive-rate RateLatency server.

    sample_arrival

    source
    fn sample_arrival(a : TokenBucket, horizon : Int, step : Double) -> Curve raise CalculusError

    sample_service

    source
    fn sample_service(s : RateLatency, horizon : Int, step : Double) -> Curve raise CalculusError

    subadditive_closure

    source
    fn subadditive_closure(f : Curve) -> Curve raise CalculusError

    Subadditive closure on a discrete prefix. Unit is f*(0)=0.

    tandem

    source
    fn tandem(services : Array[RateLatency]) -> RateLatency raise CalculusError

    Convolution of rate-latency service curves: minimum rate, summed latency.

    token_bucket

    source
    fn token_bucket(burst : Double, rate : Double) -> TokenBucket raise CalculusError

    window_bounds

    source
    fn window_bounds(a : Curve, s : Curve) -> WindowBounds raise CalculusError

    Deviations on a finite discrete prefix, not a proof about future traffic. A null delay_upper_ticks means the service window is too short.

    window_deconvolve

    source
    fn window_deconvolve(f : Curve, g : Curve) -> WindowDeconvolution raise CalculusError

    Truncated sup_{0<=u<=H-t} (f(t+u)-g(u)). It may be nonmonotone; it is NOT an infinite-horizon output envelope and is not a Curve.

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io