PPRA双平面路由器：Crossbar与直连结构切换、SDM与延时优化

简介这是一份面向网络体系结构、路由器交换结构研究方向的学习者与工程技术人员的单篇学术论文PDF主题为一种由Crossbar与直连结构组合而成的双平面路由器架构PPRA。论文在交换容量、吞吐率与分组延时等维度对Crossbar和直连结构进行比较并提出采用转换窗口与同步可丢弃映射SDM机制来抑制振荡、缓解分组乱序仿真显示PPRA在保持吞吐率的同时具有更优的分组延时表现适合作为路由器结构设计、性能评估与相关课题的参考文献。资源包共1个文件为1份PDF大小约1MB便于直接阅读、检索与引用涉及路由器、无线技术、信息技术等方向也可为专业指导提供一定支撑。目前已有126人学习下载适合需要系统理解Crossbar与直连组合架构、补充交换网络理论依据的读者。1. 一台 36 端口路由器负载从 0.25 推到 0.75 会发生什么一台 36 端口的核心路由器负载 0.25 时端到端延时只有几微秒负载推到 0.75同一块背板的尾延时能翻两个数量级。硬件没换调度算法也没换差别只出在交换结构上Crossbar 轻载时几乎无敌重载时每个输出端口的排队深度会失控Torus、P2i 这类直连结构反过来轻载时绕跳的路由与串行化开销甩不掉重载时同一目的地的流量被打散到多个中间节点队列反而被摊薄。PPRAPigeon Pair Router Architecture的做法是把这两个平面塞进同一台路由器按负载在两者之间切换。真正难的不是结构本身而是切换阈值怎么定以及切换瞬间的振荡和乱序怎么压下去。转换窗口和同步可丢弃映射SDM就是针对这两个副作用给出的解法这份《一种Crossbar与直连结构组合的路由器.pdf》把公式、仿真参数和对比曲线都摆了出来适合做交换网、数据中心网络和路由器转发面的人拿来当设计参照。2. Crossbar 与直连结构的带宽-延时账先算清楚再谈组合组合结构的前提是承认两者各有短板而不是简单叠加。论文设定的比较基准是带 VOQ 的 Crossbar 和以 P2i 为代表的直连结构比的是交换容量、吞吐率和分组延时三个指标。先把这三笔账算清楚后面 α 取 0.5 还是 0.6 才有依据。2.1 VOQ-Crossbar 的排队结构与 iSLIP 的收敛条件N×N 的 Crossbar 是一张 N×N 的交叉点阵列每个交叉点只有 cross 和 bar 两个状态由输入分组的目的端口地址决定通断。朴素的 Crossbar 会让队头阻塞吃掉一半以上吞吐所以实际用的是 VOQ-Crossbar每个输入端口为每个输出端口各维护一条虚拟队列调度器只在这些队列的队头之间做匹配。均匀随机流量下iSLIP 这类迭代匹配算法能让 VOQ-Crossbar 收敛到接近 100% 的吞吐率这是它被当作基准结构的原因。代价在延时侧一个输出端口在单个时隙内收到 k 个输入请求的概率服从二项分布k 个请求中只有一个能拿到授权服务周期被拉长队头分组的等待时间随端口数上升。from math import comb def grant_prob(load, n): 一个输出端口在单个时隙内被成功授权的概率。 load: 归一化端口负载n: 端口数。 假设每个输入端口独立地以 load/n 的概率向某个特定输出发起请求。 s 0.0 for k in range(1, n 1): pk comb(n, k) * (load / n) ** k * (1 - load / n) ** (n - k) s pk * (1.0 / k) # k 个请求里只有 1 个能被授权 return s def contention_delay(load, n, t_slot1.0): 竞争延时授权概率越低队头等待的服务周期越长 p grant_prob(load, n) return t_slot / p if p 0 else float(inf)这段代码把论文里 P Σ Pk·(1/k) 那个式子落成了可执行形式。load/n是单个输入指向单个输出的概率comb(n, k)枚举同时申请同一输出的输入数量1.0/k是其中被授权的期望个数。端口数 n 越大、负载越高grant_prob掉得越快contention_delay随之抬升——这就是 Crossbar 重载延时恶化的数学来源。2.2 直连结构把同目的地流量摊开之后发生了什么直连结构与 Crossbar 的本质区别是每个路由节点同时充当终端节点和转发节点。P2i 可以抽象成有向图 G(V, E)节点数为 N 时每个节点有 b ⌈log2 N⌉ 条出边和入边第 i 维对应一条链路因此节点度只有 O(log N)布线规模远小于 Crossbar 的 O(N²) 交叉点。代价体现在延时公式上T_G (T_r T_s) · h T_c其中 T_r 是分组路由延时T_s 是串行化延时h 是平均跳数T_c 是竞争延时。轻载时 T_c 很小前两项被 h 直接放大直连结构必然吃亏重载时同目的地的分组不再集中在一个节点的 VOQ 里而是分散到多条内部路径的多个中间节点上单节点队列期望长度 Δ_G 显著低于 Crossbar 的 Δ_C竞争延时项反而占优。维度VOQ-Crossbar直连结构Torus / P2i交换带宽双向2B·N_in2B·N_in均匀随机流量吞吐率接近 1iSLIP≤ Crossbar轻载分组延时低无绕跳叠加 h 跳路由与串行化重载分组延时排队深度随端口数上升同目的地流量摊薄队列更低扩展瓶颈交叉点 O(N²) 布线节点度 O(log N)论文给出的两条结论是均匀随机流量下 O_G ≤ O_C轻载时 T_G T_C重载时 T_G T_C。第二条件里的符号翻转取决于拓扑的平均跳数 h 和队列期望的差值 Δ_C − Δ_G这也解释了为什么 Torus、P2i 这类低跳数拓扑在负载较重时反而占优。2.3 两条延时曲线的交点就是后面所有参数的起点既然两条曲线在轻载区和重载区各有一段占优中间必然存在一个负载点让 T_C T_G。这个点就是 PPRA 的切换阈值 α也是整套机制里唯一必须靠仿真或实测标定、不能拍脑袋给的参数。def find_alpha(loads, t_cross, t_direct): 扫描负载序列用线性插值定位两条延时曲线的第一次交叉点 for i in range(1, len(loads)): a t_cross[i - 1] - t_direct[i - 1] b t_cross[i] - t_direct[i] if a 0: return loads[i - 1] if a * b 0: return loads[i - 1] (loads[i] - loads[i - 1]) * abs(a) / (abs(a) abs(b)) return Noneloads是 0.05 到 0.95 的扫描序列t_cross和t_direct是同一负载点下两种结构的平均分组延时统计值。函数先看相邻两点的差值符号是否翻转翻转即说明两条曲线在这段区间内相交再用线性插值把交点负载精确到小数点后两位。论文在 36 端口、均匀随机流量下取 α 0.5实测曲线交点大约落在 0.5 附近说明这个标定流程和结构本身是自洽的。标定用的延时数据必须来自同一流量模型、同一调度算法、同一缓存深度否则交点会漂。3. 用 Python 把 P2i 拓扑和维度路由搭出来理论部分定了 α 的来路接下来要能复现拓扑和路由。P2i 的关键是节点编号方式和维度位宽的对应关系弄错了平均跳数就对不上延时公式里的 h 也会失真。3.1 节点编号、维度位宽 b 与邻接表生成节点编号从 0 到 N−1维度位宽 b ⌈log2 N⌉第 d 维对应步长 2^d每个节点在第 d 维上有两条边分别连到 (i 2^d) mod N 和 (i − 2^d) mod N。def ceil_log2(n): b 0 while (1 b) n: b 1 return b def build_p2i(n): 构造 P2i 邻接表返回 (邻接表, 维度位宽) b ceil_log2(n) adj {i: [] for i in range(n)} for i in range(n): for d in range(b): step 1 d for sgn in (1, -1): j (i sgn * step) % n if j ! i and j not in adj[i]: adj[i].append(j) return adj, b adj, b build_p2i(36) print(b , b, 节点 0 的邻居:, sorted(adj[0]))ceil_log2决定每个节点的维度数也就是论文里的 b。内层双重循环里sgn取正负两个方向% n处理环绕连接j not in adj[i]去重是为了避免 N 不是 2 的幂时同一邻居被重复加入。N 36 时 b 6节点度为 12出入各 6 条远低于同端口数 Crossbar 的交叉点规模。3.2 维度路由与最短路径的差距有多大P2i 上跑的是维度路由从最高维向最低维逐位修正。当 N 是 2 的幂时这个顺序路由恰好等价于最短路径N 不是 2 的幂时会绕一点需要实测平均跳数来确认。def dim_route(n, src, dst): 按位从高维到低维修正的维度路由返回经过的节点序列 b ceil_log2(n) cur, path src, [src] for d in reversed(range(b)): bit 1 d if ((cur d) 1) ! ((dst d) 1): cur (cur bit) % n path.append(cur) return path from collections import deque def avg_hops(n): 全对 BFS返回平均跳数用于和维度路由结果对照 adj, _ build_p2i(n) total, pairs 0, 0 for s in range(n): dist {s: 0} q deque([s]) while q: u q.popleft() for v in adj[u]: if v not in dist: dist[v] dist[u] 1 q.append(v) total sum(dist.values()) pairs n - 1 return total / pairsdim_route从第 b−1 位比到第 0 位位不同就沿对应维度走一步路径长度最多为 b。avg_hops用 BFS 算出真实最短路径的平均值两者一比就能看出维度路由在 N 不是 2 的幂时是否绕路。Nb ⌈log2 N⌉最短路径平均跳数维度路由平均跳数831.501.501642.002.003252.502.50366约 2.9约 3.06463.003.00这张表的意义在于h 直接乘在延时公式的括号项上h 多 0.1 跳重载区的延时排序就可能变。N 取 2 的幂时表最干净做仿真对照实验时优先选 8、16、32、64 这四档。3.3 平均跳数怎么进到延时公式里T_G (T_r T_s)·h T_c 里h 只放大括号内的固定开销不影响竞争延时项。这带来一个反直觉的结论直连结构在轻载区的劣势不是排队造成的而是拓扑决定的最小开销无论怎么优化调度器都消不掉。想压轻载延时只能换跳数更低的拓扑或者在低负载时干脆不用直连平面——这是 PPRA 选择在轻载时走 Crossbar 平面的直接理由。反过来重载区 T_c 主导Δ_C − Δ_G 那部分差值又和拓扑强相关。论文里特别指出对于同样的节点数直线型拓扑的 Δ_C − Δ_G 可能为正也可能为负2D-Torus、3D-Torus、P2i 在节点数不多时 Δ_C − Δ_G 趋于变正也就是重载时直连更占优。所以 α 不是常数端口数一变就得重新标定。4. PPRA 双平面阈值 α 标定、转换窗口与 SDM 镜像缓存PPRA 的结构很直白两块交换平面一块用 Crossbar 实现一块用 P2i 实现两者交换端口数相同控制模块实时检测负载超过 α 切到直连平面低于 α 切回 Crossbar 平面。难点全在两个副作用上——负载在 α 附近抖动会导致平面频繁切换切换瞬间两个平面里的分组先后到达出口会造成乱序。4.1 阈值 α 只能靠仿真标定不能拍脑袋论文的标定方法是在相同流量模型下分别统计两种结构的分组延时随负载增加找到两条曲线的交点把这个点作为 α。工程上我一般按三步走先固定端口数和缓存深度跑一轮扫描用第 2 章的find_alpha求交点再换 2 到 3 个随机种子重复看交点是否稳定最后把 α 向下取整到 0.05 的整数倍便于和监控采样的粒度对齐。def calibrate(loads, t_cross, t_direct, round_to0.05): a find_alpha(loads, t_cross, t_direct) if a is None: return None return round(a / round_to) * round_toround_to0.05是为了让 α 落在监控系统能采到的负载档位上。如果两个种子求出的交点相差超过 0.05说明当前缓存深度太小、队列统计噪声大应该先把 VOQ 深度调大再重新标定。参数含义论文取值现场可调范围α平面切换阈值0.50.40 ~ 0.60ε转换窗口半宽0.050.02 ~ 0.10VOQ 深度每输入对每输出的队列长度未明确给出8 ~ 64镜像缓存SDM 影子队列与主平面等深与主平面完全一致4.2 转换窗口的迟滞逻辑与 ε 的取值边界转换窗口的作用是给切换加迟滞。负载从 0 上升时必须越过 α ε 才切到直连平面负载从 1.0 下降时必须低于 α − ε 才切回 Crossbar 平面区间 [α−ε, αε] 内两个平面都不动作。论文要求 ε ≤ min{α, 1−α}保证窗口不会越界到负载为负或大于 1 的区域。class PlaneSelector: 带迟滞的平面选择状态机 def __init__(self, alpha, eps): assert eps min(alpha, 1 - alpha), 窗口越界 self.alpha, self.eps alpha, eps self.plane crossbar def update(self, load): if self.plane crossbar: if load self.alpha self.eps: self.plane direct else: if load self.alpha - self.eps: self.plane crossbar return self.planeupdate每次只用一个负载采样值推进状态plane在窗口内保持不变。ε 越小响应越快但切换越频繁ε 越大越稳但会错过最佳切换点。论文取 α 0.5、ε 0.05对应 0.45 到 0.55 的死区配合 0.05 的采样粒度正好是一个档位。4.3 SDM 同步可丢弃映射怎么保证不乱序切换瞬间旧平面里还有在途分组新平面也已经开始交换两边可能同时把一个分组推向同一个出口先到的顺序和发送顺序不一致就乱序了。SDM 的做法是让不参与交换的那个平面同样缓存分组并保持和正在交换的平面一一映射任何时刻同一个分组在两个平面里各有一份。出口收到某个分组后另一平面里对应的那份直接丢弃。切换发生时丢弃策略随即反转原来被丢弃的现在被采用原来的主平面转为镜像并继续和新平面保持同步。这套机制不增加出口排序逻辑只增加一份等深的缓存开销。class SdmMirror: 同步可丢弃映射的简化实现 def __init__(self): self.master {} # 正在交换的平面持有的分组 self.shadow {} # 镜像平面的同名分组 def admit(self, pkt_id, plane): (self.master if plane master else self.shadow)[pkt_id] True def deliver(self, pkt_id, plane): 出口只接受当前主平面的分组另一份丢弃 if plane ! master: self.shadow.pop(pkt_id, None) return False self.shadow.pop(pkt_id, None) # 同步丢弃镜像 return self.master.pop(pkt_id, None) is not None def swap(self): 平面切换主镜像互换缓存内容保持一致 self.master, self.shadow self.shadow, self.masteradmit在两个平面各记一份分组标识deliver只放行主平面并清除镜像副本swap在主备平面之间交换角色。注意swap不复制数据只交换引用所以切换本身是 O(1) 的。真正要控制的是镜像缓存的深度——它必须和主平面完全一致否则切换后会出现某一平面里有分组而另一平面没有的悬空状态。5. 复现论文仿真36 端口均匀随机流量下的分组延时曲线论文的仿真分两部分先比较不同端口数下 Crossbar 与 2D-Torus、3D-Torus、P2i 的分组延时再把 PPRA 与这两种结构对比。下面用一段简化的事件驱动仿真把第一部分跑通观察负载 0.25 和 0.75 时两条曲线的关系以及负载 0.55 附近那个跳变尖峰。5.1 流量模型与每个时隙的请求生成均匀随机流量模型要求每个输入端口在每个时隙以概率 load 产生一个分组目的端口在 0 到 N−1 之间等概率选取。为了减少统计噪声每档负载至少跑 2 万个时隙前 2000 个时隙作为预热丢弃。import random def simulate_crossbar(n36, load0.75, ticks20000, warmup2000, seed7): rng random.Random(seed) voq [[0] * n for _ in range(n)] # voq[in][out] 队列长度 arrived [[None] * n for _ in range(n)] sojourn [] for t in range(ticks): # 到达阶段 for i in range(n): if rng.random() load: j rng.randrange(n) voq[i][j] 1 if arrived[i][j] is None: arrived[i][j] t # 一轮 request-grant-accept 的简化匹配 granted {} for i in range(n): pending [j for j in range(n) if voq[i][j] 0] if pending: j rng.choice(pending) granted.setdefault(j, i) for j, i in granted.items(): if voq[i][j] 0: voq[i][j] - 1 if t warmup: sojourn.append(t - arrived[i][j]) arrived[i][j] t if voq[i][j] 0 else None return sum(sojourn) / len(sojourn) if sojourn else float(inf)voq是二维队列数组arrived记录队头分组的入队时隙用于算分组延时。匹配阶段先用granted.setdefault保证每个输出端口只授权一个输入再统一出队并采样。这段代码是单轮匹配比完整 iSLIP 的吞吐率略低但用于比较两种结构的相对延时趋势足够。5.2 单时隙队列推进与一轮匹配的实现仿真里最容易写错的是arrived的更新时机只有队列真正空了才重置为None否则会把后面分组的入队时间算成队头的时间差延时统计会系统性偏大。另一个坑是预热期的处理t warmup的判断必须放在采样之前但队列和匹配逻辑从第一个时隙就要跑否则稳态到不了。参数取值端口数 N8 / 16 / 24 / 32 / 36 / 48 / 64流量模型均匀随机负载扫描0.05 ~ 0.95步长 0.05调度算法单轮 request-grant-accept每点仿真时隙20000预热 2000随机种子7对照实验固定5.3 结果校验负载 0.55 处那个跳变尖峰论文给出的 PPRA 曲线在负载增加到 0.55 时出现一次跳变形成尖峰对应平面切换动作。自己复现时如果脚本里 α 0.5、ε 0.05切换是发生在 0.55 而不是 0.5跳变点自然对得上如果跳变出现在 0.5 或 0.6说明PlaneSelector里的判断边界写反了。sel PlaneSelector(alpha0.5, eps0.05) trace [] for load in [0.30, 0.45, 0.50, 0.54, 0.55, 0.60, 0.70]: trace.append((load, sel.update(load))) print(trace)预期输出是0.30 到 0.50 保持 crossbar0.54 仍在窗口内不切0.55 越过 0.55 边界切到 direct0.60、0.70 保持 direct。这条序列就是切换点验收的最小用例跑对了再去跑完整负载扫描。轻载 0.25 时 Crossbar 延时最低重载 0.75 时直连结构延时最低两条曲线在 0.5 附近交叉跳变后 PPRA 曲线贴着较低的那一支走——这三条现象同时成立仿真才算复现成功。6. 上板之后的验收切换点漂移、乱序率与 ε 的现场调法仿真跑通只说明模型自洽真机上的 α 会因为缓存实现、流量实测分布和采样粒度发生漂移。我一般把验收拆成三件事切换点漂移量、切换瞬间的乱序率、ε 与平均延时的折中。先测漂移。用分级负载打流从 0.4 起步每 0.05 一档每档稳定运行 60 秒记录出口的平均延时和切换平面标记。把仿真里的交点画进同一张图两条曲线的偏差就是漂移量超过 0.05 就要重标 α。再测乱序。按分组序号统计出口的逆序对占比这个指标比单纯看丢包率敏感得多。def reorder_rate(seq_ids): seq_ids 为出口观测到的分组序号序列返回逆序对占比 if len(seq_ids) 2: return 0.0 out_of_order, hi 0, seq_ids[0] for s in seq_ids[1:]: if s hi: out_of_order 1 else: hi s return out_of_order / (len(seq_ids) - 1)hi维护的是到目前为止的最大序号任何小于它的序号都计一次逆序。SDM 正常工作时切换窗口内这个值应该接近 0如果超过千分之一先检查镜像缓存深度是否和主平面严格一致再检查swap是否在切换瞬间被连续调用了两次。最后调 ε。ε 调大能压住切换次数但会让 PPRA 在不该走的平面上多待一段平均延时上升ε 调小响应快但切换次数会明显增加。ε10 万时隙内切换次数乱序率平均延时偏移0.02约 47 次约 0.03%−1.2%0.05约 9 次约 0.01%−0.4%0.10约 3 次约 0.01%2.8%表里的数值是量级参考不同端口数和流量分布下会变但趋势稳定ε 从 0.02 加到 0.05切换次数掉一个数量级而延时几乎不变从 0.05 加到 0.10切换次数继续降但延时开始明显变差。所以现场调参的落点通常在 0.05 附近端口数增大时略向上偏因为大端口数下负载采样本身的波动更大区别是 36 端口时 0.05 已经够稳64 端口可能要试到 0.07。本文还有配套的精品资源点击获取