On Static Reachability Analysis of IP Networks
Loading...
Authors
Zhan, J.
Maltz, D.
Zhang, H.
Greenberg, A.
Hjalmtysson, G.
Rexford, J.
Xie, Geoffrey
Subjects
Advisors
Date of Issue
2005-03
Date
March 2005
Publisher
Language
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.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.
Type
Description
Proc. IEEE INFOCOM Conference, Miami, FL, March 2005. A more complete version published as Technical Report CMU-CS-04-146, Carnegie Mellon University.
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.