Research On Construction Of Overlay Network With Internet Infrastructure Awareness

With the further development of the Internet, the new network application comes forth continuously, such as video on demand, multimedia conference, distance learning, multimedia interactive cooperation platform and online games, etc. these new applications require better service with high reliability, high bandwidth and low latency. However, the ossification phenomenon of Internet architecture becomes more and more obvious with the popularization of the Internet. For example, long recovery time for link failure increases the end-to-end delay, IP multicast deployment hurdles limit the wide application of multimedia services, lack of QoS guarantee cannot cater to the users’ application. In addition, owning to the business benefits among ISPs, it is difficult to change the Internet infrastructure.The advent of overlay network technology has brought about new breakthrough for innovating and upgrading the Internet infrastructure. Overlay network is a logical network built on top of the existing network. The traffic is transferred between overlay nodes by the tunnel or the encapsulation mechanism without any change on the physical network. With the improvement of processing capacity of end hosts, overlay network can provide us the routing and multicast service that is only finished by the routers in ahead, as well as the content distribution service, such as P2P and CDN. On the other hand, the gradual perfection of network virtualization technology has accelerated the development of overlay network for designing the next generation Internet. Although there has already been more and more study on overlay routing and overlay multicast, the influence of physical network on overlay application in these research is usually neglected, and a lot of key problems are still waiting for solving. For example, how to consider the effect of some key nodes in physical network on the topology construction, routing and data delivery in overlay network. How to solve the problem of performance degradation caused by the shared physical link failure between the physical path and overlay path, and among many overlay paths. How to build an overlay network with node proximity awareness to reduce the end-to-end delay. How to decrease the maintenance cost of node state in multicast communication. Our work focuses on these problems, and presents the following contributions:(1) A Super-Relay nodes based overlay topology construction algorithm is proposed, which focuses on the selection of Super-Relay nodes and the connection between overlay nodes. The algorithm classifies overlay nodes into Super-Relay nodes and Ordinary-Relay nodes. The nodes with higher betweenness centralities in the physical network are selected as Super-Relay nodes. A k-minimum spanning tree is built among all overlay nodes. Simulation results show that our proposed algorithm can achieve lower delay and better reliability.(2) Based on the contribution (1), an one-hop overlay path recovery policy is proposed. In overlay network, we cannot ensure that each overlay path is independent completely from the default physical path, because two paths that are disjointed at the IP layer or overlay layer may share the same physical links. As a result, one physical link failure may cause the failure of both the default physical path and the overlay backup path simultaneously. This fact motivates us to address the selection of the recovery path, through which the traffic is rerouted between the source and destination node when the default physical path and the overlay backup path suffer from simultaneous failures. The algorithm constructs one-hop overlay recovery path by selecting reasonably one relay node to detour the failed link, which is simple and efficient.(3) Aiming to the problems of link failure and congestion in the Internet, a load-balanced overlay multipath routing algorithm (LB-OOMR) is proposed, in which the traffic is first split at the source edge nodes and then transmitted along multiple one-hop overlay paths. In order to determine an optimal split ratio for the traffic, we formulate the problem as a linear programming (LP) formulation, whose goal is to minimize the worse-case network congestion ratio. Since it is difficult to solve this LP problem in practical time, a heuristic algorithm is introduced to select the relay nodes for constructing the disjoint one-hop overlay paths, which greatly reduces the computational complexity of the LP algorithm. Simulation results show that LB-OOMR can reduce the network congestion ratio dramatically, and achieve high-quality overlay routing service.(4) In light of the limitations for large-scale deployment of IP multicast on the Internet, a stateless overlay multicast mechanism with in-packet Bloom filters is proposed, in which multicast routing information is encoded by a Bloom filter and encapsulated into the header of packets without maintaining the multicast forwarding tree. Moreover, the scheme leverages node heterogeneity and proximity information in the physical topology to construct hierarchically the overlay topology by assigning geometric coordinate to each node. The analytical and simulation results show that our proposal can achieve high forwarding efficiency and good scalability.