On Static Reachability Analysis of IP Networks

Abstract

The primary purpose of a network is to provide reachability between applications running on end hosts. In this paper, we describe how to compute the reachability a network provides from a snapshot of the configuration state from each of the routers. Our primary contribution is the precise definition of the potential reachability of a network and a substantial simplification of the problem through a unified modeling of packet filters and routing protocols. In the end, we reduce a complex, important practical problem to computing the transitive closure to set union and intersection operations on reachability set representations. We then extend our algorithm to model the influence of packet transformations (e.g., by NATs or ToS remapping) along the path. Our technique for static analysis of network reachability is valuable for verifying the intent of the network designer, troubleshooting reachability problems, and performing "what-if" analysis of failure scenarios.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 2005
Accession Number
ADA487990

Entities

People

  • Albert Greenberg
  • David A. Maltz
  • Geoffrey G. Xie
  • Gisli Hjalmtysson
  • Hui Zhang
  • Jennifer Rexford
  • Jibin Zahn

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Application Protocols
  • Boundaries
  • Commerce
  • Computer Networks
  • Computing Devices
  • Estimators
  • Failure Mode And Effect Analysis
  • Internet
  • Network Protocols
  • Networks
  • Packet Filtering
  • Routing Protocols
  • Security
  • Topology
  • Troubleshooting

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Computer Networking
  • Graph Algorithms and Convex Optimization.