Barefoot Networks, Inc.

Robert Soule

Jeongkeun Lee

Changhoon Kim

Milad Sharif

Han Wang

John Nathan Foster

Steffen Julif Smolka

Cole Nathan Schlesinger

William Hallahan

Mon Jed Liu

A method for verifying data plane programs is provided in some embodiments. Because the behavior of a data plane program (e.g., a program written in the P4 language) is determined in part by the control plane populating match-action tables with specific forwarding rules, in some embodiments, programmers are provided with a way to document assumptions about the control plane using annotations (e.g., in the form of 'assertions' or 'assumptions' about the state based on the unknown control plane contribution). In some embodiments, annotations are added automatically to verify common properties, including checking that every header read or written is valid, that every expression has a well-defined value, and that all standard metadata is manipulated correctly. The method in some embodiments translates programs from a first language (e.g., P4) to a second language (e.g., Guarded Command Language (GCL)) for verification by a satisfiability modulo theory (SMT) solver.

Data plane program verification

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

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

San Carlos, CA, United States of America

Robert Soule