On Valid and Optimal Deployments for Mixed-Tenancy Problems in SaaS-Applications

Software-as-a-Service (SaaS) is a delivery model whose basic idea is to provide applications to the customer on demand over the Internet. Thereby, SaaS promotes multi-tenancy as a tool to exploit economies of scale. A major drawback of SaaS is the customers´ hesitation of sharing infrastructure, application code, or data with other tenants. The common way in research to address this problem is to create new approaches to implement and improve the tenants´ isolation on a commonly used instance. Our approach, called mixed-tenancy approach, tackles this hesitation differently. It allows customers to choose with whom they want to share the instances of an application as well as the underlying infrastructure, and a valid deployment is computed in accordance with customer´s constraints. This paper addresses the major algorithmic problem related to the mixed-tenancy approach. In particular, we analyze the problem of computing valid and optimal deployments. In doing so, we provide a theoretical analysis of the complexity of this problem, proposing several heuristics and discussing their quality.