Backpressure with adaptive redundancy

Patent metadata

Field	Value
Publication number	US-9444751-B1
Application number	US-201313956143-A
Country	US
Kind code	B1
Filing date	Jul 31, 2013
Priority date	Aug 3, 2012
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

Routing technologies are disclosed. A described technology includes routing packets through a network based on backpressure scheduling; when a number of packets in a transmitter queue satisfies a first threshold, retaining copies of at least a portion of the packets; and once the number of packets in the transmitter queue satisfies a second threshold, transmitting the retained copies of the packets to perform the routing. Retaining the copies can include copying a packet from the transmitter queue into a duplicate buffer when the number of packets in the transmitter queue is below the first threshold.

First claim

What is claimed is:

1. A method comprising:
routing, at a node comprising hardware, packets through a network based on backpressure scheduling, wherein the node comprises a transmitter queue and a duplicate buffer;
when a number of packets in the transmitter queue satisfies a first threshold, retaining copies of at least a portion of the packets, wherein each of the retained copies comprises data that need to be forwarded through the network to a destination, and wherein each of the retained copies is a packet copied from the transmitter queue into the duplicate buffer when the number of packets in the transmitter queue is below the first threshold, wherein retaining the copies comprises copying the packet from the transmitter queue into the duplicate buffer when the number of packets in the transmitter queue is below the first threshold upon transmission of the packet from the transmitter queue; and
once the number of packets in the transmitter queue satisfies a second threshold, transmitting the retained copies of the packets to perform the routing, wherein the second threshold is a predefined number of packets in the transmitter queue.

2. The method of claim 1 , wherein the network comprises an intermittently connected mobile network, and the backpressure scheduling comprises a store-and-forward protocol in which transmission decisions for the packets are based on queue differentials between the node and target recipient nodes.

3. The method of claim 1 , wherein the node comprises a plurality of transmitter queues and a plurality of duplicate buffers, with a pair of each corresponding to a different destination or flow, the first threshold comprises a first set of predefined thresholds for the plurality of transmitter queues, and the second threshold comprises a second set of predefined thresholds for the plurality of transmitter queues.

4. The method of claim 1 , wherein the predefined number of packets is zero packets in the transmitter queue, and wherein the second threshold is satisfied when the number of packets in the transmitter queue is zero.

5. The method of claim 1 , wherein a size of the duplicate buffer and the first threshold are each set to a value corresponding to a maximum link service rate in the network.

6. The method of claim 1 , comprising:
removing a retained copy of the retained copies from the duplicate buffer once a notification of receipt by a destination node is received.

7. The method of claim 1 , comprising:
giving higher priority to packets whose next hop node is their final destination in the network.

8. The method of claim 1 , the method comprising:
when a timeout criterion is met, removing the retained copies of the packets.

9. The method of claim 8 , comprising:
modifying the timeout criterion in accordance with feedback obtained from notifications of packet receptions, delay of delivered packets, or other congestion signals from the network.

10. The method of claim 1 , comprising:
for each packet of the packets to have a copy retained, checking that a total number of copies of the each packet is bounded by a constant.

11. The method of claim 10 , wherein the constant is adjustable to tune a tradeoff between energy and delay.

12. An apparatus comprising:
a memory comprising a transmitter queue and a duplicate buffer; and
a processor configured to perform operations comprising:
routing packets through a network based on backpressure scheduling;
when a number of packets in the transmitter queue satisfies a first threshold, retaining copies of at least a portion of the packets, wherein each of the retained copies comprises data that need to be forwarded through the network to a destination, and wherein each of the retained copies is a packet copied from the transmitter queue into the duplicate buffer when the number of packets in the transmitter queue is below the first threshold, wherein retaining the copies comprises copying the packet from the transmitter queue into the duplicate buffer when the number of packets in the transmitter queue is below the first threshold upon transmission of the packet from the transmitter queue; and
once the number of packets in the transmitter queue satisfies a second threshold, transmitting the retained copies of the packets to perform the routing, wherein the second threshold is a predefined number of packets in the transmitter queue.

13. The apparatus of claim 12 , wherein the network comprises an intermittently connected mobile network, and the backpressure scheduling comprises a store-and-forward protocol in which transmission decisions for the packets are based on queue differentials between the apparatus and target recipient nodes.

14. The apparatus of claim 12 , wherein the memory comprises a plurality of transmitter queues and a plurality of duplicate buffers, with a pair of each corresponding to a different destination or flow, the first threshold comprises a first set of predefined thresholds for the plurality of transmitter queues, and the second threshold comprises a second set of predefined thresholds for the plurality of transmitter queues.

15. The apparatus of claim 12 , wherein the predefined number of packets is zero packets in the transmitter queue, and wherein the second threshold is satisfied when the number of packets in the transmitter queue is zero.

16. The apparatus of claim 12 , wherein a size of the duplicate buffer and the first threshold are each set to a value corresponding to a maximum link service rate in the network.

17. The apparatus of claim 12 , wherein the operations comprise:
removing a retained copy of the retained copies from the duplicate buffer once a notification of receipt by a destination node is received.

18. The apparatus of claim 12 , wherein the operations comprise:
giving higher priority to packets whose next hop node is their final destination in the network.

19. The apparatus of claim 12 , wherein the operations comprise:
when a timeout criterion is met, removing the copies of the packets.

20. The apparatus of claim 19 , wherein the operations comprise:
modifying the timeout criterion in accordance with feedback obtained from notifications of packet receptions, delay of delivered packets, or other congestion signals from the network.

21. The apparatus of claim 12 , wherein the operations comprise:
for each packet of the packets to have a copy retained, checking that a total number of copies of the each packet is bounded by a constant.

22. The apparatus of claim 21 , wherein the constant is adjustable to tune a tradeoff between energy and delay.

23. A system comprising:
multiple intermittently connected mobile devices forming an intermittently connected mobile network,
wherein a mobile device in the network comprises a processor and a memory, and
wherein the memory stores a program configured to cause the processor to (i) route packets through the network based on backpressure scheduling using a transmitter queue, (ii) retain copies of at least a portion of the packets when a number of packets in the transmitter queue satisfies a first threshold, each of the retained copies comprising data that need to be forwarded through the network to a destination, each of the retained copies being a packet copied from the transmitter queue into a duplicate buffer when the number of packets in the transmitter queue is below the first threshold upon transmission of the packet from the transmitter queue, and (iii) transmit the re

Assignees

• Univ Southern California

Inventors

• Alresaini Majed
• Krishnamachari Bhaskar
• Neely Michael J

Classifications

• H04L47/30 Primary

  in combination with information about buffer occupancy at either end or at transit nodes · CPC title

• H04L49/9084

  Reactions to storage capacity overflow · CPC title

• H04L47/2458

  Modification of priorities while in transit · CPC title

• H04L45/32

  Flooding (denial of service attacks H04L63/1458) · CPC title