Seamless switching for multihop hybrid networks

• US 9,722,943 B2
• Filed: 12/17/2012
• Issued: 08/01/2017
• Est. Priority Date: 12/17/2012
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Jain, Kaustubh, Tinnakornsrisuphap, Peerapol, Xue, Qi, Buesker, Brian M.
• Primary Examiner(s): Phunkulh, Bob
• Application Number:
  US13/717,111
• Publication Number:
  US 20140169383A1
• Time in Patent Office: 1,688 Days
• CPC Class Codes: H04L 1/1841 Resequencing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue

Abstract

Seamless path switching is made possible in a multi-hop network based upon stream marker packets and additional path distinguishing operations. A device receiving out-of-order packets on the same ingress interface is capable of determining a proper order for the incoming packets having different upstream paths. Packets may be reordered at a relay device or a destination device based upon where a path update is initiated. Reordering packets from the various upstream paths may be dependent upon a type of service associated with the packet.

Claims

1. A method for path switching in a network, the method comprising:

receiving, at an interface of a first device in the network, a plurality of packets from a second device;

determining that a first packet of the plurality of packets is associated with a first path used before a path update and that a second packet of the plurality of packets is associated with a second path used after the path update; and

processing the first packet and the second packet in an order based, at least in part, on the first packet being associated with the first path and the second packet being associated with the second path.

2. The method of claim 1, wherein the second packet is received before the first packet, and said processing comprises buffering the second packet until the first packet is processed.

3. The method of claim 1, wherein said processing is performed at a lower layer of a protocol stack than a transport layer.

4. The method of claim 1, wherein said processing comprises:

receiving a beginning-of-stream marker packet associated with the second path; and

in response to receiving the beginning-of-stream marker packet, buffering the second packet until the first packet has been processed.

5. The method of claim 4, wherein said processing further comprises:

receiving an end-of-stream marker packet associated with the first path; and

determining that the first packet has been processed based, at least in part, on receiving the end-of-stream marker packet.

6. The method of claim 4, wherein said buffering comprises buffering the second packet until an expiration of a buffer timeout time period.

7. The method of claim 1, wherein said determining that the second packet is associated with the second path comprises:

determining that a new path flag is included in the second packet, the new path flag indicative of the second path.

8. The method of claim 1, wherein said determining that the first packet is associated with the first path and the second packet is associated with the second path comprises:

determining that a marker packet, received by the first device from the second device, identifies the first packet as associated with the first path and transmitted from the second device prior to the path update.

9. The method of claim 8, wherein the marker packet identifies the first packet with at least one member selected from the group consisting of a packet checksum, a packet identifier, and a packet sequence number.

10. The method of claim 1,

wherein determining that the first packet is associated with the first path comprises determining that the first packet comprises a first medium access control protocol data unit that indicates a first transmit address indicative of the first path, and

wherein determining that the second packet is associated with the second path comprises determining that the second packet comprises a second medium access control protocol data unit that indicates a second transmit address indicative of the second path.

11. A method for communicating via a network, the method comprising:

transmitting, via a first path of the network from a first device to a second device, a first packet of a plurality of packets;

selecting a second path of the network from the first device to the second device, the second path to replace the first path;

transmitting, after transmitting the first packet via the first path, an end-of-stream marker packet via the first path, the end-of-stream marker packet indicative that the first path is being replaced;

transmitting, via the second path, a beginning-of-stream marker packet prior to transmitting a second packet of the plurality of packets; and

transmitting, via the second path, the second packet.

12. The method of claim 11, wherein the first path and the second path are different paths through the network that arrive at a same interface of the second device.

13. The method of claim 11, further comprising:

setting a destination address for the end-of-stream marker packet and the beginning-of-stream marker packet to an address of a relay device, in response to a determination that the relay device is in both the first path and the second path.

14. The method of claim 11, further comprising setting a path switch flag in the second packet.

15. The method of claim 11, further comprising including a path switch flag in the second packet.

16. The method of claim 11, further comprising including a path switch flag in each of a configurable number of packets transmitted via the second path.

17. The method of claim 11, further comprising:

transmitting a marker packet to the second device, wherein the marker packet includes packet identification information that identifies at least the first packet that was transmitted by the first device prior to replacement of the first path with the second path.

18. The method of claim 17, wherein the packet identification information comprises at least one member selected from the group consisting of a packet checksum, a packet identifier, and a packet sequence number.

19. An apparatus for path switching in a network, the apparatus comprising:

a processor;

an interface configured to receive a plurality of packets via a network; and

memory having program instructions stored therein, the program instructions executable by the processor to cause the apparatus to,

determine which of a first path used before a path update and a second path used after the path update is associated with each of the plurality of packets received via the interface; and

process the plurality of packets in an order that is based, at least in part, on association with either the first path or the second path.

20. The apparatus of claim 19, wherein the program instructions are further executable by the processor to cause the apparatus to buffer a second packet, which is received before a first packet, until the first packet is processed based, at least in part, on a determination that the second packet is associated with the second path and the first packet is associated with the first path, wherein the plurality of packets comprises the first packet and the second packet.

21. The apparatus of claim 19, wherein the program instructions are implemented at a lower layer of a protocol stack than a transport layer.

22. The apparatus of claim 19, wherein the program instructions are further executable by the processor to cause the apparatus to:

receive a beginning-of-stream marker packet associated with the second path; and

responsive to receipt of the beginning-of-stream marker packet, buffer a second packet associated with the second path until a first packet associated with the first path has been processed, wherein the plurality of packets comprises the first packet and the second packet.

23. The apparatus of claim 19, wherein the program instructions are further executable by the processor to cause the apparatus to:

determine that a first packet associated with the first path has been processed after receipt of an end-of-stream market packet associated with the first path, wherein the plurality of packets comprises the first packet.

24. The apparatus of claim 19, wherein the program instructions are further executable by the processor to cause the apparatus to buffer a first packet associated with the second path until an expiration of a predetermined buffer timeout time period, wherein the plurality of packets comprises the first packet.

25. The apparatus of claim 19, wherein the program instructions that cause the apparatus to determine which of the first path and the second path is associated with each of the plurality of packets comprises program instructions to cause the apparatus to determine which of the plurality of packets includes a new path flag, the new path flag indicative of the second path.

26. The apparatus of claim 19, wherein the program instructions that cause the apparatus to determine which of the first path and the second path is associated with each of the plurality of packets comprises program instructions to cause the apparatus to:

determine that a marker packet, received by the apparatus via the interface, includes packet identification information that identifies at least a first packet associated with the first path that was transmitted by a source device prior to the path update from the first path to the second path, wherein the plurality of packets comprises the first packet.

27. The apparatus of claim 26, wherein the packet identification information comprises at least one member selected from the group consisting of a packet checksum, a packet identifier, a packet sequence number, and a result of a calculation using at least one of the plurality of packets as a variable input.

28. The apparatus of claim 19, wherein the program instructions that cause the apparatus to determine which of the first path and the second path is associated with each of the plurality of packets comprises program instructions to cause the apparatus to:

determine which of a first media access control transmit address and a second media access control transmit address is indicated in each of the plurality of packets, wherein the first media access control transmit address corresponds to the first path and the second media access control transmit address corresponds to the second path.