第1期 齐小刚，等：多层信息网络故障定位综述 ·49· 故障“1”)，可以将多层网络的依赖矩阵模型分为 测路径状态是正常的当且仅当这条路径上的所有 二进制依赖矩阵模型212和非二进制依赖矩阵模 部件都是正常状态。非二进制依赖矩阵模型不仅 型242刃。二进制依赖矩阵模型假设多层网络部件 可以定位出多层网络故障部件而且可以判定多层 和探测路径只有正常和故障2种状态，且假设探 网络节点、链路的拥塞程度或链路延迟。 表1各种探测信息获取策略的比较 Table 1 Comparison of various detection information acquisition techniques 被动监测 主动探测 主被动结合探测 终端用户观察 由NMS被动接受告警通过在探测路径上发送使用被动监测和主动探使用终端用户观察到的 探测信息获取策略来分析网络中故障的具探测包诊断和定位网络测找出网络中高保真度负面症状找出可能发生 体位置 中的故障节点和链路 的故障假设集 的故障部件 图论技术（故障传播模 预计划探测策略适应性 Dempster-Shafer理论约 方法和路线 AIR框架、O-AIR框架 型) 探测策略 束满足问题 增加少量网络流量和花 不增加网络流量，增加网 网络流量及花费 不增加网络流量 增加网络流量和花费 费 络花费 响应时间 事件-驱动 事件-驱动 事件-驱动 事件-驱动 可以同时诊断多个故障 可以同时诊断多个故障 灵活、诊断时间短、精 可以同时诊断多个故障 优点 部件，诊断时间短，精度 部件 度高 部件 较高 只假设单个节点故障， 精度低，需要知道部件 需要知道部件故障以及 未考虑丢失探测，节点 需要把监测代理安装在 缺点 故障以及故障一症状之 故障-症状之间因果关系 故障的假症状，动态的 每个overlay节点上 间因果关系的先验知识 的先验知识 探测路径 获得和保持准确信息虚探测站的配置选择最小 探测站的配置选择最小终端用户观察不充足，恶 挑战 假、丢失症状存在 的探测集 的探测集 意终端用户 3.2基于图论的故障传播模型 或经由这些路径的链路之间的依赖关系，其影响 多层网络基于图论的故障传播模型(fault 的大小用条件概率表示。每个节点是多值的随机 propagation model,.FPM)描述了采用被动监测策 变量，其表达的意思是每个路径或链路可能有多 略时所有可能发生在底层网络和虚拟层网络故障 种故障类型，如延迟、大量的包丢失、完全不连通 和症状之间的关系。该模型需要具备底层网络 等。这种情形在故障传播模型中可以被表示为每 和虚拟层网络部件故障状态和告警与其他部件的 条路径和链路在贝叶斯网络模型中对应于多个路 故障。 径和链路节点，其中每个节点表示不同的故障类 建立状态和告警之间相互关联的先验知识。 型。FPM也可以建模为二部图模型。尽管在真 为了建立这样的模型，需要很好地了解每一层网 实网络中故障和症状间的关系通常比二部图表示 络部件间的依赖关系。故障定位算法的高效性和 的关系更为复杂，但许多故障定位方法仍然使用 精确性依赖于先验知识的精确性。FPM的常见 二分PM6列，原因如下：1)执行具有复杂表示形 模型有依赖图模型或贝叶斯网络模型。依赖图模 式的故障定位模型是困难的；2)详细模型通常可 型是有向图，其中节点表示事件，边表示事件间 以通过一系列的图规约操作降为二分模型；3)模 的关系。每一条有向边通过条件概率来标记，其 型建立需要对网络有深厚知识的积累，而症状 表达的意思是：由于起始节点的故障导致了终点 一故障映射关系可以通过外在的观测来获得。因 节点的故障。依赖图的每个节点既可以表示网络 此，在许多真实的问题中使用二分的症状-故障 节点的故障，也可以表示网络链路的故障。关于使 模型是可行的。 用依赖图模型的故障诊断方法的一些工作见文 为了减少由于使用大规模贝叶斯网络模型计 献[6,28-29]。贝叶斯网络模型又称信任网络模 算复杂度，Bennacer等o提出了混合模型，结合了 型，是一个有向无环图，其中，节点表示网络链路 贝叶斯网络模型(BN)和基于实例的推理机制 状态或端到端路径状态，有向边表示端到端路径 (case based reasoing,CBR)的使用。这个模型的基故障“1”)，可以将多层网络的依赖矩阵模型分为 二进制依赖矩阵模型[21-23]和非二进制依赖矩阵模 型 [24-27]。二进制依赖矩阵模型假设多层网络部件 和探测路径只有正常和故障 2 种状态，且假设探 测路径状态是正常的当且仅当这条路径上的所有 部件都是正常状态。非二进制依赖矩阵模型不仅 可以定位出多层网络故障部件而且可以判定多层 网络节点、链路的拥塞程度或链路延迟。 3.2 基于图论的故障传播模型 多层网络基于图论的故障传播模型 (fault propagation model，FPM) 描述了采用被动监测策 略时所有可能发生在底层网络和虚拟层网络故障 和症状之间的关系。该模型需要具备底层网络 和虚拟层网络部件故障状态和告警与其他部件的 故障。 建立状态和告警之间相互关联的先验知识。 为了建立这样的模型，需要很好地了解每一层网 络部件间的依赖关系。故障定位算法的高效性和 精确性依赖于先验知识的精确性。FPM 的常见 模型有依赖图模型或贝叶斯网络模型。依赖图模 型是有向图，其中节点表示事件，边表示事件间 的关系。每一条有向边通过条件概率来标记，其 表达的意思是：由于起始节点的故障导致了终点 节点的故障。依赖图的每个节点既可以表示网络 节点的故障，也可以表示网络链路的故障。关于使 用依赖图模型的故障诊断方法的一些工作见文 献[6, 28-29]。贝叶斯网络模型又称信任网络模 型，是一个有向无环图，其中，节点表示网络链路 状态或端到端路径状态，有向边表示端到端路径 或经由这些路径的链路之间的依赖关系，其影响 的大小用条件概率表示。每个节点是多值的随机 变量，其表达的意思是每个路径或链路可能有多 种故障类型，如延迟、大量的包丢失、完全不连通 等。这种情形在故障传播模型中可以被表示为每 条路径和链路在贝叶斯网络模型中对应于多个路 径和链路节点，其中每个节点表示不同的故障类 型。FPM 也可以建模为二部图模型。尽管在真 实网络中故障和症状间的关系通常比二部图表示 的关系更为复杂，但许多故障定位方法仍然使用 二分 FPM[4, 6, 9] ，原因如下：1) 执行具有复杂表示形 式的故障定位模型是困难的；2) 详细模型通常可 以通过一系列的图规约操作降为二分模型；3) 模 型建立需要对网络有深厚知识的积累，而症状 −故障映射关系可以通过外在的观测来获得。因 此，在许多真实的问题中使用二分的症状−故障 模型是可行的。 为了减少由于使用大规模贝叶斯网络模型计 算复杂度，Bennacer 等 [30]提出了混合模型，结合了 贝叶斯网络模型 (BN) 和基于实例的推理机制 (case based reasoing，CBR) 的使用。这个模型的基 表 1 各种探测信息获取策略的比较 Table 1 Comparison of various detection information acquisition techniques 被动监测 主动探测 主被动结合探测 终端用户观察 探测信息获取策略 由NMS被动接受告警 来分析网络中故障的具 体位置 通过在探测路径上发送 探测包诊断和定位网络 中的故障节点和链路 使用被动监测和主动探 测找出网络中高保真度 的故障假设集 使用终端用户观察到的 负面症状找出可能发生 的故障部件 方法和路线 图论技术(故障传播模 型) 预计划探测策略适应性 探测策略 AIR 框架、O-AIR 框架 Dempster-Shafer理论约 束满足问题 网络流量及花费 不增加网络流量 增加网络流量和花费 增加少量网络流量和花 费 不增加网络流量，增加网 络花费 响应时间 事件−驱动 事件−驱动 事件−驱动 事件−驱动 优点 可以同时诊断多个故障 部件 灵活、诊断时间短、精 度高 可以同时诊断多个故障 部件，诊断时间短，精度 较高 可以同时诊断多个故障 部件 缺点 精度低，需要知道部件 故障以及故障−症状之 间因果关系的先验知识 只假设单个节点故障， 未考虑丢失探测，节点 故障的假症状，动态的 探测路径 需要知道部件故障以及 故障−症状之间因果关系 的先验知识 需要把监测代理安装在 每个 overlay 节点上 挑战 获得和保持准确信息虚 假、丢失症状存在 探测站的配置选择最小 的探测集 探测站的配置选择最小 的探测集 终端用户观察不充足，恶 意终端用户 第 1 期 齐小刚，等：多层信息网络故障定位综述 ·49·