Packet routing as a function of direction

• US 7,746,872 B2
• Filed: 05/21/2004
• Issued: 06/29/2010
• Est. Priority Date: 05/21/2004
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Norden, Hahn
• Primary Examiner(s): Gauthier; Gerald
• Application Number:
  US10/850,672
• Publication Number:
  US 20050259665A1
• Time in Patent Office: 2,230 Days
• Field of Search: 370/389, 370/352, 370/218, 370/229, 370/230, 370/235, 370/254, 370/360, 370/388, 370/412, 370/466, 370/395.51, 370/396, 370/401, 370/424, 707/10, 707/3, 709/227, 709/252, 709/223, 709/238, 709/250, 711/110, 340/2.21, 340/906, 710/305, 714/43, 398/47, 712/15, 719/328
• US Class Current: 370/396
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/34 Source routing

Abstract

A direction of travel of a packet at a switch in an interconnection fabric that has multiple switches with ports is determined. A next turn pointer in the packet is used to identify turn bits in a routing path. The turn bits are then used to select an exit port as a function of the direction of travel of the packet.

Claims

1. A method comprising:

determining the direction of travel of a packet at a switch in an interconnection fabric that has multiple switches with ports;

identifying turn bits in a routing path as a function of a next turn pointer in the packet; and

selecting an exit port as a function of the direction of travel of the packet using the turn bits.

2. The method of claim 1 wherein the turn bits indicate an amount of rotation between an enter port and the exit port of the switch.

3. The method of claim 2 wherein the direction of travel of the packet is used to determine a direction of rotation from the enter port.

4. The method of claim 1 and further comprising updating the next turn pointer to identify bits for routing path for use by a next switch.

5. The method of claim 4, wherein the next turn pointer is updated by incrementing it for a packet traveling in a forward direction and decrementing it for a packet traveling in a backward direction.

6. The method of claim 1 wherein the next turn pointer represents a least significant bit in a forward direction of travel, and a most significant bit in a backward direction of travel of the packet.

7. The method of claim 1 wherein the number of turn bits for a switch is a function of the number of ports of the switch.

8. The method of claim 1 wherein determining a direction of travel of the packet comprises comparing the next turn pointer to a destination pointer in the packet.

9. A method comprising:

looking up a path for a packet from an origin switch to a destination switch in a switch fabric;

creating a header for the packet having a routing path, a destination pointer and a next turn pointer;

forwarding the packet to the next switch in the path; and

at each successive switch in the path;

updating the next turn pointer;

determining a direction of travel of the packet; and

forwarding the packet to the next switch based on the path, the next turn pointer and the destination pointer until the destination switch is reached.

10. The method of claim 9 and further comprising:

changing the destination pointer from the destination switch to the origin switch;

forwarding the packet to the previous switch in the path; and

at each successive switch;

updating the next turn pointer;

determining a direction of travel of the packet; and

forwarding the packet to the next switch based on the path, the next turn pointer and the destination pointer until the origin switch is reached.

11. The method of claim 10 wherein the next turn pointer identifies turn bits in the routing path that indicate an amount of rotation between an enter port and the exit port of a switch.

12. The method of claim 11 wherein the direction of travel of the packet is used to determine a direction of rotation from the enter port.

13. The method of claim 12, wherein the next turn pointer is updated by incrementing it for a packet traveling in a forward direction and decrementing it for a packet traveling in a backward direction.

14. The method of claim 10 wherein the next turn pointer represents a least significant bit in a forward direction of travel, and a most significant bit in a backward direction of travel of the packet.

15. A method comprising:

at a switch in a switch fabric that has multiple switches with ports, determining the direction of travel of a packet;

identifying turn bits in a routing path using a next turn pointer in the packet; and

calculating an exit port as a function of the direction of travel of the packet using the turn bits, wherein the turn bits represent a clockwise distance of the exit port from an enter port when the packet is traveling in a first direction, and a counter-clockwise distance of the exit port form the enter port when the packet is traveling in a second direction in the switch fabric.

16. The method of claim 15 and further comprising determining a direction for the packet as a function of a destination pointer.

17. The method of claim 16 wherein the direction of the packet is in a forward direction when the destination pointer is larger than the next turn pointer.

18. The method of claim 17 wherein the packet has arrived at a destination switch when the next turn pointer is larger than the destination pointer.

19. The method of claim 16 wherein the direction of the packet is in a backward direction when the destination pointer is less than the next turn pointer.

20. The method of claim 19 wherein the packet has arrived at a destination switch when the next turn pointer is equal to the destination pointer.

21. A switch comprising:

a processor having a computer readable medium with executable instructions stored thereon for causing the processor to implement a method comprising;

determining the direction of travel of a packet at the switch in an interconnection fabric that has multiple switches with ports;

identifying turn bits in a routing path as a function of a next turn pointer in the packet; and

selecting an exit port as a function of the direction of travel of the packet and the turn bits.

22. The switch of claim 21 wherein the turn bits indicate an amount of rotation between an enter port and the exit port of the switch.

23. The switch of claim 22 wherein the direction of travel of the packet is used to determine a direction of rotation from the enter port.

24. The switch of claim 21 and further comprising updating the next turn pointer to identify bits for routing path for use by a next switch.

25. The switch of claim 24, wherein the next turn pointer is updated by incrementing it for a packet traveling in a forward direction and decrementing it for a packet traveling in a backward direction.

26. The switch of claim 21 wherein the next turn pointer represents a least significant bit in a forward direction of travel, and a most significant bit in a backward direction of travel of the packet.

27. The switch of claim 21 wherein the number of turn bits for a switch is a function of the number of ports of the switch.

28. A computer readable medium having a packet header stored thereon, the header comprising:

a routing path identifying distances between an enter port and an exit port for switches in a switch fabric;

a next turn pointer; and

a destination bit pointer wherein a direction of travel of the packet is a function of the next turn pointer and destination bit pointer.

29. The computer readable medium of claim 28 wherein the next turn pointer identifies a set of turn bits in the routing path corresponding to the number of ports for a switch.

30. The computer readable medium of claim 29 wherein the direction of travel of the packet identifies a direction between the enter port and the exit port.

31. The computer readable medium of claim 28 wherein the next turn pointer identifies a least significant bit or a most significant bit of the routing path as a function of the direction of travel of the packet.