Systems and methods for efficient packet distribution in an ad hoc network

• US 7,369,512 B1
• Filed: 11/06/2003
• Issued: 05/06/2008
• Est. Priority Date: 11/06/2003
• Status: Expired due to Fees

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: BBN Technologies (Rtx Corporation)
• Inventors: Redi, Jason Keith, Shurbanov, Vladimir Alexandrov
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): Cho; Hong Sol
• Application Number:
  US10/702,308
• Time in Patent Office: 1,643 Days
• Field of Search: 370/229, 370254-256, 370/389, 370/390, 370/392, 370/400, 370/401
• US Class Current: 370/254
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A system provides packet flooding in a network (200) that includes multiple nodes (210). The system may receive a flood packet, select one or more of the nodes (210) as a like number of one or more relays (210), and attach a header to the flood packet. The header may instruct the one or more relays (210) to which of the nodes (210) to send the flood packet. The system may send the flood packet with the attached header to the one or more relays (210). The one or more relays (210) may retransmit the packet such that each of the nodes (210) in the network (200) receives a single copy of the flood packet.

Claims

1. A method for packet flooding in a network including a plurality of nodes, comprising:

generating a flood packet;

selecting one or more of the nodes as a like number of one or more relays to form a first relay configuration;

identifying a difference between the first relay configuration and a second relay configuration;

comparing the difference between the first relay configuration and the second relay configuration to a threshold;

updating the second relay configuration with the first relay configuration when the difference is above the threshold;

attaching a header to the flood packet, the header instructing the one or more relays to which of the nodes to send the flood packet; and

sending the flood packet with the attached header to the one or more relays.

2. The method of claim 1, wherein the selecting one or more of the nodes as a like number of one or more relays includes:

building a minimum spanning tree that covers an n-hop neighborhood of one of the nodes that generated the flood packet, and

using the minimum spanning tree to identify the one or more relays.

3. The method of claim 1, wherein the attaching a header to the flood packet includes forming the header based at least in part on the first relay configuration.

4. The method of claim 1, further comprising:

setting a transmission power for the flood packet with the attached header based on a location of the one or more relays.

5. The method of claim 4, wherein the setting a transmission power includes determining the transmission power based at least in part on a distance to a farthest one of the one or more relays.

6. The method of claim 1, further comprising:

receiving the flood packet with the attached header at one of the one or more relays as a receiving relay;

extracting the attached header; and

retransmitting the flood packet from the receiving relay to one or more other ones of the nodes.

7. The method of claim 6, wherein the retransmitting the flood packet with the attached header includes duplicating the flood packet.

8. The method of claim 6, wherein the retransmitting the flood packet with the attached header includes:

identifying one or more other nodes as one or more additional relays, and sending the flood packet with the attached header to the one or more additional relays.

9. The method of claim 1, wherein the sending the flood packet with the attached header includes:

transmitting the flood packet as a unicast transmission.

10. The method of claim 1, wherein the sending the flood packet with the attached header includes:

transmitting the flood packet as a broadcast transmission.

11. A system for flooding packets in a network that includes a plurality of nodes, comprising:

means for receiving a flood packet;

means for identifying one or more of the nodes as a like number of one or more relays to form a first relay configuration;

means for identifying a difference between the first relay configuration and a second relay configuration;

means for comparing the difference between the first relay configuration and the second relay configuration to a threshold;

means for updating the second relay configuration with the first relay configuration when the difference is above the threshold;

means for sending the flood packet to the one or more relays; and

means for retransmitting the flood packets from the one or more relays such that each of the nodes in the network receives one copy of the flood packet.

12. A system for flooding packets in a network that includes a plurality of nodes, comprising:

a flooding module configured to;

receive a flood packet,

select one or more of the nodes as a like number of one or more relays to form a first relay configuration,

identify a difference between the first relay configuration and a second relay configuration,

compare the difference between the first relay configuration and the second relay configuration to a threshold,

update the second relay configuration with the first relay configuration when the difference is above the threshold,

attach a header to the flood packet, the header instructing the one or more relays to which of the nodes to send the flood packet; and

a forwarding module configured to;

send the flood packet with the attached header to the one or more relays.

13. The system of claim 12, further comprising at least one of a directional antenna and an omni-directional antenna.

14. The system of claim 12, wherein the flooding module is configured to:

build a minimum spanning tree that covers an n-hop neighborhood of one of the nodes that generated the flood packet, and

identify the one or more relays based at least in part on the minimum spanning tree.

15. The system of claim 12, wherein the header is formed based at least in part on the first relay configuration.

16. The system of claim 12, wherein the flooding module is further configured to set a transmission power for the flood packet with the attached header based on a location of the one or more relays.

17. The system of claim 16, wherein when setting a transmission power, the flooding module is configured to determine the transmission power based at least in part on a distance to a farthest one of the one or more relays.

18. The system of claim 12, wherein the forwarding module is configured to transmit the flood packet with the attached header as a unicast transmission.

19. The system of claim 12, wherein the forwarding module is configured to transmit the flood packet with the attached header as a broadcast transmission.