As Internet migrates gradually to SOA (Service Oriented Architecture), Service Providers (SP) find out that Internet services have the potential to bring great profits. Thus various Internet services appeared in recent decades, such as VoIP, IPTV, VoD, Internet Game, VPN and etc. In order to maintain traditional customers and attract new users, SP should provide QoS (Quality of Service) for their services.Fault management is crucial for QoS guarantee, since service unavailability or performance degradation may cause Service Level Agreement (SLA) violation, which will affect the SP's credit and cause the financial loss. Therefore, in order to shorten the unavailable and performance degradation period when a service failure happens, SP needs service oriented fault management to localize the fault and take counter measures. This dissertation focuses on the fault management architecture for Internet services and the related algorithms. Graph theory based fault diagnosis, FPM (fault propagation model) modeling, fault localization algorithms analysis and improvement, and the multi-domain fault management framework for Internet services are examined in this dissertation. The main contributions are as follows:(1) The complicated causes of Internet services failure are analyzed. Based on the comparison of current fault diagnosis techniques, graph theory is chosen to be the theoretical tool and bipartite graph is employed as the FPM for Internet services. A layering FP.M with the modeling approach is proposed. By dividing the fault management task into separated layers, the layering model can simplify the fault diagnosis process.(2) By transforming the fault diagnosis in bipartite FPM into a set-covering problem, two window-based fault localization algorithms MCA (Max-Covering Algorithm) and MCA+ are proposed, based on the heuristic greedy algorithm. MCA+ is an extension of MCA, taking the loss and spurious symptoms into account. Simulation results prove that MCA and MCA+ can achieve higher fault detection rate and lower false positive rate than current algorithms. They are more stable and have lower complexity in addition.(3) MFD (Multi-window Fault diagnosis) algorithm is proposed to improve the performance of window-based algorithms in the case that the time window is set improperly. The intrinsic shortcoming of window-based algorithms is that their accuracy depends on whether the time window size is set correctly. By considering the correlation of adjacent time windows, MFD can alleviate the