路由节点(路由器或交换机)是云计算基础设施(Infrastructure as a Service,IaaS)–大规模网络(例如ISP网络,数据中心网络)的重要组成部分,其对大规模网络的性能起着至关重要的作用。恶意的路由节点,能在大规模网络中蓄意丢弃或篡改数据包,进而影响大规模网络的性能。数据面的网络故障定位技术致力于识别恶意的路由节点,并将恶意路由节点从路由转发表中移除,从而可靠的数据包转发。但是当前的网络故障定位方法存在着很大的不足,并不支持动态路由。更具体的说,其需要源节点事先知道数据包的出口路径,并且该路径能够持续较长的时间。但是真实环境中,数据中心网络中有相当部分的流持续时间较短,并且路由动态变化。为此,本文提出了两种支持动态路由的网络故障定位机制,所提出的机制引入的额外开销小,能够快速检测出异常节点,并且能够应对当前复杂的网络攻击。具体来说,本文的贡献如下:1.本文提出了一种集中式的动态故障定位机制(DFL)。该机制利用一个安全可信的管理节点负责收集和检测流摘要。具体而言,在周期开始时管理节点向各节点发送周期初始信号,并提供相应的指纹函数和抽样函数;各节点以提供的指纹函数和抽样函数计算一个周期内的流摘要,并在周期结束时基于最小生成树的汇报路径,将流摘要发送给管理节点;管理节点则通过检测节点的是否“流守恒”(对一节点而言,在良性环境下,注入该节点的流与流出该节点的流应基本一致),从而断定该节点是否异常。该机制与传统的静态网络故障定位机制相比,减小了节点的密钥数目和空间,并且无需源节点事先知道流的出口路径。2.针对动态网络故障定位机制中定期汇报流摘要可能带来的链路负载不均问题,本文提出了两种算法平衡链路的负载开销。一种为LevAdj算法,针对特殊的层次化结构的大规模网络;另一种为BinDin算法,针对更通用的拓扑的大规模网络。与最小生成树算法相比,这两种算法均将汇报流摘要的链路开销减小了约10倍,大幅改善汇报流摘要式的链路负载不均衡的问题。本文也对BinDin算法和LevAdj算法进行了比较,发现BinDin算法在网络开销的效果比LevAdj算法略胜一筹,不过就计算开销而言,LevAdj算法比BinDin算法快100倍。3.本文提出了一种分布式的动态网络故障定位机制(D2FL),该机制也是利用“流守恒”来检测节点是否异常,由节点的一个随机的二跳邻居负责收集和检测该节点的流摘要信息。具体而言,将节点分成三种角色,收集者、嫌疑者和观察者,收集者负责收集和检测流摘要,嫌疑者为待检测的节点,观察者则记录流摘要并反馈流摘要。仿真实验表明,D2FL的开销仅为2.5%。本文也在Linux平台上实现了一个开源原型,并用真实的应用程序测试D2FL的性能,实验结果表明,D2FL引入的开销不超过10%。另外,该机制能在一定程度上抵抗单点故障且不需要全局的时钟同步。