System and method for building a hierarchical data structure
A system and method for building a data structure for determining if multiple routing or forwarding tables yield the same or different forwarding behaviors. VeriTable uses a single tree/trie traversal to quickly check if multiple forwarding tables are forwarding equivalent, yield routing loops, or black holes. VeriTable also uses the Longest Prefix Matching rule for lookups, e.g., checking if route updates in control plane are consistent with the ones in forwarding plane. VeriTable can be applied to network-wide abnormality diagnosis of network problems, such as scalable and efficient forwarding loop detection and avoidance in the data plane of a network. In addition, VeriTable can be extended to handle incremental updates applied to the forwarding tables in a network.
1. A method for building a hierarchical data structure, comprising the steps of:
receiving a first forwarding table as an input, the first forwarding table comprising at least two fields, a prefix field and a next hop field;
creating a first radix tree having a plurality of parent nodes and one or more child nodes based on the prefix field and next hop field in the first forwarding table, wherein each child node associated with at least one of the plurality of parent nodes;
receiving a second forwarding table as an input, the second forwarding table comprising at least two fields, a prefix field and a next hop field;
creating a second radix tree having a plurality of parent nodes and one or more child nodes based on the prefix field and next hop field in the second forwarding table, wherein each child node associated with one of the plurality of parent nodes;
merging the parent nodes of the first radix tree and the parent nodes of the second radix tree if they have the same prefix;
merging the child nodes of the first radix tree and the child nodes of the second radix tree if they have the same prefix;
storing a next hop from the next hop field of the first forwarding table and a next hop from the next hop field in the second forwarding table in an integer array if they have the same prefix; and
wherein the integer array which is located at the parent node or child node having the same prefix as the next hop from the first or second forwarding tables.
2. The method of claim 1 , wherein the step of storing the next hop includes the step of:
placing the next hops from the first and second forwarding tables at the corresponding nth element in the integer array, starting at 0.
3. The method of claim 2 , wherein n is an index number of the input first and second forwarding tables.
4. The method of claim 1 , wherein the step of storing the next hop includes the step of:
placing an empty value in the integer array if there is no next hop for a prefix in the first and second forwarding tables.
5. The method of claim 1 , wherein the size of the integer array is the same as the number of forwarding tables.
6. The method of claim 1 , wherein there is a length difference between each child node and the one of the plurality of parent nodes in each of the first and second radix trees and the length difference is equal to or greater than 1.
7. The method of claim 1 , wherein the first radix tree and the second radix tree both have a radix of two.
8. A computer system for equivalence verification of multiple large forwarding tables, comprising:
a memory for storing a hierarchical data structure;
a processor coupled to the memory, for executing computer-executable instructions operable for creating the hierarchical data structure, comprising:
receiving a first forwarding table including two or more input fields, the two or more input fields define a parent-child relationship between a parent node and a child node based on a prefix;
creating a first radix tree based on the parent-child relationship of the first forwarding table;
receiving a second forwarding table including two or more input fields, the two or more input fields define a parent-child relationship between a parent node and a child node based on a prefix, wherein the first and second forwarding tables each comprise an input field with a next hop value;
creating a second radix tree based on the parent-child relationship of the second forwarding table;
merging the parent nodes of the first radix tree and the parent nodes of the second radix tree if they have the same prefix;
merging the child nodes of the first radix tree and the child nodes of the second radix tree if they have the same prefix; and
storing a next hop value from the first and second forwarding tables in an integer array if they have the same prefix.
9. The computer system of claim 8 , wherein the integer array which is located at the parent node or child node having the same prefix as the next hop.