Lagrangean relaxation for service location in large-scale networks with QoS constraints

Current trends in computing indicate that there is a great potential for service-oriented computing and similar technologies, such as application-oriented networks (AONs), where services can relocate to adapt to the conditions of the underlying network. In such environments, providing and consuming services and establishing a relationship between consumers (users of services) and producers (providers of services) are still challenging and vastly researched aspects. Bearing this in mind, we define a service location and planning (SLP) problem that uniquely matches producers to consumers and accounts for realistic parameters such as, quality of service (QoS) constraints of throughput and delay, and network constraints of underlying link layer bandwidth capacities, and cost of meeting consumer requests. Our contribution lies in the mathematical formulation of the SLP problem as an integer linear programming (ILP) problem that can be solved optimally for small-scale networks and extending this work using Lagrangean relaxation (LR) approximation techniques to solve the SLP problem for large-scale networks.