Back to search

University of Washington

Systems for analyzing routing policies and localizing faults in the Internet

Abstract

dc:description.abstract

Our reliance on the Internet continues to grow; however, Internet communication has seen little progress over the years because it typically spans multiple Autonomous Systems (ASes) that are operated by individual Internet Service Providers (ISPs) and organizations. This inherent autonomy of the Internet limits the visibility into other networks and the velocity of change. As a result, public Internet communication has become the weak link for Internet-based services. In this thesis, I design, build, and evaluate practical algorithms and systems that ISPs and cloud providers can use to analyze Internet routing policies and localize faults in the Internet. Knowledge of the business relationships between ASes is essential to understanding the behavior of the Internet routing system. I develop ProbLink, a probabilistic algorithm to infer business relationships between ASes in the Internet. By integrating noisy but useful features, it overcomes the challenges in inferring hard links such as routing violating the valley-free assumption, limited visibility, and non-conventional peering practices. I build three real-world applications on top of ProbLink and show that ProbLink has a significant impact when applied to practical applications compared to the state-of-the-art inference algorithms based on empirical rules. For Internet-based services such as video calls and online games, providing low latency is important. I design and build a system, BlameIt, that automatically localizes the faulty AS when there is latency degradation between clients and clouds. BlameIt employs a hybrid two-phased blame assignment, combining the best parts of passive analysis (low measurement overhead) and active probing (fine-grained fault localization). BlameIt has been in production deployment for 3 years at Microsoft Azure and produces results with high accuracy at low overheads.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jin, Yuchen
Advisor dc:contributor.advisor
  • Krishnamurthy, Arvind

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • none
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/47040

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Jin, Yuchen. Systems for analyzing routing policies and localizing faults in the Internet. 2021. http://hdl.handle.net/1773/47040