Switching device utilizing requests indicating cumulative amount of data

• US 7,570,654 B2
• Filed: 12/22/2003
• Issued: 08/04/2009
• Est. Priority Date: 12/22/2003
• Status: Expired due to Fees

• 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 B
• Assistant Examiner(s): Elpenord; Candal
• Application Number:
  US10/744,199
• Publication Number:
  US 20050135356A1
• Time in Patent Office: 2,052 Days
• Field of Search: 370/389, 370/474, 370/476, 370/465, 370/470, 370/391, 370412-418, 370428-429, 370/462
• US Class Current: 370/428
• 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/30 in combination with information about buffer occupancy at either end or at transit nodes
• 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
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/606 Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP

Abstract

In general, in one aspect, a switching device 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 operates on a pipeline schedule and modifies the requests received to account for grants generated in current period or previous period not reflected in the queues.

Claims

1. A switching device comprising

a plurality of ingress ports to receive packets from external sources;

a plurality of egress ports to transmit the packets to external destinations;

a segmentation unit to store the packets received by the plurality of ingress ports as segments, wherein the packets having a length greater than a maximum segment length are divided into multiple segments;

a plurality of queues to store the segments waiting to be transmitted from the plurality of ingress ports to the plurality of egress ports, wherein the segments are stored in a particular queue based at least in part on ingress port and egress port for an associated packet;

a framer to aggregate a plurality of segments from one or more queues associated with a particular ingress port and a particular egress port to form a frame, wherein the frame has a maximum frame length, wherein the segments are retrieved from the one or more queues, and wherein the frame may contain segments associated with different packets;

a request generator to generate requests for permission to transmit frames from the queues, wherein a request indicates a cumulative amount of data contained in a respective queue and wherein the cumulative amount of data is defined in terms of equivalent frames;

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 operates on a pipeline schedule and modifies the requests received to update the cumulative amount of data indicated as being contained in the queues to subtract the equivalent frames associated with grants generated in current period or previous period that are not reflected in the queues yet.

2. The device of claim 1, wherein the plurality of queues include at least one queue per ingress port to egress port transmission path.

3. The device of claim 2, wherein the plurality of queues include at least one queue per priority.

4. The device of claim 2, further comprising a reassembly unit to combine the segments making up a complete packet together to generate the packet.

5. The device of claim 1, further comprising a deframer to extract the segments from the frame.

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

7. The device of claim 1, wherein said scheduler transmits a grant to an associated ingress port as part of the generate grants stage of the pipeline schedule and transmits a corresponding grant to an associated egress port as part of the configure the switching matrix stage of the pipeline schedule.

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

9. The device of claim 8, 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.

12. The method of claim 4, further comprising reassembling the segments making up a complete packet together to generate the packet.

10. A method comprising:

receiving packets from external sources;

breaking the packets received having a length greater than a maximum segment length into multiple segments;

storing the segments in queues, wherein the queues are associated with a packet flow from an external source from which a packet came and an external destination to which the packet is going;

aggregating a plurality of segments from one or more queues associated with a particular packet flow to form a frame, wherein the frame has a maximum frame length, wherein the segments are retrieved from the one or more queues, and wherein the frame may contain segments associated with different packets;

generating requests for permission to transmit frames from the queues, wherein a request indicates a cumulative amount of data contained in a respective queue and wherein the cumulative amount of data is defined in terms of equivalent frames;

receiving the requests at a scheduler operating on a pipeline schedule, wherein the scheduler generates grants based on the request and configures a switching matrix, wherein said scheduler modifies the requests received to update the cumulative amount of data indicated as being contained in the queues to subtract the equivalent frames associated with grants generated in current period or previous period that are not reflected in the queues yet; and

transmitting the data to external destinations.

11. The method of claim 10, wherein the queues are also associated with priority.

13. The method of claim 10, further comprising extracting the segments from the frame.

14. The method of claim 10, further comprising striping the frames across a plurality of channels.

15. The method of claim 10, further comprising the scheduler assigning the requests an internal priority number based on at least some subset of the cumulative amount of data and other factors indicated in the request, wherein the scheduler generates grants based at least in part on the internal priority number.

16. A store and forward device comprising

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

an ingress interface module to receive the packets from external sources, break the packets having a length greater than a maximum segment length into multiple segments, store the segments in queues associated with at least some subset of destination and priority, aggregate a plurality of segments from one or more queues associated with particular flows to form frames, generate requests that identify the cumulative amount of data in associated queues in terms of equivalent frames, and transmit frames from queues upon receipt of associated grants;

and

an egress interface module to receive the frames from the ingress interface module, extract the segments from the frames, reassemble the segments making up complete packets together, and transmit the packets 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 operates on a pipeline schedule and modifies the requests received to update the cumulative amount of data indicated as being contained in the queues to subtract the equivalent frames associated with grants generated in current period or previous period that are not reflected in the queues yet.

17. The device of claim 16, wherein the backplane is optical.

18. The device of claim 16, wherein the switching matrix is optical.

19. The device of claim 16, wherein

the requests also indicate other factors, the other factors including at least some subset of priority and aging;

and

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.