View Full Document

Improving End-to-End Availability Using Overlay Networks



View the full content.
View Full Document
View Full Document

22 views

Unformatted text preview:

Improving End to End Availability Using Overlay Networks by David Godbe Andersen S 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 Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science and Engineering at the M ASSACHUSETTS I NSTITUTE OF T ECHNOLOGY February 2005 c Massachusetts Institute of Technology 2004 All rights reserved Author Department of Electrical Engineering and Computer Science December 22 2004 Certified by Hari Balakrishnan Associate Professor of Computer Science and Engineering Thesis Supervisor Accepted by Arthur C Smith Chairman Department Committee on Graduate Students 2 Improving End to End Availability Using Overlay Networks by David Godbe Andersen Submitted to the Department of Electrical Engineering and Computer Science on December 22 2004 in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science and Engineering Abstract The end to end availability of Internet services is between two and three orders of magnitude worse than other important engineered systems including the US airline system the 911 emergency response system and the US public telephone system This dissertation explores three systems designed to mask Internet failures and through a study of three years of data collected on a 31 site testbed 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 fall outside the expected domain of well behaved network failures Many traditional techniques cope with link and router failures as a result the remaining failures are those caused by software and hardware bugs misconfiguration malice or the inability of current routing systems to cope with persistent congestion The effects of these failures are exacerbated because Internet services depend upon the proper functioning of many components wide area routing access links the domain name system and the servers themselves and a failure in any of them can prove disastrous to the proper functioning of the service This dissertation describes three complementary systems to increase Internet availability in the face of such failures Each system builds upon the idea of an overlay network a network created dynamically between a group of cooperating Internet hosts The first two systems Resilient Overlay Networks RON and Multi homed Overlay Networks MONET determine whether the Internet path between two hosts is working on an end to end basis Both systems exploit the considerable redundancy available in the underlying Internet to find failure disjoint paths between nodes and forward traffic along a working path RON is able to avoid 50 of the Internet outages that interrupt communication between a small group of communicating nodes MONET is more aggressive combining an overlay network of Web proxies with explicitly engineered redundant links to the Internet to also mask client access link failures Eighteen months of measurements from a six site deployment of MONET show that it increases a client s ability to access working Web sites by nearly an order of magnitude Where RON and MONET combat accidental failures the Mayday system guards against denialof service attacks by surrounding a vulnerable Internet server with a ring of filtering routers Mayday then uses a set of overlay nodes to act as mediators between the service and its clients permitting only properly authenticated traffic to reach the server Thesis Supervisor Hari Balakrishnan Title Associate Professor of Computer Science and Engineering 3 4 To 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 5 6 Acknowledgments I am deeply indebted to my advisor Hari Balakrishnan for making five years of graduate school one of the best periods of my life For each effort I put into my research and this dissertation I think Hari put two I arrived at MIT quite without a clue and rather worried that the admissions committee would soon realize their drastic error in inviting me Fortunately it was difficult to stray too far afield when striving to follow Hari s example and exemplary advice He was a better advisor than I imagined possible Frans Kaashoek let me steal an enormous amount of his time and wisdom as I walked a line between networks and systems Frans s vigorous approach both to research and to life helped show me the fun that can be had in academia I benefited enormously from the time I spent visiting PDOS group meetings and getting an infusion of hard core systems In addition to so generously serving on my committee and on my typically short notice John Guttag taught me many of the right questions to ask about research I know of nobody better to turn to 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 timingrelated and letting me frequently barge in and borrow a rubidium oscillator or frequency counter when I was avoiding my real work Alex Snoeren my officemate for my first three years at MIT showed me how to swim both in research and socially in a very different pool than the one from which I came He was a great mentor office mate and a damn smart blackboard off which to bounce my crazy idea or dumb question of the week He s a great friend to have Thank you Alex On the topic of swimming I owe Christine Alvarado for similar help both as an occasional training partner and teacher and for successfully juggling her own Ph D research while encouraging those around her to occasionally flee the confines of their cubicles to meet other people Alex Allen Miu Stan Rost and Jon Salz made our office in room 512 an excellent and loud place to work Stan thank you for the music and all the rest Allen thank you for making me notice the badminton courts I ll miss our daily interaction Nick Feamster tolerated me as both a friend an officemate and an apartment mate and did an excellent job at all of the above I may have gotten more


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Improving End-to-End Availability Using Overlay Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Improving End-to-End Availability Using Overlay Networks and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?