Using headerspace analysis to identify flow entry reachability
AssigneeNicira, Inc.
InventorsRonghua Zhang, Amre Shakimov, Teemu Koponen
Life of this patent
Estimating the term…
Abstract
Some embodiments provide a method that uses headerspace analysis. The method receives several flow entries for distribution to a set of forwarding elements that implement a logical network. The method models each of the flow entries as a function that operates on a representation of a packet header. The method uses the modeled functions to identify a set of paths from a packet source to a packet destination. For each particular path of the identified paths, the method uses inverses of the modeled functions to determine a set of packet headers. Packets sent from the packet source with any packet header in the set of packet headers follow the particular path through the flow entries.
Claims21
1-20. (canceled)
A method comprising:
- receiving a plurality of flow entries, arranged in a sequence of stages, to be distributed to a forwarding element;
- modeling each of the flow entries as a function that operates on a set of packet header fields;
- processing sets of packet header field values, representing possible packets to be received by the forwarding element, through the sequence of stages a first time to (i) identify flow entries matched by any of the sets of packet header field values and (ii) generate new flow entries based on received flow entries that comprise actions to create a new flow entry;
- modeling each of the generated new flow entries as a function that operates on a set of packet header fields;
- and
- processing the sets of packet header field values through the sequence of stages, comprising the new flow entries in addition to the plurality of flow entries, a second time in order to identify any additional flow entries of the plurality of flow entries that are matched by any of the sets of packet header field values.
A method comprising:
- receiving a plurality of flow entries to be distributed to a forwarding element;
- modeling each of the flow entries as a function that operates on a set of packet header fields;
- determining sets of packet header field values representing possible packets to be received by the forwarding element, the sets of packet header field values comprising at least one set of packet header field values representing packets to be received by the forwarding element via a tunnel from another forwarding element;
- and
- applying the functions to the sets of packet header field values to determine a set of the flow entries that are not matched by any of the possible packets to be received by the forwarding element, wherein the determined set of flow entries are removed from the plurality of flow entries to be distributed to the forwarding element.
Dependencies are inferred from the claim text.