Flexible scheduler in an asynchronous transfer mode (ATM) switch

• US 6,396,834 B1
• Filed: 11/24/1997
• Issued: 05/28/2002
• Est. Priority Date: 11/24/1997
• Status: Expired due to Fees

• Current Assignee: Riverstone Networks, Inc.
• Original Assignee: Riverstone Networks, Inc.
• Inventors: Bonomi, Flavio Giovanni, Devarajan, Kannan
• Primary Examiner(s): RAO, SEEMA SRINIVAS
• Application Number:
  US08/976,686
• Time in Patent Office: 1,646 Days
• Field of Search: 370/389,394,395,465,470,471,473-476,400,428,429
• US Class Current: 370/394
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

Abstract

A flexible scheduler in an ATM switch. The scheduler enables each connection to be served fairly according to associated quality of service parameters, while enabling several other features. A connection can be shaped while minimizing additional memory and processing requirements. Specifically, the conformance time of cells of a connections need not be stored when significant backlog exists in the transmission of the cells. The shaping rate can be dynamically varied. Sequence of cells forming a frame are buffered in the ATM switch until the end of frame cell is received. All the cells of a frame are then sent in quick succession.

Claims

1. A method of processing a sequence of cells forming a frame in a switch, said method comprising the step of:

(a) receiving said sequence of cells including a head cell, a plurality of intermediate cells and a last cell, wherein step (a) comprises the step of receiving said sequence of cells on a connection;

(b) storing said sequence of cells in said switch, wherein step (b) comprises the step of storing said sequence of cells in a connection queue;

(c) placing said head cell in one of a sequence of buckets of a group, wherein a plurality of groups are provided to serve an output port of said switch; and

(d) forwarding said sequence of cells on a port of said switch only after said last cell is received in said switch, wherein said sequence of cells are sent for transmission in successive turns allocated to said group immediately after the turn of said head cell in said one of said sequence of buckets is reached,

wherein said sequence of buckets serve a plurality of connections including said connection,

storing in said connection queue a next unicast frame including a head cell, a last cell, and a plurality of intermediate cells on said connection; and

placing said head cell of said next unicast frame in a bucket which is away from said one of said sequence of buckets storing said head cell of said frame by a number of buckets inversely proportional to the desired bandwidth for said connection such that said plurality of connections are scheduled fairly.

2. The method of claim 1, wherein said plurality of buckets form a group serving only connections transmitting frames, and each of said plurality of connections transmits only cells forming frames.

3. The method of claim 1, further comprising the step of placing the head cell of said next frame in said bucket only after said head cell of said transmitted frame is scheduled for transmission.

4. The method of claim 1, wherein (c) comprises forwarding said sequence of cells on said port in the same sequence as the sequence in which said sequence of cells are received in step (a).

5. The method of claim 4, wherein each of said sequence of cells are received according to asynchronous transfer mode (ATM) protocol.

6. The method of claim 1, wherein each of said sequence of cells comprises a unicast cell such that said connection comprises a unicast connection, and wherein said sequence of cells are forwarded on the same unicast virtual connection as said unicast virtual connection on which said sequence of unicast cells are received such that said unicast virtual connection is not merged with other unicast virtual connections when said sequence of unicast cells are transmitted from said switch.

7. A switch for processing a sequence of cells forming a frame in a switch, said switch comprising:

means for receiving said sequence of cells including a head cell, a plurality of intermediate cells and a last cell, wherein said means for receiving comprises means for receiving said sequence of cells on a connection;

means for storing said sequence of cells in said switch, wherein said means for storing comprises means for buffering said sequence of cells in a connection queue;

means for placing said head cell in one of a sequence of buckets of a group, wherein a plurality of groups are provided to serve an output port of said switch; and

means for forwarding said sequence of cells on a port of said switch only after said last cell is received in said switch, where said sequence of cells are sent for transmission in successive turns allocated to said group immediately after the turn of said head cell in said one of said plurality of buckets is reached,

wherein said sequence of buckets serve a plurality of connections including said connection, wherein said switch further comprises;

means for storing in said connection queue a next unicast frame including a head cell, a last cell, and a plurality of intermediate cells on said connection; and

means for placing said head cell of said next unicast frame in a bucket which is away from said one of said sequence of buckets storing said head cell of said frame by a number of buckets inversely proportional to the desired bandwidth for said connection such that said plurality of connections are scheduled fairly.

8. The switch of claim 7, wherein said number of buckets is also directly proportional to the number of cells in said frame.

9. The switch of claim 7, wherein said plurality of buckets form a group serving only connections transmitting frames, and each of said plurality of connections transmits only cells forming frames.

10. The switch of claim 7, further comprising means for placing the head cell of said next frame in said bucket only after said head cell of said transmitted frame is scheduled for transmission.

11. The switch of claim 7, wherein said means for forwarding forwards said sequence of cells on said port in the same sequence as the sequence in which said sequence of cells are received by said means for receiving.

12. The switch of claim 11, wherein each of said sequence of cells are received according to asynchronous transfer mode (ATM) protocol.

13. The switch of claim 7, wherein each of said sequence of cells comprises a unicast cell such that said connection comprises a unicast connection, and wherein said means for forwarding forwards said sequence of cells on the same unicast virtual connection as said unicast virtual connection on which said sequence of unicast cells are received such that said unicast virtual connection is not merged with other unicast virtual connections when said sequence of unicast cells are transmitted from said switch.

14. A switch for processing a sequence of cells forming a frame in a switch, said switch comprising:

an ingress processor for receiving said sequence of cells including a head cell, a plurality of intermediate cells and a last cell, wherein said ingress processor receives said sequence of cells on a connection;

a queue manager for storing said sequence of cells in said switch, wherein said queue manager stores said sequence of cells in a connection queue;

an output port for transmitting said sequence of cells; and

a scheduler for forwarding said sequence of cells on said output port only after said last cell is received in said switch, wherein said scheduler places said head cell in one of a sequence of buckets of a group, wherein a plurality of groups are provided to serve said output port, and wherein said scheduler forwards said sequence of cells for transmission in successive turns allocated to said group immediately after the turn of said head cell in said one of said plurality of buckets is reached,

said queue manager storing in said connection queue a next unicast frame including a head cell, a last cell, and a plurality of intermediate cells on said connection; and

placing said head cell of said next unicast frame in a bucket which is away from said one of said sequence of buckets storing said head cell of said frame by a number of buckets inversely proportional to the desired bandwidth for said connection such that said plurality of connections are scheduled fairly.

15. The switch of claim 14, wherein said scheduler forwards said sequence of cells on said port in the same sequence as the sequence in which said sequence of cells are received by said ingres processor.

16. The switch of claim 15, wherein each of said sequence of cells are received according to asynchronous transfer mode (ATM) protocol.

17. The switch of claim 14, wherein each of said sequence of cells comprises a unicast cell such that said connection comprises a unicast connection, and wherein said scheduler forwards said sequence of cells on the same unicast virtual connection as said unicast virtual connection on which said sequence of unicast cells are received such that said unicast virtual connection is not merged with other unicast virtual connections when said sequence of unicast cells are transmitted from said switch.

18. A method of processing a sequence of unicast cells forming a unicast frame in a switch, said method comprises:

receiving said sequence of unicast cells on a unicast virtual connection, said sequence of unicast cells including a head cell, a plurality of intermediate cells and a last cell, said unicast virtual connection comprising a connection;

storing said sequence of unicast cells in a connection queue in said switch;

placing said head cell in one of a sequence of buckets of a group, wherein a plurality of groups are provided to serve an output port of said switch, wherein said sequence of buckets serve a plurality of connections including said connection;

forwarding said sequence of unicast cells on a port of said switch only after said last cell is received in said switch, said sequence of unicast cells being forwarded on the same unicast virtual connection as said unicast virtual connection on which said sequence of unicast cells are received such that said unicast virtual connection is not merged with other unicast virtual connections when said sequence of unicast cells are transmitted from said switch, wherein said sequence of unicast cells are sent for transmission in successive turns allocated to said group immediately after the turn of said head cell in said one of said sequence of buckets is reached;

storing in said connection queue a next unicast frame including a head cell, a last cell, and a plurality of intermediate cells on said connection; and

placing said head cell of said next unicast frame in a bucket which is away from said one of said sequence of buckets storing said head cell of said frame by a number of buckets inversely proportional to the desired bandwidth for said connection such that said plurality of connections are scheduled fairly.

19. The method of claim 18, wherein said plurality of buckets form a group serving only connections transmitting frames, and each of said plurality of connections transmits only cells forming frames.

20. The method of claim 19, further comprising placing the head cell of said next unicast frame in said bucket only after said head cell of said transmitted frame is scheduled for transmission.

21. A switch for processing a sequence of unicast cells forming a unicast frame, wherein said switch comprises:

means for receiving said sequence of unicast cells on a unicast virtual connection, said sequence of unicast cells including a head cell, a plurality of intermediate cells and a last cell, said unicast virtual connection comprising a connection;

means for storing said sequence of unicast cells in a connection queue in said switch;

means for placing said head cell in one of a sequence of buckets of a group, wherein a plurality of groups are provided to serve an output port of said switch, wherein said sequence of buckets serve a plurality of connections including said connection;

means for forwarding said sequence of unicast cells on a port of said switch only after said last cell is received in said switch, said sequence of unicast cells being forwarded on the same unicast virtual connection as said unicast virtual connection on which said sequence of unicast cells are received such that said unicast virtual connection is not merged with other unicast virtual connections when said sequence of unicast cells are transmitted from said switch, wherein said sequence of unicast cells are sent for transmission in successive turns allocated to said group immediately after the turn of said head cell in said one of said sequence of buckets is reached;

means for storing in said connection queue a next unicast frame including a head cell, a last cell, and a plurality of intermediate cells on said connection; and

means for placing said head cell of said next unicast frame in a bucket which is away from said one of said sequence of buckets storing said head cell of said frame by a number of buckets inversely proportional to the desired bandwidth for said connection such that said plurality of connections are scheduled fairly.

22. The switch of claim 21, wherein said number of buckets is also directly proportional to the number of cells in said frame.

23. The switch of claim 21, wherein said plurality of buckets form a group serving only connections transmitting frames, and each of said plurality of connections transmits only cells forming frames.

24. The switch of claim 23, further comprising means for placing the head cell of said next unicast frame in said bucket only after said head cell of said transmitted frame is scheduled for transmission.

25. A switch for processing a sequence of unicast cells forming a frame in a switch, said switch comprising:

an ingress processor receiving said sequence of unicast cells including a head cell, a plurality of intermediate cells and a last cell;

a queue manager storing said sequence ;

of unicast cells in said switch;

an output port transmitting said sequence of unicast cells; and

a scheduler forwarding said sequence of unicast cells on a port of said switch only after said last cell is received in said switch, said sequence of unicast cells being forwarded on the same unicast virtual connection as said unicast virtual connection on which said sequence of unicast cells are received such that said unicast virtual connection is not merged with other unicast virtual connections when said sequence of unicast cells are transmitted from said switch,

wherein said ingress processor receives said sequence of unicast cells on a connection, wherein said queue manager stores said sequence of unicast cells in a connection queue, and wherein said scheduler places said head cell in one of a sequence of buckets of a group, wherein a plurality of groups are provided to serve said output port, and wherein said scheduler forwards said sequence of unicast cells for transmission in successive turns allocated to said group immediately after the turn of said head cell in said one of said plurality of buckets is reached; and

wherein said queue manager stores in said connection queue a next unicast frame including a head cell, a last cell, and a plurality of intermediate cells on said connection, and places said head cell of said next unicast frame in a bucket which is away from said one of said sequence of buckets storing said head cell of said frame by a number of buckets inversely proportional to the desired bandwidth for said connection such that said plurality of connections are scheduled fairly.