---
title: 排队网络与瓶颈
url: https://doc.liz6.com/theory/03-queueing-theory/09-networks-and-bottlenecks
locale: zh
area: theory
tags:
- 排队论
- 基础理论
date: 2026-09-10
modified: 2026-09-10
description: 一个请求常常依次访问缓存、应用和数据库，还可能循环重试或扇出多个子请求。排队网络把局部队列连起来，让“外部每秒多少请求”转换成“每个资源每秒多少工作”。
---
# 排队网络与瓶颈
一个请求常常依次访问缓存、应用和数据库，还可能循环重试或扇出多个子请求。排队网络把局部队列连起来，让“外部每秒多少请求”转换成“每个资源每秒多少工作”。
## 先求访问流量，再求等待
外部到达节点 $j$ 的速率为 $\gamma_j$，一次节点 $i$ 完成后转到 $j$ 的概率为 $p_{ij}$。稳态流量守恒给出：
$$\lambda_j=\gamma_j+\sum_i\lambda_i p_{ij}.$$
这组流量方程来自路由记账，不自动赋予各节点 M/M/1 分布。开放 Jackson 网络还要求外部独立 Poisson 到达、节点指数服务、适当独立的无记忆路由、无限等待空间以及各节点负荷稳定等条件。内部过程也不能随意视为相互独立的请求样本。
这里使用的关键是 Jackson 的稳态乘积形式：对本章的单服务台节点，
$$P(N_1=n_1,\ldots,N_k=n_k)=\prod_{j=1}^k(1-\rho_j)\rho_j^{n_j},\qquad \rho_j=\lambda_j/\mu_j<1.$$
这是同一时刻各节点占用数的独立性，不是沿路径各次等待独立。有返回环时，节点内部到达甚至不必是 Poisson；仍可由上述边际分布求平均占用，再求网络平均时间。机制与条件见 [MIT Jackson 网络讲义](https://ocw.mit.edu/courses/6-263j-data-communication-networks-fall-2002/42cb7759de031ae20aae04632773fef4_Lecture7.pdf)。
实验中每次经过节点 1、2 后，以概率 $p$ 返回节点 1，否则离开。一次业务平均各访问 $V=1/(1-p)$ 次，节点流量都是 $\lambda_0V$。两台服务率分别为 100/s 和 250/s，稳定要求 $\lambda_0V<100$。
$$E[T_{\mathrm{network}}]=V\left(\frac1{100-\lambda_0V}+\frac1{250-\lambda_0V}\right).$$
该均值可由每节点平均人数相加再用网络 Little 定律得到，不要求沿请求路径的各次时延独立。默认 $\lambda_0=40$/s、$p=0.2$，$V=1.25$、内部各 50/s、总均值 31.25 ms。
**排队网络与瓶颈 · 实验**
外部Poisson到达节点1，随后到节点2；节点2以概率p返回1，否则离开。两节点为独立指数服务的单服务台，μ₁=100/s、μ₂=250/s。达到瓶颈时停止报告稳态延迟。
提高返回概率，即使外部流量不变，也会增大内部负荷。超过瓶颈时“网络稳态条件”为否，平均时间显示 —；一个有限图窗不能替代不存在的稳态解。
## 服务需求与瓶颈界
每完成一个业务在资源 $j$ 消耗的平均服务需求为 $D_j=V_jE[S_j]$。单容量资源利用率为 $U_j=XD_j$，故吞吐的必要上界为：
$$X\le\frac1{\max_jD_j}.$$
$D_j$ 只含资源占用工作，不含排队；若把响应时间代入，会把拥塞当成固有工作量。多份可并行同质资源可把该项改为 $c_j/D_j$，前提是任务可分派且没有共享瓶颈。瓶颈界不是在任意时延目标下都可达到的吞吐承诺。
固定 $N$ 个用户、每轮思考时间均值 $Z$ 的封闭系统满足交互响应定律 $N=X(E[T]+Z)$。响应变慢时，完成后才发下一轮的用户会降低产生新请求的速度；这与外部按计划持续到达的开放系统不同。
## 扇出为什么放大尾部
若一次请求必须等 $m$ 个子请求全完成，总时间包含 $\max(T_1,\ldots,T_m)$。只有当子时间独立同分布且分布函数为 $F$ 时，最大值分布才是 $F(t)^m$。例如单个在某阈值内完成的概率为 0.99，100 路全完成的概率只有 $0.99^{100}\approx0.366$。
共享数据库、网络或故障会造成相关性；不能无条件套乘法。串行阶段的**均值**可相加，而阶段 p99 通常不可相加为端到端 p99。需要联合测量、适当的概率界或明确的依赖模型。
## 自检
1. 数据库每业务平均访问 3 次，每次占用 5 ms，单台瓶颈上界是多少？
参考思路
$D=3\times0.005=0.015$ s/业务，故 $X\le66.67$/s。这只是该资源的必要上界；等待目标、其他资源和波动可能让可用吞吐更低。
参考思路
稳态关系给出吞吐从 100/s 降至 10/s。生成器跟着被测系统变慢，不能据此断言系统承受住了持续 100/s 的开放外部需求。