Variable packet-size backplanes for switching and routing systems
View Patent ↗The present invention provides switches and routers, preferably with fully-connected mesh fabrics, that transmit data through the switch fabric in variable-size data units. Variable-size data units allow switches and routers to provide throughputs close to hardware capabilities, eliminating the need for over-capacity hardware in the switch fabric and other components. Along with variably-size data units, preferred embodiments of this invention include scheduling methods that provide fair allocation of pre-determined bandwidths to different protocols, to different classes of service within protocols, and to different resources within the switch by use of certain weighted, fair scheduling methods. The switches and routers of this invention are particularly directed to multi-protocol, high-throughput communication applications, but may have wide applicability in systems generally where data packets are switched or routed.
1. A system for switching or routing data packets comprising:
(a) one or more ingress elements and one or more egress elements, wherein the ingress elements receive data packets from input ports, the egress elements transmit data packets to output ports and each of the ingress and egress elements includes a control element that allocates fabric paths,
(b) a switch fabric for transmitting data packets from the ingress elements to the egress elements, wherein data packets are transmitted in variably-sized payloads of fabric data units (FDUs) having total sizes varying between a minimum size and a maximum size,
wherein each control element further repeatedly performs each of the steps of (i) segmenting data packets received by an ingress element and encapsulating them into the payloads of two or more FDUs, if the packets' sizes exceed the maximum FDU payload size, and encapsulating data packets received by an ingress element into the payload of a single FDU, if the packets' sizes do not exceed the maximum FDU payload size, and (ii) transmitting FDUs from the ingress elements through the switch fabric to the egress elements.
2. The system of claim 1 wherein at least one data packet is an internet protocol (IP) packet and at least one other data packet is an asynchronous transfer mode (ATM) packet.
3. The system of claim 1 wherein at least one FDU with a size less than the maximum FDU size is transmitted through the switch fabric.
4. The system of claim 1 wherein data packets are segmented into one or more FDUs, the last FDU varying in size between the minimum and the maximum size with all but the last FDUs being of maximum size.
5. The system of claim 1 wherein the maximum FDU size is selected to limit service latency or to limit the variability of service latency.
6. The system of claim 1 wherein the switch fabric comprises at least one unshared transmission path connecting each ingress element with each egress element.
7. The system of claim 1 wherein each of the ingress and egress control elements further perform a step of allocating a path through the switch fabric between an ingress element and an egress element prior to forwarding an FDU from that ingress element to that egress element.
8. The system of claim 1 wherein each ingress control element selects a data packet for transmission through the switch fabric.
9. A method for switching or routing data packets from an ingress element to an egress element through a switch fabric wherein each of the ingress and egress elements includes a control element comprising:
(a) receiving at least one data packet from at least one input port on at least one ingress element, and
from each control element (i) allocating fabric paths, (ii) segmenting at least one received data packet and encapsulating it into the payloads of two or more fabric data units (FDUs), if the packet's size exceeds a maximum FDU payload size, wherein data is transmitted through the switch fabric in variably-sized fabric data units (FDUs) having total sizes varying between a minimum size and a maximum size, and encapsulating the data pack into the payload of a single FDU, if the packet's size does not exceed the maximum FDU payload size and (iii) transmitting at least one selected FDU from an ingress element through the switch fabric to an egress element.
10. The method of claim 9 wherein at least one data packet is an internet protocol (IP) packet and at least one other data packet is an asynchronous transfer mode (ATM) packet.
11. The method of claim 9 wherein at least one FDU with a size less than the maximum FDU size is transmitted through the switch fabric.
12. The method of claim 9 wherein data packets are segmented into one or more FDUs, the last FDU varying in size between the minimum and the maximum size with all but the last FDUs being of maximum size.
13. The method of claim 12 wherein at least one data packet is segmented into two or more FDUs wherein the size of the last FDU is less than the maximum FDU size.
14. The method of claim 9 further comprising a step of allocating a path through the switch fabric between an ingress element and an egress element prior to transmitting an FDU from that ingress element to that egress element.
15. The method of claim 9 wherein an FDU further comprises a fixed-size header area for control information, so that the total FDU size equals the fixed header size plus the variable payload size.
16. The method of claim 9 wherein the steps of receiving, segmenting, and transmitting are performed independently on at least one ingress element.
17. The method of claim 9 further comprising a step of selecting from a plurality of FDUs stored by the ingress element at least one FDU for transmission through the switch fabric.
18. The method of claim 17 wherein the step of selecting grants service to data packets that is substantially independent of data packet sizes.
19. The method of claim 18 wherein service is measured in units of bytes.
20. The method of claim 17 wherein the step of selecting grants service to data packets with similar service characteristics and/or requirements in a manner that can be substantially pre-selected.
21. The method of claim 17 wherein the step of selecting performs a deficit type of scheduling.
22. The method claim 17 wherein the step of selecting performs a weighted-fair type of scheduling.
23. The method of claim 22 wherein the weighted-fair type of scheduling method is round-robin.