Fujitsu Corporation

Alexander Horn

Mukul Ranjan Prasad

Ali Kheradmand

Paparao Palacharla

Naoki Oguchi

Eric Campbell

A method may include obtaining a forwarding rule associated with a network. The method may also include identifying a property associated with the network. The property may include a property value comprising a duration value. Additionally, the method may include validating, for the forwarding rule, the property in the network. Responsive to the property being valid for the forwarding rule, the method may include updating the duration value based on a first equation set. Responsive to the property being invalid for the forwarding rule, the method may include updating the duration value based on a second equation set. Furthermore, the method may include calculating a length of validity value of the property. The length of validity value may be based on the updated duration value. The method may include performing network monitoring. The network monitoring may be based on the length of validity value of the property.

Collection of forwarding rules

A method may include obtaining packet handling rules from at least one firewall in a network and at least one routing table in the network, and translating the packet handling rules to canonical data structures based on priority of rules at a given routing table or a given firewall. Each canonical data structure may represent a subset of packets affected by one or more corresponding packet handling rules such that each packet handling rule is covered by at least one canonical data structure. The method may also include generating a graph representation of the firewalls and the nodes corresponding to the routing tables in the network. The method may additionally include labeling vertices and edges in the graph representation based on the packet handling rules. The method may also include, using the graph representation, verifying one or more network properties to identify any network issues.

Network property verification

A method may include obtaining packet handling rules from network nodes in a network. The method also includes, using the rules, generating a transitive reduction of a partially ordered set of elements, where the elements correspond to match conditions in the rules, each match condition representing a set of packets identified by packet headers. The method may also include generating packet equivalence classes (PECs) by removing children elements from a parent element in the transitive reduction, where each PEC covers disjoint sets of packets, and each PEC is identified by fields in the packet headers including source address, destination address, and protocol of packets. The PECs may represent a group of packets treated in a same manner in the network. The method may also include generating a graph representation of the network nodes utilizing the PECs, and, using the graph representation, verifying properties of operation of the network.

A method of network property verification, the method including obtaining a property of a network to be verified and obtaining forwarding rules for multiple network devices in the network, the forwarding rules indicative of how the network devices handle incoming packets and at least one of the network devices including forwarding rules to forward an address-based packet and forward a variable-length header packet. The method may also include generating a graph representation of the forwarding rules, where each rule of the forwarding rules is independently applicable to address-based packets or variable-length header packets. The method may additionally include assigning transition operations between the network devices in the graph representation based on the forwarding rules, assigning, in the graph representation, an atom to links between network devices that forward variable-length header packets, and verifying the property of the network using the graph representation to identify any network issue.

Network property verification in hybrid networks

A network analysis method may include identifying a data plane for routing traffic through a network that includes one or more forwarding tables for each switch of a plurality of switches in the data plane. The method may also include generating an edge-labeled graph, wherein each edge of the edge-labeled graph is associated with one or more atoms to represent an Internet Protocol (IP) prefix of a forwarding rule of the data plane. Further, the method may include initializing a network summary of the network as a transitive closure of the edge-labeled graph. In addition, the method may include updating the edge-labeled graph to generate an updated edge-labeled graph in response to a modification of a forwarding table of the one or more forwarding tables. Moreover, the method may include determining a transitive closure of the updated edge-labeled graph, and updating the network summary based on the network summary and the transitive closure of the updated edge-labeled graph.

Network analysis

A network verification method may include identifying a data plane for routing traffic through a network that includes one or more forwarding tables for each switch of a plurality of switches in the data plane. The method may also include obtaining a forwarding behavior representation of the data plane based on the forwarding tables, and obtaining a forwarding rule from the one or more forwarding tables. The method may additionally include transforming the forwarding behavior representation based on the forwarding rule. The method may also include pruning meta-information about the forwarding rule that is redundant to forwarding behavior, and comparing the forwarding behavior representation of the data plane to one or more network properties of expected behavior of the data plane to detect one or more errors in the data plane as variations from the expected behavior.

Network verification

A network verification method may include identifying a data plane including one or more forwarding tables for each switch of a plurality of switches in the data plane. The method may also include generating a forwarding behavior representation of the data plane to represent Boolean combinations of forwarding rules of the one or more forwarding tables of the data plane. Further, the method may include comparing the forwarding behavior representation of the data plane to one or more network properties to detect one or more errors in the data plane.

Growing community of inventors

Sunnyvale, CA, United States of America

Alexander Horn