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.
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
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 -