近年来,服务提供商(SP,Service Providers)意识到在Internet上提供增值服务能带来潜在的高额利润,并开发了各种各样的服务,如web服务,IPTV,VoIP等。为了维持当前客户并吸引新客户,SP必须为服务提供QoS(Quality of Service)保证。但是服务相关设备、网络和服务本身都可能发生异常,从而导致服务QoS降级甚至服务不可用。为了保证QoS,SP迫切需要一种有效的服务故障管理机制来监测异常发生,分析异常原因,并尽快采取修复措施。本文围绕分布式互联网服务的故障管理体系及其相关算法进行研究,侧重于基于图论技术的服务故障管理。主要研究了基于主动探针的服务故障管理方案,静态和动态服务环境下的故障诊断算法分析和改进,以及跨多个自治域的服务故障管理机制。论文的主要工作包含以下几个方面:(1)提出不确定和噪声环境下的主动探针故障管理方案。该方案由两阶段组成:故障监测和故障诊断。在故障监测阶段,我们提出了在保证一定监测质量的条件下选择最小代价探针子集的GAPSA算法。在故障诊断阶段,我们提出了根据前一阶段发现的症状选择更多探针来获取系统详细信息的FDPSA算法。仿真结果证明了GAPSA和FDPSA算法的有效性和效率。(2)提出基于增量信度评估的事件驱动故障诊断算法。为了更好地适应症状流的特性,我们提出以事件驱动形式实时分析症状并计算后验故障概率的增量信度评估函数。在此函数基础上,我们提出一个计算次优解的贪婪故障诊断算法。为了进一步减小故障选择阶段的复杂度,我们将故障诊断问题转化为独立寻找每个节点最可能值的问题,并提出了相应的故障诊断算法。仿真结果显示,本文算法极大地减少了诊断时间,并得到了较好的诊断精确度。(3)提出了动态服务环境下的故障诊断算法。分析了服务环境中的动态性对故障诊断算法性能可能造成的影响。针对故障自动修复机制导致的动态故障集环境,在故障持续时间统计的基础上修正当前窗口内先验故障概率;针对动态模型环境,基于当前窗口内原始模型和观察症状时间建立期望模型。仿真结果表明,本文算法可以有效诊断动态环境下的互联网服务故障。(4)提出了多域服务环境下的故障诊断方案。分析了多域服务环境中域间故障传播对故障诊断算法性能造成的影响。提出了多域服务环境下的分布式依赖模型,在该模型基础上提出分布式故障诊断算法,并从减小通信开销、更准确的症状引发评估函数和虚假症状概率三个方面对算法进行了改进。仿真结果表明,本文算法可以有效诊断多域环境下的服务故障。