«A LOCATION MODEL FOR WEB SERVICES INTERMEDIARIES By YI SUN A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL ...»
A LOCATION MODEL FOR WEB SERVICES INTERMEDIARIES
A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL
OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT
OF THE REQUIREMENTS FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY
UNIVERSITY OF FLORIDACopyright 2003 by Yi Sun I would like to dedicate this work to my family, especially my wife Ziya and our daughter Emily. Their love has supported me throughout all the hesitations and frustrations of this dissertation.
ACKNOWLEDGMENTSThis dissertation could not have been completed without the support, guidance and patience of a multitude of people. One individual is significantly responsible for my success, Dr. Gary Koehler. His willingness to patiently share his expertise coupled with high expectations encouraged me to seek excellence. I would also like to express my appreciation to the other members of my committee, Drs. Hsing Kenneth Cheng, Asoo J.
Vakharia, Haldun Aytug, and Joseph P. Geunes, for sharing their time and insights.
I also acknowledge my colleagues in the Ph.D. program for their unwavering moral support and friendship throughout my years in the program, especially Dr. Kutsal Dogan, Dr. Cheryl Aasheim, and Mr. Nihat Kasap.
I also thank my friends who have been patient, considerate and encouraging during my Ph.D program. Finally, I am forever indebted to my family, particularly my wife, Ziya Sun, for always believing in me.
TABLE OF CONTENTSPage ACKNOWLEDGMENTS
LIST OF TABLES
LIST OF FIGURES
CHAPTER 1 INTRODUCTION
1.2 Research Problem
1.5 Organization of Dissertation
2 WEB SERVICES
2.2.1 Definition of Web Services
2.2.2 Support and Framework
2.2.3 Standard and Protocol
2.3 Players and Implementations
2.4 Comparison with Earlier Technologies
2.5 Business Benefits and Potentials
3 FACILITY LOCATION MODELS AND WEB SERVICES
3.2 Location Models
3.2.1 Network Location Models
3.2.2 Discrete Location Models
3.3 Online Services
v 3.3.1 Network Latency and Response Time
3.3.2 Network Latency and Web Services
3.3.3 Measuring Network Latency and Proximity
4 MODLE FORMULATION
4.4 Model Setup
4.5 Objective Function
4.6.1 Web Services Usage Constraint
4.6.2 WSI Server’s Capacity and Client Assignment Constraint
4.6.3 WSP’s Capacity and WSI Assignment Constraint
4.6.4 Client Service Constraint
5 SOLUTIONS TO FACILITY LOCATION PROBLEMS
5.2 Exact Methods
5.2.1 Linear Programming Relaxation
5.2.2 Lagrangian Relaxation
5.2.3 Decomposition Method
5.3.1 Construction Heuristics
5.3.2 Improvement Heuristics
5.4 Multi-level Capacitated Facility-Warehouse Problem
6 HEURISTICS DEVELOPMENT
6.2 Overview of the DAL Heuristics
6.4 DROP Procedure
6.5 ALA Procedure
7 DATA COLLECTION AND ANALYSIS
7.2 Data Analysis
7.3 Network Locations and Latencies
7.4 Network Latency Measurement
7.5 WSI Servers Fixed Cost
7.6 WSP Fixed Fees
8 EXPERIMENTAL DESIGN
8.2 Experiment Environment and Setup
8.3 Performance Measures
8.3.1 Solution Quality
8.3.2 Solution Speed
8.3.3 Solution Robustness
8.3.4 Performance of ALA Compared with DROP
9 EXPERIMENTAL RESULTS
9.2 DAL Performance
9.2.1 Solution Quality
9.2.2 General Computer Times
9.2.3 Computer Times by the Dimensions of Web Services Vectors.................80 9.2.4 Test Results with Different Fixed Costs between WSI and WSP..............82 9.2.5 Robustness of DAL
9.3 Hypotheses Testing
9.3.1 Hypothesis 1: Communication/Latency Cost
9.3.2 Hypothesis 2: WSI Server and WSP Fixed Costs
9.3.3 Hypothesis 3: Client Demand
9.3.4 Hypothesis 4: Number of Web Services Shared per Sharing
9.3.5 Number of WSI Servers and WSPs
10.1 Project Overview and Contribution
10.3 Direction for Future Research
A CITY LISTS
B CITY DISTANCE MATRIX
C EXPERIMENTAL STUDY RESULTS FOR EFFICACY STUDY
D EXPERIMENTAL STUDY RESULTS FOR PARAMETOR STUDY..................169 LIST OF REFERENCES
4-1. Summary of Notation
7-1. A Service Plan from UpTown Web Hosting
8-1. Machine and Software Configurations
8-2. An Example of Base Values for a Problem.
8-3. Performance Test Class
8-4. Test Instance for Each Class.
8-5. Common Base Values for Test Problem Parameters.
8-6. Experiment Parameters.
9-1. Objective Function Value Gap between DAL and CPLEX
9-2. DAL Computer Times
9-3. CPLEX 8 Computer Times.
9-4. Computer Times with Two Dimensions of Web Services Vectors.
9-5. Computer Times with Eight Dimensions of Web Services Vectors.
9-6. Solution Quality Improvement of ALA over DROP.
9-7. Average DROP and ALA Computer Times
9-8. Test Results of Problems with Different WSI and WSP Location Costs..................84 9-9. Pearson Correlations: The Impact of Network Latency Cost on the Number of WSI Servers and WSPs.
9-10. Pearson Correlations: The Impact of WSI and WSP Fixed Cost on the Number of WSI Servers and WSPs.
9-12. Pearson Correlations: The Impact of Number of Web Services Shared per Transaction on the Number of WSI Servers and WSPs.
2-1. Web Services Roles and Operations
6-1. DAL Heuristics Flowcharts.
7-1. US Internet Backbone Networks with 40 City Locations and Connections..............62 9-1. Average Computer Times of DAL and CPLEX
9-2. DAL Computer Times by Dimensions of Web Services Vectors.
9-3. Average Computer Times for DROP, ALA and DAL Procedures (ALA Computer Times Are the Gap between the Times of DROP and DAL)........83 9-4. The Number of WSI Servers and WSPs for Each Latency Costs Decrement (Higher Values of the Denominator Mean Lower Latency Costs)........85 9-5. The Number of WSI Servers and WSPs for Each WSP and WSI Fixed Costs Increment.
9-6. The Number of WSI Servers and WSPs for Each Client Demand Increment..........88 9-7. Sharing between WSI Servers for Each Client Demand Increment
9-8. The Number of WSI Servers and WSPs for Each Number of Web Services Shared per Sharing Increment
9-9. Sharing between WSI Servers for Each Number of Web Services Shared per Sharing Increment
Chair: Gary J. Koehler Major Department: Decision and Information Sciences In the recent past, Web services have entered the competition for distributed ecommerce platforms. By exploiting existing open standards such as XML and HTTP, Web services promise unprecedented levels of interoperation between programs on different frameworks. Questions remain on how to capitalize on this new technology.
This dissertation attempts to answer the questions from a service location perspective. We focus on the behaviors of Web services intermediaries that serve as common interfaces to their clients and obtain Web services from independent Web services providers on behalf of their clients. The distributed nature of Web services and the ever-increasing prominence of network latency in determining server performance justify the study of locating servers of Web services intermediaries on the Internet to optimize their performance and/or financial goals. We propose a mathematical integer programming model to help these intermediaries decide on the locations and usage rates of their servers.
number of participants increases. We therefore develop an efficient heuristic method named DAL to tackle the problem. For the problems tested, the DAL heuristics provide near optimal solutions in short computer times and with limited computer memory usage.
In the recent past, Web services have entered the competition for distributed ecommerce platforms. They promise to deliver an unprecedented level of interoperation between programs written in different languages and running on different platforms by exploiting existing open standards, such as XML and HTTP. Because of modularization and open interfaces, Web services facilitate the development of highly customizable and adaptable applications to meet business demand. In addition, Web services offer a convenient service registration, search and discovery system. This system breeds a market of Web services intermediaries (WSIs) who, on behalf of their clients, search, assemble and customize various Web services at run time. It is this market on which we attempt to capitalize in this research.
Until recently, research on the performance of Internet services focused on increasing server processing speed, reducing transmission time, and shortening queuing delays. Network latency, which measures the time it takes for a signal to travel from one place to another on the network, was often ignored. Compared with other factors that influence service response time, especially on a slow network, network latency was often negligible. Nevertheless, because of recent changes in the networking environment, such as the prevalence of high-speed Internet communication, and because of the tremendous increase of computing power, studies (Johansson 2000; Jamin et al. 2001) suggest that network latency has begun to play a more important role in determining service response time. Minimizing service response time now requires decreasing the network latencies between servers and clients.
The network latency problem of Web services is even more prominent. Most Web services are offered on the Internet which, compared with a small and controlled environment such as an intranet, is famous for high latency. In addition, a WSI is involved to match his clients and Web services providers (WSPs). Therefore network latencies occur both between the WSI and his clients, and between the WSI and WSPs.
Network latency can be treated as an operating cost incurred by the WSI. This research attempts to develop a location model that capture the intricacies to minimize a WSI’s operating cost or maximize his profit. Furthermore, since the WSI can find and assemble Web services at run time, matchmakings are often done dynamically while minimizing latencies. This requires fast algorithms to solve the problem.
In this chapter, we provide an overview of our thesis, including a brief description of the model and its application environment, our motivation, and the research contribution. The research problem is presented in Section 1.2, the motivation for developing the particular model and the anticipated impact of this study are discussed in Section 1.3. The expected contributions and applications of this research are presented in Section 1.4. The organization of this dissertation is provided in Section 1.5.
A WSI serves as an interface to both his clients and WSPs. Since network latency is becoming an increasingly important factor that determines service performance, it is imperative for the WSI to find ideal locations that balance the expected loads between his clients and WSPs he may contact. The research problem is in designing a general model to describe the cost structures for a WSI with the understanding that network latency is treated as an operating cost. The WSI needs to determine where to locate his servers and how many servers to deploy. At the same time, the model asks the WSI to choose appropriate WSPs who offer Web services at different prices and with different performance and capacities. To capture the level of customization that Web services offer, the model allows the WSI to map each client request to a vector of the Web services needed to process the request.
This is a capacitated and fixed cost mixed integer mathematical programming problem. As expected, the proposed model becomes computationally intractable as the number of participants increases. We therefore address the question to ascertain if heuristics can be employed to solve the problem.
The primary motivation for studying this problem is to acknowledge the need for models that solve WSI location problems. Web services have been touted as the “next big thing” by industry analysts. This technology promises to alleviate organizations’ concerns for interoperability in areas such as Enterprise Application Integration (EAI) and Business-to-Business Integration (B2BI). The development managers seek to jump on board to cut development and integration cost.
There are many uncertainties around the deployment of Web services and the capitalization on this new technology. Questions include, for example, what is the appropriate pricing scheme for a WSI? How many servers should he set up to meet his objective? Where should he position his servers to be exposed to his clients and WSPs?
Without definitive answers to these questions, businesses are hesitant to commit to Web services. In this paper, we attempt to answer some of these questions. The main purpose of this dissertation is to provide a framework that guides a WSI to set up his services.
Our model derives from the well-developed literature of facility location models.