Barefoot Networks, Inc.

Milad Sharif

Changhoon Kim

Jeongkeun Lee

Robert Soule

Chaitanya Kodeboyina

Parag Dattatraya Bhide

Vasanth Kumar

Some embodiments provide a method for a forwarding element (FE) operating in a network of FEs. The method receives a data message with an access control list (ACL) rule and a first digest for the ACL rule appended to the data message. The ACL rule specifies that the packet is allowed to be sent through the network. The method verifies the ACL rule by computing a second digest from the ACL rule using a secret key and comparing the first digest to the second digest. The method determines whether the packet matches the ACL rule by comparing values in headers of the data message to values specified in the ACL rule. The method only forwards the data message if the ACL rule is verified and the packet matches the ACL rule.

Verification of access control list rules provided with a message

A method of forwarding packets by a physical network switch is provided. The method assigns egress ports that connect the network switch to each particular next hop to a weighted-cost multipathing (WCMP) group associated with the particular next hop. The method assigns weights to each egress port in each WCMP group according to the capacity of each path that connects the egress port to the next hop associated with the WCMP group and normalizes the weights over a range of values. For each packet received at the network switch, the method identifies the WCMP group associated with a next hop destination of the packet. The method calculates a hash value of a set of fields in the packet header and uses the hash value to perform a range lookup in the identified WCMP group to select an egress port for forwarding the packet to the next hop.

Weighted-cost multi-pathing using range lookups

Some embodiments provide a method for configuring unit memories (e.g., unit static random access memories (SRAMs) and ternary content addressable memories (TCAMs) of a network forwarding IC to implement a set of longest prefix matching (LPM) tables. Two different methods of providing a longest prefix match (LPM) operation that minimize the use of ternary content addressable memory (TCAM) are presented. Each method takes advantage of the use of match-action stages and the programmability of the unit memories. An algorithmic LPM embodiment is presented which uses a TCAM index with pointers to SRAM partitions that store subtrees of a routing tree (routing trie structure) and performs subtree rearrangements in the partitions upon the addition of certain routing entries. A chained LPM embodiment, allocates separate exact-match tables for a set of address prefix lengths in, for example, SRAMS, as well as a set of non-exact match tables in, for example, TCAMs.

Chained longest prefix matching in programmable switch

Some embodiments provide a method for a particular FE in a network of FEs. The method receives a data message at a first port of the FE. The data message includes a header that specifies an egress port for each FE along a path from a source of the data message to a destination of the data message and an ingress port for at least each FE along the path that the data message has previously traversed. The method determines that the particular egress port specified for the FE is a second port that is not operational. The method generates a path failure message specifying that the second port is not operational and including a header that uses the egress ports and ingress ports in the data message. The method sends the path failure message out of the first port for delivery to the source of the data message.

Generation of path failure message at forwarding element based on message path

Some embodiments provide a method for a particular forwarding element (FE) in a network of FEs. The method receives a packet at the particular FE. The packet includes a packet header that includes, for each of multiple FEs along a path from a source of the packet to a destination of the packet, (i) an identifier for the FE and (ii) a set of one or more actions for the FE to perform on the packet. The method parses the packet header to identify the set of actions for the particular FE. The method performs the identified set of actions.

Execution of packet-specified actions at forwarding element

Some embodiments provide a network that includes (i) multiple forwarding elements, (ii) a set of one or more global control plane (GCP) servers, and (iii) multiple end-node machines. The GCP servers maintain topological information about connections between the forwarding elements. Each of the end-node machines receives the topological information, identifies a source-routing path for a message sent by the machine, and embeds the source-routing path in a source-routing message header that includes an egress port for each forwarding element along the path.

Growing community of inventors

Mountain View, CA, United States of America

Milad Sharif