Research On Overlay Routing Mechanisms Based On Network Coordinates

Overlay network technology has been developed with the rise of Peer-to-Peer network and applications. Overlay network routing is defined as routing service provided by overlay network technologies. Compared with traditional IP routing, overlay network routing provides a flexible and service-oriented routing model by construction logical paths on the top of IP paths. The scenarios of overlay network routing can be categorized into three classes. The first class is called as’Node-oriented Rouing’. The second is called as’Content-oriented Rouing’. The third is called as’Semantics-oriented Routing’.Overlay network routing plays different roles in three scenarios. In ’Node-oriented Rouing’, the object of routing is the address of nodes, Overlay routing constructs detour paths with better performance than IP default paths which can’t satisfy the quality of service.In’Content-oriented Rouing’, the object of routing is the contents. The contents are distributed into nodes in the overlay. Overlay routing helps locating the nodes that store the specific content which is queried by users.In’Semantics-aware Rouing’, the goal of routing is the abstract semantic information implied by the contents. Overlay network routing is capable of understanding the queries semantically, judging the semantic relationships, and searching the relative content resources.In the above scenarios, the common objective of research in overlay network routing mechanisms, is how to improve the quality and performance of overlay network routing, i.e. how to reduce the logical hops and physical latency of overlay network paths. As overlay network is commonly applied in distributed networks or peer-to-peer computing environments, the overhead and scalability are two important factors that need to be considered to design the overlay network routing mechanisms.In order to fulfill the above mentioned goals, this dissertation analyzes the scenarios, generalizes the requirement, summarize the key factors than have effects on the ruting performance, and deeply investigates overlay routing mechnanisms. The main contributions include the following aspects:Firstly, considering the’triangle inequality violation (TIV for short)’ phenomena, a model is defined to quantify the effects of TIV phenomena, and a method to discover TIVs based on network coordinates is designed. In order to describe the phenomna that the latency of IP default paths exceeds the latency of overlay paths, TIV model is introduced and’relay utility’metric is defined to quantify the latency-reducing effects. The distribution characteristics are also analyzed. In order to fully utilize TIV to reduce latency, a method to discover TIVs is needed. By theoretically analysis and experiments which reveal the relationship between the TIV and network coordinates, a method to predict and discover TIVs based on network coordinates is proposed, which makes preparations to bring TIVs to overlay routing mechanisms.Secondly, an application relay discovery and selection algorithm called TIVER is proposed to utilize TIVs to reduce latency in the ’Node-oriented Routing’scenario. The node searches neighbors to construct TIV candidate sets according to’relay utility’. When the node needs to construct a shorter detour path, it tries to select the neighbors with highest relay utility from candidate sets. The simulation results verify the performance of TIVER algorithm in the aspects of latency-reducing effects, selection efficiency and measurement overhead.Thirdly, considering the mismatching between logical overlay topoplogy and physical underlay topology, a content querying algorithm based on network coordinates called as PT-CAN is proposed. In order to gather the latency proximity information from the physical networks, network coordinates are combined with distributed hash tables and a content querying algorithm called P-CAN is designed. On the basis of P-CAN, considering the TIV’s latency reducing effects, a content querying algorithm called PT-CAN is proposed to gather latency information and discovery TIV phenomena, which further reduces the latency needed for content querying. The performance of our algorithm is verified by theoretical analysis and simulations.Fourthly, in the’Semantic-oriented Routing’scenario, a semantic routing mechanism called SOCS is proposed to improve the query efficiency and enhance the search functionality. Semantically modeling methods are introduced to help analyze and handle the semantic information in the contents. In this way, sematic search functionality is realized in overlay networks. The routing strategy is to cluster nodes into semantic clusters and routes the queries inner or inter clusters according to its semantic information. As a result, a hybrid routing architecture is designed to reduce both the hops and latency for semantic search. The performance analysis and simulation proves its effects. Besides, a topology generation mechanism is designed to fit into other semantic representation models, which expand the application scopes for SOCS.Summary is given in the end, where the future research directions related to this dissertation are also putted forward.