Switching device utilizing internal priority assignments

• US 7,324,541 B2
• Filed: 12/22/2003
• Issued: 01/29/2008
• Est. Priority Date: 12/22/2003
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Muthukrishnan, Raman, Varma, Anujan
• Primary Examiner(s): Yao; Kwang Bin
• Assistant Examiner(s): Elpenord; Candal
• Application Number:
  US10/744,198
• Publication Number:
  US 20050135355A1
• Time in Patent Office: 1,499 Days
• Field of Search: 370/389, 370/231, 370/474, 370/465, 370/444, 370/476, 370/412, 370/391, 370/428, 370/429, 370/447, 370/461, 370/462
• US Class Current: 370/429
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

In general, in one aspect, a switching device is described that includes a segmentation unit to receive packets and divide packets having a length greater than a maximum segment length into multiple segments. A plurality of queues associated with a source and a destination stores the segments. A request generator generates requests that include external factors including amount of data contained in the queue and at least some subset of priority and age. A scheduler receives the requests and assigns the requests an internal priority based on the external factors. The scheduler processes the requests for the queues by internal priority in order to generate grants. A framer, responsive to the scheduler, aggregates a plurality of segments for the queues that received a grant to form a frame and to transmit the frame to an associated destination. The frame may contain segments associated with different packets.

Claims

1. A switching device comprising

a segmentation unit to receive packets and to divide the packets having a length greater than a maximum segment length into multiple segments;

a plurality of queues to store the segments, wherein the queues are associated with sources and destinations;

a request generator to generate requests to transmit the segments, wherein a request indicates external factors including amount of data contained in the queue and at least some subset of priority and age;

a scheduler to receive the requests and assign the requests an internal priority based on the external factors, wherein the scheduler processes the requests for the queues by internal priority in order to generate grants; and

a framer, responsive to said scheduler, to aggregate a plurality of the segments for the queues that received a grant to form a frame and to transmit the frame to an associated destination, wherein the frame may contain segments associated with different packets.

2. The device of claim 1, wherein said scheduler performs multiple arbitration iterations in order to generate the grants.

3. The device of claim 2, wherein said scheduler performs multiple iterations per internal priority.

4. The device of claim 3, wherein if the requests for one priority are granted prior to completion of the multiple iterations associated with that internal priority remaining iterations are used by next internal priority.

5. The device of claim 3, wherein if the requests for one priority are not granted by the completion of the multiple iterations associated with that internal priority, any remaining requests are processed as if they were next internal priority level requests.

6. The device of claim 5, wherein the requests indicate cumulative amount of data within the queues.

7. The device of claim 1, wherein the cumulative amount of data is quantized based on number of frames.

8. The device of claim 1, wherein the age is waiting time of the segment at head of the queue.

9. The device of claim 1, wherein said scheduler includes:

a plurality of request pre-processors to assign the internal priority; and

an arbitrator to arbitrate between the requests received and generate the grants.

10. The device of claim 1, further comprising a switching matrix to provide selective connectivity between the sources and the destinations.

11. The device of claim 10, wherein the scheduler configures the switching matrix based on the grants.

12. The device of claim 1, wherein said scheduler includes:

a plurality of grant arbiters to arbitrate between requests received and select a request to issue a grant for, wherein the plurality of grant arbiters is equal in number to the number of destinations, and wherein the grant arbiters are associated with specific destinations; and

a plurality of accept arbiters to arbitrate between grants received and select a grant to accept, wherein the plurality of grant arbiters is equal in number to number of sources, and wherein the grant arbiters are associated with specific sources.

13. The device of claim 12, wherein the grant arbiters receive a request from each source and the accept arbiters are capable of receiving a grant from each grant arbiter.

14. The device of claim 13, wherein the grant arbiter and the accept arbiter associated with an accepted grant are not included in a next iteration of the scheduler.

15. The device of claim 1, further comprising

a deframer to extract the segments from the frame;

and

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

16. The device of claim 1, further comprising a striper to stripe the frame across a plurality of channels.

17. A method comprising:

receiving data packets;

forming segments from the received data packets, wherein the data packets received having a length greater than a maximum segment length are divided into multiple segments;

storing the segments in queues, wherein the queues are associated with a source and a destination;

generating requests to transmit the segments from the queues, wherein a request indicates external factors including amount of data contained in a queue and at least some subset of priority and age;

receiving the requests at a scheduler and assigning the requests an internal priority based on the external factors;

processing the requests for the queues by the internal priority in order to generate the requests;

aggregating a plurality of the segments, responsive to said processing the requests, to form a frame, wherein the frame may contain the segments associated with different data packets; and

transmitting the frame to the associated destination, wherein the segments within the frame are transmitted together.

18. The method of claim 17, wherein said processing includes performing multiple arbitration iterations per internal priority in order to generate the grants.

19. The method of claim 18, wherein said processing includes utilizing remaining iterations as part of next internal priority iterations when requests for a previous internal priority are granted prior to completion of the multiple iterations associated with the previous internal priority.

20. The device of claim 18, wherein said processing includes processing any remaining requests as a part of next internal priority level requests if requests for a previous internal priority are not granted by completion of the multiple iterations associated with the previous internal priority.

21. The method of claim 18, wherein said processing includes excluding sources and destinations associated with an accepted grant from a next iteration.

22. The method of claim 17, wherein the requests indicate cumulative amount of data within the queues.

23. The method of claim 22, wherein the cumulative amount of data is quantized based on number of frames.

24. The method of claim 17, wherein the age is waiting time of the segment at head of the queue.

25. The method of claim 17, further comprising

extracting the segments from the frame;

and

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

26. The method of claim 17, wherein said transmitting includes striping the frame across a plurality of channels.

27. 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 packets, store the packets as segments in queues associated with at least some subset of destination and priority, aggregate multiple segments together to form a frame, transmit the segments within the frame together, and generate requests for permission to transmit data from the queues, wherein the segments larger than a maximum segment size are divided into the multiple segments, wherein the frames may include segments associated with different packets, and wherein the requests include external factors including at least some subset of quantity, priority and age;

and

an egress interface module to receive the frames, divide the frames into the segments making up the frames, store the segments in a queue, monitor the queues for complete packets, and reassemble a packet after the segments making up the packet are received;

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, assign the requests an internal priority based on the external factors, and to configure the switching matrix accordingly, wherein the scheduler processes the requests for the queues by internal priority in order to generate grants.

28. The device of claim 27, wherein said scheduler includes:

a plurality of grant arbiters to arbitrate between requests received and select a request to issue a grant for, wherein the plurality of grant arbiters is equal in number the to number of destinations, and wherein the grant arbiters are associated with specific destinations; and

a plurality of accept arbiters to arbitrate between the grants received and select a grant to accept, wherein the plurality of grant arbiters is equal in number the to number of sources, and wherein the grant arbiters are associated with specific sources.

29. The device of claim 28, wherein the grant arbiters receive a request from each source and the accept arbiters receive a grant from each grant arbiter.

30. The device of claim 28, wherein the grant arbiter and the accept arbiter associated with an accepted grant are not included in a next iteration of the scheduler.

31. A store and forward device comprising

an ingress interface including

a receiver to receive packets from external sources;

a segmentation unit to divide the packets having a length greater than a maximum segment length into multiple segments;

a plurality of queues to store the segments, wherein the queues are associated with sources and destinations;

a request generator to generate requests to transmit the segments, wherein a request indicates external factors including quantity, priority and age;

a framer to aggregate a plurality of the segments for the queues that received a grant to form a frame, wherein the frame may contain the segments associated with different packets; and

a transmitter to transmit the frame to an associated destination an egress interface including

a receiver to receive the frame;

a deframer to extract the segments from the frame;

queues to store the segments;

a monitor to monitor the queues for complete packets; and

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

a switching matrix to provide selective connectivity between the ingress interface and the egress interface;

a backplane consisting of a plurality of channels to connect the ingress interface and the egress interface to the switching matrix; and

a scheduler to receive the requests, assign the requests an internal priority based on the external factors, and to configure the switching matrix accordingly, wherein the scheduler processes the requests for the queues the by internal priority in order to generate the grants.

32. The device of claim 31, wherein said scheduler includes:

a plurality of grant arbiters to arbitrate between requests received and select a request to issue a grant for, wherein the plurality of grant arbiters is equal in number the to number of egress interfaces, and wherein the grant arbiters are associated with specific egress interfaces; and

a plurality of accept arbiters to arbitrate between grants received and select a grant to accept, wherein the plurality of grant arbiters is equal in number to number of ingress interfaces, and wherein the grant arbiters are associated with specific ingress interfaces.