Regulating Data-Burst Transfer

• US 20080165688A1
• Filed: 03/19/2008
• Published: 07/10/2008
• Est. Priority Date: 05/14/2003
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bilel N. Jamoussi, Maged E. Beshai
• Inventors: Beshai, Maged E., Jamoussi, Bilel N.
• Granted Patent: US 7,817,543 B2
• Time in Patent Office: Days
• US Class Current: 370/232
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects

Abstract

The invention discloses methods and apparatus for regulating the transfer of data bursts across a data network comprising electronic edge nodes interconnected by fast-switching optical core nodes. To facilitate switching at an electronic edge node, data bursts are organized into data segments of equal size. A data segment may include null data in addition to information bits. The null data are removed at the output of an edge node and the information data is collated into bursts, each carrying only information bits in addition to a header necessary for downstream processing. To ensure loss-free transfer of bursts from the edge to the core, burst transfer permits are generated at controllers of the optical core and sent to respective edge nodes based on flow-rate-allocation requests. Null-padding is not visible outside the edge nodes and only the information content is subject to transfer rate regulation to ensure high efficiency and high service quality.

Claims

1. A device for regulating the transfer of data bursts from a burst buffer, each data burst belonging to one of a plurality of burst streams, said device comprising:

A burst flow-rate controller;

a flow-rate-allocation memory containing a flow-rate allocation for each of said plurality of burst streams;

a burst-record memory containing a record of a selected burst from each active burst stream;

a first calendar memory organized into a predefined number of calendar slots;

a second calendar memory organized into a predefined number of calendar slots; and

a burst-transfer memory;

wherein said burst flow-rate controller is operable to determine burst dequeueing instants from said burst buffer such that for each of said plurality of burst streams the flow-rate allocation multiplied by the time interval between successive burst dequeueing instants equals the size of a specified one of said bursts selected during said time interval.

2. The device of claim 1 wherein said burst flow-rate controller further includes:

means for creating a vector of pointers, each entry of which corresponds to a one of said plurality of burst streams, and indicating an address in said burst buffer of a next-burst to be transferred to said burst-transfer memory, and indicating the length of said next-burst;

means for creating a calendar having a predefined number of calendar slots each of which containing an identifier associated with a respective one of said plurality of burst streams, wherein each of said plurality of burst streams is given an allocated number of calendar slots;

means for creating a vector of credits, each entry of which corresponds to respective ones of said plurality of said burst streams; and

means for continually reading burst-stream identifiers from selected ones of said calendar slots, and for each burst stream identifier read from a selected calendar slot;

increasing a previous entry of a credit vector credit, said entry corresponding to said burst stream identifier by a predetermined amount to determine a new credit;

determining said length of said next-burst using said vector of pointers; and

if said new credit exceeds said next-burst length, transferring said next-burst from said burst buffer to said result buffer and reducing said new credit by said next-burst length.

3. The device of claim 1 further including a cyclic counter having a repetitive counter period comprising a number of equal time slots, wherein a selected one of said calendar slots is read during each of said time slots.

4. The device of claim 1 wherein said allocated number of calendar slots allocated to a burst stream occupies consecutive calendar slots and said selected ones of said calendar slots are determined according to a one-to-one mapping function that associates a time slot with a calendar slot.

5. The device of claim 4 wherein said one-to-one mapping function is a reverse-binary function, where a reverse binary function converts a first number to a second number such that the binary representation of said second number is derived from the binary representation of said first number by reversing the bit order, with the least significant bit of the first number becoming the most-significant bit of the second number.

6. The device of claim 5 wherein each of said packets is divided into a number of data segments of equal size and at least one of said data segments is padded with null data.

7. The device of claim 6 wherein said allocated number of calendar slots allocated to a burst stream occupies calendar slots determined by a one-to-one mapping function of consecutive time slots of said counter period and said selected ones of said calendar slots are read from consecutive calendar slots.

8. The device of claim 7 wherein said one-to-one mapping function is a reverse-binary function.

9. A network having a plurality of edge nodes interconnected by a network core, wherein at least one input port of a one of said edge nodes includes a device for rate regulation as claimed in claim 1.

10. A network having a plurality of edge nodes interconnected by a network core, wherein at least one output port of an edge node includes a device as claimed in claim 1.

11. A device for structuring each of a plurality of burst streams into data bursts and regulating the transfer of said data bursts, wherein each of said plurality of burst streams comprises bursts of time-varying burst sizes, said device comprising:

A burst transfer-permit controller;

a flow-rate-allocation memory containing a flow-rate allocation for each of said plurality of burst streams;

a burst-record memory containing a record of a burst-descriptor from each active burst stream;

a first calendar memory organized into a predefined number of calendar slots;

a second calendar memory organized into a predefined number of calendar slots;

a burst-size calculator; and

a burst-descriptor memory;

wherein

said burst-size calculator is operable to compute a nominal burst size for each of said plurality of burst streams; and

said burst transfer-permit controller is operable to determine burst-descriptor generation instants such that for each of said plurality of burst streams the flow-rate allocation multiplied by the time interval between successive burst-descriptor generation instants equals the nominal burst size corresponding to said each of said plurality of burst streams.

12. The device of claim 11 wherein said burst regulator further includes:

means for creating a vector of nominal burst sizes each entry of which corresponds to a specified one of said plurality of burst streams and indicating a nominal size of a data burst;

means for creating a calendar having a predefined number of calendar slots each of which containing a respective burst stream identifier wherein each of said plurality of burst streams is allocated a number of calendar slots;

means for creating a vector of credits each entry of which corresponding to a specified one of said plurality of burst streams; and

means for continually scanning selected ones of said calendar slots to read data-stream identifier and for each burst stream identifier;

increasing a previous credit in a specified one of said credit vector entries corresponding to said data-stream identifier by a predetermined amount to determine a new credit;

determining a nominal burst size using said vector of nominal burst sizes; and

if said new credit exceeds said nominal burst size, enqueueing a burst descriptor comprising said burst stream identifier and said nominal burst size in said burst-descriptor memory and reducing said new credit by said nominal size of said data burst.

13. The device of claim 12 further including a cyclic counter having a counter period comprising a number of equal time slots and wherein a specified one of said calendar slots is read during each of said time slots.

14. The device of claim 12 where said allocated number of calendar slots allocated to a burst stream occupies consecutive calendar slots and said selected ones of said calendar slots are determined according to a one-to-one mapping function that associates a time slot with a calendar slot.

15. The device of claim 11 wherein said one-to-one mapping function is a reverse-binary function, where said reverse binary function converts a first number to a second number such that the binary representation of said second number is derived from the binary representation of the first number by reversing the bit order such that the least-significant bit of the first number becomes the most-significant bit of the second number.

16. The device of claim 11 wherein said allocated number of calendar slots allocated to a burst stream occupies calendar slots determined by a one-to-one mapping function of consecutive time slots of said counter period and said selected ones of said calendar slots are read from consecutive calendar slots.

17. The device of claim 16 wherein said one-to-one mapping function is a reverse-binary function.

18. The device of claim 14 wherein said burst transfer-permit controller is adapted to send said burst descriptors to a burst-scheduling device.

19. A network having a plurality of edge nodes interconnected by a network core, wherein at least one input port of a one of said edge nodes includes a device for rate regulation as claimed in claim 12.

20. A network having a plurality of edge nodes interconnected by a network core, wherein at least one output port of a one of said edge nodes includes a device for rate regulation as claimed in claim 12.