耐延遲網路之可適性網路編碼資料路由機制

Adaptive Network Coding Based Routing in Delay-Tolerant Networks

張嘉惠(Chia-Huei Chang)

指導教授 ： 周承復

共同指導教授 ： 陳伶志

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.01337

摘要

耐延遲網路(Delay-Tolerant Network)與傳統網際網路的不同點在於發送端與目的端之間不一定存在有一條點到點的資料路由路徑，而以往所提出的網際網路架構及路由協定卻需要有從發送端到目的端的點到點路徑，因此耐延遲網路這樣的網路型態需要另外設計適合的路由機制。用於高移動性的移動隨意網路(Mobile Ad Hoc Network)的傳輸機制Epidemic Routing，因為資料傳送到目的端是靠著節點的移動將資料散佈出去，所以不需要事先決定資料路由路徑，因此可用於耐延遲網路的資料傳輸，但是Epidemic Routing卻會造成網路整體的傳輸負荷過大以及消耗大量的資源。本篇論文以類似Epidemic Routing的方式散佈資料，同時以網路編碼(Network Coding)技巧對資料做編碼處理，設計一個使用較少的網路資源卻有高資料送達率的資料路由機制。
可適性網路編碼資料路由機制根據節點成功傳送資料的能力選擇適合的傳送節點，並且隨著網路連線情況調整代表資料複製份數的冗餘程度以控制傳送過程中所消耗的資源量。透過運用真實網路連線情況紀錄的模擬實驗可驗證我們所提出的路由機制的效能。實驗結果顯示我們的機制可有效減少資源使用量、改善資料送達率、降低資料傳送的延遲時間。

關鍵字

耐延遲網路 ； 網路編碼 ； 資料路由 ； 機率路由 ； 臨機網路

並列摘要

Delay-tolerant networks, which are different from conventional networks, do not always have a complete path between the source and the destination. On the other hand, the conventional network architectures and routing protocols require at least one end-to-end path between the source and the destination pair, thus we have to design new routing strategies adapted to delay-tolerant networks. Since the Epidemic Routing proposed for mobile ad hoc networks (MANETs) transfers data via node mobility, it doesn’t have to decide a complete path before forwarding data. However, although Epidemic Routing is useful for transferring data in delay-tolerant networks because of the above reason, it causes undesirable traffic overhead and consumes too much network resources. In this thesis, we propose a data forwarding scheme with low resource consumption and high data delivery ratio which is based on Epidemic Routing and employs Network Coding to increase throughput.
Adaptive network coding based routing scheme combines the advantages of knowledge-based strategies with replication-based strategies. It predicts node’s delivery probability based on contact history, and then uses the probability to select relays. Besides, it adapts the redundancy according to delivery ratio in order to control the resource consumption. From simulations on real network scenarios, we verify the efficiency of our proposed scheme. The simulation results show that our proposed scheme can effectively reduce resource consumption and improve data delivery ratio, as well as decrease end-to-end delay.

並列關鍵字

Delay-Tolerant Network ； Network Coding ； Data Routing ； Probabilistic Routing ； Opportunistic Network

參考文獻

[1] K. Fall. A delay-tolerant network architecture for challenged Internets. In Proceedings of ACM SIGCOMM, pp. 27-34, August 2003.

[3] J. Alonso, K. Fall. A linear programming formulation of flows over time with piecewise constant capacity and transit times. Intel Research Technical Report IRB-TR-03-007, June 2003.

[4] S. Jain, M. Demmer, R. Patra, and K. Fall. Using redundancy to cope with failures in a delay tolerant network. In Proceedings of ACM SIGCOMM, pp. 109-120, October 2005.

[5] T. Small and Z. J. Haas. Resource and performance tradeoffs in delay-tolerant wireless networks. In Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN’05), pp. 260-267, August 2005.

[6] S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K. Scott, and H. Weiss. Delay-tolerant networking: an approach to interplanetary internet. In IEEE Communications Magazine, vol. 41, pp. 128-136, June 2003.