Congestion management in a network

• US 8,855,121 B2
• Filed: 03/12/2013
• Issued: 10/07/2014
• Est. Priority Date: 05/24/2002
• Status: Expired due to Term

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: Conversant Intellectual Property Management Inc (MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management))
• Inventors: Brown, David
• Primary Examiner(s): Pham, Brenda H
• Application Number:
  US13/795,070
• Publication Number:
  US 20130208596A1
• Time in Patent Office: 574 Days
• Field of Search: 370/368, 370/371, 370/374, 370/378, 370/379, 370/381, 370/382, 370/383, 370/395.31, 370/395.7, 370/395.32
• US Class Current: 370/395.32
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

Management of congestion level, in a computer-related context, is disclosed. Also disclosed is a system generating a plurality of computer network-related tables during system operation. A number of the tables are each separately indexed by a different index. The system includes at least one tangible computer-readable medium adapted to store, at each indexed location, a swap count providing an indication of the congestion level of the indexed location. The system also includes insert logic stored as instructions on the at least one medium for execution. When executed, the insert logic is operable to: i) insert, when a predetermined condition has been satisfied, a new entry by overwriting the current entry stored in the indexed location having the lowest swap count; and ii) update the swap counts in each of the indexed locations in a manner that maintains the total swap count at least substantially constant over time.

Claims

1. A network device comprising:

one or more processing modules operable to generate a plurality of indexes associated with each of a plurality of keys;

a look-up table having a plurality of memories, each memory including at least one indexed location for storing at least one indexed entry, each indexed entry being separately indexed by one of the plurality of indexes, wherein;

each indexed entry includes a key field, a data field, and a count field;

the count field stores a count value dependent on a number of insert operations for all keys associated with the indexed location, the count value being indicative of a congestion level of the indexed entry; and

the one or more processing modules are further operable to;

receive a request to insert an insert entry in the look-up table, the entry including an insert key and insert data;

select an entry with a lowest count value among the indexed entries of the multiple memories associated with the insert key;

modify the count value of the selected entry; and

write the count value along with insert data in the selected entry.

2. The network device as claimed in claim 1, wherein the data field includes a logical port forward vector associated with a key stored in the key field.

3. The network device as claimed in claim 1, wherein each indexed entry is inserted in the look-up table with an initial count value equal to one half of a maximum count value.

4. The network device as claimed in claim 1, wherein the one or more processing modules are further operable to modify the count value of the non-selected entries associated with the insert key such that a sum of the count values associated with the insert key remains constant.

5. The network device as claimed in claim 1, wherein modifying the count value of the selected entry comprises incrementing the count value of the selected entry.

6. The network device as claimed in claim 5, wherein modifying the count value of the selected entry further comprises decrementing the count values of the non-selected entries associated with the insert key.

7. The network device as claimed in claim 1, wherein selecting an entry with the lowest count comprises:

when multiple entries have the lowest count value, randomly selecting one of the entries with the lowest count.