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

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.