Efficient hitless upgrade of packet processing filters
AssigneeArista Networks, Inc.
InventorRamakrishna Paduvalli
Life of this patent
Estimating the term…
Abstract
Upgrading packet processing rules in a network device with a replacement set of rules includes generating an edit sequence that represents edit operations to transform an already-installed old set of rules into the replacement rules. The edit sequence is used to identify a subsequence of rules that is common to both the old rules and the replacement rules. A merged list is generated by a combination of the old rules, the replacement rules, and the common subsequence of rules. The merged list is downloaded to the network device, overwriting the old rules in bottom-up fashion to allow packet processing to continue concurrently using the old rules.
Claims20
A method in a network device having stored in a memory thereof a plurality of filters generated from a first plurality of access control lists (ACLs), the method comprising:
- receiving a second plurality of ACLs;
- producing a first list comprising ACLs that are common to both the first and second plurality of ACLs, wherein the first list is a longest common subsequence (LCS) of the ACLs between the first and second plurality of ACLs;
- storing into a merged list first filters generated from ACLs in the first and second plurality of ACLs that are not listed in the first list;
- producing a plurality of second lists, each second list corresponding to an ACL listed in the first list and comprising rules that are common to both an ACL in the first plurality of ACLs and an ACL in the second plurality of ACLs that are identified by the listed ACL, wherein each second list is an LCS of the rules;
- storing into the merged list second filters generated from rules in the first and second plurality of ACLs that are not in any of the plurality of second lists;
- for each rule listed in each of the plurality of second lists:
- producing third filters from a first rule in the first plurality of ACLs and fourth filters from a second rule in the second plurality of ACLs;
- computing a third list comprising filters that are common to both the third and fourth filters, wherein the third list is an LCS of the filters;
- and
- storing each of the third and fourth filters into the merged list, including setting a version bit of the filter being stored according to whether or not the filter is in the third list;
- and
- replacing the plurality of filters stored in the memory of the network device with filters stored in the merged list.
A network device comprising:
- a first memory;
- a second memory;
- and
- one or more computing elements,
- the first memory having stored therein executable program code, which when executed by the one or more computing elements, causes the one or more computing elements to:
- compute a longest common subsequence of access control lists (ACL LCS) from a first plurality of ACLs and a second plurality of ACLs;
- generate first filters from ACLs that are not identified in the ACL-LCS and store the first filters in a merged list;
- compute a plurality of rules LCSs from rules in ACLs identified in the ACL LCS;
- generate second filters from rules that are not identified among the plurality of rules LCSs and store the second filters in the merged list;
- compute a plurality of filter LCSs from third filters computed from rules identified among the rules LCSs;
- store the third filters in the merged list, including setting a version bit on each filter in accordance with whether or not the filter is among the plurality of filter LCSs;
- and
- store filters in the merged list to the second memory.
A method in a network device, the method comprising:
- identifying pairs of access control lists (ACLs) between first and second collections of ACLs that have a same ACL identifier, including computing a longest common subsequence (LCS) of the ACL identifiers between the first collection of ACLs and the second collection of ACLs;
- identifying, for a given pair of ACLs, pairs of rules between the given pair of ACLs that have the same rule name, including computing an LCS of the rule names between the given pair of ACLs;
- and
- for a given pair of rules:
- generating a first set of filters for a first rule in the given pair of rules and a second set of filters for a second rule in the given pair of rules;
- computing an LCS of filters between the first set of filters and the second set of filters, wherein filters in the LCS of filters occurs in both the first and second sets of filters;
- and
- storing each filter among the first and second sets of filters to a merged list, including setting a version bit according to whether the filter occurs in the LCS of filters or not.
Dependencies are inferred from the claim text.