臺灣博碩士論文加值系統

網路快取路徑選擇及資料複製之設計與模擬(Path Selection and Data Replication in Web Caching)，從使用著的觀點與網路路徑快取運用上，選擇適當的路徑與網路快取，使得傳輸與快取的成本最低，並且符合個人在不同的使用時間上的要求。在此採用一個有效率的線上排程與網路服務控管的機制，同時設計一個有效率的網路快取傳輸的演算法，讓網路快取伺服器決定何時、何地、在多久的時間內必須被儲存或是複製，在何時、何地因為使用者的要求而傳送。
在本論文中，我們選擇多種不同的路徑選擇來建立網路的圖形結構，並加入演算法中對於多址傳輸Steiner tree所建立起來的樹狀結構，根據不同傳輸結構下的模擬結果，分析並找出一個最佳化的快取傳輸模式，在複製與傳輸花費最小的模式下滿足在不同網域的子網路中，不同使用者在不同時間的要求下，達到系統管理的最佳化模式。

This thesis deals with ''Path Selection and Data Replication in Web Caching'', in order to minimize costs for transmission and replication in the network. Taking into account the user's viewing time and costs of web caching transmission and
replication, the goal is to choose an optimal solution to decrease costs the transmission and replication cost, while meeting the need of individual user's viewing time in different local severs. So we must find an efficient on-line schedule and network service control mechanism, as well as construct and design an efficient transmission and replication algorithm in web caching. The techniques consider the individual costs of storage and transmission of object programs and compute caching schedules for programs by determining when, where and how long object programs must be stored at strategic locations in the network. We design different network transmission models to construct different network topologies to simulate. We also deal with what is known as the Steiner problem in our network model. Since the Steiner problem in networks is NP-complete, it is practical to develop heuristic algorithms whose costs are close to optimal. In this thesis, we survey previous multicast routing algorithms in the networks and include heuristic algorithms based on the concept of Minimal Cost Path and Distance Network heuristic Steiner tree in the networks.
Keyword: Web caching, the Steiner problem in networks, Multicast tree, on-line algorithm

1 INTRODUCTION
2 RELATED WORK
2.1 Review for Determining an Optimal Caching Schedule
2.2 Review of some Shortest Paths problems
2.3 Review of a Multimedian heuristic problems
2.4 Review of a Design Guidelines for Distributed Network
Caches
2.5 Multicast Routing Protocol
2.6 Review of Multicast Routing Algorithm
2.7 Approximation Algorithm for Steiner Trees
3 WEB CACHING: TRANSMISSION AND REPLICATION
3.1 The Problem Formulation
3.2 System Control and Schedule Replication
3.3 The Network Models and Evaluation
4 SIMULATION
4.1 Evaluation Methodology
4.2 Numerical Results
5 CONCLUSIONS AND FUTURE WORK

Y. Amir, D. Shaw, ``WALRUS- a Low Latency, High Throughput Web Service Using Internet-wide Replication'', by the Defense Advanced Research Projects Agency (DARPA).
S. K. Baruah, ``On-Line Scheduling to Maximize Task Completions'', IEEE, 1994.
A. Belloum and L. O. Hertzberger, ``Document Replacement Policies dedicated to Web Caching'', IEEE, SEPTEMBER 1998, PP. 14-17.
T. Billhartz, J. B. Cain, E. Farrey-Goudreau, D. Fieg and S. Gordon, ``Performance and Resource Cost Comparisons for the CBT and PIM Multicast Routing Protocols'', IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, Vol. 15, NO. 3, APRIL 1997.
C. Bouras, V. Kapoulas, G. E. Pantziou and P. G. Spirakis, ``Competitive Video on Demand Schedulers for Popular Movies'', it ACM PODC, 1996.
S. W. Carter and D. E. Long, ``Improving bandwidth efficiency of video-on-demand servers'', Computer Networks, 31 (1999) pp. 111-123.
J. Cho and J. Breen, ``Analysis of the performance of dynamic multicast routing algorithms'', Computer Communications, 22 (1999). pp. 667-674.
J. Cheriyan, R. Ravi, ``Approximation algorithms for network problems'', September 1998.