Regulating data-burst transfer

• US 7,817,543 B2
• Filed: 03/19/2008
• Issued: 10/19/2010
• Est. Priority Date: 05/14/2003
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Beshai, Maged E., Jamoussi, Bilel N.
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Rutkowski, Jeffrey M
• Application Number:
  US12/051,317
• Publication Number:
  US 20080165688A1
• Time in Patent Office: 944 Days
• Field of Search: 370/230, 370/233, 370/235.1, 370/235, 370/414, 370/469, 370/395.62, 370/395.64, 370/416, 370/389, 370/509, 710/31, 710/7, 710/35
• US Class Current: 370/230
• 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 transfer of data bursts from a burst buffer, each data burst belonging to one of a number S, S>

1, of data streams, where said data streams share a channel of transmission rate R, said device comprising;

a flow-rate-allocation memory containing a flow-rate allocation ρ

_j, 0≦

j<

S, for each of said S burst streams;

a burst-record memory containing S records having one-to-one correspondence to said S streams;

a burst-size calculator for determining a nominal burst size B_j for burst stream j, 0≦

j<

S, as B_j≦

{min{ρ

_j×

Δ

₁, R×

Δ

₂}, where Δ

₁ is a specified burst-formation delay upper bound, Δ

₂ is a specified transmission-duration upper bound;

and

a controller for;

forming data bursts for each active data stream so that a data burst belonging to stream j, 0≦

j<

S, has a size not exceeding B_j;

placing said data burst in a burst buffer;

populating said burst-record memory to indicate a size of a waiting data burst in said burst buffer belonging to a specific data stream and a current credit of said specific data stream;

visiting each record j, 0≦

j<

S, in said burst-record memory with a mean periodicity of at most (ρ

_j/B_j) visits per time unit;

and

transmitting said each record j to a scheduler for determining exact time instants at which a burst of respective data stream is to be transmitted.

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

3. The device of claim 1 further comprising:

two calendar-memory devices each organized into a number K of calendar slots initialized with null entries, K>

S;

a first 1;

2 selector providing said controller alternate WRITE-access during each calendar cycle to one of said two calendar-memory devices; and

a second 1;

2 selector providing said controller alternate READ-access during said each calendar cycle from one of said two calendar-memory devices.

4. The device of claim 3 wherein said controller:

allocates for each burst stream j, 0≦

j<

S, a mean number v_j=(ρ

_j×

K/R) of calendar slots represented as an integer part n_j=└

(ρ

_j×

K/R)┘ and

a fraction ε

_j=v_j−

n_j, where └

r┘

denotes an integer part of a real number r;

initializes a remainder δ

_j for burst stream j to zero; and

during each calendar cycle;

adds said fraction ε

_j to said remainder δ

_j;

determines a number m_j of calendar slots for burst stream j as m_j=n_j+└

δ

_j┘

;

updates δ

_j to equal (δ

_j−

└

δ

_j┘

); and

writes in each of m_j calendar slots of one of said two calendar-memory devices an identifier of data stream j.

5. The device of claim 3 wherein said controller:

sequentially reads from each calendar slot of one of said two calendar-memory devices an identifier of a data stream j, 0≦

j<

S and increases a credit C_j corresponding to said data-stream j by 1.0; and

subject to an indication that C_j≧

(Φ

×

B_j), where Φ

, 0≦

Φ

≦

1.0, is a predefined fraction;

reduces said credit C_j by a value of B_j; and

directs a burst of said data stream to said scheduler.

6. The device of claim 3 wherein said controller accesses each calendar memory device for a time duration h and selects said nominal burst size B_j to be an integer multiple of h×

R not exceeding {min{ρ

_j×

Δ

₁, R×

Δ

₂}.

7. The device of claim 3 further comprising a calendar-addressing unit coupled to said controller, said calendar-addressing unit comprising

a first up-counter for addressing one of said two calendar-memory device being read during a current calendar cycle;

a second up-counter for addressing the other calendar-memory device being updated during said current calendar cycle;

a down-counter coupled to said second up-counter for defining a partition of said K calendar slots for each of said S data streams; and

a 2×

2 connector cyclically connecting said two calendar-memory devices to said first up-counter and said second up-counter, said connector being triggered to change connectivity every calendar cycle;

wherein each of said first up-counter, second up-counter, and down counter has a counter cycle of K with an output taking consecutive values between 0 and (K−

1).

8. The device of claim 7 wherein output bits of said first up-counter directly address one of said two calendar-memory devices to read data stream identifiers while reversed output bits of said second up-counter address the other calendar-memory device to write updated data stream identifiers.

9. The device of claim 7 wherein reversed output bits of said first up-counter address one of said two calendar-memory devices to read data stream identifiers while output bits of said second up-counter directly address the other calendar-memory device to write updated data stream identifiers.

10. The device of claim 1 further comprising a time-counter exchanging time-counter readings with an identical time counter coupled to a source of said data streams for time-locking said source to said device.

11. The device of claim 1 wherein said controller selects said number K to equal 2^χ

, χ

>

1.

12. A device for structuring a number S, S>

1, of data streams into data bursts and regulating transfer of said data bursts, where said data streams share a channel of transmission rate R, said device comprising;

a flow-rate-allocation memory containing a flow-rate allocation ρ

_j, 0≦

j<

S, for each of said S burst streams;

a burst-size calculator for determining a nominal burst size B_j for burst stream j, 0≦

j<

S, as B_j={min {ρ

_j×

Δ

₁, R×

Δ

₂}, where Δ

₁ is a specified burst-formation delay upper bound, Δ

₂ is a specified transmission-duration upper bound;

and

a controller for;

generating, for each burst stream j, 0≦

j<

S, a sequence of burst descriptors each specifying said nominal burst size B_j, said burst descriptors timed so that a mean value d_j of a time interval between successive burst descriptors at least equals Bj/ρ

_j; and

submitting said burst descriptors to a scheduler for determining exact time instants at which bursts of respective data streams are to be transferred.

13. A network having a plurality of edge nodes interconnected by a plurality of core nodes, wherein at least one core node includes a device as claimed in claim 12.

14. The device of claim 12 further comprising:

two calendar-memory devices each organized into a number K of calendar slots initialized with null entries, K>

S;

a first 1;

2 selector providing said controller alternate WRITE-access to one of said two calendar-memory devices; and

a second 1;

2 selector providing said controller alternate READ-access from one of said two calendar-memory devices.

15. The device of claim 14 wherein, during a calendar cycle, said controller:

writes in each calendar slot of one of said two calendar-memory devices identifiers of said S data streams so that a mean number of calendar slots between successive entries of a burst stream j, 0≦

j<

S, allocated a flow-rate ρ

_j is R/ρ

_j;

sequentially reads from each calendar slot of the other calendar-memory device an identifier of a data stream j, 0≦

j<

S and increases a credit, C_j, corresponding to said data-stream j identifier by 1.0; and

subject to an indication that C_j≧

(Φ

×

B_j), where Φ

, 0≦

Φ

≦

1.0, is a predefined fraction;

reduces said credit C_j by a value of B_j; and

inserts a burst descriptor of said data stream j in said sequence of burst descriptors.

16. The device of claim 14 wherein said controller accesses each calendar memory device for a time duration h and selects said nominal burst size B_j to be an integer multiple of h×

R.

17. The device of claim 12 further comprising a time-counter exchanging timing signals with a source of said data streams for time-locking said source to said device.

18. The device of claim 12 wherein said controller selects said number K to equal 2^χ

, χ

>

1.