System and method for distributing packets among a plurality of paths to a destination

• US 7,190,696 B1
• Filed: 03/05/2002
• Issued: 03/13/2007
• Est. Priority Date: 03/05/2002
• Status: Active Grant

• Current Assignee: Dell Marketing Corporation (Dell Technologies Inc.)
• Original Assignee: Force10 Networks, Inc. (Dell Technologies Inc.)
• Inventors: Manur, Rajeev, Subramanian, Krishnamurthy, Senevirathne, Tissa
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): HAMANN, JORDAN J
• Application Number:
  US10/092,198
• Time in Patent Office: 1,834 Days
• Field of Search: None
• 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/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A network-processor device comprises a packet-processor for an ingress port that is operative to distribute data flows to a plurality of equal-cost paths for transfer of data toward a given destination. The packet-processor also includes further distribution circuitry for designating a link of a link aggregation by which to channel the data between routers within a part of a selected path. Accordingly, each of the layer distributions—i.e., amongst the higher-level equal-cost-paths and amongst the lower-level link aggregation—are capable of being coordinated by a common, generic packet-processor.

Claims

1. A network-processing device comprising:

a first table to be addressed by content information of received data, and to provide output data dependent upon the content information;

a second table to be addressed by an output of the first table, and comprising an output to present output data dependent upon the output of the first table, the output comprising a plurality of fields; and

a multiplexer operable to obtain information of a next-hop transfer of the received data by selecting from amongst a plurality of next-hop designations;

separate fields of the plurality of the second table to originate at least two of the next-hop designations.

2. A network-processing device according to claim 1, further comprising a processor to obtain content information from a header of the received data;

the first table comprising a content addressable memory;

the processor to use the obtained content information to address the content addressable memory; and

the content addressable memory having separate pointer entries to be selectively output dependent on the content information presented thereto.

3. A network-processing device according to claim 2, in which

the second table is addressed by the output of the content addressable memory;

the second table to output data for the separate fields dependent on the output of the content addressable memory;

a first field of the plurality to originate one of the plurality of next-hop designations; and

a second field of the plurality to originate at least another of the next-hop designations.

4. A network-processing device according to claim 3, in which the first field of the plurality is coupled directly to the multiplexer to provide one of the next-hop designations.

5. A network-processing device according to claim 4, further comprising:

a third table;

the third table comprising a plurality of selectable entries comprising next-hop data;

the second field of the output of the second table to index the third table;

the third table to output next-hop data from a select entry thereof, the entry selection dependent upon the indexing established by the second field of the output of the second table; and

the output of the third table providing another of the plurality of next-hop designations.

6. A network-processing device according to claim 5, in which the second field of the output of the second table comprises at least two subportions;

the network-processing device further comprises a second multiplexer to select one subportion from the at least two subportions; and

the second multiplexer is to index the third table with the select one subportion.

7. A network-processing device according to claim 6,

the second multiplexer to make the selection dependent upon a control signal;

the output of the second table further comprising a third field; and

the third field to establish the control signal.

8. A network-processing device according to claim 7, the third field of the output of the second table also to establish a control signal for the first multiplexer.

9. A network-processing device according to claim 8, the second table to include at least one entry to provide a value to the third field to enable the first multiplexer to select the first field of the plurality.

10. A network-processing device according to claim 9, in which the at least one entry of the second table to provide a next-hop data value to the first field of the plurality.

11. A network-processing device according to claim 10, in which the second table comprises at least another entry to provide a value for the third field to enable the first multiplexer to select the output of the third table.

12. A network-processing device according to claim 7, in which

the second multiplexer is to select from the at least two subportions dependent upon a control signal;

and

the network-processing device further comprises;

a modulo processor to output a control signal to the second multiplexer dependent upon a hash input and a count input;

the count input to receive a count value from the third field; and

the hash input to receive a hash value based upon header information of the received data.

13. A network-processing device according to claim 12, the second field of the plurality comprising M subportions;

the second table to include entries of a first plurality having count values n to be output to the third field of the plurality of fields dependent upon indexing by pointers of the content addressable memory; and

the entries of the first plurality of the second table including values for at least n subportions of the M subportions.

14. A network-processing device according to claim 13, in which n is less than (M+1).

15. A network-processing device according to claim 1, in which

the second table output includes a third field;

the third field to establish a control signal; and

the multiplexer to select from amongst the plurality of next-hop data sources dependent upon the control signal established by the third field.

16. A network-processing device comprising:

a first table having a plurality of selectable pointers and an output to present a selected pointer of the plurality;

a second table configured to be indexed by the selected pointer of the first table, the second table comprising a plurality of selectable entries to be output when designated by the pointer output of the first table;

a link aggregation (LAG) circuit operable to define a next-hop pointer based upon a first output of the second table;

a next-hop table comprising a plurality of selectable entries with next-hop port ID'"'"'s; and

a multiplexer to select a next-hop pointer to index the next-hop table from one of the LAG circuit or a second output of the second table.

17. A network-processing device according to claim 16, in which the second table comprises a plurality of output fields, the output fields including a control-field, the entries of a first plurality of the second table comprise first data for the control-field, the entries of a second plurality of the second table comprise second data for the control-field;

the multiplexer selection to depend upon data in the control field of the output of the second table.

18. A network-processing device according to claim 17, in which the LAG circuit comprises:

a LAG table to provide a plurality of entries comprising LAG-size values indexed by LAG-ID values;

each entry of the first plurality of the second table having a pointer-field comprising a LAG-ID value for indexing the LAG table;

the LAG table to output a LAG-size value dependent on the LAG-ID value in the pointer-field output of the second table; and

distribution circuit to establish an output value of magnitude up to the LAG-size value;

the output of the distribution circuit combined with the pointer-field of the second table output to establish and present a next-hop pointer to a selectable first input of the multiplexer.

19. A network-processing device according to claim 18, in which the pointer-field portion of the second table output establishes the most significant bits for the next-hop pointer for the selectable first input of the multiplexer and the output of the distribution circuit the least significant bits.

20. A network-processing device according to claim 18, in which the distribution circuit comprises:

a mod processor to provide the output value up to the LAG-size value by using one of either a mod or modulo operator to operate upon a HASH value with a LAG-length value, the LAG-length determined from the LAG-size value output from the LAG table, and the HASH value to be determined from a header of data received by the network processing device.

21. A network-processing device according to claim 20, in which the distribution circuit further comprises an incrementor to receive and increment the LAG-size value from the LAG table to provide the LAG-length value.

22. A network-processing device according to claim 20, further comprising a data processor to identify a header of the received data, and present an index to the first table dependent upon a destination address of the header.

23. A network-processing device according to claim 22, in which the data processor is to provide the HASH value to the mod processor dependent upon the identified header.

24. A network-processing device according to claim 16, in which the second table comprises a SRAM.

25. A network-processing device according to claim 24, in which the entries of the SRAM comprise first, second and third data fields;

the first data field of at least the first plurality of entries comprising LAG-values to be used by the LAG circuit in generating the next-hop pointer;

the second data field of at least the second plurality of entries comprising next-hop pointer values to index the next-hop table; and

the third data field of at least the first and second plurality of entries comprising control data to establish respective selections of the multiplexer.

26. A network-processing device according to claim 25, in which the bits for the first data field of the output of the SRAM over-lap a portion of the second data field.

27. A network-processing device according to claim 26, in which the first data field comprises the least significant bits of the second data field.

28. A network-processing device according to claim 25, the second table further comprising at least one selectable entry comprising a next-hop port-ID value to be used directly by the network-processing device for designating an egress port for a next-hop data transfer.

29. A network-processing device according to claim 28, the SRAM further comprises a fourth data field comprising the at least one next-hop port-ID value to be used directly for designating the egress port.

30. A network-processing device according to claim 29, further comprising a second multiplexer to select one of the fourth data field from the output of the SRAM or the output from the next-hop table to obtain the port ID value for designating the select egress port.

31. A multiple-link network-processing device for routing data, comprising:

a data processor to receive data and determine content information thereof;

a content addressable memory having a plurality of pointers to be output dependent upon content information determined by the data processor;

a second table comprising a plurality of selectable entries to be output dependent upon the pointers output by the content addressable memory;

the second table output comprising a plurality of data fields;

a first data field of the plurality comprising a plurality of sub-fields;

at least a first plurality of the selectable entries of the second table comprising ID values for at least one sub-field of the first data field; and

a multiplexer to select one of the sub-fields of the first data field of the output of the second table to obtain an ID value for establishing an egress port for transfer of the received data.

32. A multiple-link network-processing device according to claim 31, further comprising a next-hop table comprising a plurality of selectable entries having port identifications to be output when selectively indexed by a pointer value provided by the multiplexer'"'"'s output.

33. A multiple-link network-processing device according to claim 32, in which a second data field of at least a portion of the selectable entries of the second table comprise control values;

and

the multiplexer selection dependent upon the control value in the second data field of the output of second table.

34. A multiple-link network-processing device according to claim 33, in which the multiplexer comprises M inputs coupled to M sub-fields of the first-field of the output of the second table;

and

the control values for the second data field of at least the portion of the selectable entries of the second table comprise integer count values from 1 to N, wherein N is a value up to M;

the multiple link network device further comprising a distribution circuit to establish a control signal to enable the multiplexer to select from one of 1 to N inputs of its M inputs when N is not equal to zero.

35. A multiple-link network-processing device according to claim 34, in which the distribution circuit comprises a mod processor operable to provide the control signal of value up to N by performing one of either a mod or modulo operation of a HASH value acted upon by the count value N plus one, the data processor to provide the HASH value based upon a header of the received data.

36. A multiple-link network-processing device according to claim 34, in which the data processor is to examine content information of a header of the received data to determine one of a Forwarding Equivalent Class (FEC) or Quality of Service (QS) for identifying a given flow.

37. A multiple-link network-processing device according to claim 34, in which the data processor is to keep the HASH value fixed for a given identified flow.

38. A multiple-link network-processing device according to claim according to claim 34, further comprising a link aggregation (LAG) circuit operable to define a next-hop pointer based upon at least a portion of the output of the multiplexer.

39. A multiple-link network-processing device according to claim 38, in which the LAG circuit comprises:

a LAG-size table indexed by at least the portion of the multiplexer output;

the LAG-size table comprising a plurality of selectable entries with LAG-size values to be output when selected by respective LAG-ID pointers as established via the portion of the multiplexer output; and

a second distribution circuit to establish a LAG value of magnitude up to the LAG-size value provided by the LAG-size table;

the LAG value to define at least the least-significant-bits of the next-hop pointer.

40. A multiple-link network-processing device according to claim 39, in which the portion of the output of the multiplexer to index the LAG-size table is to be combined with the LAG value provided by the LAG-size table for defining the next-hop pointer.

41. A multiple-link network-processing device according to claim 40, in which the portion of the output of the multiplexer is to define the most significant bits of the next-hop pointer and the output of the second distribution circuit the least-significant-bits of the next-hop pointer.

42. A multiple-link network-processing device according to claim 41, in which the second distribution circuit comprises a mod processor to establish the LAG value per one of a mod or module operation of a HASH value using a LAG length as the mod divisor, the LAG length related to the LAG size value provided by the LAG-size table, the data processor to provide the HASH value to the mod processor based upon header information of the received data.

43. A multiple-link network-processing device according to claim 42, in which the LAG circuit further comprises an incrementor to increment the LAG-size value provided by the LAG-size table to provide the LAG length to the mod processor.

44. A multiple-link network-processing device according to claim 41, further comprising a second multiplexer to output a select next-hop pointer to index the next-hop table, the second multiplexer to make its selection from at least first and second inputs, the first input to receive the next-hop pointer of the output of the LAG circuit and the second input coupled to the output of the first multiplexer.

45. A multiple-link network-processing device according to claim 44, in which the second multiplexer is to receive a control signal related to the value of the output of the first multiplexer.

46. A multiple-link network-processing device according to claim 45, in which the most significant bits of the output of the first multiplexer determine the control signal of the second multiplexer.

47. A multiple-link network-processing device according to claim 46, in which bits other than the most significant bits of the output of the first multiplexer provide the portion to index the LAG size table.

48. A multiple-link network-processing device according to claim 44, further comprising a third multiplexer to select one of at least first and second inputs from which to obtain an output port identification for identifying the egress port, the first input of the third multiplexer coupled to receive the port identification of the output of the next-hop table and the second input of the third multiplexer coupled to receive data from a third field of the output of the second table.

49. A multiple-link network-processing device according to claim 48, in which the third data field of at least another portion of the selectable entries of the second table comprises port identification values for identifying, when selected per indexing by the pointers of the output of the content addressable memory, an egress port for transfer of the received data.

50. A multiple-link network-processing device according to claim 49, in which the third multiplexer selection is to be determined by the control value of the second data field of the output of the second table.

51. A multiple-link network-processing device according to claim 50, in which the at least another portion of the selectable entries of the second table comprise a count value of zero for the second data field and the third multiplexer to select the second input when zero is the count value of the second data field of the output of the second table.

52. A multiple link network-processing device according to claim 31, further comprising data handling circuitry to transfer the received data to the designated egress port using a protocol procedure of the group consisting of MPLS, IP Switching, Cell Switching, Tag Switching and Aggregate Route-Based IP Switching protocols.

53. A network processing device comprising:

a first table having a plurality of indexed pointers for selectable output;

a second table to be indexed by a pointer output of the first table, the second table comprising;

a plurality of entries for selective output, and

a plurality of output fields to present respective bit-fields of a selected entry of the plurality;

a first selection circuit to select an output field of the plurality of output fields of the second table from which to obtain a second pointer;

a third table to be indexed by the second pointer established by the first selection circuit, the third table comprising;

a plurality of entries for selective output, and

a plurality of output fields to present respective bit-fields of a selected entry of the plurality;

a second selection circuit to select an output field of the plurality of output fields of the third table from which to obtain a third pointer; and

egress port look-up circuitry to establish an egress port identification based upon the third pointer selected by the second selection circuit.

54. A network processing device according to claim 53, in which the first selection circuit comprises:

a distribution circuit to receive a count-value and a hash value and provide a selection signal based upon at least one of a mod or modulo operation of the hash value acted upon by the count value as the mod divisor; and

a multiplexer having multiple inputs coupled to output fields of the plurality of output fields of the second table;

the multiplexer selecting an output field of the plurality dependent upon the selection signal provided by the distribution circuit.

55. A network processing device according to claim 54, in which the second selection circuit comprises:

a distribution circuit to receive a second count-value and a second hash value and provide a selection signal based upon at least one of a mod or modulo operation of the second hash value acted upon by the second count value as the mod divisor; and

a multiplexer having multiple inputs coupled to output fields of the plurality of output fields of the third table;

the multiplexer selecting an output field of the plurality dependent upon the selection signal provided by the distribution circuit.

56. A network processing device according to claim 55, in which the count value for the first selection circuit is obtained from an output field of the plurality of output fields of the second table.

57. A network processing device according to claim 56, in which the count value for the second selection circuit is obtained from an output field of the plurality of output fields of the third table.

58. A network processing device according to claim 57, further comprising a processor to determine header information of a received data packet, establish a pointer for the first table based upon a destination address of the header information, and establish hash values for the distribution circuits of the first and second selection circuits based upon the header information.

59. A network processing device according to claim 58, in which the plurality of outputs of the second table comprises a count output to present the count-value to the modulo circuit of the first selection circuit.

60. A network processing device according to claim 59, in which the processor is further to establish a second hash value for the distribution circuit of the second selection circuit based upon the header information.

61. A network processing device according to claim 60, the processor to establish the second hash value by a bit rotation of the first hash value.

62. A network processing device according to claim 59, in which the plurality of outputs of the third table comprises a count output to present the count-value to the modulo circuit of the second selection circuit.

63. A network processing device according to claim 58, in which the egress port look-up circuitry comprises:

a LAG distribution circuit to select one of a plurality of LAG egress-port identifications by which to designate a select egress-port, the selection based upon a LAG ID and a LAG hash value; and

LAG identification circuitry to establish the LAG ID for the LAG distribution circuit based upon one of the output fields of the third table;

the processor to provide the LAG hash value based upon the header information of the received data packet.

64. A network processing device according to claim 63, in which the LAG identification circuitry comprises:

a next-hop table to be indexed by the output of the second selection circuitry, the next-hop table comprising a plurality of entries including LAG ID values and an output for presenting a selected LAG ID value; and

a multiplexer to select the next-hop LAG ID from one of the output of the next hop table and an output field of the plurality of output fields of the third table, the next hop LAG ID selected by the multiplexer to provide the LAG ID for the LAG distribution circuit.

65. A network processing device according to claim 64, in which the LAG identification circuitry further comprises multiplexing to alternatively obtain the select LAG ID from an output field of the plurality of output fields of the second table as an alternative direct LAG ID.

66. A network processing device according to claim 65, in which the next-hop table of the LAG identification circuitry further comprises another plurality of entries having egress-port ID values for selective output, the network processing device further comprising an output multiplexer to select a next hop egress-port identification from the group consisting of the egress-port ID value output of the LAG-distribution circuit and the select egress-port ID value output of the next hop table.

67. A network processing device according to claim 66, in which the output multiplexer further comprises additional multiplexing to enable alternative selection of the next hop egress-port identification from an egress port ID value output field from the plurality of output fields of the third table.

68. A network processing device according to claim 67, in which the output multiplexer further comprises additional multiplexing to alternatively select the next hop egress-port identification from an egress port ID value output field from the plurality of output fields of the second table.

69. A network processing device according to claim 68, in which the output multiplexer selection to depend on at least one of the group of:

the count values of the first and second distribution circuits of the respective first and second selection circuits;

enablement of the LAG distribution circuitry to provide an egress-port ID value; and

enablement of the next hop table of the LAG ID circuitry to provide a LAG ID for the LAG distribution circuitry.

70. A network processing device according to claim 64, in which the LAG distribution circuit further comprises:

a LAG egress port table comprising a plurality of egress-port ID'"'"'s for selectable output; and

a LAG address calculation circuit to determine a pointer by which to index the LAG egress port table, the address calculation to be based upon the next-hop LAG ID selected by the multiplexer of the LAG identification circuitry and a LAG hash value;

the processor further to establish the LAG hash value based upon the header information of the received data packet.

71. A network processing device according to claim 70, in which the LAG address calculation circuit comprises:

a LAG size table to receive the next-hop LAG ID and output a LAG size value dependent on the received LAG ID;

distribution circuit to determine an output value of magnitude up to the LAG size value, the output value based upon the LAG hash value; and

merger circuit to merge the output of the distribution circuit with the LAG ID to provide the pointer for indexing the LAG egress port table.

72. A network processing device according to claim 71, in which the distribution circuit of the LAG address calculation circuit comprises a mod processor to provide its output value by performing one of a mod or modulo operation of the hash value acted upon by the LAG size as the mod divisor.