行動網際網路之群播支援

Abstract

網路之間的資訊散佈經常利用群播(multicast)的技術來達成，此亦為 建構分散式系統之重要機制之一。現今由於無線通訊的發展，行動使用 者在可攜式電腦加上無線界面，便得以在任何時刻、地點連上網路，進 行資料存取、檔案傳輸等工作。這種新型態的網路環境提供了我們更多 便利的服務與應用，然而，卻也由於使用者的可移動性，使得既有的群 播機制無法正確或有效率地運作。其中之一重要缺陷是：原先用以連接 所有群組(group)成員的繞送路徑(route)將不再反映組員們所在的真正 位置，某些行動主機可能將因此無法接收到訊息。所造成的資料漏失， 定會對須要可靠傳輸之通訊協定以及應用軟體產生若干不利影響 ---- 譬如繁複的錯誤更正(error recovery)與非循序的資料遞送。另一方 面，倘若欲隨時依行動主機位置來建置繞送路徑，卻又很可能引發過高 的系統負擔。 本論文對於上述幾個問題，提出一些改進方式。我們在群組成員仍維持 著繞送路徑相連，如此便可讓資料有效率地遞送，同時也減少資料漏失 的情形發生。為了降低動態整繞送路徑所需之花費，我們設計了以下二 個方法： 一､利用使用者移動經常具區域性(locality)的特性，我們將行動主機 在過去一段時間中所拜訪的網路，均保留在繞送路徑上。如此一來，只 要同一群組的使用者在這些保留的網路範圍內漫遊，繞送路徑仍不致需 經常變動。 二､我們將網際網路劃分成若干個大型區域，例如以學校或企業為單 位，並將整個通訊環境視為由這些大區域網路所構成，每個區域視為一 個體。使用者在同一大區域內移動所造成的繞送路徑改變將會被侷限在 該區域內；區域外的繞送路徑將不需作改變，因此能大大地降低系統負 擔。 我們所提出的方法，經由效能分析模型所得之評估結果顯示確實有其價 值。為了更能有效地支援群播機制，除了主機可移動性的問題之外，吾 人尚須克服其他方面的難題。這些問題主要源自於傳統的通訊協定並未 考量到行動網路環境的特殊屬性，例如行動主機的資源嚴重受限以及不 穩定的無線通訊品質等等。我們認為有必要將協定作功能切割，僅把比 較簡單的執行步驟留給行動主機，其它較複雜的工作便交給固定網路的 節點來完成。在此，我們特別考慮一重要的傳輸層服務(transport service)，其可令群組成員皆能依照當初信息發生的前後因果(causal) 關係，來循序地收取信息，系統中各個分散的程序也將能因而達到相當 程度的一致性。為此，我們利用主從架構的觀念，發展了二個具優良擴 張性(scalable)的協定。整個網路環境中的因果次序，可藉由每個交換 站台(switching station)對其旗下的行動主機群所產生的信息作單一 排序，併在交換站台之間執行一傳統分散式因果演算法來達成。我們所 提出來的因果次序協定可被證明優於其他現有的方法；所需的複雜度較 小並且可適用於為數眾多的行動使用人口。

Multicast is a communication paradigm widely used for information dissemination, and is one of the most important facilities for constructing reliable, distributed cooperative applications. The current trend towards ubiquitous computing has resulted in the development of wireless Internet, aiming to provide users with convenient anytime and anywhere accesses to the network. The introduction of host mobility, however, challenges the deployment of multicast in this environment. For example, since a multicast delivery path locates all the participants in a given group, the path can become obsolete upon members' movements. Migrant hosts may therefore experience substantial data loss. As a consequence, this can overwhelm the protocols that require reliable ordered message delivery, due to repeatedly performing error recovery and handling out-of-order message arrivals. On the other hand, if we restructure multicast delivery paths in the system along with host migrations, prohibitive cost could result. In this thesis, we present approaches to the above problems. First of all, two cost-effective schemes, both sharing the same routing efficiency, provide leverages to adjusting multicast delivery paths to mobile host locations. To save the overhead of dynamically modifying the paths, one way is to exploit the locality in host movement patterns and keep active the networks that mobile members visited most recently. Therefore as long as hosts of the same group migrate within these active networks, the established paths need not change in the event of users' mobility. Alternatively, we can partition the mobile environment into non-overlapping regions, so that changes in multicast routes upon participant intra-region movements are localized within the region. In this manner, topology alterations are mostly hidden from other regions. The afore-mentioned solutions prove to be promising. Despite this, we still need to tackle some issues other than host mobility to support Internet multicast. These issues mainly stem from that conventional protocols do not take into account important characteristics of a mobile system, such as tight resource constraints on mobile hosts and lossy communication links. In particular, here we are concerned with an essential transport service that orders multicast messages in light of a potential causality relation. Given this support, group members can observe consistent ordering of events affecting the group as a whole. Otherwise multicast messages may be misinterpreted. To this end, we propose two scalable protocols by organizing the system into a client-server model. Causally ordered delivery results from serializing messages by mobile clients within the administrative realm of each switching station and using these stations to maintain server-level causal order. These proposals are effective to accommodate the explosive growth of mobile users in the future, and exhibit lower complexity than counterpart protocols.