Patent ID: 8887266
Filing Date: 2014-11-11
Classification: G06F,H04L

Abstract:
1. A method for computing network reachability between a pair of subnetworks in a computer network, comprising: determining data paths between a first subnetwork of interest in the computer network and a second subnetwork of interest in the computer network; identifying, for a given data path, two or more access control lists implemented along the given data path, where each access control list is a set of rules for filtering network packets and each rule in the set of rules sets forth values for fields in a network packet and a decision for packets having matching field values; representing each of the access control lists in the given data path as a different diagram, thereby yielding a plurality of diagrams; reducing domain for each diagram in the plurality of diagrams to a set of network addresses used in the first subnetwork and the second subnetwork; merging the plurality of diagrams into a merged diagram by applying a logical AND operation to the decisions at terminals nodes of the plurality of diagrams, where the merged diagram represents an intersection between the access control lists in the given data path; deriving a set of network packets that traverse from the first subnetwork to the second subnetwork from the merged diagram; and computing instantaneous reachability from the first subnetwork to a second subnetwork for connectionless protocols on a given data path by sorting the merged diagram associated with the given data path such that a root node of the merged diagram corresponds to a field in the network packets that specifies type of network protocol; identifying subtrees in the sorted diagram that are associated with connectionless protocols; forming a reachability diagram from the identified subtrees; and deriving from the reachability diagram a set of network packets that traverse from the first subnetwork to the second subnetwork, wherein each step is implemented by processor-executable instructions executed by a computer processor.