Scheduling system utilizing pointer perturbation mechanism to improve efficiency

• US 7,623,524 B2
• Filed: 12/22/2003
• Issued: 11/24/2009
• Est. Priority Date: 12/22/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Muthukrishnan, Raman, Varma, Anujan
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): LOO, JUVENA W
• Application Number:
  US10/744,430
• Publication Number:
  US 20050135398A1
• Time in Patent Office: 2,164 Days
• Field of Search: 370411-418, 370/474, 370/395.4, 370/395.41, 370/395.42, 370/428, 370/429
• US Class Current: 370/395.41
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• 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 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 49/1576 Crossbar or matrix

Abstract

In general, in one aspect, the disclosure describes a switching device that includes a plurality of ingress ports to receive data from external sources and a plurality of egress ports to transmit data to external destinations. The switching device also includes a plurality of queues to store data waiting to be transmitted from a particular ingress port to a particular egress port. A request generator generates requests for permission to transmit data for the queues. A request indicates a cumulative amount of data contained in a respective queue. A switching matrix provides selective connectivity between the ingress ports and the egress ports. The switching device further includes a scheduler to receive the requests, generate grants based thereon, and configure the switching matrix. The scheduler incorporates a mechanism to periodically monitor its operating efficiency and perturb its internal state when its efficiency is below a certain desired level.

Claims

1. A scheduling device comprising a plurality of ingress ports to receive data from external sources;

a plurality of egress ports to transmit data to external destinations;

a plurality of queues to store data waiting to be transmitted, wherein the queues are associated with a particular ingress port and a particular egress port;

a request generator to generate requests for permission to transmit data from the queues;

a switching matrix to provide selective connectivity between the plurality of ingress ports and the plurality of egress ports; and

a scheduler to receive the requests, generate grants based thereon, and configure the switching matrix, wherein said scheduler monitors its efficiency by tracking requests granted and grants accepted for a defined period and if the efficiency is determined to be below a defined threshold said scheduler performs perturbation of its scheduling state, wherein said scheduler considers a scheduling phase inefficient if some predetermined amount of requests sent from sources or some predetermined amount of requests received by destinations are not granted, and wherein said scheduler is considered inefficient if more than a certain percentage of scheduling phases is considered inefficient.

2. The device of claim 1, wherein said scheduler determines if it is operating efficiently at fixed intervals.

3. The device of claim 2, wherein the fixed internals are a number of scheduling phases.

4. The device of claim 1, wherein the defined period is a number of scheduling phases.

5. The device of claim 1, wherein the tracking requests granted includes tracking number of sources sending requests being issued grants.

6. The device of claim 1, wherein the tracking requests granted includes tracking number of destinations receiving requests being issued grants.

7. The device of claim 1, wherein said scheduler performs perturbation by blocking requests from a particular source.

8. The device of claim 7, wherein the particular source is selected according to an arbitration scheme.

9. The device of claim 8, wherein the arbitration scheme is a round-robin.

10. The device of claim 8, wherein the selection of the particular source includes determining if requests for the particular source have been the same priority.

11. The device of claim 8, wherein the selection of the particular source includes determining throughput of the particular source.

12. The device of claim 1, wherein the plurality of queues store at least some subset of packets, segments, and frames.

13. The device of claim 1, wherein the requests indicate cumulative amount of data.

14. The device of claim 13, wherein the requests indicate the cumulative amount of data in terms of at least some combination of bytes, packets, segments, and frames.

15. The device of claim 1, further comprising

a segmentation unit to receive variable size packets and to store the variable size packets as segments in the queues, wherein the variable size packets having a length greater than a maximum segment length are divided into multiple segments;

and

a reassembly unit to combine the segments making up a complete packet together to generate the packet.

16. The device of claim 15, further comprising

a framer to aggregate a plurality of segments to form a frame, wherein the segments are retrieved from the at least one queue, and wherein the frame may contain segments associated with different packets;

and

a deframer to extract the segments from the frame.

17. The device of claim 13, wherein the requests also indicate other factors, wherein the other factors include at least some subset of priority and aging.

18. The device of claim 17, wherein the scheduler assigns the requests internal priority numbers based on at least some subset of the cumulative amount of data and the other factors, and generates the grants based at least in part on the internal priority numbers associated with the requests.

19. A method comprising:

receiving data from external sources;

storing the data waiting to be transmitted in queues, wherein the queues are associated with an external source from which the data came and an external destination to which the data is going;

generating requests for permission to transmit data from the queues;

receiving the requests at a scheduler;

generating grants in the scheduler based on the received requests;

monitoring the scheduler efficiency by tracking requests granted and grants accepted for a defined period, wherein a scheduling phase is considered inefficient if some predetermined amount of requests sent from sources or some predetermined amount of requests received by destinations are not granted, and wherein the scheduler is considered inefficient if more than a certain percentage of scheduling phases is considered inefficient;

performing perturbation when the scheduler is considered inefficient; and

selectively connecting the external sources and the external destinations based on the generated grants.

20. The method of claim 19, wherein said performing includes blocking requests associated with a specific source.

21. The method of claim 19, wherein said storing includes storing at least some subset of packet, segments and blocks in the queues.

22. The method of claim 19, wherein the requests indicate the cumulative amount of data in terms of bytes, packets, segments or frames.

23. The method of claim 22, wherein the requests also indicate other factors including at least some subset of priority and aging.

24. The method of claim 19, further comprising

dividing variable sized packets having a length greater than a maximum segment length into multiple segments, wherein said storing includes storing segments;

and

reassembling the segments making up a complete packet together to generate the packet.

25. The method of claim 24, further comprising

aggregating a plurality of segments to form a frame, wherein the segments are retrieved from the at least one queue, and wherein the frame may contain segments associated with different packets;

and

extracting the segments from the frame.

26. A store and forward device comprising

a plurality of Ethernet cards to receive data from and transmit data to external sources, wherein the plurality of Ethernet cards include

an ingress interface module to receive data from external sources, store the data in queues associated with at least some subset of destination and priority, generate requests for transmitting data, and transmit data from queues upon receipt of an associated grant;

and

an egress interface module to receive data from the ingress interface module, and transmit the data to a destination;

a switching matrix to provide selective connectivity between the Ethernet cards;

a backplane consisting of a plurality of channels to connect the plurality of Ethernet cards to the switching matrix; and

a scheduler to receive the requests, process the requests and generate grants therefrom, and configure the switching matrix accordingly, wherein said scheduler monitors its efficiency by tracking requests granted and grants accepted for a defined period, wherein said scheduler considers a scheduling phase inefficient if some predetermined amount of requests sent from sources or some predetermined amount of requests received by destinations are not granted, and wherein said scheduler is considered inefficient if more than a certain percentage of scheduling phases is considered inefficient and the scheduler performs perturbation by blocking requests from a selected ingress interface module.

27. The device of claim 26, wherein

the data is variable sized packets;

the ingress interface module includes a segmentation unit to receive the variable sized packets and to store the variable sized packets as segments, wherein the variable sized packets having a length greater than a maximum segment length are divided into multiple segments; and

the egress interface module includes a reassembly unit to combine the segments making up a complete packet together to generate the packet.

28. The device of claim 27, wherein

the ingress interface module further includes a framer to aggregate a plurality of segments to form a frame, wherein the segments are retrieved from the at least one queue, and wherein the frame may contain segments associated with different packets;

and

the egress interface module further includes a deframer to extract the segments from the frame.

29. The device of claim 26, wherein

the requests indicate at least some subset of quantity, priority and aging;

and

the scheduler assigns the requests internal priority numbers based on at least some subset of the quantity, priority and aging, and generates the grants based at least in part on the internal priority numbers associated with the requests.

30. The device of claim 26, wherein the selected interface module is selected based on interface module throughput.

31. The device of claim 26, wherein the selected ingress interface module is selected based on ingress interface module throughput.