Flood-and-forward routing for broadcast packets in packet switching networks

• US 5,056,085 A
• Filed: 08/09/1989
• Issued: 10/08/1991
• Est. Priority Date: 08/09/1989
• Status: Expired due to Term

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Vu, Thu V.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/391,197
• Time in Patent Office: 790 Days
• Field of Search: 370/60, 370/60.1, 370/94.1, 370/94.2, 370/94.3, 370/85.13, 370/85.14
• US Class Current: 370/400
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• 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/16 Multipoint routing
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A routing algorithm for broadcast packets in packet switching networks, utilizing a "flood-and-forward" technique. In such networks, data are often transmitted in grat quantities from a sensor node to all other nodes in the network, or in a subnetwork, over point-to-point links. Existing broadcast routing algorithms, including multidestination addressing, constrained flooding, minimum spanning tree forwarding, and reverse path forwarding, suffer from an excessive use of bandwidth, a poor choice of routes, or a costly need for memory or computing power. In flood-and-forward routing, periodically a data packet is designated as a Scout packet and is transmitted in a constrained flood broadcast transmission. The Scout packet is identified by a Source Id and a Scout Label. Each receiving node sends a Ack Scout packet to the node from which it first receives a particular Scout packet, acknowledging receipt of that packet. Each relaying node keeps a log of nodes from which it has received Ack Scout packets and sends subsequent, non-scout packets to those same nodes. This flood-and-forward broadcast routing algorithm thus offers the best selection of routes, as in constrained flooding, and the least consumption of bandwidth, as in minimum spanning tree forwarding, while keeping the overhead cost of storage and processing to a low level. With the support of a reliable link service, the algorithm performs well in delivering critical data to all reachable destinations despite to-be-expected losses of packets, links, or nodes.

Claims

1. In a communication network having a plurality of communication nodes including at least one source node and a plurality of receiving nodes, the source node transmitting data packets to all the receiving nodes in a broadcast transmission mode, a method of operation comprising:

(a) at the source node, periodically designating one of the data packets as a scout packet for establishing broadcast routes to the receiving nodes;

incorporating into the scout packet a source identification, indicative of the identification of the source node, and a scout label, indicative of the particular scout packet;

transmitting that scout packet to all the receiving nodes in a constrained flood broadcast transmission; and

initiating a first time interval having a predetermined duration for receipt of acknowledgements of receipt of the scout packet;

(b) at each receiving node, maintaining a constraint table of the source identifications and scout labels of received scout packets and a broadcast routing table for received scout packets, said broadcast routing table being indexed by source identifications and scout labels;

receiving the transmitted scout packet;

determining whether the source identification and scout label of the received scout packet are in the constraint table;

if the source identification and scout label of the received scout packet are in the constraint table, then discarding the scout packet; and

if the source identification and scout label of the received scout packet are not in the constraint table, then (1) transmitting an acknowledgement of the scout packet to the node from which the scout packet was received, (2) transmitting the scout packet to other receiving nodes in accordance with the constrained flood broadcast transmission, (3) initiating a second time interval having a predetermined duration for receipt of acknowledgements of receipt of the scout packet by said other receiving nodes, (4) recording the source identification and scout label of the scout packet in the constraint table, and (5) recording in a "received column" in the broadcast routing table the identification of the node from which the scout packet was received, and (6) recording in a "send to" column in the broadcast routing table the identification of the other receiving nodes from which an acknowledgement of receipt of the scout packet is received during the second time interval;

(c) at the source node, receiving acknowledgements of receipt of transmitted scout packets;

incorporating into non-scout data packets the source identification and scout label of the scout packet for which the first time interval has most recently expired; and

transmitting the non-scout data packets to those nodes from which an acknowledgement has been received of receipt of the scout packet having the source identification and scout label that are incorporated into such non-scout data packet; and

(d) at each receiving node, receiving non-scout data packets;

determining whether the "received from" column of the broadcast routing table has recorded therein as the node from which said receiving node received the scout packet having the same source identification and scout label as are incorporated in the received non-scout data packet the identification of the node from which said each receiving node received the non-scout-data packet;

if the "received from" column of the broadcast routing table has recorded as the node from which said receiving node received the scout packet having the same source identification and scout label as are incorporated in the received non-scout data packet the node from which the receiving node received the non-scout data packet, then transmitting the non-scout data packet to those receiving nodes recorded in the "send to" column of the broadcast routing table for that scout packet; and

if the "received from" column of the broadcast routing table does not have recorded as the node from which said receiving node received the scout packet having the same source identification and scout label as are incorporated in the received non-scout data packet the node from which the receiving node received the non-scout data packet, then discarding the non-scout data packet.

2. A method as claimed in claim 1, wherein each receiving node initiates the second time interval to have a time substantially equal to the longest round trip transmission time between the receiving node and the other receiving nodes to which said receiving node transmits the scout packet.

3. A method as claimed in claim 1, wherein each receiving node transmits the source identification and scout label of the received scout packet as the acknowledgement.