Multi-service queuing method and apparatus that provides exhaustive arbitration, load balancing, and support for rapid port failover

• US 20030058880A1
• Filed: 09/21/2001
• Published: 03/27/2003
• Est. Priority Date: 09/21/2001
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Terago Communications, Inc. (SLT Logic, Inc.)
• Inventors: Sarkinen, Scott A., Davidson, Scott A.
• Granted Patent: US 7,151,744 B2
• Time in Patent Office: Days
• US Class Current: 370/413
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

The present invention provides a multi-service queuing method and apparatus that provides exhaustive arbitration, load balancing, and support for rapid port failover. Routers and switches according to the present invention can instantaneously direct the flow of traffic to another port should there be a failure on a link, efficiently handle multicast traffic and provide multiple service classes. The fabric interface interfaces the switch fabric with the ingress and egress functions provided at a network node and provides virtual input and output queuing with backpressure feedback, redundancy for high availability applications, and packet segmentation and reassembly into variable length cells. The user configures fixed and variable-length cells. Virtual input and output queues are coupled to a switch fabric. Statistics regarding the virtual input and output queues are collected and packet queuing for the virtual input and output queues is controlled using the collected statistic to provide congestion control for the virtual input and output queues and the switch fabric.

Claims

1. A switching method, comprising:

providing virtual input and output queues coupled to a switch fabric comprising switch elements;

collecting statistics regarding the virtual input and output queues; and

controlling packet queuing for the virtual input and output queues using the collected statistic to provide congestion control for the virtual input and output queues and the switch fabric.

2. The method of claim 1 wherein the controlling packet queuing for the virtual input and output queues further comprises providing load balancing by monitoring a state for the virtual output queue and directing traffic to an appropriate port on a switch element of the switch fabric.

3. The method of claim 1 wherein the controlling packet queuing for the virtual input and output queues further comprises applying a multilevel backpressure indication that is fed back to the virtual output queue to prevent violation of a threshold condition caused by storage of a new packet by the virtual input queues.

4. The method of claim 3 wherein the multilevel backpressure indication may be selected to reduce an instantaneous rate for a virtual output queue associated with the packet causing congestion or to reduce an average transmission rate of a virtual output queue associated with the packet causing congestion.

5. The method of claim 3 wherein the applying multilevel backpressure further comprises dynamically allocating buffers in the virtual output queues to ensure fairness under congestion control.

6. The method of claim 5 wherein the buffers are dynamically allocated using per queue thresholds.

7. The method of claim 1 wherein the controlling packet queuing for the virtual input and output queues further comprises providing efficient multicast data transfer.

8. The method of claim 7 wherein efficient multicast data transfer is provided by combining multiple enqueueing via the virtual output queues and fabric replication.

9. The method of claim 7 wherein efficient multicast data transfer is provided by combining a memory approach for logical multicast and a switch approach for spatial multicast.

10. The method of claim 1 wherein the virtual input and output queues and switch fabric support multi-service classes.

11. The method of claim 10 wherein the multi-service classes comprise variable length packets.

12. The method of claim 10 wherein the multi-service classes comprise variable quality of service requirements.

13. The method of claim 10 wherein the multi-service classes comprise a plurality of rate classes.

14. The method of claim 1 wherein the controlling packet queuing for the virtual input and output queues provides rapid failover through reassignment of packets to the virtual input and output queues.

15. The method of claim 14 wherein the controlling packet queuing for the virtual input and output queues further comprises instructing a virtual output queue to drop a packet routed to a virtual input queue experiencing congestion based upon the collected statistics.

16. The method of claim 15 wherein the dropping of the packet at the virtual output queue reduces a number of resources used in the switch fabric.

17. The method of claim 14 wherein the controlling packet queuing further comprises instructing a virtual output queue to reroute a packet routed to a virtual input queue experiencing congestion based upon the collected statistics.

18. The method of claim 1 wherein the controlling packet queuing for the virtual input and output queues further comprises mapping packets to the virtual input and output queues.

19. The method of claim 18 wherein the mapping includes mapping different queues for different service classes.

20. The method of claim 18 wherein the mapping allows rapid failover for a queue that fails to meet a selected failover criteria.

21. The method of claim 1 wherein the collecting statistics further comprises maintaining a state for all virtual input and output queues.

22. The method of claim 21 wherein the maintaining a state for all virtual input and output queues further comprises maintaining a state of buffers having worst load violations.

23. A switch, comprising:

virtual input and output queues for storing packets;

a switch fabric, coupled to the virtual input and output queues, the switch fabric including switch elements for receiving packets from a virtual output queue and routing the packet to a virtual input queue;

a statistics interface for collecting statistics regarding the virtual input and output queues; and

a fabric interface controlling packet queuing for the virtual input and output queues, the fabric interface providing congestion control for the virtual input and output queues and the switch fabric.

24. The switch of claim 23 further comprising a load balancer for monitoring a state for the virtual output queues and directing traffic to an appropriate port on a switch element of the switch fabric to balance loading across the switch fabric.

25. The switch of claim 23 wherein the fabric interface controls the packet queuing for the virtual input and output queues by applying a multilevel backpressure indication that is fed back to the virtual output queue to balance loads based upon the collected statistics.

26. The switch of claim 25 wherein the multilevel backpressure indication may be selected to reduce an instantaneous rate for a virtual output queue associated with the packet causing congestion or to reduce an average transmission rate of a virtual output queue associated with the packet causing congestion.

27. The switch of claim 25 wherein the fabric interface applies multilevel backpressure by dynamically allocating buffers in the virtual output queues to ensure fairness under congestion control.

28. The switch of claim 27 wherein the buffers are dynamically allocated using per queue thresholds.

29. The switch of claim 23 wherein the fabric interface provides efficient multicast data transfer.

30. The switch of claim 29 wherein the fabric interface provides efficient multicast data transfer by using multiple enqueueing via the virtual output queues and fabric replication.

31. The switch of claim 29 wherein efficient multicast data transfer is provided by combining a memory approach for logical multicast and a switch approach for spatial multicast.

32. The switch of claim 23 wherein the virtual input and output queues and switch fabric support multi-service classes.

33. The switch of claim 32 wherein the multi-service classes comprise variable length packets.

34. The switch of claim 32 wherein the multi-service classes comprise variable quality of service requirements.

35. The switch of claim 32 wherein the multi-service classes comprise a plurality of rate classes.

36. The switch of claim 23 further comprising a programmable mapping table, the mapping table programmed to map each of the virtual input and output queues according to traffic characteristics governing packet flows. the mapping table providing rapid failover through reassignment of packets to the virtual input and output queues.

37. The switch of claim 36 wherein the mapping table maps different queues for different service classes.

38. The switch of claim 36 wherein the mapping table enables rapid failover for a queue that fails to meet a selected failover criteria.

39. The switch of claim 36 wherein the fabric interface comprises a backpressure flow controller, the backpressure flow controller providing a multilevel backpressure indicator for instructing a virtual output queue to drop a packet routed to a virtual input queue experiencing congestion based upon the collected statistics.

40. The switch of claim 39 wherein the dropping of the packet at the virtual output queue reduces a number of resources used in the switch fabric.

41. The switch of claim 36 wherein the fabric interface comprises a backpressure flow controller, the backpressure flow controller providing a multilevel backpressure indicator for instructing a virtual output queue to reroute a packet routed to a virtual input queue experiencing congestion based upon the collected statistics.

42. The switch of claim 23 wherein the statistics interface maintains a state for all virtual input and output queues.

43. The switch of claim 23 wherein the statistics interface maintaining a state of buffers having worst load violations.