Reliable Communication in Overlay NetworksYair Amir and Claudiu DanilovJohns Hopkins University{yairamir, claudiu}@cs.jhu.eduAbstractReliable point-to-point communication is usuallyachieved in overlay networks by applying TCP on the endnodes of a connection. This paper presents a hop-by-hopreliability approach that considerably reduces the latencyand jitter of reliable connections. Our approach is feasibleand beneficial in overlay networks that do not have thescalability and interoperability requirements of the globalInternet.The effects of the hop-by-hop reliability approach arequantified in simulation as well as in practice using a newlydeveloped overlay network system that is fair with the ex-ternal traffic on the Internet. The experimental results showthat the overhead associated with overlay network process-ing at the application level does not play an important fac-tor compared with the considerable gain of the approach.1 IntroductionReliable point-to-point communication is one of themain utilizations of the Internet, where over the last fewdecades TCP has served as the dominant protocol. Over theInternet, reliable communication is performed end-to-end inorder to address the severe scalability and interoperabilityrequirements of a network in which potentially every com-puter on the planet could participate. Thus, all the workrequired in a reliable connection is distributed only to thetwo end nodes of that connection, while intermediate nodesroute packets without keeping any information about the in-dividual packets they transfer.Overlay networks are opening new ways to Internet us-ability, mainly by adding new services (e.g. built-in secu-rity) that are not available or cannot be implemented in thecurrent Internet, and also by providing improved servicessuch as higher availability [2]. However, the usage of over-lay networks may come with a price, usually in added la-tency that is incurred due to longer paths created by overlayrouting, and by the need to process the messages in the ap-plication level by every overlay node on the path.Reliable communication in overlay networks is usuallyachieved by applying TCP on the edges of a connection.This surely works. However, this paper argues that employ-ing hop-by-hop reliability techniques considerably reducesthe average latency and jitter of reliable communication.When using such an approach one has to consider network-ing aspects such as congestion control, fairness, flow con-trol and end-to-end reliability. We discuss these aspects andour design decisions in Section 2.In Section 3, we demonstrate through simulation that ourapproach provides tremendous benefit for the application aswell as for the network itself, even when very few packetsare lost. Simulations usually do not take into account manypractical issues such as processing overhead, CPU schedul-ing, and most important, the fact that overlay network pro-cessing is performed at the application level of general pur-pose computers. These may have considerable impact onreal-life behavior and performance. Therefore, we test ourapproach in practice on an overlay network platform calledSpines that we have built.We introduce Spines in Section 4. Spines [16] is an opensource research platform that allows deployment of over-lay networks in the Internet. We run the same experimentsthat were simulated, on a Spines overlay network. The re-sults are presented in Section 5. We show that the benefitof hop-by-hop reliability greatly overcomes the overhead ofoverlay routing and achieves much better performance com-pared to standard end-to-end TCP connections deployed onthe same overlay network.We describe existing related work and compare it withour approach in Section 6, and end the paper, concludingthat hop-by-hop reliability is a viable and beneficial ap-proach to reliable communication in overlay networks.2 Hop-by-hop reliable communication inoverlay networksAn overlay network constructs a user level graph on topof an existing networking infrastructure such as the Inter-net, using only a subset of the available network links andnodes. An overlay link is a virtual edge in this graph and0-7695-1959-8/03 $17.00 (c) 2003 IEEEProceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)may consist of many actual links in the underlying network.Overlay nodes act as routers, forwarding packets to the nextoverlay link toward the destination. At the physical level,packets traveling along a virtual edge between two overlaynodes follow the actual physical links that form that edge.Overlay networks have two main drawbacks. First, theoverlay routers incur some overhead every time a messageis processed, which requires delivering the message to theapplication level, processing it, and resending the messageto the next overlay router. Second, the placement of overlayrouters in the topology of the physical network is often farfrom optimal, because the creator of the overlay networkrarely has control over the physical network (usually theInternet) or even the knowledge about its actual topology.Therefore, overlay networks provide longer paths that havehigher latency than point to point Internet connections.The easiest way to achieve reliability in Overlay Net-works is to use a reliable protocol, usually TCP, between theend points of a connection. This mechanism has the benefitof simplicity in implementation and deployment, but pays ahigh price upon recovery from a loss. As overlay paths havehigher delays, it takes a relatively long time to detect a loss,and data packets and acknowledgments are sent on multipleoverlay hops in order to recover the missed packet.2.1 Hop-by-hop reliabilityWe propose a mechanism that recovers the losses only onthe overlay hop on which they occurred, localizing the con-gestion and enabling faster recovery. Since an overlay linkhas a lower delay compared to an end-to-end connectionthat traverses multiple hops, we can detect the loss fasterand resend the missed packet locally. Moreover, the con-gestion control on the overlay link can increase the conges-tion window back faster than an end-to-end connection, asit has a smaller round-trip time.Hop-by-hop reliability involves buffers and processingin the intermediate overlay nodes. These nodes need to de-ploy a reliable protocol, and keep track of packets, acknowl-edgments and congestion control, in addition to their regularrouting functionality. Although such an approach may notbe
View Full Document
Unlocking...