Switching device utilizing requests indicating cumulative amount of data

• US 20050135356A1
• Filed: 12/22/2003
• Published: 06/23/2005
• 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
• Granted Patent: US 7,570,654 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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, 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 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 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 from a particular ingress port to a particular egress port;

a request generator to generate requests for permission to transmit data for the queues, wherein a request indicates a cumulative amount of data contained in a respective queue;

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 account for 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 store packets.

3. The device of claim 1, wherein the plurality of queues store segments.

4. The device of claim 1, wherein the plurality of queues store frames.

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

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

7. The device of claim 1, wherein the requests indicate the cumulative amount of data in terms of bytes.

8. The device of claim 1, wherein the requests indicate the cumulative amount of data in terms of packets.

9. The device of claim 1, wherein the requests indicate the cumulative amount of data in terms of segments.

10. The device of claim 1, wherein the requests indicate the cumulative amount of data in terms of frames.

11. The device of claim 1, wherein the data is variable sized packets.

12. The device of claim 11, further comprising a segmentation unit to receive the variable size packets and to store the variable size packets as segments, wherein the variable size packets having a length greater than a maximum segment length are divided into multiple segments.

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

14. The device of claim 12, further comprising a framer to aggregate a plurality of segments to form a frame, wherein the frame has a maximum frame length, wherein the segments are retrieved from the at least one queue, and wherein the frame may contain segments associated with different packets.

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

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

17. 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.

18. 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.

19. The device of claim 18, 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.

21. The method of claim 18, wherein said storing includes storing packets, segments, or frames.

22. The method of claim 18, wherein the queues are also associated with priority.

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

24. The method of claim 18, wherein the data is variable sized packets.

25. The method of claim 22, further comprising dividing the variable sized packets having a length greater than a maximum segment length into multiple segments, wherein said storing includes storing segments.

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

27. The method of claim 23, further comprising aggregating a plurality of segments to form a frame, wherein the frame has a maximum frame length, wherein the segments are retrieved from the at least one queue, and wherein the frame may contain segments associated with different packets.

28. The method of claim 25, further comprising extracting the segments from the frame.

29. The method of claim 18, further comprising striping the data across a plurality of channels.

30. The method of claim 18, 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.

32. The device of claim 28, wherein the backplane is optical.

33. The device of claim 28, wherein the switching matrix is optical.

34. The device of claim 28, wherein

the data is variable sized packets;

the ingress interface module includes a segmentation unit to receive the variable size packets and to store the variable size packets as segments, wherein the variable size 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.

36. The device of claim 28, 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.

20. A method comprising:

receiving data from external sources;

storing the data 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, wherein a request indicates a cumulative amount of data contained in a respective queue;

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 account for grants generated in current period or previous period that are not reflected in the queues yet; and

transmitting the data to external destinations;

31. 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 that identify the cumulative amount of data in associated queues, 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 operates on a pipeline schedule and modifies the requests received to account for grants generated in current period or previous period that are not reflected in the queues yet.

35. The device of claim 31, wherein

the ingress interface module further includes a framer to aggregate a plurality of segments to form a frame, wherein the frame has a maximum frame length, 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.