Minimum User-Perceived Interference Routing in Service Composition
Li Xiao, Klara Nahrstedt · 2006
Abstract — Service Composition is a promising technology for providing on-demand composed services in dynamic and loosely coupled peer-to-peer (P2P) networks. Because of system dynamics, such as the peer leaving from the system, end users may perceive interference from service disruptions. How to minimize the userperceived interference and provide Quality of Service guarantees to the composite services thus becomes important and challenging. In this paper, we take a novel approach to study the problem of minimum interference service composition with QoS guarantees. First, we propose a general analytic framework to model the interference and its intensity to the end users due to system dynamics. Based on this framework, the minimum interference routing problem is formulated. Then, we present an optimal solution to the problem through dynamic programming and investigate some optimization simplifications in special cases. We further propose a heuristic measure for fast interference calculation and design efficient routing algorithms by exploiting the local path recovery and reliable service paths. Our analysis and extensive simulations demonstrate that our model and algorithms can achieve much better performance than the traditional methods in finding service paths, with respect to decreasing the interference to end users, especially in the scenarios of stringent QoS requirement, highly dynamic networks, or the type of impatient users. I.