臺灣博碩士論文加值系統

隨著網路世界爆炸性的成長，人們已經和網路環境緊密的結合。許許多多的人依賴著網路來處理各種事務，因此成千上萬的網站可能面對的工作量龐大到無法負荷，這樣的情況造成人們瀏覽網站的品質下降。面對著不堪負荷的情況，各網站除了隨著負荷的增加持續添購硬體設備以求提供令使用者滿意的品質，也應該從如何以有限的能力提供使用者最適當的需求來考慮。
在本論文中，我們先將網站工作量區分為服務使用者的檢索以及更新系統資料兩大類，在這兩類的工作中，希望至少能符合其中一類的需求後，也讓另一類工作能有好的效率。於是我們設計一個適當的演算法來提供系統對於這兩類的工作來做正確的排程。
這個演算法的主要精神在於根據伺服器的負荷以及工作要求產生的速率，來決定採取何種排程策略以求達到系統所定義之需求。而關於演算法細部的機制，可以分為三個部份來考量: 關於兩類工作要求產生速率的預測、利用queueing theory來判斷該採取何種策略，以及watermark的設定使用。
經過實驗模擬結果得知，此演算法在多種不同條件下都能準確的符合系統所定義之需求，並且使得另一類工作能夠得到不錯的效率。

With the explosive growth of the World-Wide-Web (WWW), people have integrated with the WWW closely. A large of number of people depend on network to manage various affairs. Thus, tens of thousands of Web sites may face enormous work load such that they cannot afford. This situation makes the quality of surfing the WWW decrease. Under this circumstance of inability, Web sites should try to find the resolution by considering how to provide the suitable service for user essential requirement with limited ability besides purchase additionally the machines to afford to users the satisfied Web quality.
In this thesis, we firstly divide the work of Web servers into process of user retrieval and process of data update. For two types of jobs, we hope that at least one type of them can be satisfied and then another type can have a good performance. Therefore, we design a proper algorithm to schedule both of the two types of jobs.
The main principle of this algorithm is to adopt a suitable scheduling policy according to the server load and the arrival rates of the retrieval and update types. And the detail mechanisms are considered in three parts: the arrival-rate prediction, the judgment of adopting scheduling policy based on the queueing theory, and the determination and the usage of the watermark.
According to the results of the simulations, this algorithm can accurately conform to the system-defined requirement under various conditions. At the same time, the other type of jobs will have a good performance.

摘要
Abstract
誌謝
Table of Contents
List of Figures
Chapter 1 Introduction
1.1 Main Jobs of Web Servers
1.2 Service Scheduler
1.3 Motivation and Objective
1.4 Organization of the Thesis
Chapter 2 Related Work
2.1 Related Scheduling Policies
2.1.1 Basic Scheduling Policies 7
2.1.2 Shortest-Connection-First Scheduling Policy
2.2 Analysis of Queueing System for Priority Scheduling
Chapter 3 Preliminary Work for System Model
3.1 Model of Queueing System with Two Queues
3.2 Mathematical Fundamental of the Proposed Queueing System
RTF
UTF
Chapter 4 Adaptive Requirement-Conformed Algorithm
4.1 Architecture of the Service Scheduler for ARCA
4.2 Terminology Definitions
4.3 Scheduling Controller
4.3.1 For Retrieval Requirement
Procedure of the Scheduling Controller
Watermark Determination
Arrival-Rate Prediction
Ending Condition
4.3.2 For Update Requirement 33
Procedure of the Scheduling Controller
Watermark Determination
Arrival-Rate Prediction
Ending Condition
4.4 Queue Manager
Chapter 5 Simulations and Results
5.1 Simulation Environment
5.2 Effects under Different Conditions: Server Loads, Requirement, and Coefficients of Watermark
5.3 Contrast: Watermark-Based Algorithm
5.4 Distribution of Response Time of Each Job
Chapter 6 Conclusions
Appendix
A. Mean Waiting Time under HOL with Two Classes
B. Mean Waiting Time under FCFS with Two Classes
Reference

[1] A. Aggarwal, J. l. Wolf, and P. S. Yu. Caching on the World Wide Web. IEEE Transactions on Knowledge and Data Engineering, 1999.
[2] Dimitri Bertsekas and Robert Gallager. DATA NETWORK. PRENTICE HALL, Inc., 1987.
[3] G. Barish and K. Obraczka. World Wide Web Caching: Trends and Techniques. IEEE Communication Magazine, 2000.
[4] John N. Daigle. Queueing Theory for Telecommunications. Addison-Wesley Publishing Company, 1992.
[5] Junghoo Cho, Hector Garcia-Molina. Synchronizing a Database to Improving Freshness. In Proc. of 2000 ACM International Conference on Management, 1999.
[6] Junghoo Cho and Hector Garcia-Molina. The Evolution of the Web and Implications for an Incremental Crawler. In Proc. of the 26th International Conference on Very Large Databases, 2000.
[7] Leonard Kleinrock, Queueing Systems. A Weley-Interscience Publication, 1975.
[8] Mar E. Crovella, Robert Frangioso and Mor Harchol-Balter. Connection Scheduling in Web Servers. In Proc. of 2nd USENIX Symposium on Internet Technologies and Systems, 1999
[9] Manit Satitsamitpong and Helen Thomas. Cache Freshness Optimization: Sliding Scale Guarantees. In Proc. of the 3rd International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems, 2001.
[10] Mor Harchol-Balter, Nikhil Bansal and Bianca Schroeder, Mukesh Agrawal. Implementation of SRPT Scheduling in Web Server. Technical Report CMU-CS-00-107, Carnegie Mellon University, 2000.
[11] S. Brin and L. Page. The Anatomy of Large-Scale Hypertexual Web Search Engine. In proc. of the 7th WWW conference, 1998.
[12] Silberschatz Galvin. Operating System Concept. Addison Wesley
Publishing Company, 1994.
[13] Vijay Gupta and Roy Campbell. Internet Search Engine Freshness by Web Server Help. In Proc. of 2001 Symposium on Applications and the Internet.
[14] http://www.search-engine-optimization-strategies.net/