FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |   ...   | 19 |

«Reliable Internet Routing Martin Suchara A Dissertation Presented to the Faculty of Princeton University in Candidacy for the Degree of Doctor of ...»

-- [ Page 1 ] --

Reliable Internet Routing

Martin Suchara

A Dissertation

Presented to the Faculty

of Princeton University

in Candidacy for the Degree

of Doctor of Philosophy

Recommended for Acceptance

By the Department of

Computer Science

Adviser: Professor Jennifer Rexford

September 2011

c Copyright by Martin Suchara, 2011. All rights reserved.


Network routing algorithms responsible for selecting paths to destinations have a profound

impact on network reliability experienced by the network users. Unfortunately, performance of state-of-the-art routing algorithms often falls short of users’ expectations.

(i) The flexibility with which operators of independently administered networks can choose their routing policies allows them to make selections that are “conflicting” and may lead to route oscillations. Oscillating routes have a negative impact on performance experienced by the user, and also cause overloading of the routers with control messages. (ii) Interdomain routing in the Internet is based on trust. As a result, false route announcements can be made by a malicious network operator. Such false announcements can be made even without knowledge of the network operator, e.g., due to accidentally misconfigurations or router hijacking. False route announcements may lead to denial of service, or worse yet, traffic can be intercepted without detection of both the sender and recipient. (iii) Even if network routes are stable and secure, unexpected equipment failures may cause performance degradation. It is difficult to pre-configure current routing protocols with all possible failures in mind, and not enough flexibility is offered to balance load in the network evenly.

This thesis addresses these three challenging problems. (i) We provide a new theoretical model of interdomain routing and derive the necessary and sufficient conditions that determine which policy combinations lead to route oscillations. Moreover, we also provide a practical polynomial-time algorithm that allows network operators to verify the existence of such conflicts. (ii) To secure routing against malicious attacks, we offer a new secure routing protocol that, unlike earlier attempts, is incrementally deployable. Our solution can protect both participants and non-participants if as few as 5–10 independently administered domains deploy our solution. (iii) To handle traffic engineering in the presence of failures, we propose a new architecture that optimizes load balancing for a wide range of failure scenarios. Our architecture supports flexible splitting of traffic over multiple precomputed paths, with efficient path-level failure detection and automatic load balancing over the remaining paths.

Collectively, the contributions of the dissertation provide tools that improve routing reliability and as a result network performance perceived by the user.

–  –  –

also the downs of my graduate career at Princeton. Words cannot express Jennifer’s passion for teaching and mentoring. She worked with me selflessly and was happy to discuss new ideas, give feedback about my writing style, presentations, and career advice. I admire her sharp intellect, professionalism with which she deals with all tasks, and ability to prioritize. I would also like to thank Jennifer for her support and encouragement to present my results at conferences and as a speaker at several universities.

I would like to thank Mung Chiang for being my co-advisor and mentor in my early years at Princeton. I highly value Mung’s expertise in optimization theory. His mentoring helped me to understand and tackle the complex optimization problems I faced when I worked on this dissertation. I would also like to thank all my thesis committee members, Mung Chiang, Gordon Wilfong, Ed Felten, and Mike Freedman for their feedback on my thesis.

I am grateful for the help I received from all the co-authors of the papers that I published. I am especially indebted to Alex Fabrikant, Ioannis Avramopoulos, and Jiayue He. Alex taught me how to think like a theorist, provided help during my job search, and was a great friend. I thank Ioannis and Jiayue for their creative ideas and co-authoring several major publications with me.

I am very lucky to have worked with a number of excellent researchers at AT&T Labs Research where I spent two summers. In particular, I am grateful to my mentors Robert Doverspike, and Dahai Xu for their mentoring and encouragement to work on practical problems with real-world impact. I also appreciate the numerous interactions I had with David Johnson. In addition, I owe thanks to Quynh Nguyen, Kostas Oikonomou, Rakesh Sinha, Kobus van der Merwe, and Jennifer Yates for help and advice with understanding the operation of the AT&T’s backbone, measurement, data collection, and data processing that I needed to finish this dissertation.

I thank Barbara Terhal and Sergey Bravyi at IBM research where I spent one summer working on quantum error correcting codes. I especially thank you for your time explaining me the concepts of a new research area I wasn’t familiar with.

I thank my fellow Cabernet group members: Minlan Yu, Yaping Zhu, Eric Keller, Wenjie (Joe) Jiang, Rob Harrison, Michael Schapira, Sharon Goldberg, Haakon Ringberg, Elliott Karpilovsky, Changhoon Kim, Yi Wang, Steven Ko, Nate Foster, Rui Zhang-Shen, Matthew Caesar, and others.

–  –  –

Melissa Lawson, the administrator in the Computer Science Department.

I was fortunate to work with and co-supervise two bright undergraduate students, Will Fisher and Umar Javed. Thank you for your hard work, you were great students.

Writing this dissertation would not be possible without the support of research grants from AFOSR, NSF and AT&T. In addition, my graduate study at Princeton was partly supported by the Gordon Wu Fellowship, and my two summer internships at AT&T by the DARPA CORONET Program.

I thank my parents for their love, support and encouragement. Without them this accomplishment would have been impossible.

–  –  –

2.5 Internal architecture of routers or ASes causes spurious updates and oscillations.. 28

2.6 Router architecture where loss of the most preferred route causes spurious announce

–  –  –

2.12 Sequence of activations that results in permanent oscillations............. 42

2.13 Reduction showing NP completeness of determining safety when router configura

–  –  –

3.3 Security performance with partial soBGP deployment with 25 large ISPs participating. 71

3.4 Security performance with ideal malicious route filters and with 25 large ISPs par

–  –  –

3.5 Security performance when participants use overlay routing to select valid routes.. 77

3.6 Security performance with overlay routing provided by SBone and up to 5 tier-1

–  –  –

3.11 Security performance when the adversary mounts a sub-prefix hijacking attack... 88

4.1 The network architecture consisting of a management system that precalculates

–  –  –

4.5 Existing tools and protocols that can be used to deploy our architecture....... 115 Chapter 1 Introduction Since the first message was sent on the ARPANET network, the predecessor of the modern Internet, the network has experienced a dramatic growth. Once reserved for academic use, the Internet presently connects billions of users around the world who rely on the infrastructure in their daily lives.

The Internet has become much more than just a network used to access information. In the past two decades, new important applications have emerged, such as electronic commerce, voice over IP, social networking, and many more. In addition, many applications such as online banking or online trading are business critical and time sensitive. As a result, users and businesses who rely on the Internet infrastructure require a high degree of reliability from the operators of the network. Reliability encompasses the ability to offer the network users high-bandwidth and lowlatency service in the presence of accidental hardware failures or planned maintenance, and ability to deliver data securely even in the presence of malicious attacks on the Internet infrastructure.

This thesis addresses these challenging problems.

Network routing, the selection of paths to destinations, is perhaps one of the most important features of the Internet that determines the performance, security, and reliability of the network.

For example, selecting the “right” paths can reduce congestion and decrease queuing and propagation delay, improving the performance for the users. Furthermore, dynamic rerouting is a critical operation that ensures that connectivity is re-established after a failure of a link or router.

Rerouting is also important when traffic demands of the users change. Finally, security of network routing protocols has implications on the reliability of the entire network – a malicious user may for example manipulate the routing protocol so that network traffic is forwarded to him, or to cause widespread connectivity disruptions.

In Section 1.1 we describe the basic operation of two main families of routing protocols – intradomain and interdomain routing protocols. Then, in Section 1.2 we describe the shortcomings of the current design and the impact on the safety, security and reliability of the network. We also outline the proposed solutions to address these important issues.

1.1 Routing in the Internet Interdomain routing concerns the problem of calculating the paths across domains that the traffic needs to traverse to reach the destination. Intradomain routing determines the path inside a single administrative domain that the traffic needs to take to reach the destination. The two problems are very different. Intradomain routing is done in a single network and the owner of the network has a full control and information about the network topology, load, configuration, etc. Interdomain routing concerns exchanging traffic between separate networks whose owners, who are business competitors, do not have full information about the other networks. For this reason, interdomain and intradomain routing rely on different routing protocols and face different challenges.

1.1.1 Interdomain Routing The Internet consists of tens of thousands of autonomous systems (ASes) that are independently owned and operated. To achieve global connectivity, ASes exchange information about reachability.

This information exchange is facilitated by the Border Gateway Protocol (BGP) [92]. BGP is a path vector protocol, that is, when an AS uses BGP to announce a route to its neighbor, the announcement contains a list of all other ASes that the path traverses before reaching the destination. The adjacent ASes exchange the BGP messages between their edge routers, which are also sometimes referred to as BGP speakers.

ASes are typically Internet Service Providers who have business relationships with their neighboring ASes. These business relationships determine any transit fees. While business relationships are confidential, a model [19] that is believed to correspond to reality classifies business relationships into two categories: customer-provider and peer-peer. In customer-provider relationship, the customer has to pay the provider for all traffic that traverses the link between the ASes, no matter what the direction of the traffic. In peer-peer relationships, the peers forward traffic for each other free of charge.

The nature of business relationships determines which routes are preferred by ASes. For example, given the choice between a customer, peer and provider route, the AS will prefer the customer route which is the most profitable. Business relationships also play a role even after a BGP speaker selects the single route to the destination that it prefers – a BGP speaker will not announce a provider route to another provider as it would have to pay to both providers for the transit traffic. For this reason ASes need the flexibility to choose among multiple paths, and the option to announce the selected path to an arbitrary subset of their neighbors. BGP allows such flexibility – if an AS learns about multiple routes from its neighbors, it can apply an arbitrary policy to choose the preferred path, and decide which neighbors to announce the path to.

BGP is a protocol based on trust. When a route announcement is received, autonomous systems cannot verify whether a path announced by a neighboring BGP speaker corresponds to an existing physical path, and whether that path is available to the neighbor. For this reason, BGP is extremely vulnerable to malicious attacks where an attacker compromises a router to make false routing announcements, and to misconfigurations where a speaker mistakenly announces an incorrect route.

1.1.2 Intradomain Routing Network operators need intradomain routing protocols that ensure network connectivity even as the network topology changes due to link additions, hardware failures, or during planned equipment maintenance. In addition, network operators desire to balance the load in their networks to avoid congestion. One protocol satisfying these goals is Open Shortest Path First (OSPF) [69]. OSPF is a link state routing protocol, i.e., a protocol that collects information from routers about their connectivity (the state of their links). Then, the routers construct a graph representing the network, and traffic is sent on the shortest path according to link weights that were pre-assigned to each link. If a router finds multiple shortest paths, traffic is split evenly on the outgoing links.

The link state information is maintained by each router and if it changes, it is flooded in the network. The benefits of using OSPF include the ability to react to link failures – when a link fails the information is immediately flooded in the network and all of the routers can compute new shortest paths that avoid the failed link. Furthermore, proper link weight assignment allows load balancing. However, OSPF only allows to split the traffic on paths of the same minimal cost.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 19 |

Similar works:

«Transit for National Parks and Gateway Communities: Impacts and Guidance A Dissertation Presented to The Academic Faculty By Anne E. Dunning In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in Civil and Environmental Engineering Georgia Institute of Technology January 2005 Copyright © Anne E. Dunning, 2005.Transit for National Parks and Gateway Communities: Impacts and Guidance Approved by: Dr. Michael D. Meyer, Advisor Dr. Michael O. Rodgers School of Civil and...»

«TROUBLED TIMES: DESEGREGATION OF PUBLIC SCHOOLS IN CHESTERFIELD, SOUTH CAROLINA, 1965-1971 By Cheryl Jenkins Guy Bachelor of Arts University of South Carolina, 1984 Master of Arts University of South Carolina, 1991 Master of Arts University of South Carolina, 2006 _ Submitted in Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy in Educational Administration College of Education University of South Carolina 2010 Accepted by: Doyle Stevick, Major Professor Chairman,...»

«COULD MORALITY HAVE A SOURCE? BY CHRIS HEATHWOOD JOURNAL OF ETHICS & SOCIAL PHILOSOPHY VOL. 6, NO. 2 | APRIL 2012 URL: WWW.JESP.ORG COPYRIGHT © CHRIS HEATHWOOD 2012 JOURNAL OF ETHICS & SOCIAL PHILOSOPHY | VOL. 6, NO. 2 COULD MORALITY HAVE A SOURCE? Chris Heathwood Could Morality Have a Source? Chris Heathwood I T IS A COMMON IDEA THAT MORALITY, or moral truths, if there are any, must have some sort of source. If it is wrong to break a promise, or if our fundamental moral obligation is to...»

«AN INTEGRATED PRODUCT – PROCESS DEVELOPMENT (IPPD) BASED APPROACH FOR ROTORCRAFT DRIVE SYSTEM SIZING, SYNTHESIS AND DESIGN OPTIMIZATION A Thesis Presented to The Academic Faculty by Sylvester Vikram Ashok In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in Aerospace Engineering Daniel Guggenheim School of Aerospace Engineering Georgia Institute of Technology August 2013 Copyright © 2013 by Sylvester Vikram Ashok AN INTEGRATED PRODUCT – PROCESS DEVELOPMENT...»

«La garderie Centre Copains-Copines 901, chemin Francis Burlington, ON, L7T 3Y3 (905)631-8490 srainville@csdccs.edu.on.ca PHILOSOPHIE ET RÈGLEMENTS DEFINITION La garderie Copains-Copines est un organisme à but non-lucratif géré par le conseil scolaire de district catholique Centre-Sud. La directrice est responsable du service de garde et est supervisé par l’agente de liaison sous la responsabilité de la surintendance des services éducatifs. Notre but est d’offrir des services de garde...»

«Theory and Design of High-Index-Contrast Microphotonic Circuits by Miloˇ Popovi´ s c B.Sc.E. (Electrical and Computer Engineering) Queen’s University, Canada (1999) S.M. (Electrical Engineering and Computer Science) Massachusetts Institute of Technology (2002) Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical Engineering at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY...»

«Efficient Delivery of Web Services Mourad Ouzzani Dissertation submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science and Applications Dr. Athman Bouguettaya, Chair Dr. Reza Barkhi Dr. Ing-Ray Chen Dr. Edward A. Fox Dr. Naren Ramakrishnan January 16, 2004 Falls Church, Virginia Keywords: Web Services, Web Databases, Query Optimization, Semantic Web Copyright 2003,...»

«Pre-Course Handbook BA (Hons) Professional Cookery with foundation London Geller College of Hospitality & Tourism BA (Hons) Food and Professional Cookery with foundation Course Handbook 2016-2017 Section BA (Hons) Food and Professional Cookery with foundation Course Handbook Contents Page No. Section 1 Key Information 1.1 Welcome to the Course 4 1.2 Overview of the Course 5 1.3 Sources of Help and Support 6 1.4 Facts and Figures 8 1.5 Your Responsibilities 9 Section 2 Structure and Content 2.1...»

«Loughborough University Institutional Repository Chemical kinetics modelling study on fuel autoignition in internal combustion engines This item was submitted to Loughborough University's Institutional Repository by the/an author.Additional Information: • A Doctoral Thesis. Submitted in partial fulllment of the requirements for the award of Doctor of Philosophy of Loughborough University. https://dspace.lboro.ac.uk/2134/6533 Metadata Record: c Zhen Liu Publisher: Please cite the published...»

«UNIVERSITY OF CALIFORNIA Santa Barbara A Micro/Nano-Fabricated Gecko-Inspired Reversible Adhesive A Dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Materials by Michael Thomas Northen Committee in charge: Professor Kimberly Turner, Chair Professor Noel MacDonald Professor Anthony Evans Professor Jacob Israelachvili March 2006 The dissertation of Michael Thomas Northen is approved. _ Anthony Evans _ Jacob Israelachvili _ Noel MacDonald _...»

«SAMUEL MICHAELIDES – ISFP FELLOWSHIP DISSERTATION Mary and the Philosophical Goose Chase: Physicalism and the Knowledge Argument Introduction 0.1 In his paper ‘Epiphenomenal Qualia’, Frank Jackson introduces his famous thought experiment as follows: Mary is a brilliant scientist who is, for whatever reason, forced to investigate the world from a black and white room via a black and white television monitor. She specialises in the neurophysiology of vision and acquires, let us suppose, all...»


<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.