PDF《DCN 地址配置 冲 突检 测技术》

1 右 所示, 两条电缆同时发生错误接线, 使得由一条电缆接 线错误造成的度变化被另一个错误接线所掩盖 , 因此 没有节 点度变化 的情况 .这将是要讨论 的一种最 困难 的情况 . 在故障检测中, 对于以上三种类型的故障, 无论是 链路造成的故障, 还是错误接线 , 都只报告相关的故障 节点( 即故障设备) , 然后由网络管理员再对故障节点 作下一步的处理 . 图1错误接线度变化与度不变化

1 .

2 故障节点的度不变化 大多数情况下 , 网络 故障会 使节点 度发 生可探 测 到的变化 , 但是 , 错误接线导致节点度没有变化的情 况仍然存在.这种情况发生后, 管理员检查网络, 首先 将引起度变化的故障进行修复.这时, 可以认为, 节点 故障和链路故障均已被排除, 网络中只存在错误连线 故障. 这里 可以做 出假设 :

1 ) 相对于所有节点 , 涉及度不 变化 的故 障节点 的 数量是很 小的 ;

2 ) G . 和G有相同数 目的节点以及节点度模式. 基于数 据 中心 网络 的特 点和网络 的真 实应 用场景, 提出自己的故障检测算法, 通过识别设备 I D检测 故障设备. 尽管存在错误接线, 但绝大部分 G . 和G 仍然是相 同的 .利用 这个事实来检测这种错误接线 .基本想法 是,首先发 现一些 G . 和G之间的对应节点 , 然后用 这 些节点作 为定位点来检测子 图推测它们是否 同构.通 过这一点 , 得 出了两个 图之 间的差异 , 对于不 同的定位 点, 相互关联故障候选者, 最终作出决定.所以, 文中 冲突检测算法包含两个部分 : 定位点的选择和故障检 测.2DAC地址 冲突检测方 法DAC[1o2(DatacenterAddressConfigurationsystem) 是一个通用的数据中心和 自动地址配 置系统 .对于所 有现有和未来的数据中心网络 , D A C给出了一个很有 意义的解决方案.D A C系统设计了一个实用的方案 , 巧妙地利用了在所有数据 中心结构度的规律性, 检测 故障导致设备的度的变化.对于最难的没有度的变 化,系统提出了一个方案 , 从多个定位点 比较蓝 图和物 理拓扑 图和 通过多数 表决的相关 故障.评价 表明,DAC的解决方案, 能够快速检测出所有的最难以检测 的故障 . 第11期陈勇等: D C N地址配置冲突检测技术 .

7 9. 三点不足 : (

1 ) 考虑到在错误接线所涉及的节点数量很少 , 为了尽 量减少人 为干 预,DAC算 法采 用SPLD作 为评 价指标 自动选择定位对, 但是鉴于 S P L D计算量较大 , 而 且两 个类 似SPLDs节点 不一 定 是真 正 的对称 的一 对,故障检测方案将考虑到潜在的误报. (

2 ) 搜索最大的同构子图的过程中, 一h o p中 的值是随机选择的, 并不利于提高效率. (

3 )在DAC的故障检测中, 对于以上三种类型的 故障, 无论是链路造成的故障, 还是错误接线, 都只报 告相关的故障节点( 即故障设备) , 然后由网络管理员 再对故障节点作下一步的处理.

3 改进算法 在蓝 图G和物理拓扑图 G . 中,自动地选 择定位 节 点对, 利用电压模拟法 来进行节点对的选择.在实 际的网络 中, 错 误接线所涉及 的节点数量是很少 的,因此图 G 和G.中的两个 对称 节点仍会有近似的节点 电压值 , 相 比于 S P L D, 准确性更高 . 基于此, 设计定位点对选择算法, 即Anchor―Pair―Selection(),见图

2 .在该算法中, I I 节点电压 ( v )一 节点电压( v ) I l 是简单 的欧氏距 离.一旦 定位节点对 已被选中, 比较这些 G 和G.的定位节点对, 通过多数 投票的方式关联故障. 图2定位 点对选择 算法的伪代码 如图3所示, 故障检测算法是一 M a l f u n c t i o n ― D e t e e . t i o n ( ) .具体来说 , 给定图 G D / G , 节点对集合 A / A , 定义最大 的子图 . s : ( 口),对于每个定位点对 v / v ∈ A / A , 在图 G D / G 中搜索最大的同构子图, 分别从节 点v/v拓展 ―h o p , 获得一个子图 . 的值通常 参照为定位点的最大跳数的