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

146 Scopus citations

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.

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
Pages2170-2183
Number of pages14
DOIs
StatePublished - 2005
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

Publication series

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

Other

OtherIEEE INFOCOM 2005
CountryUnited States
CityMiami, FL
Period3/13/053/17/05

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Keywords

  • Routing
  • Static Configuration Analysis

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

  • Cite this

    Xie, G. G., Zhan, J., Maltz, D. A., Zhang, H., Greenberg, A., Hjalmtysson, G., & Rexford, J. L. (2005). On static reachability analysis of IP networks. In K. Makki, & E. Knightly (Eds.), Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies (pp. 2170-2183). (Proceedings - IEEE INFOCOM; Vol. 3). https://doi.org/10.1109/INFCOM.2005.1498492