Cristina Duarte Murta1
|
Tarcísio Paulo Corlassoli2
|
1Department of Computer Science -
Federal University of Paraná
POBox 19081 - 81531990
Curitiba PR Brazil
2Federal Center of
Technological Education - Paraná
Department of Computer
Science - 85503390 Pato Branco PR Brazil
Scheduling policies for Web servers have been designed
to improve the delay at the servers, which may comprise a significant
fraction of the response time. However, these policies have not taken
into consideration the interaction between the server system and the
host TCP implementation. Web servers are mainly used in the wide-area
Internet, which presents high variability in bandwidth, round-trip
time and packet loss characteristics. This paper presents a new
scheduling policy for the processing of the static HTTP requests in
Web servers. This policy, called FCF (Fastest Connection First),
gives priority to HTTP requests based on the size of the requested
file and on the throughput of the user connection. The requests for
smaller files issued through faster connections receive the higher
priorities. Our goal is to improve the mean response time. This
policy takes into consideration the interaction between the server
system and the TCP implementation at the server. We compare FCF to
FIFO and SRPT policies. We find that FCF gives the best mean response
time, although SRPT provides the shortest server delay. We conclude
that the scheduling policy should be aware of the WAN conditions and
take them into consideration to set up priorities to the requests.
Web servers service requests from a large and heterogeneous user population. The diversity of the user characteristics is shown not only by their culture, idiom and geographical differences but also by their hardware and software platforms and their connectivity conditions. The connection bandwidth of the Web users presents high variability. The link capacity goes from a 14.4 Kbps modem to a 10 Mbps connection. Besides the high variability of the capacity of the user connections, dynamic factors contribute to increase the variability of the connection speed such as congestion, number of hops in the TCP connection path, network and router delays, bottleneck links, and the characteristics of the TCP implementations.
Scheduling policies for Web servers have been designed to improve the delay at the servers, which may be an important part of the response time. It has been shown that the performance of the Web servers is affected by the Internet traffic. Nevertheless, the scheduling policies proposed for web servers do not take into consideration the interaction between the server system and the host TCP implementation, which handles the TCP connections at the server. Previous work has shown that when the size of the file requested is the main criterion for the scheduling policies, very good improvements in the server response time are observed in relation to policies that make no use of this information. In fact, it has long been known that SRPT (Shortest Remaining Processing Time) has the best mean response time of all scheduling policies.
This paper proposes a new scheduling policy for Web servers that exploits the high variability of the Web, observed in two of its characteristics: the speed of the connections and the response file size. The new idea is to explore the variability of the connectivity conditions of the Web clients. The proposed policy gives the highest priority to the request issued through the connection that will be completed first, that is, the connection that will have the smallest connection time. The fastest connection is the one that has requested the smallest document and has the best connectivity conditions (large bandwidth, low latency, no congestion). Our goal is to improve the user-perceived performance, the response time seen at the client side. The proposed policy is called Fastest Connection First (FCF).
A policy that gives priority at the server to the requests issued through fast connections will reduce the service time of these requests and the life time of the respective connection. When a connection is closed, the server resources reserved to that connection will be available for the new connections. When a server gives priority to the users with the best connectivity conditions, it is helping to keep the response time according to the user expectation. The users connected by very fast connections want to experiment very small response times. FCF aims to serve each request as fast as the throughput of its respective connection. The main issue of our policy is to assure that the buffers of the faster connections will receive data quickly from the file system. We show that FCF can reduce the mean response time compared to other policies.
FCF policy gives priority to the processes according to some characteristics of the specific request issued. The next process to get the resource is the one with the highest priority. The priority is based on two parameters: the throughput of the connection and the number of bytes to be processed. The idea is to give priority to the request whose connection can be finished first, that is, the smallest request issued through the fastest connection (the one with the best transmission rate). The transfer rate depends on the connectivity conditions of the user as well as the dynamic behavior of the Internet.
The FCF policy algorithm has two steps. First, it searches the request queue for the request with the shortest remaining number of bytes to process. Second, it searches the queue again for all requests whose size is smaller than the smallest one times some constant (called beta). From those, we choose the one with the highest estimated throughput. Beta defines the range of the second search and the trade-off between size and throughput. When beta is large, we are giving priority to throughput. On the other side, when beta is small (close to 1), we are giving priority to the remaining size of the request.
Web requests are served through a TCP connection. Due to the TCP congestion control, a small number of packets is sent each time, while the remaining packets must wait for the ack confirmation package . The acks from the fast connections arrive first and then new packets can be sent through these connections. The FCF policy aims to ensure that the socket buffers of the fast connections will always have data to be sent as soon as the ack arrives. To have the packets ready to be sent, the server must give priority to the requests at the CPU, at the disk and at the network interface. The buffers of the fast connections must receive the data from the disk as soon as the acks arrive. When the load on the server is light or moderate, the connection buffers usually have the data to send as the ack arrives, no matter the scheduling policy. Nevertheless, when the server is overloaded, giving priority to the small requests issued through fast connections will ensure that the buffers of these requests will have data to transfer when the acks arrive. As a consequence, when priority is given to the requests issued through fast connections at the server, these requests will be able to finish quickly, releasing the resources at the server to the requests waiting in queue.
3. Experimental Methodology and Summary of Results
To show the effectiveness of our proposal, we simulated FCF and compared it to SRPT and FIFO policies. We built simulation models for the server and the Internet. The workload was modeled using SURGE. The server model includes CPU, disk and network interface resources. The TCP and HTTP protocols were modeled, including RTT, congestion and packet loss characteristics. We evaluate the effectiveness of FCF scheduling policy in terms of mean response time and mean server delay. We also make analysis of the starvation of the large files, and of the starvation of the slow connections. In the full paper [1], we describe in details the simulation model, the workload characterization, and the results of the performance evaluation over a range of response sizes, connectivity conditions and server loads.
Figure 1 shows the result for the most important metric, the mean response time. The response time includes the server delay and the transmission time. FCF has consistently the best results at all loads, with higher gains as the load is increased. Although FCF policy has not the best server delay (SRPT provides the shortest server delay), the interaction done with the server and the TCP implementation leads to the best results in response time.
4. Conclusion
The information sharing between a Web server system and the TCP connections running in the server is exploited in this paper to propose a new scheduling policy based on the throughput of the user connection. The proposed policy, FCF, improves the most important user-oriented metric, the mean response time, which makes FCF a particularly appealing policy. We conclude that the scheduling policy should be aware of the WAN conditions and take them into consideration to set up priorities to the requests. We are currently working on the FCF implementation based on Linux and Apache Web server.
References
[1] C. D. Murta and T. P. Corlassoli, Fastest Connection First: A New Scheduling Policy for Web Servers. Technical Report RT001/2002, Federal University of Parana, Department of Computer Science.