Lockless atomic table update

• US 8,537,825 B1
• Filed: 03/09/2011
• Issued: 09/17/2013
• Est. Priority Date: 09/28/2007
• Status: Expired due to Fees

• Current Assignee: F5 Networks, Inc. (F5 Incorporated)
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Mimms, Alan
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): MAGLO, EMMANUEL K
• Application Number:
  US13/044,339
• Time in Patent Office: 923 Days
• Field of Search: 370/389, 370/392, 370/395.31
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

Upon detecting a data event initiating an update to a table, a first classifier index associated with the data event is identified. From a classifier table, the current position in a first dimension of the table associated with the classifier index is determined. An open position in the first dimension of the table is also identified. Updated data is stored in the open position within the table. In the classifier table, the open position storing the updated data is associated with the classifier index.

Claims

1. A traffic manager device configured to provide uninterrupted access to a network traffic handling table during table updates, the device comprising:

a memory configured to store a set of processor executable instructions;

a network transceiver configured to handle network traffic;

a processor coupled to the network transceiver and the memory, the processor configured to execute the set of stored processor executable instructions which causes the processor to perform a method, the method further comprising;

identifying a first classifier index associated with a data packet received via the network interface;

identifying a second classifier index associated with the data packet;

accessing a first classifier table to determine a current position in a first dimension of a network traffic handling table associated with the first classifier index;

determining an open position in the first dimension of the network traffic handling table;

copying existing packet handling data from the current position to one or more corresponding locations in the open position in the first dimension of the network traffic handling table;

storing updated packet handling data within the open position in the network traffic handling table at a second dimension location indicated by the second classifier index;

associating the open position with the first classifier index in the first classifier table, wherein the open position becomes a new current position associated with the first classifier index;

designating the current position previously associated with the first classifier index as a new open position in the network traffic handling table; and

determining the second dimension location indicated by the second classifier index by referencing a second classifier table associating a plurality of second dimension locations with a plurality of second classifier indices.

2. The traffic manager device of claim 1, wherein at least one of the first classifier index or the second classifier indices are identified from the data packet by one of:

reading a segment of the data packet;

or

applying a function to at least a portion of the data packet.

3. The traffic manager device of claim 2, wherein the function applied to at least the portion of the data packet includes a hash function.

4. A traffic manager device configured to provide uninterrupted access to a network traffic handling table during table updates, the device comprising:

a memory configured to store a set of processor executable instructions;

a network transceiver configured to handle network traffic;

a processor coupled to the network transceiver and the memory, the processor configured to execute the set of stored processor executable instructions which causes the processor to perform a method, the method further comprising;

identifying a first classifier index associated with a data packet received via the network transceiver;

identifying a second classifier index associated with the data packet;

accessing a first classifier table to determine a current position in a first dimension of a network traffic handling table associated with the first classifier index;

determining an open position in the first dimension of the network traffic handling table;

copying existing packet handling data from the current position to one or more corresponding locations in the open position in the first dimension of the network traffic handling table;

storing updated packet handling data within the open position in the network traffic handling table at a second dimension location indicated by the second classifier index;

associating the open position with the first classifier index in the first classifier table, wherein the open position becomes a new current position associated with the first classifier index; and

designating the current position previously associated with the first classifier index as a new open position in the network traffic handling table,

wherein the network traffic handling table includes a destination table configured to store entries containing addresses of one or more resources to which one or more other data packets are to be directed, wherein an address of a resource to which an additional data packet is to be delivered is retrieved from the destination table based on a classifier index associated with the additional data packet.

5. A non-transitory machine readable medium having stored thereon instructions for providing uninterrupted access to a network traffic handling table during table updates, comprising machine executable code which when executed by at least one processor, causes the processor to perform steps comprising:

identifying a first classifier index associated with a data packet received by at least one of a plurality of traffic management devices;

determining from a first classifier table an initial table position in a first dimension of a network traffic handling table, the first classifier table associating classifier indices with table positions such that the initial table position is associated with the first classifier index;

determining an initial open table position in the first dimension of the network traffic handling table;

storing information associated with the data packet in the initial open table position in the network traffic handling table; and

associating the initial open table position with the first classifier index in the first classifier table.

6. The medium as set forth in claim 5, further comprising designating the initial table position previously associated with the first classifier index as an updated open position for the network traffic handling table.

7. The medium as set forth in claim 6, further comprising maintaining an indication of the updated open position in the network traffic handling table.

8. The medium as set forth in claim 5, further comprising:

identifying a second classifier index associated with the data packet;

determining a second initial table position in the network traffic handling table in a second dimension of the network traffic handling table such that the second initial table position is associated with the second classifier index; and

upon storing the information associated with the data packet in the initial open position in the network traffic handling table, storing the information associated with the data packet at the second initial table position of the second dimension in the initial open position in the network traffic handling table.

9. The medium as set forth in claim 8, wherein the first dimension of the network traffic handling table includes a plurality of columns and the second dimension of the network traffic handling table includes a plurality of rows.

10. The medium as set forth in claim 8, further comprising, before storing the information associated with the data packet in the initial open position in the network traffic handling table, copying existing data from the initial table position to one or more corresponding positions in the initial open table position of the network traffic handling table.

11. The medium as set forth in claim 8, wherein at least one of the first classifier index and the second classifier index are identified from the data packet by one of reading the first classifier index from a segment of the data packet or deriving the classifier index from the data packet by applying a function to at least a portion of the data packet.

12. The medium as set forth in claim 11, wherein the function applied to at least the portion of the data packet includes a hash function.

13. The medium as set forth in claim 5, wherein the network traffic handling table includes a destination table configured to store entries containing addresses of one or more resources to which one or more data packets are to be directed, such that an address of a resource to which an additional data packet is to be delivered is retrieved from the destination table based on a classifier index associated with the additional data packet.

14. The medium as set forth in claim 5, further comprising allowing multiple traffic management devices to update the network traffic handling table, wherein:

the multiple traffic management devices manage mutually exclusive sets of first classifier indices and initial open table positions within the network traffic handling tables such that the first classifier indices and initial open table positions being managed within the network traffic handling table cannot be updated by another traffic management device; and

the multiple traffic management devices determine the initial table position associated with the first classifier index in the first dimension of the network traffic handling table by applying one of;

a dedicated classifier table dedicated for each of the multiple traffic management devices;

or

a dedicated portion of the first classifier table for each of the multiple traffic management devices.

15. A method to provide uninterrupted access to a network traffic handling dataset during dataset updates, the method comprising:

identifying, by a network traffic management computing entity, a first classifier index associated with a data packet received by one of a plurality of traffic management entities;

determining, by the network traffic management computing entity from a first classifier dataset, an initial dataset position in a first dimension of the network traffic handling dataset, the first classifier dataset associating classifier indices with dataset positions such that the initial dataset position is associated with the first classifier index;

determining, by the network traffic management computing entity, an initial open dataset position in the first dimension of the network traffic handling dataset;

storing, by the network traffic management computing entity, information associated with the data packet in the initial open dataset position in the network traffic handling dataset; and

associating, by the network traffic management computing entity, the initial open dataset position with the first classifier index in the first classifier dataset.

16. The method of claim 15, further comprising designating, by the network traffic management computing entity, the initial dataset position previously associated with the first classifier index as an updated open position for the network traffic handling dataset.

17. The method of claim 16, further comprising maintaining, by the network traffic management computing entity, an indication of the updated open position in the network traffic handling dataset.

18. The method of claim 15, further comprising:

identifying, by the network traffic management computing entity, a second classifier index associated with the data packet;

determining, by the network traffic management computing entity, a second initial dataset position in the network traffic handling dataset in a second dimension of the network traffic handling dataset such that the second initial dataset position is associated with the second classifier index; and

upon storing the information associated with the data packet in the initial open position in the network traffic handling dataset, storing, by the network traffic management computing entity, the information associated with the data packet at the second initial dataset position of the second dimension in the initial open position in the network traffic handling dataset.

19. The method of claim 18, wherein the first dimension of the network traffic handling dataset includes a plurality of columns and the second dimension of the network traffic handling dataset includes a plurality of rows.

20. The method of claim 18, further comprising, before storing the information associated with the data packet in the initial open position in the network traffic handling dataset, copying, by the network traffic management computing entity, existing data from the initial dataset position to one or more corresponding positions in the initial open dataset position of the network traffic handling dataset.

21. The method of claim 18, wherein at least one of the first classifier index and the second classifier index are identified from the data packet by one of reading, by the network traffic management computing entity, the first classifier index from a segment of the data packet or deriving, by the network traffic management computing entity, the classifier index from the data packet by applying a function to at least a portion of the data packet.

22. The method of claim 21, wherein the function applied to at least the portion of the data packet includes a hash function.

23. The method of claim 15, wherein the network traffic handling dataset includes a destination dataset configured to store entries containing addresses of one or more resources to which one or more data packets are to be directed, such that an address of a resource to which an additional data packet is to be delivered is retrieved from the destination dataset, by the network traffic management computing entity, based on a classifier index associated with the additional data packet.

24. The method of claim 15, further comprising allowing, by the network traffic management computing entity, multiple traffic management entities to update the network traffic handling dataset, wherein:

the multiple traffic management entities manage mutually exclusive sets of first classifier indices and initial open dataset positions within the network traffic handling dataset such that the first classifier indices and initial open dataset position being managed within the network traffic handling dataset cannot be updated by another traffic management entity; and

the multiple traffic management entities determine the initial dataset position associated with the first classifier index in the first dimension of the network traffic handling dataset by applying one of;

a dedicated classifier dataset dedicated for each of the multiple traffic management entities;

or

a dedicated portion of the first classifier dataset for each of the multiple traffic management entities.

25. A method to provide uninterrupted access to a network traffic handling table during table updates, the method comprising:

receiving, by a network traffic management computing device, a data packet;

identifying, by the network traffic management computing device, a first classifier index associated with the data packet;

identifying, by the network traffic management computing device, a second classifier index associated with the data packet;

accessing, by the network traffic management computing device, a first classifier table to determine a current position in a first dimension of the network traffic handling table associated with the first classifier index;

determining, by the network traffic management computing device, an open position in the first dimension of the network traffic handling table;

copying, by the network traffic management computing device, existing packet handling data from the current position to one or more corresponding locations in the open position in the first dimension of the network traffic handling table;

storing, by the network traffic management computing device, updated packet handling data within the open position in the network traffic handling table at a second dimension location indicated by the second classifier index;

associating, by the network traffic management computing device, the open position with the first classifier index in the first classifier table, wherein the open position becomes a new current position associated with the first classifier index; and

designating, by the network traffic management computing device, the current position previously associated with the first classifier index as a new open position in the network traffic handling table.

26. The method of claim 25, further comprising determining, by the network traffic management computing device, the second dimension location indicated by the second classifier index by referencing a second classifier table associating a plurality of second dimension locations with a plurality of second classifier indices.

27. The method of claim 26, wherein at least one of the first classifier index or the second classifier indices are identified from the data packet by one of:

reading, by the network traffic management computing device, a segment of the data packet;

or

applying, by the network traffic management computing device, a function to at least a portion of the data packet.

28. The method of claim 27, wherein the function applied to at least the portion of the data packet includes a hash function.

29. The method of claim 25, wherein the network traffic handling table includes a destination table configured to store entries containing addresses of one or more resources to which one or more other data packets are to be directed, such that an address of a resource to which an additional data packet is to be delivered is retrieved from the destination table, by the network traffic management computing device, based on a classifier index associated with the additional data packet.