Optimal Routing Protocols to Routing on Multiple Optimality Criteria

Abstract

传统路由协议（如BGP、EIGRP）在非等张性（non-isotonic）度量下无法计算最优路径，且仅支持单一最优准则。本文提出部分序矢量协议（Partial-Order Vectoring Protocol），通过：

1. 部分序替代全序：将全序（total order）转化为满足等张性（isotonicity）的部分序（partial order），确保协议收敛到主导路径（dominant paths）。
2. 多准则路由：支持同时为不同应用（如文件传输、视频流）选择不同最优路径。
3. 标签转发机制：基于属性集选举结果动态标记数据包，实现路径选择。
   实验证明：在真实拓扑（Rocketfuel/CAIDA）中，平均主导属性数<3，收敛速度优于传统协议。

1. Introduction

背景与问题

• 路由代数模型：路径属性（attribute）通过扩展操作（⊕）和全序（≼）定义最优路径（如最短路径）。
• 等张性缺失问题：若⊕对≼非等张（$a≼b$ 但 $c⊕a \not≼ c⊕b$），则标准矢量协议（如BGP）无法收敛到最优路径（例：图1中EIGRP无法计算最快路径）。
• 单一准则限制：现有协议无法同时支持多目标（如低延迟+高带宽）。

现有方案缺陷

• 启发式协议（如EIGRP）：缺乏理论保证，路径非最优。
• 多路径协议（如ECMP）：仅支持等张度量，无法处理策略冲突。

本文贡献

1. 理论框架：提出最大等张约减（Largest Isotonic Reduction），将任意全序转化为满足等张性的部分序。
2. 协议设计：
   • 节点选举属性集（非单一属性）并广播。
   • 源节点基于应用需求从集合中选择最优属性（如最短最宽/最宽最短）。
3. 多准则支持：通过部分序交集体系统一处理多目标。
4. 实验验证：在ISP/AS级拓扑中验证高效性与可扩展性。

2. Background

关键概念

• 等张性（Isotonicity）：$a ≼ b ⇒ c⊕a ≼ c⊕b$，确保协议收敛到最优路径。
• 严格左膨胀（Strictly Left-Inflationary）：环路属性满足 $b ≺ \hat{a}[C]⊕b$，避免无限循环。
• 主导属性（Dominant Attribute）：集合中不被其他属性支配的元素（帕累托最优）。

相关工作分类

类别	代表工作	局限
代数路由框架	Sobrinho [5], Griffin [7]	仅支持全序且需等张性
多目标路径算法	Hansen [30], Martins [31]	集中式计算，不适用分布式协议
BGP多路径扩展	Wang [23], YAMR [37]	无法解决非等张性问题

3. Method

3.1 理论框架设计

• 最大等张约减（LIR）：
  对全序≼，构造部分序 $≼^{R^*}$：$a ≼^{R^*} b$ 当且仅当 $∀x_1..x_n, \ \hat{x}⊕a ≼ \hat{x}⊕b$（定理1）。
  示例：最短最宽序 → 宽度-长度积序（图2 vs 图6）。
• 多准则整合：
  对准则集$O$，取部分序交集 $≼^O = \cap_{i∈O} ≼_i$，再求其LIR（图6）。

3.2 协议设计

部分序矢量协议流程：

1. 初始化：目的节点广播 $\{ε\}$。
2. 属性计算：节点$u$收到邻居$v$的属性集$B$后：
   $$C_u[v,t] = \{ a[uv] ⊕ b \mid b ∈ B \}$$
3. 选举主导集：
   $$E_u[t] = \mathcal{D}_≼ \left( \cup_{v} C_u[v,t] \right)$$
4. 标签转发（图3）：
   • 为 $E_u[t]$ 中每个属性分配本地唯一标签。
   • 数据包携带标签，中间节点根据标签表交换（如：图3中$u→v→x$）。

3.3 关键机制

• 终止性证明（定理4）：在属性集有限且无环条件下，协议必然终止。
• 主导性保证（定理5）：等张性+严格左膨胀 → 稳定态路径为简单主导路径。

4. Evaluation

实验设置

拓扑	属性	协议对比
Rocketfuel AS1239（284节点）	宽度=1/OSPF权重，长度=延迟	宽度-长度积协议 vs 最宽最短/最短最宽协议
CAIDA AS关系（70k AS）	类型=客户/对等/提供商，长度=跳数	类型-长度积协议 vs BGP

结果分析

• 主导属性数（图8-9）：
  • AS1239中平均2.45个/路径，93.8%路径≤3个。
  • CAIDA中93.85%源-目的对仅需1个类型-长度。
• 收敛速度（图10）：
  • 目的宣告：宽度-长度积协议（212.3ms） vs BGP（235.9ms）。
  • 链路故障：宽度-长度积协议（99.3ms）仍快于BGP。
• 路径优化（图11）：
  • CAIDA中BGP提供商路径平均长度4.72 → 类型-长度积协议降至3.94。
  • 最宽最短路径平均长度5.07 → 类型-长度积协议支持的最短最宽路径降至3.29。

5. Conclusion

1. 理论突破：通过部分序解决非等张性问题，首次实现多准则最优路径路由。
2. 协议高效性：
   • 主导属性集极小（AS级拓扑中93.85%仅需1个）。
   • 收敛速度优于传统协议（尤其非等张场景）。
3. 部署价值：
   • ISP可独立部署获利（图5案例：AS_w通过多属性吸引客户流量）。
   • 支持应用感知路由（如文件传输选$K$-最快路径，视频流选最宽路径）。

未来方向：探索增量更新机制、跨域策略协同优化。