Verifying interconnect fabric designs

Abstract

A technique for verifying an interconnect fabric design for interconnecting a plurality of network nodes. A design for the interconnect fabric specifies an arrangement of elements of the fabric and flow requirements among the network nodes. The invention programmatically verifies that the flow requirements are satisfied by the design and that the design does not violate constraints on the elements, such as available bandwidth or number of ports. This may also include determining whether the network can continue to satisfy the flow requirements in the event of one or more failures of elements of the interconnect fabric.

What is claimed is:  
     
         1 . A computer implemented method for verifying a design for an interconnect fabric, the design including an arrangement of interconnect elements for interconnecting a plurality of network nodes and the design having requirements for a plurality of flows among the network nodes, and for each of the plurality of flows, the method comprising associating the flow with a path for the flow through the interconnect fabric, and for each interconnect element in each path, aggregating requirements associated with each of the corresponding flows and determining whether the aggregated requirements exceeds a capacity of the interconnect element.  
     
     
         2 . The method according to  claim 1 , wherein the interconnect elements include interconnect devices and links.  
     
     
         3 . The method according to  claim 2 , wherein the interconnect devices are selected from the group consisting of switches and hubs.  
     
     
         4 . The method according to  claim 3 , wherein when the interconnect devices includes a hub, the method further comprises identifying an extent of a domain of hub connected components.  
     
     
         5 . The method according to  claim 4 , wherein said identifying the extent of the domain of hub connected components comprises performing a depth first search of the interconnect fabric for the hub connected components.  
     
     
         6 . The method according to  claim 5 , wherein said identifying an extent of a domain of hub connected components comprises constructing a tree data structure wherein a hub occupies a position in the tree and a other interconnect elements connected to the hub occupy positions in the tree one level down from the hub.  
     
     
         7 . The method according to  claim 1 , wherein the aggregated requirements include bandwidth requirements.  
     
     
         8 . The method according to  claim 7 , further comprising aggregating requirements of ports for each of the plurality of flows and determining whether a number of available ports of one or more of the interconnect elements is exceeded by the aggregated requirements of ports.  
     
     
         9 . The method according to  claim 1 , wherein the aggregated requirements include a number of ports.  
     
     
         10 . The method according to  claim 1 , said method further comprising determining whether a flow corresponds to a valid path through the interconnect fabric, a valid path starting at a source node for the flow, terminating at an end node for the flow and passing through a contiguous subset of the interconnect elements.  
     
     
         11 . The method according to  claim 10 , further comprising rejecting the design if it does not include a valid path for each flow.  
     
     
         12 . The method according to  claim 1 , wherein said associating comprises assigning a flow to a primary path in the design and further comprising assigning the flow to a backup path in the design to determine whether the design has capacity for the flow in the primary path and the backup path simultaneously.  
     
     
         13 . The method according to  claim 1 , wherein said associating comprises assigning a flow to a backup path for the flow in the design to determine whether the design has capacity for the flow in the secondary path in event of a failure in a primary path for the flow.  
     
     
         14 . A system for verifying a design for an interconnect fabric comprising: 
 a set of design information including requirements for a plurality of flows and a design specification wherein each of the plurality of flows is associated with a path for the flow through the interconnect fabric; and    a fabric design verification tool that, for each interconnect element in each path, aggregates requirements associated with each of the corresponding flows and determines whether the aggregated requirements exceeds a capacity of the interconnect element.    
     
     
         15 . The system according to  claim 14 , wherein the interconnect elements include interconnect devices and links.  
     
     
         16 . The system according to  claim 15 , wherein the interconnect devices are selected from the group consisting of switches and hubs.  
     
     
         17 . The system according to  claim 16 , wherein when the interconnect devices includes a hub, the design verification tool identifies an extent of a domain of hub connected components.  
     
     
         18 . The system according to  claim 17 , wherein the design verification tool identifies the extent of the domain of hub connected components by performing a depth first search of the interconnect fabric for the hub connected components.  
     
     
         19 . The system according to  claim 18 , wherein the design verification tool identifies an extent of a domain of hub connected components by constructing a tree data structure wherein a hub occupies a position in the tree and a other interconnect elements connected to the hub occupy positions in the tree one level down from the hub.  
     
     
         20 . The method according to  claim 14 , wherein the aggregated requirements include bandwidth requirements.  
     
     
         21 . The system according to  claim 20 , wherein the design verification tool aggregates requirements of ports for each of the plurality of flows and determines whether a number of available ports of one or more of the interconnect elements is exceeded by the aggregated requirements of ports.  
     
     
         22 . The method according to  claim 14 , wherein the aggregated requirements include a number of ports.  
     
     
         23 . The system according to  claim 14 , wherein the design verification tool determines whether a flow corresponds to a valid path through the interconnect fabric, a valid path starting at a source node for the flow, terminating at an end node for the flow and passing through a contiguous subset of the interconnect elements.  
     
     
         24 . The system according to  claim 23 , wherein the design verification tool rejects the design if it does not include a valid path for each flow.  
     
     
         25 . The system according to  claim 14 , wherein the design verification tool assigns a flow to a primary path in the design and also assigns the flow to a backup path in the design to determine whether the design has capacity for the flow in the primary path and the backup path simultaneously.  
     
     
         26 . The system according to  claim 14 , wherein the design verification tool assigns a flow to a backup path for the flow in the design to determine whether the design has capacity for the flow in the backup path in event of a failure in a primary path for the flow.