QoS-Guaranteed Path Selection Algorithm for Service Composition

Service overlay networking is an emerging approach, which employs overlay nodes to provide advanced services by dynamically composing it from basic services available on overlay nodes. Advanced service request from users can have different and multiple quality-of-service (QoS) requirements and finding a service path that meets these multiple requirements is an open problem. Also, network operators have operating requirements such as load-balancing to minimize hotspots and/or minimizing the overall utilization of resources in their network. In this work, we describe a novel algorithm K-Closest Pruning (KCP), based on proximity based tree pruning, to efficiently determine a service path meeting all the QoS requirements. An additional novel feature in this algorithm is that it incorporates the minimal resource utilization or load-balancing constraints into the path selection process. KCP algorithm achieves a polynomial running time and is the first, in our knowledge, to take both the QoS requirements (user/application perspective) and resource utilization (operator perspective) into account. We show that the KCP algorithm performs significantly better than previous solutions in terms of meeting the QoS requirements of user requests.