Minimum user-perceived interference routing in service composition

Li Xiaot, Klara Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Service Composition is a promising technology for providing on-demand services in dynamic and loosely coupled peerto-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 user-perceived interference and provide Quality of Service (QoS) 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 service 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 requirements, highly dynamic networks, or the type of impatient users.

Original languageEnglish (US)
Title of host publicationProceedings - INFOCOM 2006
Subtitle of host publication25th IEEE International Conference on Computer Communications
StatePublished - 2006
EventINFOCOM 2006: 25th IEEE International Conference on Computer Communications - Barcelona, Spain
Duration: Apr 23 2006Apr 29 2006

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherINFOCOM 2006: 25th IEEE International Conference on Computer Communications

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Minimum user-perceived interference routing in service composition'. Together they form a unique fingerprint.

Cite this