On static reachability analysis of IP networks

Geoffrey G. Xie, Jibin Zhan, David A. Maltz, Hui Zhang, Albert Greenberg, Gisli Hjalmtysson, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

175 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
EditorsK. Makki, E. Knightly
Number of pages14
StatePublished - 2005
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Country/TerritoryUnited States
CityMiami, FL

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


  • Routing
  • Static Configuration Analysis


Dive into the research topics of 'On static reachability analysis of IP networks'. Together they form a unique fingerprint.

Cite this