Systems and methods for processing any-to-any transmissions

• US 8,125,997 B1
• Filed: 09/18/2007
• Issued: 02/28/2012
• Est. Priority Date: 03/12/2003
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Greene, Spencer
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US11/857,086
• Time in Patent Office: 1,624 Days
• Field of Search: None
• US Class Current: 370/401
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A data processing system performs any-to-any transmission of data blocks. The system receives the data blocks on incoming data streams, and load balances the data blocks across a number of processing paths. The processing paths process the data blocks causing one or more of the data blocks to become out of order relative to an order in which the data blocks were received. The system hashes the data blocks to determine a manner in which to transmit the data blocks, reorders the data blocks to restore the order in which the data blocks were received, and transmits the reordered data blocks on outgoing data streams.

Claims

1. A method for any-to-any transmission of data blocks in a data processing system, comprising:

receiving, at the data processing system, a plurality of data blocks associated with an incoming data stream;

assigning the data blocks to a plurality of input links using a load balancing technique to balance a quantity of the data blocks assigned to each of the plurality of input links;

sending the data blocks to a plurality of processing paths via the plurality of input links;

independently processing the data blocks by the plurality of processing paths;

outputting the processed data blocks from the plurality of processing paths in an order different from an order in which the data blocks were received;

restoring the order of the processed data blocks to the order in which the data blocks were received at the data processing system; and

transmitting the ordered data blocks on an outgoing data stream.

2. The method of claim 1, where the plurality of processing paths comprise at least one of a plurality of routers, a plurality of processors, or one or more switch fabrics.

3. The method of claim 1, further comprising:

assigning a stream number to the data blocks, where the stream number identifies the incoming data stream.

4. The method of claim 3, further comprising:

assigning a sequence number to each of the data blocks, where the sequence number for one of the data blocks identifies a relative order in which the one of the data blocks was received with regard to other ones of the data blocks within the incoming data stream.

5. The method of claim 4, where restoring the order of the processed data blocks includes:

using the stream number and the sequence numbers to reorder the processed data blocks.

6. The method of claim 1, further comprising:

assigning a sequence number to each of the data blocks, where the sequence number for one of the data blocks identifies a relative order in which the one of the data blocks was received with regard to other ones of the data blocks within the incoming data stream.

7. The method of claim 6, where restoring the order of the processed data blocks includes:

using the sequence numbers to reorder the processed data blocks.

8. The method of claim 1, where the plurality of processing paths are connected to the plurality of input links and a plurality of output links;

and

where the data blocks are transmitted in a many-to-many fashion between multiple ones of the plurality of input links and multiple ones of the plurality of output links.

9. A data processing system, comprising:

a plurality of input circuits, one input circuit, of the plurality of input circuits, connecting to an input stream and a plurality of input links, where the one input circuit is to;

receive a plurality of data blocks on the input stream in a first order,

assign the data blocks to the plurality of input links based on a load balancing scheme to balance a quantity of the data blocks assigned to each of the plurality of input links, and

send the data blocks to the plurality of input links to which the data blocks were assigned;

a plurality of processing paths, connected to the plurality of input links, to;

independently process the data blocks,

output the data blocks in a second order that differs from the first order; and

a plurality of output circuits connected to the plurality of processing paths, where one output circuit, of the plurality of output circuits, is to;

receive the data blocks in the second order,

reorder the data blocks from the second order to the first order, and

transmit the reordered data blocks from the one output circuit.

10. The system of claim 9, where the plurality of processing paths comprise at least one of a plurality of routers, a plurality of processors, or one or more switch fabrics.

11. The system of claim 9, where the one input circuit is further to assign a stream number to the data blocks, where the stream number identifies the input stream.

12. The system of claim 11, where the one input circuit is further to assign sequence numbers to the data blocks, where the sequence number for one of the data blocks identifies a relative order in which the one of the data blocks was received with regard to other ones of the data blocks within the input stream.

13. The system of claim 12, where the one output circuit is to use the stream number and the sequence numbers to reorder the data blocks.

14. The system of claim 9, where the one input circuit is further to assign sequence numbers to the data blocks, where the sequence number for one of the data blocks identifies a relative order in which the one of the data blocks was received with regard to other ones of the data blocks within the input stream.

15. The system of claim 14, where the one output circuit is to use the sequence numbers to reorder the data blocks.

16. The system of claim 9, where the plurality of processing paths receive the data blocks on the plurality of input links and output the data blocks on a plurality of output links;

and

where the data blocks are transmitted in a many-to-many fashion between multiple ones of the plurality of input links and multiple ones of the plurality of output links.

17. A network device, comprising:

at least one input circuit to;

receive a plurality of data blocks in a first order,

assign sequence numbers to the data blocks, the sequence numbers identifying a relative order of the data blocks within the first order, and

output the data blocks to one or more input links, where when outputting the data blocks to the one or more input links, the at least one input circuit is to distribute the data blocks across the one or more input links using a load balancing technique;

a plurality of processing paths, connected to the one or more input links and one or more output links, to;

receive the data blocks via the one or more input links, process the data blocks, and output the data blocks to the one or more output links; and

at least one output circuit to;

receive, via the one or more output links, the data blocks from the processing paths in a second order that differs from the first order,

restore the data blocks to the first order using the sequence numbers, and

transmit the data blocks in the first order.

18. The network device of claim 17, where the one or more input links include a plurality of input links at least some of which are bundled together to form a high speed input link.

19. The network device of claim 17, where the one or more output links include a plurality of output links at least some of which are bundled together to form a high speed output link.