Switching device based on aggregation of packets

• US 20050207436A1
• Filed: 03/18/2004
• Published: 09/22/2005
• Est. Priority Date: 03/18/2004
• Status: Abandoned Application

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Inventors: Varma, Anujan
• Application Number:
  US10/804,674
• Publication Number:
  US 20050207436A1
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control
• CPC Class Codes: H04L 47/628 based on packet size, e.g. shortest packet first
• CPC Class Codes: H04L 49/3027 Output queuing

Abstract

In general, in one aspect, the disclosure describes a switching device that includes a segmentation unit to receive data packets of variable size and to store the data packets as segments. The data packets received having a length greater than a maximum segment length are divided into multiple segments. A plurality of queues associated with destinations store the segments. The switching device also includes a scheduler to generate a schedule including a data path from at least one queue to an associated destination. A framer aggregates a plurality of segments to form a frame. The frame has a maximum frame length and may contain segments associated with different data packets. The segments are retrieved from the at least one queue. The switching device further includes a transmitter to transmit the frame to the associated destination. The segments within the frame are transmitted together.

Claims

1. A switching device comprising

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

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

a scheduler to generate a schedule including a data path from at least one queue to an associated destination;

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 data packets; and

a transmitter to transmit the frame to the associated destination, wherein the segments within the frame are transmitted together.

2. The device of claim 1, wherein said segmentation unit divides the data packets having a length greater than the maximum segment length to form at least a first segment having the maximum segment length.

3. The device of claim 2, wherein a last segment formed by said segmentation unit may be less than the maximum segment length.

4. The device of claim 1, wherein said segmentation unit identifies a final segment belonging to a particular data packet.

5. The device of claim 1, wherein said scheduler generates the schedule based on requests for data packets from particular queues to be transmitted to particular destinations.

6. The device of claim 5, wherein said scheduler matches the requests and resolves conflicts in order to generate the schedule.

7. The device of claim 1, wherein said plurality of queues include one or more queues per destination based on priorities associated with the destinations.

8. The device of claim 1, wherein said framer forms the frame by aggregating segments from some subset of the one or more associated queues.

9. The device of claim 1, wherein said framer forms the frame by aggregating complete segments.

10. The device of claim 9, wherein said framer pads the frame to reach the maximum frame length.

11. The device of claim 1, wherein said transmitter transmits the segments making up a particular data packet in order.

12. The device of claim 1, wherein said transmitter interleaves segments associated with different data packets.

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

14. The device of claim 1, further comprising a switch fabric to provide a configurable connection between a plurality of sources and a plurality of destinations, wherein said switch fabric is configured by said scheduler, and wherein said switch fabric transmits frames from at least a subset of the plurality of sources to at least a subset of the plurality of destinations during a schedule cycle.

15. A method comprising:

receiving data packets of variable size;

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 destinations;

selecting a data path from at least one queue to an associated destination;

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 data packets;

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

16. The method of claim 15, wherein said forming segments includes dividing the data packets having a length greater than the maximum segment length into at least a first segment having the maximum segment length, and wherein a last segment formed may be less than the maximum segment size.

17. The method of claim 15, wherein said aggregating includes aggregating complete segments.

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

19. An apparatus comprising

a plurality of sources;

a plurality of destinations;

a receiver to receive frames, wherein the frames include a plurality of segments and the segments may be associated with multiple data packets;

a deframer to extract the segments from the frame;

a queue to store the segments;

a state monitor to track complete packets contained within the queue;

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

a scheduler to generate a schedule for transmitting frames; and

a switch fabric to selectively connect the plurality of sources to the plurality of destinations based on the schedule, wherein said switch fabric transmits frames from at least a subset of the plurality of sources to at least a subset of the plurality of destinations.

20. The apparatus of claim 19, wherein the frames are striped over a plurality of channels and said receiver is a deskewer that receives the frame over the plurality of channels and deskews the stripes and combines them into the frame.

21. The apparatus of claim 19, further comprising an error checker to check for errors in the frame.

22. The apparatus of claim 21, wherein said error checker checks for errors by comparing a grant received to the frame.

23. The apparatus of claim 19, wherein said state monitor determines complete packets by detecting an end of packet.

24. A method comprising

receiving frames of data from a plurality of sources for a plurality of destinations over a switch fabric, wherein a frame includes a plurality of segments and wherein the segments may be associated with multiple data packets;

extracting the segments from the frame;

storing the segments in a queue;

monitoring complete packets contained within the queue; and

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

25. The method of claim 24, further comprising checking for errors in the frame.

26. The method of claim 24, wherein said monitoring includes detecting an end of packet.

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 of variable size, 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, and transmit the segments within the frame together, wherein the segments stored in the queues have a segment maximum size and the packets having a larger size are divided into multiple segments, and wherein the frames have a maximum frame size, include a plurality of segments and may include segments associated with different packets, and

an egress interface module to receive frames, divide the frames into segments, 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 said Ethernet cards;

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

a scheduler to select connectivity between Ethernet cards and to configure said switching matrix accordingly.

28. The device of claim 27, wherein said backplane also connects said plurality of Ethernet cards to said scheduler.

29. The device of claim 28, wherein said backplane uses same channels to connect said Ethernet cards to said switching matrix and to said scheduler.

30. The device of claim 28, wherein said backplane provides a logical separation of data path between said Ethernet cards and said switching matrix and scheduling path between said Ethernet cards and said scheduler.

31. The device of claim 27, wherein the maximum frame size is selected based on at least some subset of configuration time of data path, scheduling time for scheduler, and complexity of scheduling algorithms.

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

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

34. A store and forward device comprising

a plurality of ingress interface modules to receive packets of variable size, store the packets as segments in queues, aggregate multiple segments together to form a frame, and transmit the segments within the frame together, wherein the segments stored in the queues have a segment maximum size and the packets having a larger size are divided into multiple segments, and wherein the frames have a maximum frame size and include a plurality of whole segments and may include segments associated with different packets;

a plurality of egress interface modules to receive frames, divide the frames into segments, store the segments in queues, 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 said plurality of ingress interface modules and said plurality of egress interface modules;

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

a scheduler to select connectivity between said plurality of ingress interface modules and said plurality of egress interface modules, and to configure said switching matrix accordingly.

35. The device of claim 34, wherein a pipeline schedule is implemented that includes at least some subset of

said ingress interface modules forming and transmitting requests to said scheduler,

scheduler computing a schedule based on the requests,

said scheduler transmitting grants to associated ingress interface modules and configuring said switching matrix, and

said ingress interface modules transmitting the frames in response to the grants.

36. The device of claim 34, wherein said switching matrix extracts a clock from frames received, re-times the frames to a common internal clock domain, aligns any configuration changes provided by said scheduler to the boundaries of the frames, and maintains an uninterrupted data stream to the egress interface modules by transmitting an idle stream when no frames are being transmitted.