Methods, apparatuses and systems facilitating data transmission across bonded communications paths

• US 7,006,500 B1
• Filed: 12/30/2002
• Issued: 02/28/2006
• Est. Priority Date: 04/26/2002
• Status: Expired due to Fees

• Current Assignee: Klamath Networks Corporation
• Original Assignee: Valo, Inc.
• Inventors: Thom, Danny, Shilshtut, Radimir, Soltani, Sina, Pedersen, Soren Bo, Lohani, Manish
• Primary Examiner(s): QURESHI, AFSAR M
• Application Number:
  US10/334,051
• Time in Patent Office: 1,156 Days
• Field of Search: 370/229, 370/230.1, 370/255, 370/347, 370/352, 370/355, 370/389, 370/390, 370/394, 370/395.21, 370/401, 370/474, 370/392, 370/395.51, 370/395.54, 370/399, 370/409
• US Class Current: 370/394
• 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: H04M 11/062 using different frequency bands for speech and other data
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Methods, apparatuses and systems facilitating the aggregation or bonding of communications paths into a higher-bandwidth, logical communications path. Embodiments of the present invention can be applied to bond different physical links (e.g., xDSL over twisted pairs), different channels on the same physical line, or even different channels or frequencies in a wireless communications network. The present invention further provides methods, apparatuses and systems facilitating the re-sequencing of data flows transmitted across bonded communications paths. In one embodiment, the re-sequencing methodology of the present invention adapts to the transmission delays (both absolute and relative) across the bonded communications path.

Claims

1. A method facilitating the re-sequencing of user cells transmitted across one or more bonded communications paths, comprising:

receiving user cells, wherein each user cell has a sequence number associated therewith;

generating time stamp values for the user cells, wherein the time stamp value is based on the time the user cell is received;

writing the user cells and corresponding time stamps to locations in a sequence queue based on the respective sequence numbers associated with the user cells;

maintaining the lowest time stamp value and the location in the sequence queue corresponding to the user cell having the lowest sequence number;

performing a conditional read operation on the sequence queue to read the user cell associated with the lowest sequence number, wherein the read operation is conditioned on the current time being greater than or equal to the time the first user cell was received plus a delta time.

2. The method of claim 1 wherein the conditional read operation comprises:

reading the user cell from the sequence queue;

updating the lowest time stamp value and the location in the sequence queue corresponding to the user cell having the lowest sequence number.

3. The method of claim 1 wherein the time stamp value associated with each user cell is a time value corresponding to receipt of the user cell plus the delta time.

4. The method of claim 1 wherein the delta time is based on the path delay differences associated with the bonded communications paths.

5. The method of claim 4 wherein the delta time is dynamically updated based on real-time monitoring of the path delay differences.

6. The method of claim 1 wherein the delta time is statically configured.

7. The method of claim 1 wherein the current time is maintained by an electronic counter.

8. The method of claim 1 wherein the electronic counter is embedded in an integrated circuit.

9. The method of claim 1 wherein the current time is a virtual time maintained by an electronic counter.

10. The method of claim 9 wherein the time stamp is a virtual time value.

11. The method of claim 9 wherein the virtual time value is a binary value maintained by a counter.

12. The method of claim 1 wherein the current time is a real-time value.

13. The method of claim 12 wherein the time stamp is a real-time value.

14. The method of claim 1 wherein the user cell is written to the sequence queue location associated with the last N-bits of the sequence number associated with the user cell.

15. A method for operating on a sequence queue and sequencing data structure to facilitate the re-sequencing of user cells transmitted across bonded communications paths, wherein user cells includes a sequence number associated therewith, and wherein the sequencing data structure includes fields to maintain the lowest time stamp value, a read address, a write address, and a read bit operative to condition reading of user cells from the sequence queue, comprising

receiving a cell from a bonded communications path;

if the cell is a user cell, then;

generating a time stamp for the user cell, wherein the time stamp is the arrival time of the user cell plus a delta time;

writing the user cell and the time stamp to a location in the sequence queue based on the sequence number associated with the user cell;

setting the write address of the sequencing data structure to the location in the sequence queue corresponding to the user cell;

maintaining the lowest time stamp value and the location of the user cell associated with the lowest sequence number in the read address of the sequencing data structure;

if the read bit is invalid, and the current time is greater than or equal to the lowest time stamp maintained in the sequencing data structure, then;

setting the read bit to valid;

reading the user cell stored in the location maintained by the read address field of the sequencing data structure from the sequence queue;

updating the lowest time stamp value and the read address of the sequencing data structure;

otherwise, if the read bit is valid, then;

if the read address does not equal the write address, then;

if the current time is greater than or equal to the time stamp associated with the user cell corresponding to the read address, then;

reading the user cell stored in the location maintained by the read address field of the sequencing data structure from the sequence queue;

updating the lowest time stamp value and the read address of the sequencing data structure;

else, if the read address equals the write address, then setting the read bit to invalid.

16. The method of claim 15 wherein the conditional read operation comprises:

reading the user cell from the sequence queue;

updating the lowest time stamp value and the location in the sequence queue corresponding to the user cell having the lowest sequence number.

17. The method of claim 15 wherein the time stamp value associated with each user cell is a time value corresponding to receipt of the user cell plus the delta time.

18. The method of claim 15 wherein the delta time is based on the path delay differences associated with the bonded communications paths.

19. The method of claim 18 wherein the delta time is dynamically updated based on real-time monitoring of the path delay differences.

20. The method of claim 15 wherein the delta time is statically configured.

21. The method of claim 15 wherein the current time is maintained by an electronic counter.

22. The method of claim 15 wherein the electronic counter is embedded in an integrated circuit.

23. The method of claim 15 wherein the current time is a virtual time maintained by an electronic counter.

24. The method of claim 23 wherein the time stamp is a virtual time value.

25. The method of claim 23 wherein the virtual time value is a binary value maintained by a counter.

26. The method of claim 15 wherein the current time is a real-time value.

27. The method of claim 26 wherein the time stamp is a real-time value.

28. The method of claim 15 wherein the user cell is written to the sequence queue location associated with the last N-bits of the sequence number associated with the user cell.

29. The method of claim 15 wherein the bonded communications paths are physical links.

30. A method facilitating the re-sequencing of user cells transmitted across one or more bonded communications paths, comprising:

receiving cells across the one or more bonded communications paths, wherein each user cell has a sequence number associated therewith;

decrementing a burst count value for each cell received after a first read operation has been performed;

generating time stamp values for the user cells, wherein the time stamp value is based in part on the time the user cell is received;

writing the user cells and corresponding time stamps to locations in a sequence queue based on the respective sequence numbers associated with the user cells;

maintaining the lowest time stamp value and the location in the sequence queue corresponding to the user cell having the lowest sequence number;

upon receipt of each cell from the one or more bonded communications paths, performing at least a first read operation on the sequence queue to read the user cell associated with the lowest sequence number, wherein the first read operation is conditioned on the current time being greater than or equal to the time the first user cell was received plus a delta time;

wherein the subsequent read operations are performed until an invalid sequence queue location is encountered;

wherein the read operations comprise;

reading the user cell from the sequence queue; and

updating the lowest time stamp value and the location in the sequence queue corresponding to the user cell having the lowest sequence number;

incrementing the burst count value;

waiting until the burst count value is zero before performing subsequent read operations; and

re-initializing the read operation if the last written user cell is read from the sequence queue.

31. A method for operating on a sequence queue and sequencing data structure to facilitate the re-sequencing of user cells transmitted across bonded communications paths, wherein user cells have a sequence number associated therewith, and wherein the sequencing data structure includes fields to maintain the lowest time stamp value, a burst count, a read address, a write address, and a read bit operative to condition reading of user cells from the sequence queue, comprising

receiving a cell from a bonded communications path;

if the cell is a user cell, then;

generating a time stamp for the user cell, wherein the time stamp is the arrival time of the user cell plus a delta time;

writing the user cell and the time stamp to a location in the sequence queue based on the sequence number associated with the user cell;

setting the write address of the sequencing data structure to the location in the sequence queue corresponding to the user cell;

decrementing the burst count stored in the sequencing data structure if the read bit is valid;

maintaining the lowest time stamp value and the location of the user cell associated with the lowest sequence number in the read address of the sequencing data structure;

if the read bit is invalid, and the current time is greater than or equal to the lowest time stamp maintained in the sequencing data structure, then;

setting the read bit to valid;

reading the user cell stored in the location maintained by the read address field of the sequencing data structure from the sequence queue;

updating the lowest time stamp value and the read address of the sequencing data structure;

incrementing the burst count value stored in the sequencing data structure;

otherwise, if the read bit is valid, then;

if the read address does not equal the write address, then;

if the wait bit is set and the burst count value equals zero, then;

resetting the wait bit;

updating the lowest time stamp value and the read address of the sequencing data structure; and

incrementing the burst count value stored in the sequencing data structure;

if the wait bit is not set and the read address corresponds to a valid user cell, then;

reading the user cell stored in the location maintained by the read address field of the sequencing data structure from the sequence queue;

updating the lowest time stamp value and the read address of the sequencing data structure; and

incrementing the burst count value stored in the sequencing data structure;

else, if the read address equals the write address, reinitializing the read bit in the sequencing data structure.

32. A system allowing for aggregation of a plurality of communications paths into a logical communications path, comprising

a first bonding engine operably coupled via a plurality of native communications paths to a second bonding engine;

wherein the first bonding engine is operative to;

receive native data streams comprising a plurality of packets, each packet including a header and a payload;

convert the native data streams by aggregating at least two payloads associated with the packets into corresponding bonded frames; and

transmit the bonded frames across at least one of the plurality of native communications paths to the second bonding engine;

wherein the size of each bonded frame is determined by the speed of the native communications path over which it is transmitted and a maximum delay time;

wherein the second bonding engine is operative to recover the native data stream from the bonded frames.

33. The system of claim 32 wherein the first bonding engine is operative to convert native data streams into user cells of uniform size;

associate contiguous sequence numbers to the user cells, and then aggregate the user cells into bonded frames;

wherein the bonded frames comprise at least one user cell payload and the sequence number associated with the first of the at least one user cell payload.

34. The system of claim 33 wherein the number of user cell payloads in each bonded frame depends on the speed of the native communications path over which it is transmitted.

35. The system of claim 33 wherein the second bonding engine is operative to:

receive the bonded frames;

recover the user cells based on the sequence number and use cell payloads of each bonded frame; and

sequence the user cells based on the sequence numbers associated with each user cell.

36. A method enhancing the efficiency of data transfer over a communications path, comprising

detecting the transmission speed of a communications path to a remote network device;

receiving a native data stream comprising a plurality of native cells, wherein the native cells each comprise a cell header and a payload;

aggregating payloads of the native cells associated with the native data stream into a bonded frame, wherein the number of payloads in the bonded frame depends on the transmission speed of the communications path;

transmitting the bonded frame over the communications path to the remote network device.

37. The method of claim 36 wherein the number of payloads aggregated into the bonded frame is based on the transmission speed of the communications path and at least one predetermined performance criterion associated with the communications path.

38. The method of claim 37 wherein the performance criterion is a maximum delay requirement associated with head of the line blocking conditions across the communications path.

39. The method of claim 36 further comprising

dynamically updating the number of payloads aggregated into the bonded frame based on detected changes in the transmission speed of the communications path.

40. The method of claim 36 wherein the communications path is a physical link.

41. The method of claim 40 wherein the physical link is a xDSL link.

42. The method of claim 36 wherein the communications path is a channel in a wireless communications network.

43. The method of claim 36 wherein the communications path is a frequency channel allocated within a physical link.

44. The method of claim 36 further comprising

associating a contiguous sequence number to each native cell in the native data stream.

45. The method of claim 44 wherein the bonded frame header includes data allowing for recovery of the contiguous sequence number associated with each native cell.

46. The method of claim 45 wherein the bonded frame header includes the sequence number associated with the first user cell payload in the bonded frame.

47. The method of claim 46 wherein the payloads corresponding to the user cells in the bonded frame are ordered according to the sequence numbers associated with each corresponding user cell.