在有限資源限制下的非對稱式冗餘消除演算法

A Resource-Constrained Asymmetric Redundancy Elimination Algorithm

李育賢(Yu-Sian Li)

指導教授 ： 徐正炘

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

本論文針對高速通訊網路下非對稱的頻寬和資源問題，提出了一個在有限資源下的非對稱冗餘消除演算法(RCARE) ，利用多餘的下載頻寬和接收端的資源，以加速上傳的數據傳輸。該系統可以部署於客戶端或代理伺服器上。RCARE 與現有的非對稱演算法不同，它使用更加靈活的匹配機制來識別冗餘資料，並使用一個傳送端的暫存器吸收過高的下載流量。和現有的冗餘消除演算法相比，它提供了一個可根據資源與效能調整的傳送端暫存器。我們從多個伺服器和校園網路記錄了真實的流量資料，並利用這些資料評估RCARE 的效能。由我們的模擬結果顯示， RCARE 可比目前的非對稱式通訊演算法達到更高的上傳增益，以及更低的下載流量。我們也為有限資源的傳送端設計了動態調整演算法。此演算法可根據目前的樣本資料，預測並分配資源給目前的數據流，以達到最大的上傳增益。與平均分配資源的基準演算法相比較，動態調整演算法提高了高達87％ 的上傳增益。在前 10% 的實驗結果中( 以最佳的上傳增益排序) ， RCARE 平均達到了高達 40.5% 的上傳增益。

關鍵字

非對稱式傳輸 ； 物聯網 ； 網路協定 ； 效能評估

並列摘要

We focus on the problem of efficient communications over access networks with asymmetric bandwidth and capability. We propose a resource-constrained asymmetric redundancy elimination algorithm(RCARE) to leverage downlink bandwidth and receiver capability to accelerate the uplink data transfer. RCARE can be deployed on a client or a proxy. Different from existing asymmetric algorithms, RCARE uses flexible matching mechanism to identify redundant data, and allocates a small sender cache to absorb the high downlink traffic overhead. Compared to redundancy elimination algorithms, RCARE provides a scalable sender cache which is adaptive based on resource and performance. We evaluate RCARE with real traffic traces collected from multiple servers and a campus gateway. The trace-driven simulation results indicate that RCARE achieves higher goodput gains and reduces downlink traffic compared to existing asymmetric communication algorithms. We design an adaptation algorithm for resource-constrained senders sending multiple data streams. Our algorithm takes samples from data streams and predicts how to invest cache size on individual data streams to achieve maximal uplink goodput gain. The adaptation algorithm improves the goodput gain by up to 87% compared to the baseline. In first 10% of data streams (sorted by the optimal goodput gains), RCARE achieves up to 40.5% goodput gain on average.

並列關鍵字

Asymmetric communications ； Internet-of-things ； network protocols ； performance evaluation

參考文獻

[2] G. Aceto, A. Dainotti, W. De Donato, and A. Pescape. Portload: Taking the best of two worlds in traffic classification. In Proc. of IEEE INFOCOM’10, pages 1 –5, march 2010.

[3] M. Adler and B.Maggs. Protocols for asymmetric communication channels. Journal of Computer and System Sciences, 63(4):573–596, December 2001.

[8] L. Atzori, A. Iera, and G. Morabito. The Internet of things: A survey. Computer Networks, 54(15):2787–2805, October 2010.

[9] H. Balakrishnan and V. Padmanabhan. How network asymmetry affects TCP. IEEE Communications Magazine, 39(4):60–67, April 2001.

[10] P. Bose, D. Krizanc, S. Langerman, and P. Morin. Asymmetric communication protocols via hotlink assignments. Theory of Computing Systems, 36(6):655–661, November 2003.