臺灣博碩士論文加值系統

隨著網際網路以及相關基礎設施的普及, 愈來愈多的應用已經提供即時、變化快速的動態資料服務。這些即時性的資訊包括財經資訊、天氣預測以及運動比賽轉播等等。傳統的資料傳遞方式可以分為Pull跟Push兩種常見技術, 對於傳遞動態的資料而言, 這兩種方式各有其可互補的優缺點。資訊的傳遞主要必須考量一致性的要求, 也就是在提供內容服務給廣大使用者的同時, 必須滿足使用者對於資料正確程度的要求。對於一般web server常用的HTTP protocol, 使用者必須根據資料的變化率以及對於一致性的要求來Pull 資料。至於具有Push能力的server可以只主動傳遞使用者覺得重要性較高的資訊。
雖然使用Push方式可以有較高的資料傳真度, 但是server卻需要針對每個使用者跟資料類別記錄額外的state狀況; 這樣的系統一但發生server failure, 就無法繼續提供原來的服務。這篇論文主要是提出一個方法, 適當的結合Push跟Pull兩種技術, 在有限的Push跟Pull使用次數下, 有效率的分配資料傳遞時間點, 儘可能滿足使用者對於資料傳真性的需求。我們將提出的方法與傳統的方式進行比較, 實驗結果顯示我們的方法比傳統的方式有較高的資料正確性, 在時間上的分配也較合理; 跟傳統方法相比, 即使使用者一開始給定的一致性要求與實際資料變化差異過大, 透過我們的調整機制, 可以有效的提升資料傳真度, 並且避免Push資源提早用完的問題。

An increasing fraction of the data disseminated through the Internet varies frequently and unpredictably. These time-varying data are generally used in real-time information delivery applications, such as stock update, weather data and sports score.
Nowadays, most of the web servers running the HTTP protocol, clients need to regularly pull the time-varying data according to the variation of the occurrences received by the clients. However, the effective and reliable approach is pushing from the server. That is, a server with push capability retains state information affiliated to clients then pushes only those changes that are of interest to the clients. Yet, the server bandwidth and the network bandwidth are both limited, the total number of push and pull is restricted by a prior bound. So, the foundation of pushing and pulling time-varying data is to maintain the coherency control as well as to regulate the pull interval simultaneously. Note that these push and pull techniques are complementary to each other. In pure pull approach, the degree of temporal coherency attained is relatively low while in pure push approach, it is rather high.
In this thesis, we present an interaction mechanism for incorporating both push and pull techniques. First, an approach that adaptively adjusts the pull interval due to the variation of the perceived data is presented. Then, we utilize push events to deal with unpredictable spike using the coherency control. Finally, we let the push event adjusts the pull interval to prevent the ineffective pulls. Besides, several dimensions have been compared in our results: communication overhead, temporal coherency and fidelity. Experimental results indicate that the proposed adaptive time-varying data dissemination is expected to meet diverse coherency control and for the effective and scalable utilization of server and network resources.

Chapter 1 Introduction 1
Chapter 2 Related Works 4
2.1 Internet Notification Services using Web Push 6
2.2 Push-Based Web Content Dissemination 7
2.3 Using Multicast and Hybrid approaches 9
Chapter 3 Adaptive Push-Pull Methods 10
3.1 The Adaptive Time-to-Refresh Algorithm 10
3.2 The Push-Pull Algorithm 11
Chapter 4 The Adaptive Push-and-Pull Algorithm with Floating Coherency 13
4.1 Uniform distributed Pulls 13
4.2 Demand Pull and Fixed Coherency Push 15
4.3 Demand Pull and Dynamic Coherency Push 16
4.4 The Balanced Push-Pull 18
Chapter 5 Performance Evaluation 20
5.1 Communication Overhead 20
5.2 Computational Overhead 20
5.3 Space Overhead 21
5.4 Number of Redundant Pulls 21
5.5 The Tradeoff between Fidelity and Cost 22
Chapter 6 Experimental Results 24
6.1 Comparison between the uDP and DPFCP Algorithms 24
6.2 The Comparison 27
Conclusions 33
References 34

[1] P. Deolasee, A. Katkar, A. Panchbudhe, K. Ramamritham and P. Shenoy, “Adaptive Push-Pull: Disseminating Dynamic Web Data,” 10th WWW Conference May 1-5, 2001, Hong Kong.
[2] P. Deolasee, A. Katkar, A. Panchbudhe, K. Ramamritham and P. Shenoy, “Adaptive Push-Pull of Dynamic Web Data,” IEEE Transactions on Computer, 2002.
[3] Pumatech Mind-It, http://www.pumatech.com/mymindit_main.html
[4] Infogate, http://www.infogate.com/
[5] S. Acharya, M. J. Franklin and S. B. Zdonik, “Balancing Push and Pull for Data Broadcast,” Procs. of the ACM SIGMOD, May 1997.
[6] E. Amir, S. McCanne and R. Katz, “An Active Service Framework and its Application Real-time Multimedia Transcoding,” Proceedings of the ACM SIGCOM Conference, pages 178-189, September 1998.
[7] G. R. Malan, F. Jahanian and S. Subramanian, Salamander, “A Push Based Distribution Substrate for Internet Applications,” Proceedings of the USENIX Symposium on Internet Technologies and Systems, December 1997.
[8] G. Banavar, T. Chandra, B. Mukherjee, J. Nagarajarao, R. R. Strom, and D. C. Sturman, “An Efficient Multicast Protocol for Content-based Publish-Subscribe Systems,” International Conference on Distributed Computing Systems 1999.
[9] P. Cao and S. Irani, “Cost-Aware WWW Proxy Caching Algorithms,” Proceedings of the USENIX Symposium on Internet Technologies and Systems, December 1997.
[10] Raghav Srinivasan, Chao Liang, and K. Ramamritham, “Maintaining Temporal Coherency of Virtual Warehouses,” Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS98), Madrid, Spain, December, 1998.
[11] J. Gwertzman and M. Seltzer, “World-Wide-Web Cache Consistency,” Proceedings of 1996 USENIX Technical Conference, January 1996.
[12] C. Liu and P. Cao, “Maintaining Strong Cache Consistency in the World-Wide-Web,” Proceedings of the Seventeenth International Conference on Distributed Computing Systems, pages 12-21, May 1997.
[13] V. Duvvuri, P. Shenoy, and R. Tewari, “Adaptive Leases: A Strong Consistency Mechanism for the World Wide Web,” Proceedings of IEEE INFOCOM'2000, Tel Aviv, Israel, March 2000.
[14] S. Brandt and A. Kristensen, “Web Push as an Internet Notification Service,” http://keryxsoft.hpl.hp.com/
[15] T. Wong, “Push-Based Web Content Dissemination Service,” MASH project, http://bmrc.berkeley.edu/~twong/research/push-poster/ , 1998.
[16] Carl A. Waldspurger, “Lottery and Stride Scheduling: Flexible Proportional Share Resource Management,” Ph.D. dissertation, September 1995.
[17] V. Kumar, “MBone: Interactive Multimedia On The Internet,” Macmillan Publishing, November 1995.
[18] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, “RTP: A Transport Protocol for Real-Time Applications,” Network Working Group, January 1996, RFC 1889, http: //www.ietf.org/rfc/rfc1889.txt.
[19] M. Day, J. F. Patterson, and D. Mitchel, “The Notification Service Transfer Protocol (NSTP): infrastructure for synchronous groupware.”
[20] The Minstrel Push System Project. Distributed Systems Group, Technical University of Vienna, 1999, http://www.infosys.tuwien.ac.at/Minstrel/.