Distributed control of data flow in a network switch

• US 7,006,438 B2
• Filed: 05/31/2001
• Issued: 02/28/2006
• Est. Priority Date: 05/31/2001
• Status: Expired due to Term

• Current Assignee: Force10 Networks, Inc. (Dell Technologies Inc.)
• Original Assignee: Turin Networks, Inc. (Dell Technologies Inc.)
• Inventors: West, Steve, Smith, Russ, Brandis, Dirk, Marrone, Frank
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/872,125
• Publication Number:
  US 20020186703A1
• Time in Patent Office: 1,734 Days
• Field of Search: 370/395.1, 370412-413, 370/415, 370/417, 370428-429, 370/406, 370/395.42, 370/395.43, 370/418, 370/468, 370/395.41, 370/230, 370/231, 370/235
• US Class Current: 370/231
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/112 Switch control, e.g. arbitration
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/405 Physical details, e.g. power supply, mechanical construction or backplane of ATM switches
• CPC Class Codes: H04L 49/606 Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9068 in the network interface card

Abstract

The network switch described herein provides a cell/packet switching architecture that switches between line interface cards across a meshed backplane. In one embodiment, the switching can be accomplished at, or near, line speed in a protocol independent manner. The protocol independent switching provides support for various applications including Asynchronous Transfer Mode (ATM) switching, Internet Protocol (IP) switching, Multiprotocol Label Switching (MPLS) switching, Ethernet switching and frame relay switching. The architecture allows the network switch to provision service on a per port basis. In one embodiment, the network switch provides a non-blocking topology with both input and output queuing and per flow queuing at both ingress and egress. Per flow flow-control can be provided between ingress and egress scheduling. Strict priority, round robin, weighted round robin and earliest deadline first scheduling can be provided.

Claims

1. A network switch comprising:

an asynchronous mesh;

N ingress interfaces coupled to the asynchronous mesh, the N ingress interfaces having an ingress scheduler to receive data from external sources and to selectively schedule and asynchronously transmit the data across the asynchronous mesh according to a first schedule; and

N egress interfaces coupled to the asynchronous mesh, the N egress interfaces having an egress scheduler to receive data from the asynchronous mesh and to schedule and transmit the data to external destinations according to a second schedule different than the first schedule,

wherein the ingress scheduler performs scheduling and transmitting data across the asynchronous mesh independent of the egress scheduler performing scheduling and transmitting data to the external destinations,

wherein each of the N ingress interfaces includes N ingress buffers to temporarily store the data received from the external sources before being transmitted across the asynchronous mesh, each of the N ingress buffers corresponding to each of the N egress interfaces respectively,

wherein each of the N egress interfaces includes N egress buffers separated from the N ingress buffers to temporarily store the data received from each of the N ingress interfaces across the asynchronous mesh before being transmitted to the external destinations, each of the N egress buffers corresponding to each of the N ingress interfaces respectively,

wherein the ingress scheduler retrieves the data from each of the ingress buffers and transmits the retrieved data to a corresponding egress buffer of each of the egress interfaces according to the first schedule, and

wherein the egress scheduler retrieves the data from each of the egress buffers and transmits the retrieved data to the external destinations according to the second schedule independent of the first schedule.

2. The network switch of claim 1, wherein each of the ingress buffers of each ingress interface includes a plurality of ingress queues corresponding to a plurality of classes of data, and wherein each ingress interface segregates data received from the external sources into one or more of the ingress queues of a respective ingress buffer of a respective ingress interface based on a class identifier associated with the data.

3. The network switch of claim 2 wherein the egress interfaces generate a flow control signal to prevent transmission to one or more of the N egress buffers of the respective egress interfaces when an amount of data stored in the one or more of the N egress buffers exceeds a predetermined threshold.

4. The network switch of claim 3, wherein the flow control signal is associated with one of the plurality of service classes of data, wherein the flow control signal prevents data of an ingress queue associated with a class of the flow control signal to be transmitted while allowing other ingress queues having a priority lower than a priority of the data of the ingress queue associated with the class of the flow control signal to be transmitted.

5. The network switch of claim 4, wherein the plurality of classes of data comprises a real-time (RT) class, a multi-cast (MC) class, and a non-real-time (NRT) class, wherein the RT class has highest priority, wherein the MC class has a medium priority, and wherein the NRT class has lowest priority.

6. The network switch of claim 2 wherein the N ingress interfaces transfer data to a shared egress buffer and further wherein the egress interfaces schedule and retrieve the data stored in the shared egress buffer prior to transmitting the data to the external destinations.

7. The network switch of claim 2 wherein the N ingress interfaces concurrently transmit fixed-length cells and variable-length packets across the asynchronous mesh to the N egress interfaces.

8. The network switch of claim 1 wherein one or more of the N ingress interfaces segregates incoming data into queues based on a quality of service (QoS) identifier.

9. The network switch of claim 1 wherein one or more of the N ingress interfaces segregates incoming data into queues based on a priority identifier.

10. The network switch of claim 1 wherein one or more of the N ingress interfaces segregates incoming data into queues based on a deadline identifier.

11. The network switch of claim 1, wherein each egress buffer of each egress interface comprises one or more egress queues, each of the one or more egress queues corresponding to a distinctive service class, and wherein the data received from the N ingress interfaces is stored in the one or more egress queues based on the service class identifier associated with the data.

12. The network switch of claim 11, wherein each of the egress queues is associated with a respective priority.

13. The network switch of claim 12, wherein the egress scheduler schedules and transmits data from each of the egress queues to the external sources according to a schedule associated with each of the egress queues determined based on the respective priority.

14. The network switch of claim 13, wherein if an amount of data stored in one of the egress queues of an egress interface exceeds a predetermined threshold, the egress scheduler transmits a backpressure signal to a corresponding ingress interface, and wherein in response to the backpressure signal, the corresponding ingress interface prevents data having a service class associated with the queue of the egress interface from being transmitted to the egress interface, while allowing data of other service classes to be transmitted to the egress interface.

15. The network switch of claim 14, wherein in response to the backpressure signal associated with the queue of the egress interface, the corresponding ingress interface prevents data having a service class associated with the queue of the egress interface from being transmitted to the egress interface, while allowing data of service classes having priorities lower than a priority of the queue of the egress interface associated with the backpressure signal to be transmitted to the egress interface.

16. A network switch comprising:

N ingress cards coupled to receive data from external sources, each of the N ingress cards having a plurality of ports to transmit data, wherein each of the N ingress cards comprises an ingress scheduler coupled to the ports of the ingress card, the ingress scheduler to cause data to be selectively and asynchronously transmitted via the ports of the ingress card according to a first schedule, and wherein one or more of the ingress cards segregates incoming data into queues based on a service class identifier; and

M egress cards coupled to the N ingress cards over an asynchronous mesh, each of the M egress cards having ports coupled to receive data from one or more of the plurality of ports of the N ingress cards, the egress cards coupled to transmit data to external destinations, wherein each of the M egress cards comprises an egress scheduler coupled to the ports of the egress card, the egress scheduler to cause data to be selectively transmitted to the external destinations according to a second schedule different then the first schedule,

wherein the ingress scheduler and the egress scheduler schedule and transmit data independent of each other,

wherein each of the N ingress cards includes M ports and each of the M egress cards includes N ports, wherein each of the M ports of each of the N ingress cards is communicatively coupled to one of the N ports of each of the M egress cards respectively, and wherein each of the N ports of each of the M egress cards is communicatively coupled to one of the M ports of each of the N ingress cards respectively.

17. The network switch of claim 16 wherein N and M are equal.

18. The network switch of claim 16 wherein one or more of the ingress cards segregates incoming data into queues based on a quality of service (QoS) identifier.

19. The network switch of claim 16 wherein one or more of the ingress cards segregates incoming data into queues based on a priority identifier.

20. The network switch of claim 16 wherein one or more of the N ingress cards segregates incoming data into queues based on a deadline identifier.

21. The network switch of claim 16 further comprising:

N ingress interfaces, each of the N ingress interfaces including N independent cache buffers to temporarily store incoming data at the ingress interfaces; and

N egress interfaces, each of the egress interfaces including N independent cache buffers to temporarily store data received from the N ingress interfaces,

wherein each of the N independent cache buffers of each ingress interface is coupled to one of N respective egress interfaces and wherein each of the N independent cache buffers of each egress interface is coupled to one of N respective ingress interfaces.

22. The network switch of claim 21 in which the egress interfaces generate a flow control signal to prevent access to one or more of the N independent cache buffers of the respective egress interfaces.

23. The network switch of claim 21 wherein the egress interfaces generate a flow control signal to prevent transmission to one or more of the N independent cache buffers of the respective egress interfaces.

24. The network switch of claim 21 wherein the N ingress interfaces transfer data to a shared egress buffer and further wherein the egress interfaces schedule and retrieve the data stored in the shared egress buffer prior to transmitting the data to the external destinations.

25. The network switch of claim 21 in which the N ingress interfaces concurrently transmit fixed-length cells and variable-length packets to the egress interfaces.