Granted Patent B2

US 8,891,517 · App. 12/252,835 · Granted Nov 18, 2014

Abstract

Claims (137)

1. A switching device comprising a plurality of ingress ports and a plurality of egress ports, the switching device being arranged to receive data packets, at least one of which comprises a plurality of cells, through said ingress ports, and to forward received data packets to respective ones of said egress ports, wherein the switching device is further arranged to:

schedule the forwarding times of all of the cells of the data packet in a single integrated scheduling operation comprising:

determining a first time at which a first cell of the selected data packet is to be forwarded to one of said egress ports; and

determining a further time at which a respective further cell of the selected data packet is to be forwarded to said one of said egress ports; and

storing data indicating that said respective further cell is to be forwarded at said determined further time;

forwarding said first cell at said first time; and

forwarding said further cell of said selected data packet at said determined further time;

the switching device further comprising a memory storing a data structure comprising an ordered plurality of slots, each slot being associated with a respective time;

wherein storing data indicating that a respective further cell is to be forwarded at a determined further time comprises storing data identifying said data packet in one of said slots associated with said determined further time;

wherein the scheduling operation further comprises:

determining a plurality of further times at which respective further cells of said selected data packet are to be forwarded to said one of said egress ports;

for each of said further cells, storing data indicating the respective determined time at which the further cell is to be forwarded to said one of said egress ports; and

wherein the switching device is further arranged to forward each of said further cells of said selected data packet to said one of the egress ports at the respective determined time;

wherein said data structure comprises first slots defining a first phase and second slots defining a second phase; and

wherein cells of different data packets are forwarded in an interleaved manner.

2. A switching device according to claim 1 , wherein said at least one further time is determined according to a characteristic of the egress port to which the selected data packet is to be forwarded.

3. A switching device according to claim 2 , wherein said characteristic is a data rate of an egress link associated with said one of said egress ports.

4. A switching device according to claim 1 , wherein data packets received through said ingress ports are stored in at least one buffer.

5. A switching device according to claim 4 , wherein the or each buffer is associated with a respective single one of said plurality of ingress ports such that each buffer stores data packets received through a single ingress port.

6. A switching device according to claim 4 , wherein the or each buffer is a queue.

7. A switching device according to claim 4 , wherein the or each buffer is arranged to store a data packet by storing cells of that data packet.

8. A switching device according to claim 7 , wherein the or each buffer is arranged to store a data packet by storing cells of that data packet as a linked-list.

9. A switching device according to claim 7 , wherein the or each buffer is arranged to store a plurality of pointers, each pointer indicating the first cell of a respective data packet.

10. A switching device according to claim 4 , wherein said switching device is arranged to:

generate a set of candidate data packets from packets stored in said at least one buffer; and

select a data packet to be forwarded from said set of candidate data packets.

11. A switching device according to claim 10 , wherein said switching device is arranged to carry out said generating and said selecting separately from one another.

12. A switching device according to claim 10 , wherein said generating comprises determining whether a given data packet can be accepted by an egress port to which it is to be forwarded and including said given data packet in a set of candidate data packets only if said data packet can be accepted by the egress port to which it is to be forwarded.

13. A switching device according to claim 10 , wherein a plurality of sets of candidate data packets are created, each set comprising data packets received through a single one of said ingress ports, and said switching device is arranged to make selections from said plurality of sets of candidate data packets separately from other selections from said plurality of sets of candidate data packets.

14. A switching device according to claim 1 , wherein each cell is of an equal predetermined size.

15. A switching device according to claim 1 , wherein said switching device is arranged to forward cells of received data packets at a data rate greater than the data rate of an egress link associated with any one of said plurality of egress ports.

16. A switching device according to claim 1 , wherein said switch is arranged to forward cells of received data packets at a data rate at least twice the data rate of an egress link associated with any one of said plurality of egress ports.

17. A switching device according to claim 1 , wherein for any two adjacent slots of said data structure, a first slot is part of said first phase and a second slot is part of said second phase.

18. A switching device according to claim 1 , wherein if no data is stored in slots of said second phase the switching device attempts to store data in slots of said first phase.

19. A switching device according to claim 1 , wherein if data is stored in at least some slots of said second phase, but data is not stored in determined slots of the second phase, the switching device defers storing data in slots of the first phase.

20. A switching device according to claim 1 arranged to connect a plurality of computing devices to a plurality of input/output devices.

21. A switching device according to claim 1 , wherein the switching device is a PCI Express switching device.

22. A method of switching data packets between a plurality of ingress ports and a plurality of egress ports, wherein data packets, at least one of which comprises a plurality of cells, are received through said ingress ports and forwarded to respective ones of said egress ports, wherein the method comprises:

scheduling the forwarding times of all of the cells of the data packet in a single integrated scheduling operation comprising:

determining a first time at which a first cell of the selected data packet is to be forwarded to one of said egress ports;

determining a further time at which a respective further cell of the selected data packet is to be forwarded to said one of said egress ports; and

storing data indicating that said respective further cell is to be forwarded at said determined further time;

forwarding said first cell at said first time; and

forwarding said respective further cell of said selected data packet at said determined further time;

wherein storing data indicating that a respective further cell is to be forwarded at a determined further time comprises storing data identifying said data packet in a particular one of an ordered plurality of slots, each slot being associated with a respective time, and the particular one of the slots being associated with said determined further time;

wherein the scheduling operation further comprises:

determining a plurality of further times at which respective further cells of said selected data packet are to be forwarded to said one of said egress ports;

for each of said further cells, storing data indicating the respective determined time at which the further cell is to be forwarded to said one of said egress ports; and

wherein the switching device is further arranged to forward each of said further cells of said selected data packet to said one of the egress ports at the respective determined time;

wherein the ordered plurality of slots comprises first slots defining a first phase and second slots defining a second phase; and

wherein cells of different data packets are forwarded in an interleaved manner.

23. A non-transitory carrier medium carrying a computer program arranged to carry out a method according to claim 22 .

24. Apparatus for switching data packets, comprising:

a memory storing processor readable instructions; and

a processor arranged to read and execute instructions stored in said memory;

wherein the processor readable instructions comprise instructions configured to cause the processor to carry out the method of claim 22 .

25. A switching device comprising a plurality of ingress ports and a plurality of egress ports, the switching device being arranged to receive data packets through said ingress ports and to forward received data packets to respective ones of said egress ports, the switching device further comprising:

a plurality of ingress modules associated with said ingress ports, each ingress module comprising at least one buffer, an ingress arbiter, and an ingress scheduler, and each ingress module being arranged to, independently of the other ingress modules:

receive data packets from a respective single one of said ingress ports, store received data packets in the at least one buffer, select data packets from the at least one buffer as candidate data packets for forwarding to an egress port, and schedule transmission of selected ones of said candidate data packets to destination egress ports, said scheduling comprising:

determining a first time at which a first cell of a selected data packet is to forwarded to one of said egress ports;

determining at a further time at which a respective further cell of the selected data packet is to be forwarded to said one of said egress ports;

storing data indicating that said respective further cell is to be forwarded at said determined further time;

forwarding said first cell at said first time; and

forwarding said respective further cell of said selected data packet at said determined further time;

the switching device further comprising a memory storing a data structure comprising an ordered plurality of slots, each slot being associated with a respective time;

wherein storing data indicating that a respective further cell is to be forwarded at a determined further time comprises storing data identifying said data packet in one of said slots associated with said determined further time;

wherein the scheduling further comprises:

determining a plurality of further times at which respective further cells of said selected data packet are to be forwarded to said one of said egress ports;

for each of said further cells, storing data indicating the respective determined time at which the further cell is to be forwarded to said one of said egress ports; and

wherein the switching device is further arranged to forward each of said further cells of said selected data packet to said one of the egress ports at the respective determined time;

wherein said data structure comprises first slots defining a first phase and second slots defining a second phase; and

wherein cells of different data packets are forwarded in an interleaved manner.

26. A switching device according to claim 25 , wherein said ingress arbiter and said ingress scheduler operate independently of one another.

27. A switching device according to claim 25 , wherein said at least one further time is determined according to a characteristic of the egress port to which the selected data packet is to be forwarded.

28. A switching device according to claim 27 , wherein said characteristic is a data rate of an egress link associated with said one of said egress ports.

29. A switching device according to claim 25 arranged to connect a plurality of computing devices to a plurality of input/output devices.

30. A switching device according claim 25 , wherein the switching device is a PCI Express switching device.

31. A method of switching data packets between a plurality of ingress ports and a plurality of egress ports of a switching device, wherein data packets are received through said ingress ports and forwarded to respective ones of said egress ports, the switching device further comprising an ingress module for each of said ingress ports, wherein the method comprises, at each ingress module, independently of the other ingress modules:

receiving at an ingress module data packets from a respective single one of said ingress ports, each ingress module comprising at least one buffer for storage of received data packets;

selecting at the ingress module data packets from said at least one buffer as candidate data packets for forwarding to an egress port;

scheduling at the ingress module transmission of a selected one of said candidate data packets to destination egress ports;

wherein said scheduling comprises:

determining a first time at which a first cell of said selected data packet is to be forwarded to one of said egress ports;

determining at a further time at which a respective further cell of the selected data packet is to be forwarded to said one of said egress ports;

storing data indicating that said respective further cell is to be forwarded at said determined further time;

forwarding said first cell at said first time; and

forwarding said respective further cell of said selected data packet at said determined further time;

the switching device further comprising a memory storing a data structure comprising an ordered plurality of slots, each slot being associated with a respective time;

wherein storing data indicating that a respective further cell is to be forwarded at a determined further time comprises storing data identifying said data packet in one of said slots associated with said determined further time;

wherein the scheduling further comprises:

determining a plurality of further times at which respective further cells of said selected data packet are to be forwarded to said one of said egress ports;

for each of said further cells, storing data indicating the respective determined time at which the further cell is to be forwarded to said one of said egress ports; and

wherein the switching device is further arranged to forward each of said further cells of said selected data packet to said one of the egress ports at the respective determined time;

wherein said data structure comprises first slots defining a first phase and second slots defining a second phase; and

wherein cells of different data packets are forwarded in an interleaved manner.

32. A non-transitory carrier medium carrying a computer program arranged to carry out a method according to claim 31 .

33. Apparatus for switching data packets, comprising:

a memory storing processor readable instructions; and

a processor arranged to read and execute instructions stored in said memory;

wherein the processor readable instructions comprise instructions configured to cause the processor to carry out the method of claim 31 .

34. A switching device comprising a plurality of ingress ports and a plurality of egress ports, the switching device being arranged to receive data packets, at least one of which comprises a plurality of cells, through said ingress ports and to forward received data packets to respective ones of said egress ports, the switching device further comprising:

an ingress module arranged to receive data packets from at least some of said ingress ports, the ingress module comprising at least one buffer for storage of received data packets, an ingress arbiter for selecting data packets from said plurality of buffers as candidate data packets for forwarding to an egress port, and an ingress scheduler for scheduling transmission of selected ones of said candidate data packets to destination egress ports;

wherein said ingress arbiter selects data packets based upon an ability of an egress port to which a data packet is to be forwarded to accept a data packet; and

wherein said ingress scheduler is arranged to schedule the forwarding times of all of the cells of the data packet in a single integrated scheduling operation comprising determining a first time at which a first cell of the selected data packet is to be forwarded to one of said egress ports, determining a further time at which a respective further cell of the selected data packet is to be forwarded to said one of said egress ports, and storing data indicating that said respective further cell is to be forwarded at said determined further time, the ingress scheduler further being arranged to forward said first cell at said first time, and forward said respective further cell of said selected data packet at said determined further time;

the switching device further comprising a memory storing a data structure comprising an ordered plurality of slots, each slot being associated with a respective time;

wherein storing data indicating that a respective further cell is to be forwarded at a determined further time comprises storing data identifying said data packet in one of said slots associated with said determined further time;

wherein the scheduling further comprises:

determining a plurality of further times at which respective further cells of said selected data packet are to be forwarded to said one of said egress ports;

for each of said further cells, storing data indicating the respective determined time at which the further cell is to be forwarded to said one of said egress ports; and

wherein the switching device is further arranged to forward each of said further cells of said selected data packet to said one of the egress ports at the respective determined time;

wherein said data structure comprises first slots defining a first phase and second slots defining a second phase; and

wherein cells of different data packets are forwarded in an interleaved manner.

35. A switching device according to claim 34 , wherein said ingress arbiter and said ingress scheduler operate independently of one another.

36. A switching device according to claim 34 , wherein said at least one further time is determined according to a characteristic of the egress port to which the selected data packet is to be forwarded.

37. A switching device according to claim 36 , wherein said characteristic is a data rate of an egress link associated with said one of said egress ports.

38. A switching device according to claim 34 arranged to connect a plurality of computing devices to a plurality of input/output devices.

39. A switching device according to claim 34 , wherein the switching device is a PCI Express switching device.

40. A method of switching data packets between a plurality of ingress ports and a plurality of egress ports of a switching device, wherein data packets, at least one of which comprises a plurality of cells, are received through said ingress ports and forwarded to respective ones of said egress ports, wherein the method comprises:

receiving data packets from at least some of said ingress ports;

storing said received data packets in at least one buffer provided by an ingress module associated with said at least some ingress ports;

selecting data packets from said at least one buffer as candidate data packets for forwarding to an egress port;

scheduling, by way of respective single integrated scheduling operations, transmission of all of the cells of selected ones of said candidate data packets to destination egress ports;

wherein said selecting is based upon an ability of an egress port to which a data packet is to be forwarded to accept a data packet; and

wherein said scheduling comprises determining a first time at which a first cell of a selected data packet is to be forwarded to one of said egress ports, determining a further time at which a respective further cell of the selected data packet is to be forwarded to said one of said egress ports, storing data indicating that said respective further cell is to be forwarded at said determined further time, forwarding said first cell at said first time, and forwarding said respective further cell of said selected data packet at said determined further time;

the switching device further comprising a memory storing a data structure comprising an ordered plurality of slots, each slot being associated with a respective time;

wherein storing data indicating that a respective further cell is to be forwarded at a determined further time comprises storing data identifying said data packet in one of said slots associated with said determined further time;

wherein the scheduling operation further comprises:

determining a plurality of further times at which respective further cells of said selected data packet are to be forwarded to said one of said egress ports;

for each of said further cells, storing data indicating the respective determined time at which the further cell is to be forwarded to said one of said egress ports; and

wherein the switching devices is further arranged to forward each of said further cells of said selected data packet to said one of the egress ports at the respective determined time;

wherein said data structure comprises first slots defining a first phase and second slots defining a second phase; and

wherein cells of different data packets are forwarded in an interleaved manner.

41. A non-transitory carrier medium carrying a computer program arranged to carry out a method according to claim 40 .

42. Apparatus for switching data packets, comprising:

a memory storing processor readable instructions; and

a processor arranged to read and execute instructions stored in said memory;

wherein the processor readable instructions comprise instructions configured to cause the processor to carry out the method of claim 40 .

Assignments (10)