| 摘要 |
Exemplary methods for maintaining a shared forwarding table 133 in a forwarding plane include a first network device 103 operating in a forwarding plane 106 receiving information associated with a first forwarding table 108 from a second network device 101 operating in a control plane 105, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table 108. The method further includes for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table. In an embodiment, for each entry in the received information associated with the first forwarding table, the first network device 103 determines a first candidate location in the shared forwarding table in which the entry may be inserted and determines whether the first candidate location already contains another entry (resulting in a "collision"). In response to determining that there is no collision, the first network device 103 inserts the entry of the first forwarding table in the first candidate location. Alternatively, the first network device 103 determines whether the number of collision resolution attempts has reached a predetermined threshold. The first network device 103 includes a table generator 121 for generating forwarding tables as part of shared forwarding table 133, using forwarding table information 108 received from control plane 105. Table generator 121 includes a collision detector 132. Collision detector 132 determines whether the referenced location already contains another entry. Where table generator 121 is configured to generate shared forwarding table 133 as a hash table, collision detector 132 may implement a collision resolution algorithm such as separate chaining, open addressing, coalesced hashing, cuckoo hashing, robin hood hashing, 2-choice hashing, hopscotch hashing. |
