On static reachability analysis of IP networks

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

doi:10.1109/INFCOM.2005.1498492

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 proceeding › Conference contribution

150 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 language	English (US)
Title of host publication	Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies
Editors	K. Makki, E. Knightly
Pages	2170-2183
Number of pages	14
DOIs	https://doi.org/10.1109/INFCOM.2005.1498492
State	Published - 2005
Event	IEEE INFOCOM 2005 - Miami, FL, United States Duration: Mar 13 2005 → Mar 17 2005

Publication series

Name	Proceedings - IEEE INFOCOM
Volume	3
ISSN (Print)	0743-166X

Other

Other	IEEE INFOCOM 2005
Country	United States
City	Miami, FL
Period	3/13/05 → 3/17/05

All Science Journal Classification (ASJC) codes

Computer Science(all)
Electrical and Electronic Engineering

Keywords

Routing
Static Configuration Analysis

Access to Document

10.1109/INFCOM.2005.1498492

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

Xie, Geoffrey G. ; Zhan, Jibin ; Maltz, David A. ; Zhang, Hui ; Greenberg, Albert ; Hjalmtysson, Gisli ; Rexford, Jennifer L. / On static reachability analysis of IP networks. Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies. editor / K. Makki ; E. Knightly. 2005. pp. 2170-2183 (Proceedings - IEEE INFOCOM).

@inproceedings{507890d49f4d4156b8472b471ae6b558,

title = "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.",

keywords = "Routing, Static Configuration Analysis",

author = "Xie, {Geoffrey G.} and Jibin Zhan and Maltz, {David A.} and Hui Zhang and Albert Greenberg and Gisli Hjalmtysson and Rexford, {Jennifer L.}",

year = "2005",

doi = "10.1109/INFCOM.2005.1498492",

language = "English (US)",

isbn = "0780389689",

series = "Proceedings - IEEE INFOCOM",

pages = "2170--2183",

editor = "K. Makki and E. Knightly",

booktitle = "Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies",

}

Xie, GG, Zhan, J, Maltz, DA, Zhang, H, Greenberg, A, Hjalmtysson, G & Rexford, JL 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. Proceedings - IEEE INFOCOM, vol. 3, pp. 2170-2183, IEEE INFOCOM 2005, Miami, FL, United States, 3/13/05. https://doi.org/10.1109/INFCOM.2005.1498492

On static reachability analysis of IP networks. / Xie, Geoffrey G.; Zhan, Jibin; Maltz, David A.; Zhang, Hui; Greenberg, Albert; Hjalmtysson, Gisli; Rexford, Jennifer L.

Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies. ed. / K. Makki; E. Knightly. 2005. p. 2170-2183 (Proceedings - IEEE INFOCOM; Vol. 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On static reachability analysis of IP networks

AU - Xie, Geoffrey G.

AU - Zhan, Jibin

AU - Maltz, David A.

AU - Zhang, Hui

AU - Greenberg, Albert

AU - Hjalmtysson, Gisli

AU - Rexford, Jennifer L.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - Routing

KW - Static Configuration Analysis

UR - http://www.scopus.com/inward/record.url?scp=25844500375&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=25844500375&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2005.1498492

DO - 10.1109/INFCOM.2005.1498492

M3 - Conference contribution

AN - SCOPUS:25844500375

SN - 0780389689

T3 - Proceedings - IEEE INFOCOM

SP - 2170

EP - 2183

BT - Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies

A2 - Makki, K.

A2 - Knightly, E.

T2 - IEEE INFOCOM 2005

Y2 - 13 March 2005 through 17 March 2005

ER -

Xie GG, Zhan J, Maltz DA, Zhang H, Greenberg A, Hjalmtysson G et al. On static reachability analysis of IP networks. In Makki K, Knightly E, editors, Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies. 2005. p. 2170-2183. (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2005.1498492