臺灣博碩士論文加值系統

由於斷線問題和用戶端具有行動能力，傳統的快取無效驗證方法不適用於無線環境。一個已提出的方法，是利用伺服器周期性的發布〝無效報告〞來維持快取的一致性。然而，同類型的方法皆具有一個共同的缺點：使用者必須等到下一次的無效報告來臨，才能回應現在的請求。本篇論文中，我們提出了一個合適的方法來改善這個缺點。藉由用戶端發送一個〝提早確認〞的訊息，使用者可以盡快的回應目前的請求。而在伺服器端，我們提出了一個具有彈性的改良：藉由對〝提早確認〞訊息的統計，伺服器會在其能力範圍內，動態地調整〝無效報告〞的廣播週期進而達到減少延遲的效果。模擬的結果明顯地顯示我們的方法減少了平均的等待回應時間。

Traditional cache invalidation strategies are not suitable for mobile environments due to frequent disconnections and mobility of the clients. One proposed solution is based on invalidation reports (IRs). However, the common main drawback of the IR-based scheme is that it takes a long time to answer a query since a client has to wait for the next IR to keep cache consistent. In this paper, we propose an adaptive solution to improve this problem. By usage of early validation messages, a client can get response as fast as possible when cache hit happens. We then define a parameter as a criterion on the server side and the server can further adjust the IR interval dynamically in its capability. Simulation experiments are made with proposed scheme to evaluate the performance. The result represents that usage of early validation messages significantly reduce the query latency.

Chapter 1 Introduction 1

Chapter 2 Related Work 9
2.1 Broadcast timestamp 10
2.1 Bit–Sequence (BS) 11
2.1 Updated Invalidation Report (UIR) 14

Chapter 3 Proposed Schemes 19
3.1 Key assumptions 19
3.2 Early validation messages 20
3.3 The hit ratio 25
3.4 Adjusting the interval 27
3.5 The Q/U bit 30
3.6 Replacement 33

Chapter 4 Performance 37
4.1 The simulation environment and parameters 37
4.2 The response time 38
4.3 The clients' hit ratio 47

Chapter 5 Conclusion 49

Reference 50

[1] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast Disks: Data Management for Asymmetric Communication Environments,” Proc. ACM-SIGMOD, Int’l Conf. Management of Data, San Jose, pp. 199-210, June 1995.

[2] Howard, J., Kazar, M., Menees, S., Nichols, D, Satyanarayanan, M., Sidebotham, R., and West, M. “Scale and Performance in a Distributed File System,” ACM Transactions on Computer Systems, 6(1):51–58, February 1988.

[3] Nelson, M., Welch, B., and Ousterhout, J. “Caching in the Sprite Network File System,” ACM Transactions on Computer Systems, 6(1), February 1988.

[4] D. Barbara and T. Imielinski, “Sleepers and Workaholics: Caching Strategies in Mobile Environments,” Proc. ACM SIGMOD Int’l Conf. Management of Data, vol. 23, no. 2, pp. 1–12, May 1994

[5] T. Imielinski, S. Viswanathan and B. Badrinath, “Data on Air: Organization and Access,” IEEE Trans. Knowledge and Data Eng., vol. 9, pp. 353-372, May/June 1997.

[6] J. Jing, A. Elmagarmid, A. Helal, and R. Alonso. “Bit-Sequence: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments,” Mobile Networks and Applications, vol. 31, no. 2, pp. 115-127

[7] G. Cao, “A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments,” ACM Int’l Conf. on Mobile Computing and Networking (MobiCom), pp. 200–209, Aug. 2000.