Chapter 6
Genetic Algorithms for Constrained Service Provisioning

Phil Benjamin

Data Services Integration Division
AT&T
101 Crawfords Corner Road
Holmdel, NJ, 07733
e-mail: pmbenjamin@att.com

ABSTRACT

The focus of this chapter is an industrial decision problem involving the provisioning of services subject to a variety of constraints. Provisioning involves the allocation of generally scarce and costly resources to services subject to a variety of constraints, including both resource constraints and inter-service constraints. In addition to technical constraints on resource utilization and cost minimization, there are also often fuzzy and even contradictory criteria about the “quality” of a proposed provisioning. The approach taken here allows a dualism between satisfying soft constraints and meeting service objectives. Objectives include minimizing cost, meeting individual service objectives, and providing both service redundancy and isolation. A practical approach to this problem requires finding a “good enough” solution to a provisioning problem in a “reasonable” amount of time. A related problem is to reallocate resources when a new service is added to the collection of currently offered services. A genetic algorithm has been implemented to solve an abstraction of the problem of constrained resource provisioning. The implementation is quite general and can be used to solve a wide variety of constrained provisioning problems. This chapter discusses the approach, the implementation, and the evaluation of the approach using some sample data.

PROBLEM FORMULATION

Problem Background

It is desired to offer network-based computer-telephony services to customers. A “service” in this context is generally a computer resident complex (programs, databases, links to customer-based resources, etc.) which is accessible via a telephony network and is used to provide an economic service to a customer. The services are “provisioned ”by assigning them to resident computer and telephony resources. The “provisioning problem” is to make a set of interrelated decisions about how to allocate resources to services.

There are both technical and business constraints to consider in the provisioning process. On the one hand, a certain contractual commitment may be in effect which requires a certain level of service to exist. There is little latitude in meeting this constraint. On the other hand, a service may be provisioned at a level to maximize net revenue. This decision often involves “soft” market data and guesses about revenue potential, especially for new services.

In general, services are not provisioned independently from each other. Resource sharing may be feasible for some sets of services but others must be provisioned so that they do not share resources. This may be for contractual reasons (e.g., guaranteed service levels) or for risk minimization (i.e., “not putting all eggs in one basket”).

Providing a multitude of services must be done, in the short term, using existing resources. The available resource levels can be “stretched” but usually with some penalty such as excessive cost. So resources, like services, are subject to both “hard” and “soft” constraints.

Provisioning Procedures in Practice

There have been attempts to automate the provisioning of telephony services. A common problem encountered is the accumulation and access to appropriate data needed to make decisions. Much of the data needed to make provisioning decisions is surprisingly “soft”. Estimated traffic volume and patterns may be off by a factor of two or more. Usage of telephony resources should be reliable so critical services are often over-provisioned in order to (try to) guarantee a certain level of service even under adverse conditions.

In practice, a great deal of experience and insight is necessary in order to make good provisioning decisions. Automated decision procedures have not had a good track record and are not widely used. Many projects use resident “provisioning experts” who have sufficient experience with past provisioning practices and “rules of thumb” that they can often make reasonable, if not optimal, provisioning decisions. A typical scenario is that a person makes an informed decision about how to provision a new service and then considerable monitoring is done after the service “goes live”, to see whether the human decision is working well. Frequently, adjustments will be made after the service is deployed. This process is often expensive and error-prone. Better provisioning approaches are needed.

The current effort does not attempt to model a real provisioning system due to both the magnitude and complexity of the problem. Rather, some basic ideas from genetic algorithms, as presented in Goldberg [1], are applied to the provisioning problem in order to gain an understanding of their applicability to various aspects of the provisioning process.