Flow-rate-regulated burst switches

• US 7,535,841 B1
• Filed: 05/14/2003
• Issued: 05/19/2009
• 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): Orgad, Edan
• Assistant Examiner(s): Ahmed, Salman
• Application Number:
  US10/437,628
• Time in Patent Office: 2,197 Days
• Field of Search: 370/395.71, 370/417, 370/415, 370/436, 370/437, 370/470, 370/472, 370/428
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/357 Fibre channel switches
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 11/0071 Provisions for the electrical-optical layer interface
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects

Abstract

Burst-switching nodes using a common-memory or a time shared space switch and employing flow-rate control are disclosed. Within a switching node, data bursts are segmented into data segments of a fixed size with some segments containing information bits as well as null bits. A switching node handles data streams allocated different flow rates and, for any data stream, the internal flow rate through the switching node can be higher than the external flow rate due to null padding of segmented data. The switching node is provided with a sufficient internal capacity expansion in order to offset the effect of null padding. A controller of the switching node is provided with a flow-rate-regulation apparatus to enable scheduling the transfer of data segments across the switching node in a manner that guarantees adherence to the allocated information flow rates.

Claims

1. A common-memory switch comprising:

a number M>

1 of input ports;

a number N≧

1 of output ports;

a memory device storing data segments each having a segment size of W bits;

a controller including an output flow-rate regulation device; and

an input flow-rate-regulation device that regulates the rate of transfer of said information bits from each of said input ports to said memory device;

wherein

each of said data segments is associated with one of a plurality of predefined data streams and at least one of said data segments contains a number of information bits less than said segment size W;

wherein

said controller assigns a nominal flow-rate to each of said plurality of predefined data streams; and

said output flow-rate regulation device uses said number of information bits and said nominal flow-rate to select at least one of said data segments for dequeueing;

wherein an output port collates said information bits from selected ones of said data segments to form data bursts;

wherein said at least one of said data segments containing a number of information bits less than said segment size W is padded with null bits;

wherein each of said input ports receives data packets, associates each received data packet with one of said plurality of predefined data streams and delays said received data packets associated with each of said predefined data streams for a time interval not exceeding an upper bound D to accumulate sufficient data to form one of said data segments;

wherein the width W of said memory device is determined as;

2. The common-memory switch of claim 1 wherein only said information bits in each data segment are transmitted by said output port.

3. The common-memory switch of claim 1 wherein each of said input ports transfers data to the memory device at a rate R and the width W of said memory device is determined as:

W≧

(M×

R×

δ

)/(1−

(N−

1)×

N×

δ

/D),

where δ

is the time required to access the memory device to write and read a data segment and D is a permissible segment queueing delay at any of the M input ports.

4. The common-memory switch of claim 1 wherein at least two of said M input ports have different bit-rate capacities.

5. The common-memory switch of claim 1 wherein N>

1 and at least two of said N output ports have different bit-rate capacities.

6. The common-memory switch of claim 4 wherein each of said input ports writes at most a first constrained number of said data segments in said memory device during a predefined time frame, said first constrained number being specific to each of said input ports.

7. The common-memory switch of claim 5 wherein each output port reads at most a second constrained number of selected ones of said data segments from said memory device during a predefined time frame, said second constrained number being specific to each of said output ports.

8. The common-memory switch of claim 2 wherein the sum, over said M input ports, of a first constrained number of said data segments, does not exceed a predefined upper bound and the sum, over said N output ports, of a second constrained number of selected ones of said data segments does not exceed said predefined upper bound.

9. The common-memory switch of claim 8 wherein said output flow-rate regulation device controls the transfer of said data segments from said memory device according to information content of each segment.

10. The common-memory switch of claim 1 wherein at least one of said output ports time-locks to an external switching node.

11. An edge node comprising:

a plurality of input-ports, each input port comprising an input buffer and a flow-rate regulator;

a plurality of output ports each output port comprising a burst-formation device for transmitting continuous concatenated data bursts;

a space switch connecting said plurality of input ports to said plurality of output ports; and

a scheduler to schedule transfer of variable length packets from said plurality of input ports to said plurality of output ports;

wherein each input port receives data from traffic sources at a rate R₁ and transmits data to said plurality of output ports through said space switch at a rate not exceeding Q₁ such that the ratio R₁/Q₁ does not exceed (1−

(N₂−

1)×

δ

*/D₁), where N₂ is the number of output ports, δ

* is a nominal packet duration, and D₁ is a permissible waiting time in said input buffer,

wherein each of said variable length packets belongs to one of a plurality of data streams, and

wherein said variable length packets associated with a selected one of said data streams are aggregated at each output port into data bursts.

12. The edge node of claim 11 further comprising an output buffer at each of said plurality of output ports said output buffer receiving data from said plurality of input ports through said space switch at a rate not exceeding Q₂ and transmitting data to traffic sources at a rate not exceeding R₂ such that the ratio R₂/Q₂ does not exceed (1−

(N₁−

1)×

δ

*/D₂), where N₁ is the number of said input ports, δ

* is a nominal packet duration, and D₂ is a permissible waiting time in said output buffer.

13. The edge node of claim 12 wherein the width W₁ of said input buffer is determined as:

W₁>

(R₁×

δ

)/(1−

(N₂−

1)×

δ

/D₁),

where δ

is the time required to access the input buffer to write and read a data segment.

14. The edge node of claim 12 wherein the width W₂ of said output buffer is determined as:

W₂≧

(R₂×

δ

)/(1−

(N₁−

1)×

δ

/D₂),

where δ

is the time required to access the output buffer to write and read a data segment.

15. The edge node of claim 11 wherein said burst-formation device includes a burst-size calculator for computing a nominal burst size B for each of said plurality of data streams.

16. The edge node of claim 15 wherein said burst-formation device aggregates a number of said variable length packets associated with a selected one of said plurality of data streams, into an assembled one of said data bursts, wherein said assembled data burst has a size not exceeding said nominal burst size.

17. The edge node of claim 16 wherein said nominal burst size is determined as:

B=min{ρ

×

Δ

₁,R×

Δ

₂},

where

Δ

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

Δ

₂ is a specified upper bound of burst transmission duration,

ρ

is an allocated flow rate for said selected one of said plurality of data streams, and

R is the transmission rate of the one of said output ports from which said selected one of said plurality of data streams is transmitted.

18. The edge node of claim 11 wherein at least one of said output ports time-locks to an external switching node.