Improving End-to-End Availability Using Overlay NetworksbyDavid Godbe AndersenS.M. Computer Science, Massachusetts Institute of Technology (2001)B.S., Computer Science, University of Utah (1998)B.S., Biology, University of Utah (1998)Submitted to the Department of Electrical Engineering and Computer Sciencein partial fulfillment of the requirements for the degree ofDoctor of Philosophy in Computer Science and Engineeringat theMASSACHUSETTS INSTITUTE OF TECHNOLOGYFebruary 2005c Massachusetts Institute of Technology 2004. All rights reserved.Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .Department of Electrical Engineering and Computer ScienceDecember 22, 2004Certified by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .Hari BalakrishnanAssociate Professor of Computer Science and EngineeringThesis SupervisorAccepted by . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .Arthur C. SmithChairman, Department Committee on Graduate Students2Improving End-to-End Availability Using Overlay NetworksbyDavid Godbe AndersenSubmitted to the Department of Electrical Engineering and Computer Scienceon December 22, 2004, in partial fulfillment of therequirements for the degree ofDoctor of Philosophy in Computer Science and EngineeringAbstractThe end-to-end availability of Internet services is between two and three orders of magnitude worsethan other important engineered systems, including the US airline system, the 911 emergency re-sponse system, and the US public telephone system. This dissertation explores three systems de-signed to mask Internet failures, and, through a study of three years of data collected on a 31-sitetestbed, why these failures happen and how effectively they can be masked.A core aspect of many of the failures that interrupt end-to-end communication is that they falloutside the expected domain of well-behaved network failures. Many traditional techniques copewith link and router failures; as a result, the remaining failures are those caused by software andhardware bugs, misconfiguration, malice, or the inability of current routing systems to cope withpersistent congestion. The effects of these failures are exacerbated because Internet services dependupon the proper functioning of many components—wide-area routing, access links, the domainname system, and the servers themselves—and a failure in any of them can prove disastrous to theproper functioning of the service.This dissertation describes three complementary systems to increase Internet availability in theface of such failures. Each system builds upon the idea of an overlay network, a network createddynamically between a group of cooperating Internet hosts. The first two systems, Resilient OverlayNetworks (RON) and Multi-homed Overlay Networks (MONET) determine whether the Internetpath between two hosts is working on an end-to-end basis. Both systems exploit the considerableredundancy available in the underlying Internet to find failure-disjoint paths between nodes, andforward traffic along a working path. RON is able to avoid 50% of the Internet outages that interruptcommunication between a small group of communicating nodes. MONET is more aggressive,combining an overlay network of Web proxies with explicitly engineered redundant links to theInternet to also mask client access link failures. Eighteen months of measurements from a six-sitedeployment of MONET show that it increases a client’s ability to access working Web sites bynearly an order of magnitude.Where RON and MONET combat accidental failures, the Mayday system guards against denial-of-service attacks by surrounding a vulnerable Internet server with a ring of filtering routers. May-day then uses a set of overlay nodes to act as mediators between the service and its clients, permittingonly properly authenticated traffic to reach the server.Thesis Supervisor: Hari BalakrishnanTitle: Associate Professor of Computer Science and Engineering34To my parents, Mary Lou Godbe and Jerry Richard Andersen,and to my grandfather Hampton Clawson Godbe,who always encouraged me to discover things,instilling in me the curiosity to become a scientist,and the impatience to become a computer scientist.56AcknowledgmentsI am deeply indebted to my advisor, Hari Balakrishnan, for making five years of graduate schoolone of the best periods of my life. For each effort I put into my research and this dissertation, Ithink Hari put two. I arrived at MIT quite without a clue, and rather worried that the admissionscommittee would soon realize their drastic error in inviting me. Fortunately, it was difficult to straytoo far afield when striving to follow Hari’s example and exemplary advice. He was a better advisorthan I imagined possible.Frans Kaashoek let me steal an enormous amount of his time and wisdom as I walked a linebetween networks and systems. Frans’s vigorous approach both to research and to life helped showme the fun that can be had in academia. I benefited enormously from the time I spent visiting PDOSgroup meetings and getting an infusion of hard-core systems.In addition to so generously serving on my committee, and on my typically short notice, JohnGuttag taught me many of the right questions to ask about research. I know of nobody better to turnto when wondering, “What’s the really important thing about what I’m doing here?”I have to thank Robert Morris for two things: First, as one of the people behind the RON project,for his early guidance and frequent advice; and second, for sharing his passion for all things timing-related and letting me frequently barge in and borrow a rubidium oscillator or frequency counterwhen I was avoiding my real work.Alex Snoeren, my officemate for my first three years at MIT, showed me how to swim, bothin research and socially, in a very different pool than the one from which I came. He was a greatmentor, office-mate, and a damn smart blackboard off which to bounce my crazy idea or dumbquestion of the week. He’s a great friend to have. Thank you, Alex. On the topic of swimming, Iowe Christine Alvarado for similar help, both as an occasional training partner and teacher, and forsuccessfully juggling her own Ph.D. research while encouraging those