REVERSE DIRECTED ACYCLIC GRAPH FOR MULTIPLE PATH REACHABILITY FROM ORIGIN TO IDENTIFIED DESTINATION VIA MULTIPLE TARGET DEVICES

• US 20160269188A1
• Filed: 03/10/2015
• Published: 09/15/2016
• Est. Priority Date: 03/10/2015
• Status: Abandoned Application

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: THUBERT, PASCAL, WETTERWALD, PATRICK, VASSEUR, JEAN-PHILIPPE, LEVY-ABEGNOLI, ERIC MICHEL
• Application Number:
  US14/643,190
• Publication Number:
  US 20160269188A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/34 Source routing

Abstract

In one embodiment, a method comprises: multicasting, by a wireless network device in a wireless network, a first message originated by the wireless network device and requesting reachability to an identified destination device via an identified target device class; generating, by the wireless network device, plural paths for reaching the identified destination device based on receiving destination advertisement messages having been originated by respective target devices belonging to the target device class; and pluricasting copies of a data packet to the identified destination device via the plural paths.

Claims

1. A method comprising:

multicasting, by a wireless network device in a wireless network, a first message originated by the wireless network device and requesting reachability to an identified destination device via an identified target device class;

generating, by the wireless network device, plural paths for reaching the identified destination device based on receiving destination advertisement messages having been originated by respective target devices belonging to the target device class; and

pluricasting copies of a data packet to the identified destination device via the plural paths.

2. The method of claim 1, further comprising:

the wireless network device specifying, in the first message, one or more constraints required for each target device of the target device class, including at least one of a first latency cost for transmission of a data packet from the wireless network device to the corresponding target device, a second latency cost for transmission of the data packet from the corresponding target device to the identified destination device via a backbone network, or a total latency cost for transmission of the data packet from the wireless network device to the identified destination device via the corresponding target device;

each destination advertisement message indicating the corresponding target device can guarantee the one or more constraints.

3. The method of claim 1, wherein:

the generating includes any one of identifying whether any one of the paths is a fully non-congruent path having no shared links based on whether any destination advertisement message indicates origination by a first and only the first of the target devices, or identifying whether any one of the paths is a partially non-congruent path having at least one shared link and a branch node that can reach at least two of the target devices;

the generating further including selectively generating a first path based on a determined availability of a first fully non-congruent path for reaching the first target device, and generating a second path based on at least one of a determined availability of a second fully non-congruent path for reaching a second of the target devices or selection of one of the partially non-congruent paths for reaching the second target device via the branch node.

4. The method of claim 3, wherein the generating further includes pruning any convergent paths sharing a link between the branch node and a corresponding one of the target devices.

5. The method of claim 1, further comprising the wireless network device setting a replication policy for a first of the paths, the replication policy causing a branch node along the first path to limit replication of the data packet among multiple target devices reachable by the branch node.

6. The method of claim 5, wherein the replication policy is output along the first path based on at least one of:

supplying the replication policy in one of the corresponding copy of the data packet output onto the first path;

or

sending a second message specifying the replication policy, distinct from the copies of the data packet, onto the first path.

7. An apparatus comprising

a device interface circuit configured for multicasting, into a wireless network, a first message requesting reachability to an identified destination device via an identified target device class, the device interface circuit further configured for receiving destination advertisement messages having been originated by respective target devices belonging to the target device class;

and

a processor circuit configured for generating the first message, the processor circuit further configured for generating plural paths for reaching the identified destination device via the target devices based on the destination advertisement messages, the processor circuit further configured for causing the device interface circuit to pluricast copies of a data packet to the identified destination device via the plural paths.

8. The apparatus of claim 7, wherein:

the processor circuit is configured for specifying, in the first message, one or more constraints required for each target device of the target device class, including at least one of a first latency cost for transmission of a data packet from the apparatus to the corresponding target device, a second latency cost for transmission of the data packet from the corresponding target device to the identified destination device via a backbone network, or a total latency cost for transmission of the data packet from the apparatus to the identified destination device via the corresponding target device;

each destination advertisement message indicating the corresponding target device can guarantee the one or more constraints.

9. The apparatus of claim 7, wherein the processor circuit further is configured for:

identifying whether any one of the paths is a fully non-congruent path having no shared links based on whether any destination advertisement message indicates origination by a first and only the first of the target devices, or identifying whether any one of the paths is a partially non-congruent path having at least one shared link and a branch node that can reach at least two of the target devices;

selectively generating a first path based on a determined availability of a first fully non-congruent path for reaching the first target device, and generating a second path based on at least one of a determined availability of a second fully non-congruent path for reaching a second of the target devices or selection of one of the partially non-congruent paths for reaching the second target device via the branch node.

10. The apparatus of claim 9, wherein the processor circuit further is configured for pruning any convergent paths sharing a link between the branch node and a corresponding one of the target devices.

11. The apparatus of claim 7, wherein the processor circuit is configured for setting a replication policy for a first of the paths, the replication policy causing a branch node along the first path to limit replication of the data packet among multiple target devices reachable by the branch node.

12. The apparatus of claim 11, wherein the processor circuit is configured for causing the device interface circuit to output the replication policy along the first path based on at least one of:

supplying the replication policy in one of the corresponding copy of the data packet output onto the first path;

or

sending a second message specifying the replication policy, distinct from the copies of the data packet, onto the first path.

13. One or more non-transitory tangible media encoded with logic for execution by a machine and when executed by the machine operable for:

multicasting, by a wireless network device in a wireless network, a first message originated by the wireless network device and requesting reachability to an identified destination device via an identified target device class;

generating, by the wireless network device, plural paths for reaching the identified destination device based on receiving destination advertisement messages having been originated by respective target devices belonging to the target device class; and

pluricasting copies of a data packet to the identified destination device via the plural paths.

14. A method comprising:

receiving, via a wireless data link by a border router device providing reachability to an identified destination device, a first message requesting reachability to the identified destination device via an identified target device class;

generating, by the border router device in response to the first message, a destination advertisement message in response to the border router device belonging to the target device class; and

outputting, by the border router device, the destination advertisement message via the wireless data link for delivery to an originator device of the first message, the destination advertisement specifying the identified destination device is reachable.

15. The method of claim 14, wherein:

the first message further specifies one or more constraints required for a target device of the target device class, including at least one of a first latency cost for transmission of a data packet from the originator device to the target device, a second latency cost for transmission of the data packet from the target device to the identified destination device via a backbone network, or a first path a total latency cost for transmission of the data packet from the originator device to the identified destination device via the target device;

the generating including generating the destination advertisement message based on the border router device determining the constraints required for the target device can be guaranteed by the border router device.

16. The method of claim 14, wherein the generating includes inserting at least one of a border router device identifier indicating the identified destination device is reachable via the border router device, first path metrics describing propagation characteristics of a path of the first message from the originator device to the border router device via a wireless network, or second path metrics describing propagation characteristics for the border router device reaching the identified destination device via a backbone network.

17. The method of claim 14, further comprising:

receiving a data packet originated by the originator device via the wireless data link and destined for the identified destination device; and

selectively forwarding the data packet to the identified destination device, via a backbone network, based on a determined absence of any other border router device in the backbone network having already forwarded the data packet to the identified destination device.

18. The method of claim 17, wherein the data packet is received via the wireless data link from a first wireless network device, the method further comprising:

receiving a copy of the data packet via a second wireless data link from a second wireless network device and destined for the identified destination device; and

dropping the copy of the data packet from transmission to the identified destination device, based on determining the data packet has already been forwarded to the identified destination device.

19. An apparatus providing reachability to an identified destination device, the apparatus comprising:

a device interface circuit configured for receiving, via a wireless data link, a first message requesting reachability to the identified destination device via an identified target device class; and

a processor circuit configured for generating, in response to the first message, a destination advertisement message in response to the apparatus, as a border router device, belonging to the target device class, the processor circuit further configured for causing the device interface circuit to output the destination advertisement message via the wireless data link for delivery to an originator device of the first message, the destination advertisement specifying the identified destination device is reachable.

20. The apparatus of claim 19, wherein:

the first message further specifies one or more constraints required for a target device of the target device class, including at least one of a first latency cost for transmission of a data packet from the originator device to the target device, a second latency cost for transmission of the data packet from the target device to the identified destination device via a backbone network, or a first path a total latency cost for transmission of the data packet from the originator device to the identified destination device via the target device;

the processor circuit configured for generating the destination advertisement message based on determining the constraints required for the target device can be guaranteed by the apparatus.

21. The apparatus of claim 19, wherein the processor circuit is configured for inserting, into the destination advertisement message, at least one of a border router device identifier indicating the identified destination device is reachable via the apparatus, first path metrics describing propagation characteristics of a path of the first message from the originator device to the apparatus via a wireless network, or second path metrics describing propagation characteristics for the apparatus reaching the identified destination device via a backbone network.

22. The apparatus of claim 19, wherein:

the device interface circuit is configured for receiving a data packet originated by the originator device via the wireless data link and destined for the identified destination device;

the processor circuit configured for selectively causing the device interface circuit to forward the data packet to the identified destination device, via a backbone network, based on a determined absence of any other border router device in the backbone network having already forwarded the data packet to the identified destination device.

23. The apparatus of claim 22, wherein:

the data packet is received by the device interface circuit via the wireless data link from a first wireless network device;

the device interface circuit further configured for receiving a copy of the data packet via a second wireless data link from a second wireless network device and destined for the identified destination device;

the processor circuit configured for dropping the copy of the data packet from transmission to the identified destination device, based on determining the data packet has already been forwarded to the identified destination device.

24. One or more non-transitory tangible media encoded with logic for execution by a machine and when executed by the machine operable for:

receiving, via a wireless data link by a border router device providing reachability to an identified destination device, a first message requesting reachability to the identified destination device via an identified target device class;

generating, by the border router device in response to the first message, a destination advertisement message in response to the border router device belonging to the target device class; and

outputting, by the border router device, the destination advertisement message via the wireless data link for delivery to an originator device of the first message, the destination advertisement specifying the identified destination device is reachable.