随着Internet逐渐向面向服务体系架构(SOA)演化，服务提供商(SP)开始发现Internet服务能带来潜在的高额利润，因此，近年来出现了各种各样的Internet服务，如IP电话、IP电视、视频点播、网络游戏、VPN等。为了维持已有顾客群并吸引更多新用户，SP需要保证所提供服务的服务质量(QoS)。 故障管理对于服务QoS保证非常重要，服务的不可用或性能降级都会引起SLA(Service Level Agreement，服务等级协定)违约，影响SP的信誉，并造成经济损失。因此，SP需要面向服务的故障管理机制，在服务发生故障时能迅速定位故障并采取相应措施，以缩短服务宕机时间和性能降级时间。本文围绕着Internet服务的故障管理体系及其相关算法进行了研究，研究的侧重点在于基于图论技术的服务故障诊断，服务故障传播模型建立，故障定位算法的分析和改进，跨多个自治域的服务故障管理框架、以及基于资源规划的服务性能降级故障处理。论文的主要工作包含以下几个方面： (1) 分析造成服务故障的复杂原因，比较了现有的故障诊断技术，选择图论技术作为本文研究的理论工具，采用二分图作为服务的故障传播模型，提出了分层的故障传播模型，并提出了建模方法。分层模型通过将故障管理任务划分到多个独立的层次，简化了故障诊断过程。 (2) 将二分图故障传播模型的故障诊断问题转化为集合覆盖问题，借鉴启发式贪婪算法，设计了最大覆盖算法MCA和MCA+。MCA和MCA+算法是基于时间窗口的，其中MCA+算法是MCA算法的扩展版本，综合考虑了丢失和虚假症状对故障诊断造成的影响。仿真结果证明了MCA和MCA+算法能够获得比现有算法更高的故障检测率和更低的误判率，并且算法稳定，计算复杂度较低。 (3) 为了改进基于时间窗口算法在时间窗口设置不合适的情况下的性能，提出了多时间窗口故障诊断算法MFD。基于时间窗口的算法存在着固有缺陷，即算法的准确度依赖于时间窗口的设置值。MFD算法在MCA+算法的基础上增加了相邻时间窗口关联关系分析，能在一定程度上克服时间窗口设置不准确对算法造成的影响。仿真结果表明，MFD在时间窗口设置准确的情况下能获得与MCA+类似的性能；而在时间窗口设置不准确(包括大窗口和小窗口)的情况下，MFD算法能获得比MCA+算法更高的故障检测率和更低的误判率，并且其算法复杂度与MCA+相同。 (4) 分析了在多域异构网络环境中服务故障管理存在的问题，提出了基于PDB