Determination of a plurality of paths before selection of one path of the plurality of paths for transmission of one or more packets

• US 20050259647A1
• Filed: 05/20/2004
• Published: 11/24/2005
• Est. Priority Date: 05/20/2004
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Wakumoto, Shaun Kazuo, Ersoy, Cetin, Bare, Ballard Claude
• Granted Patent: US 7,609,705 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/34 Source routing

Abstract

An apparatus in one example comprises a first mesh network switch, of a plurality of mesh network switches, that employs mesh connection information of one or more mesh network switches of the plurality of mesh network switches to determine a plurality of paths between the first mesh network switch and a second mesh network switch, of the plurality of mesh network switches, before a selection of one path of the plurality of paths for transmission of one or more packets from the first mesh network switch to the second mesh network switch.

Claims

1. An apparatus, comprising:

a first mesh network switch, of a plurality of mesh network switches, that employs mesh connection information of one or more mesh network switches of the plurality of mesh network switches to determine a plurality of paths between the first mesh network switch and a second mesh network switch, of the plurality of mesh network switches, before a selection of one path of the plurality of paths for transmission of one or more packets from the first mesh network switch to the second mesh network switch.

2. The apparatus of claim 1, wherein the plurality of paths comprises a plurality of predetermined redundant unicast paths between the first mesh network switch and the second mesh network switch.

3. The apparatus of claim 1, wherein the one or more packets comprise a packet, wherein the first mesh network switch inserts a mesh tag into the packet, wherein the mesh tag comprises an identifier of the one path of the plurality of paths to route the packet from the first mesh network switch along the one path to the second mesh network switch.

4. The apparatus of claim 3, wherein the mesh tag comprises a unique identifier of the first mesh network switch, a unique identifier of the second mesh network switch, and the identifier of the one path.

5. The apparatus of claim 3, in combination with the second mesh network switch, wherein the second mesh network switch removes the mesh tag from the packet before sending the packet out of a mesh network that comprises the plurality of mesh network switches.

6. The apparatus of claim 1, wherein the one path comprises a first path, wherein the one or more packets comprises one or more first packets;

wherein upon a determination to not use the first path for one or more second packets, the first mesh network switch selects a second path of the plurality of paths for transmission of the one or more second packets to the second mesh network switch.

7. The apparatus of claim 6, wherein the first mesh network switch determines and assigns an identifier to the second path before the determination to not use the first path.

8. The apparatus of claim 6, wherein upon failure of a link in the first path, the first mesh network switch selects the second path for transmission of the second packet to the second mesh network switch.

9. The apparatus of claim 6, wherein the one or more first packets comprise a first packet, wherein the first mesh network switch inserts a first mesh tag into the first packet, wherein the first mesh tag comprises an identifier of the first path of the plurality of paths to route the first packet along the first path to the second mesh network switch;

wherein the one or more second packets comprise a second packet, wherein the second mesh network switch inserts a second mesh tag into the second packet, wherein the second mesh tag comprises an identifier of the second path of the plurality of paths to route the second packet along the second path to the second mesh network switch.

10. The apparatus of claim 1, wherein the plurality of paths between the first mesh network switch and the second mesh network switch comprise a subset of a plurality available paths between the first mesh network switch and the second mesh network switch.

11. The apparatus of claim 10, wherein the first mesh network switch assigns a unique path identifier to each of the plurality of paths between the first mesh network switch and the second mesh network switch.

12. The apparatus of claim 10, wherein the first mesh network switch stores a unique mesh tag for each of the plurality of paths between the first mesh network switch and a second mesh network switch.

13. The apparatus of claim 10, wherein the plurality of paths between the first mesh network switch and the second mesh network comprises a plurality of selected paths of the plurality available paths;

wherein the first mesh network switch periodically tests the plurality of available paths between the first mesh network switch and the second mesh network switch to determine whether the plurality of selected paths are preferred over unused paths of the plurality of available paths.

14. The apparatus of claim 1, wherein the first mesh network switch employs the mesh connection information to determine a plurality of paths to each of the plurality of mesh network switches;

wherein the first mesh network switch stores one unique mesh tag for each of the plurality of paths to the plurality of mesh network switches.

15. The apparatus of claim 1, wherein the first mesh network switch stores a list of the plurality of paths, wherein upon a determination that a link in the one path has failed, the first mesh network switch checks the list for a second path that does not run through the link;

wherein the first mesh network switch selects the second path for transmission of one or more second packets from the first mesh network switch to the second mesh network switch.

16. The apparatus of claim 1, wherein the first mesh network switch stores a list of the plurality of paths, wherein upon a determination that a link in the one path has failed, the first mesh network switch associates a flag with any path on the list that run through the link.

17. The apparatus of claim 16, wherein upon the determination that the link in the one path has failed, the first mesh network switch searches the list for a second path that is not associated with the flag.

18. The apparatus of claim 1, wherein upon the determination by the first mesh network switch that the link in the one path has failed, the first mesh network switch sends updated mesh connection information to one or more other mesh network switches of the plurality of mesh network switches to indicate failure of the link.

19. The apparatus of claim 1, wherein the first mesh network switch assigns one or more destination and/or source Media Access Control (“

MAC”

) addresses to the one path.

20. The apparatus of claim 19, wherein the first mesh network switch predetermines the plurality of paths;

wherein upon failure of the one path, the first mesh network switch assigns one or more of the one or more destination and/or source MAC addresses to a second path of the plurality of paths.

21. The apparatus of claim 1, wherein the first mesh network switch employs mesh connection information of the plurality of mesh network switches to determine a plurality of redundant broadcast paths between the first mesh network switch and each of the plurality of mesh network switches.

22. A method, comprising the steps of:

assigning a first path identifier to a first path of a plurality of paths between a first mesh network switch and a second mesh network switch;

assigning a second path identifier to a second path of the plurality of paths between the first mesh network switch and the second mesh network switch; and

employing the first path identifier to direct one or more packets along the first path rather than the second path.

23. The method of claim 22, wherein the one or more packets comprise one or more first packets, the method further comprising the step of:

employing, upon a determination to avoid the first path for one or more second packets, the unique path identifier of the second path to direct the one or more second packets along the second path between the first mesh network switch and the second mesh network switch.

24. The method of claim 22, wherein the one or more packets comprise one or more first packets, the method further comprising the steps of:

storing a list of the plurality of paths;

searching, upon a determination that a link in the first path has failed, the list for the second path that does not run through the link; and

employing the second path identifier to direct one or more second packets along the second path rather than the first path.

25. The method of claim 22, wherein the step of employing the first path identifier to direct the one or more packets along the first path rather than the second path comprises the step of:

inserting one or more mesh tags into the one or more packets to direct the one or more packets along the first path, wherein the one or more mesh tags comprise a unique identifier of the first mesh network switch, a unique identifier of the second mesh network switch, and the first path identifier.

26. The method of claim 22, further comprising the steps of:

selecting the plurality of paths from a plurality of plurality of available paths between the first mesh network switch and the second mesh network switch based on one or more performance characteristics of the plurality of paths; and

testing the plurality of available paths to determine whether the plurality of paths are preferred over unused paths of the plurality of available paths.

27. A method, comprising the step of:

selecting a substitute path of a plurality of predetermined paths to a mesh network switch for transmission of one or more packets to the mesh network switch upon a determination to avoid an intended path of the plurality of predetermined paths for transmission of the one or more packets.

28. The method of claim 27, wherein the one or more packets comprise one or more second packets, wherein the step of selecting the substitute path of the plurality of predetermined paths to the mesh network switch for transmission of the one or more packets to the mesh network switch upon the determination to avoid the intended path of the plurality of predetermined paths for transmission of the one or more packets comprises the steps of:

selecting the intended path of the plurality of predetermined paths for transmission of one or more first packets to the mesh network switch; and

selecting, upon failure of a link in the intended path, the substitute path for transmission of the one or more second packets to the mesh network switch.

29. The method of claim 28, wherein the step of selecting, upon failure of the link in the intended path, the substitute path for transmission of the one or more second packets to the mesh network switch comprises the steps of:

searching a database that stores the plurality of predetermined paths for the substitute path that avoids the link; and

inserting a path identifier of the substitute path into the one or more second packets to direct the one or more second packets along the substitute path.

30. The method of claim 28, further comprising the step of:

sending an indication of the failure of the link in the intended path to one or more mesh network switches to update mesh connection information stored by the one or more mesh network switches.

31. The method of claim 27, further comprising the step of:

reassigning one or more destination and/or source MAC addresses from use of the intended path to use of the substitute path upon failure of the intended path.

32. An apparatus, comprising:

means for employing mesh connection information of one or more mesh network switches of a plurality of mesh network switches to determine a plurality of paths between a first mesh network switch and a second mesh network switch of the plurality of mesh network switches; and

means for selecting one path of the plurality of paths for transmission of one or more packets from the first mesh network switch to the second mesh network switch.

33. The apparatus of claim 32, further comprising:

means for assigning a plurality of identifiers to the plurality of paths between the first mesh network switch and the second mesh network switch; and

means for inserting an identifier of the one path of the plurality of identifiers of the plurality of paths into the one or more packets to direct the one or more packets along the one path from the first mesh network switch to the second mesh network switch.

34. The apparatus of claim 32, wherein the one path comprises a first path, wherein the one or more packets comprise one or more first packets, the apparatus further comprising:

means for storing a list of the plurality of paths between the first mesh network switch and the second mesh network switch; and

means for selecting a second path of the plurality of paths from the list for transmission of one or more second packets to the second mesh network switch upon a determination to avoid the first path for the one or more second packets.

35. An article, comprising:

one or more computer-readable signal-bearing media;

means in the one or more media for assigning a first path identifier to a first path of a plurality of paths between a first mesh network switch and a second mesh network switch;

means in the one or more media for assigning a second path identifier to a second path of the plurality of paths between the first mesh network switch and the second mesh network switch; and

means in the one or more media for employing the first path identifier to direct one or more packets along the first path rather than the second path.