United States Patent [19]
`United States Patent [191
`Vu
`Vu
`
`[i i] Patent Number:
`[11] Patent Number:
`[45] Date of Patent:
`[45] Date of Patent:
`
`5,056,085
`5,056,085
`Oct. 8, 1991
`Oct. 8, 1991
`
`[56]
`[56]
`
`[54] FLOOD-AND-FORWARD ROUTING FOR
`[54] FLOOD-AND-FORWARD ROUTING FOR
`BROADCAST PACKETS IN PACKET
`BROADCAST PACKETS IN PACKET
`SWITCHING NETWORKS
`SWITCHING NETWORKS
`[75] Inventor:
`Inventor: Thu V. Vu, West Melbourne, Fla.
`[75]
`Thu V. Vu, West Melbourne, Fla.
`[73] Assignee:
`[73] Assignee: Harris Corporation, Melbourne, Fla.
`Harris Corporation, Melbourne, Fla.
`[21] Appl. No.: 391,197
`[21] Appl. No.: 391,197
`[22] Filed:
`Aug. 9, 1989
`[22] Filed:
`Aug. 9, 1989
`H04Q 11/04
`[51] Int. CI.5
`[51] Int. c1.5 ........................................... .. 11040 11/04
`[52] U.S. CI.
`370/60; 370/94.1
`[52] 05.0. .................................... .. 370/60; 370/941
`[58] Field of Search
`370/60, 60.1, 94.1,
`[58] Field of Search ..................... .. 370/60, 60.1, 94.1,
`370/94.2, 94.3, 85.13, 85.14
`370/942, 94.3, 85.13, 85.14
`References Cited
`References Cited
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`al.
`4,399.531 8/1983 Grande et
`.. 370/60
`4,399.53l 8/1983 Grande et al. ...................... .. 370/60
`370/94.1
`4,905,233 2/1990 Cain et al
`4,905,233 2/1990 Cain et al. ........................ .. 370/94.1
`OTHER PUBLICATIONS
`OTHER PUBLICATIONS
`Computer Networks, by Andrew S. Tananbaum, Pren­
`Computer Networks, by Andrew S. Tananbaum, Pren
`tice Hall, Englewood Cliffs, N.J., 1981.
`tice Hall, Englewood Cliffs, N.J., 1981.
`"Reverse Path Forwarding of Broadcast Packets," Y.
`“Reverse Path Forwarding of Broadcast Packets,” Y.
`K. Dalai and R. M. Metcalf, Communications of the
`K. Dalal and R. M. Metcalf, Communications of the
`ACM, vol. 21, pp. 1040-1048, Dec. 1978.
`ACM vol. 21, pp. 1040-1048, Dec. 1978.
`Primary Examiner-Douglas W. Olms
`Primary Examiner—Douglas W. Olms
`Assistant Examiner—Wellington Chin
`Assistant Examiner-Wellington Chin
`Attorney, Agent, or Firm—Antonelli, Terry,
`Stout
`Attorney, Agent, or Firm-Antonelli, Terry, Stout &
`Kraus
`Kraus
`_
`[57]
`ABSTRACT
`[57]
`ABSTRACT
`A routing algorithm for broadcast packets in packet
`A routing algorithm for broadcast packets in packet
`
`switching networks, utilizing a "flood-and-forward"
`switching networks, utilizing a “?ood-and-forward"
`technique. In such networks, data
`are
`
`often transmitted
`technique. In such networks, data are often transmitted
`in grat quantities from a sensor node to all other nodes
`in grat quantities from a sensor node to all other nodes
`in the network, or
`
`in a subnetwork, over
`point-to-point
`in the network, or in a subnetwork, over point-to-point
`links. Existing broadcast routing algorithms, including
`links. Existing broadcast routing algorithms, including
`multidestination addressing,
`
`constrained flooding, mini­
`multidestination addressing, constrained ?ooding, mini
`mum spanning tree forwarding, and reverse path for­
`mum spanning tree forwarding, and reverse path for
`warding, suffer from an excessive use of bandwidth, a
`warding, suffer from an excessive use of bandwidth, a
`poor choice of routes, or a costly need for memory or
`poor choice of routes, or a costly need for memory or
`computing power. In flood-and-forward routing, peri­
`computing power. In ?ood-and-forward routing, peri
`odically a data packet is designated as a Scout packet
`odically a data packet is designated as a Scout packet
`and is transmitted in a constrained flood broadcast
`and is transmitted in a constrained flood broadcast
`transmission. The
`Scout
`packet
`
`is identified by a Source
`transmission. The Scout packet is identi?ed by a Source
`Id and a Scout Label. Each receiving node
`sends
`Id and a Scout Label. Each receiving node sends a Ack
`Scout packet to the node
`from which it first receives a
`Scout packet to the node from which it ?rst receives a
`particular Scout packet, acknowledging receipt of that
`particular Scout packet, acknowledging receipt of that
`packet. Each relaying node keeps a log of nodes from
`packet. Each relaying node keeps a log of nodes from
`which it has received Ack Scout packets and sends
`which it has received Ack Scout packets and sends
`subsequent, non-scout packets
`
`to same nodes. This those
`
`subsequent, non-scout packets to those same nodes. This
`flood-and-forward broadcast routing algorithm thus
`?ood-and-forward broadcast routing algorithm thus
`offers the best selection of routes, as in constrained
`offers the best selection of routes, as in constrained
`flooding, and
`the least consumption of bandwidth, as
`?ooding, and the least consumption of bandwidth, as in
`minimum spanning tree forwarding, while keeping the
`minimum spanning tree forwarding, while keeping the
`to
`overhead cost of storage and processing
`overhead cost of storage and processing to a low level.
`With the support of a reliable link service,
`the algorithm
`With the support of a reliable link service, the algorithm
`performs well
`in delivering
`
`
`data critical all reachable
`performs well in delivering critical data to all reachable
`destinations despite to-be-expected losses of packets,
`destinations despite to-be-expected losses of packets,
`&
`links, or nodes.
`links, or nodes.
`
`in
`
`a
`
`a
`
`Ack
`
`low
`
`to
`
`3 Claims, 10 Drawing Sheets
`3 Claims, 10 Drawing Sheets
`
`TRANSMITTING NODE
`TRANSMITTING NODE
`
`RECEIVING NODE
`RECEIVING NODE
`
`DESIGNATE A
`SCOUT PACKET WITH
`/
`DESIGNATE A SCOUT PACKET WITH
`/
`SOURCE IDENTIFICATION AND SCOUT X
`SOURCE IDENTIFICATION AND SCOUT /
`LABLE
`LABLE
`I
`I
`f?
`£*
`TRANSMIT SCOUT PACKET IN C0N-
`TRANSMIT SCOUT PACKET IN CON- ___ ___.
`STRA1NED FLOOD
`STRAIN
`FLOOD
`
`/0
`/0\ mscarw
`DISCARD *
`J
`3'\
`DETERMINE WHETHER THIS SCOUT
`DETERMINE WHETHER THIS SCOUT
`PACKET HAS BEEN RECEIVED
`PACKET HAS BEEN RECEIVED
`PREVIOUSLY
`PREVIOUSLY
`
`YES
`YES
`
`NO
`NO
`b~
`y-
`
`LOG IN CONSTRAINT TABLE
`LOG IN CONSTRAINT TABLE
`
`SEND ACKNOWLEDGEMENT
`SEND ACKNOWLEDGEMENT
`
`RECORD IN RECEIVED FROM
`RECORD IN RECEIVED FROM
`COLUMN OF BROADCAST
`ROUTING
`COLUMN OF BROADCAST ROUTING
`TABLE
`TABLE
`
`TRANSMIT TO
`ALL NODES EXCEPT
`TRANSMIT TO ALL NODES EXCEPT
`THE NODE FROM WHICH RECEIVED
`THE NODE FROM WHICH RECEIVED
`
`9 C - 4
`f9
`PASS TO NEXT HIGHER LAYER
`4\L PASS TO NEXT HIGHER LAYER
`5
`
`r//
`
`X
`SET ACKNOWLEDGEMENT TIMER
`SET ACKNOWLEDGEMENT TIMER
`I
`t
`INHIBIT
`INHIBIT
`RECORD IN
`SEND TO COLUMN OF
`RECORD IN SEND E COLUMN 0F 4- - — _ ‘
`4 '
`BROADCAST ROUTING TABLE
`BROADCAST ROUTING TABLE
`±
`TRANSMIT REGULAR BROADCAST
`TRANSMIT REGULAR BROADCAST
`PACKETS TO NODES RECORDED IN
`PACKETS TO NODES RECORDED IN
`SEND TO COLUMN OF BROADCAST
`SEND TO COLUMN OF BROADCAST
`ROUTING TABLE
`— ROUTING TABLE
`
`7
`
`8
`
`BUNGIE - EXHIBIT 1030
`
`

`

`V s - P a t
`
` e n t
`
`US. Patent
`US. Patent
`
`Q c t - 8 » 1 9 9 1
`Oct. 8, 1991
`Oct. 8, 1991
`
` 1 o f
` 1 0
`S h e e t
`Sheet 1 of 10
`Sheet 1 of 10
`
`S > 0 5 6 , 0 8 5
`
`5,056,085
`5,056,085
`
`\
`\
`
`/
`/
`
`\
`\
`
`/
`/
`
`I F
`
`\
`\ y
`
`/
`
`
`
`/
`
`
`
`/
`
`/
`
`/
`
`
`
`\
`\
`
`IG.
`
`C D
`
`c:
`
`

`

`U.S. Patent
`. US. Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 2 of 10
`Sheet 2 of 10
`
`5,056,085
`5,056,085
`
`%
`
`.V
`•J-
`<3I_
`
`'T •<+
`
`R
`
`FIG. 2
`
`«
`
`fe
`
`%
`
`>
`•o.
`
`FIG. 3A
`
`\
`
`7
`
`tw
`
`•YV y.
`
`I
`
`• T t
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 3 of 10
`Sheet 3 of 10
`
`5,056,085
`5,056,085
`
`y
`
`i
`r
`t
`r
`i
`
`i
`T t
`
`i
`
`i—i i
`
`I
`
`JTJ
`
`4
`
`J
`
`I
`
`FIG. 3B
`FIG. 3B
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 4 of 10
`Sheet 4 of 10
`
`5,056,085
`5,056,085
`
`PROCEDURE GENERATE.BROADCAST(DATA_UNIT) IS
`PROCEDURE GENERATE_BROADCAST(DATA_UNIT) IS
`BEGIN
`BEGIN
`IF (CURRENT.TIME > SCOUT_LAST_SENT_TIME + NON_FLOOD_PERIOD) THEN
`IF (CURRENT_TIME > SCOUT_LAST_SENT_TIME + NON_FLOOD_PERIOD) THEN
`— IT'S TIME TO SEND A SCOUT PACKET
`-— IT'S TIME TO SEND A SCOUT PACKET
`GENERATE.FLOOD.BROADCAST(SCOUT_LABEL,DATA.UNIT);
`GENERATE_FLOOD_BROADCAST(SCOUT_LABEL,DATA_UNIT) ;
`SCOUT_LAST.SENT_TIME :« CURRENT.TIME;
`SCOUT_LAST_SENT_TIME :8 CURRENT_TIME;
`INCREMENT.SCOUT.UIBEL;
`INCREMENT_SCOUT_LABEL;
`ELSE IF (CURRENT.TIME > ROUTES_LAST_UPDATED_TIME + ROUTES_LIFE) THEN
`ELSE IF (CURRENT_TIME > ROUTES_LAST_UPDATED_TIME 4- ROUTES_LIFE) THEN
`— ROUTES ARE NOT UP TO DATE
`—- ROUTES ARE NOT UP TO DATE
`PUT.PACKETS.ON.HOliD(DATA.UNIT) ;
`PUT_PACKETS_ON_HOLD(DATA_UNIT) i
`ELSE
`ELSE
`— USE BROADCAST ROUTING TABLES
`—- USE BROADCAST ROUTING TABLES
`GENERATE.NON.FLOOD.BROADCAST(CURRENT_ROUTES,DATA.UNIT);
`GENERATE_NON_FLOOD_BROADCAST(CURRENT_ROUTES,DATA_UNIT) ;
`END IF;
`END IF;
`END GENERATE.BROADCAST;
`END GENERATE_BROADCAST;
`
`FIG. 4
`FIG. 4
`
`PROCEDURE PROPAGATE_FLOOD_BROADCAST(SCOUT.PACKET,LINK.ARRIVED.ON) IS
`PROCEDURE PROPAGATE_FLOOD_BROADCAST(SCOUT_PACKET,LINK_ARRIVED_ON) IS
`BEGIN
`BEGIN
`NOT.VET_SEEN :- CHECK.CONSTRAINT.TABLE(SCOUT.PACKET);
`NOT_YET_SEEN :8 CHEC1<_CONSTRAINT_TABLE_(SCOUT_PACKET) ;
`IF (NOT.YET.SEEN) THEN
`IF (NOT_YET_SEEN) THEN
`ACCEPT_AND_LOG_PACKET(SCOUT.PACKET);
`ACCEPT_AND_LOG_PACKET(SCOUT_PACKET) ;
`— FORWARD SCOUT PACKET
`-- FORWARD SCOUT PACKET
`.
`FORWARD.LINKS
`ALL.LINKS - LINK.ARRIVED.ON;
`FORWARD_LINKS :II. ALL_LINKS - LINK_ARRIVED_ON;
`FORWARD_PACKET(SCOUT.PACKET,FORWARD.LINKS);
`FORWARD_PACKET(SCOUT_PACKET,FORWARD_LINKS) ;
`-- SET UP MECHANISM FOR EXTRACTING ROUTES FROM SCOUT PACKET
`-- SET UP MECHANISM FOR EXTRACTING ROUTES FROM SCOUT PACKET
`SOURCE.ID :- SCOUT.PACKET.SOURCE.ID;
`SOURCE_ID :- SCOUT_FACKET.SOURCE_ID;
`SCOUT.LABEL
`SCOUT.PACKET.SCOUT.LABEL;
`SCOUT_LABEL :- SCOUT_PACKET.SCOUT_LABEL;
`ACK_SCOUT_TIMER(SOURCE.ID,SCOUT.LABEL) :» CURRENT.TIME +
`ACK_SCOUT_TIMER(SOURCE_ID,SCOUT_LABEL) :- CURRENT_TIME +
`ACK.SCOUT.PERIOD;
`ACK_SCOUT_PERIOD;
`.
`BROADCAST.ROUTING.TABLE(SOURCE.ID,SCOUT.LABEL).SEND.TO :» NULL;
`BROADCAST_ROUTING_TABLE(SOURCE_ID,SCOUT_LABEL) .SEND_T :8 NULL;
`BROADCAST.ROUTING.TABLE(SOURCE.ID,SCOUT.LABEL).RECEIVED.FROM
`BROADCAST_ROUTING_TABLE(SOURCE_ID,SCOUT_LABEL) .RECEIVED_FROM :'
`LINK.ARRIVED.ON;
`LINK_ARRIVED_ON;
`— SEND ACK SCOUT PACKET
`—- SEND ACK SCOUT PACKET
`PREPARE.ACK.SCOUT.PACKET(SOURCE.ID,SCOUT.LABEL,ACK.SCOUT.PACKET);
`PREPARE_ACK_SCOUT_PACKET(SOURCE_ID,SCOUT_LABEL,ACK_SCOUT_PACKET) ;
`FORWARD.LINKS :- LINK.ARRIVED.ON;
`FORWARD_LINKS :- LINK_ARRIVED_ON;
`FORWARD_PACKET(ACK_SCOUT_PACKET,FORWARD.LINKS);
`FORWARILPACKET(ACK_SCOUT_PACKET,FORWARD_LINKS) ;
`END IF;
`END IF;
`'
`END PROPAGATE.FLOOD.BROADCAST;
`END PROPAGATE_FLOOD_DROADCASTi
`
`'
`
`FIG.5
`FIG.5
`
`

`

`U.S. Patent
`us. Patent
`
`Oct. 8, 1991
`05.51991 '
`
`Sheet 5 of 10
`sheet 5 of 10
`
`5,056,085
`5,056,085
`
`I S
`PROCEDURE GENERATE_rLOOD_BROADCAST(SCOUT.LABEL,DATA.UNIT)
`PROCEDURE GENERATE_FLOOD_BROADCAST(SCOUT_LABEL,DATA;UNIT) IS
`BEGIN
`BEGIN
`OWN.ID;
`SOURCE_ID
`SOURCE_ID :- OWN_ID;
`PREPARE.SCOUT_PACKET(SOURCE.ID,SCOUT.LABEL,DATA.UNIT,SCOUT.PACKET);
`PREPARE_SCOUT_PACKET(SOURCE_ID,SCOUT_LABEL,DATA_UNIT,SCOUT_PACKET) ;
`FORWARD.LINKS :> ALL.LINKS;
`FORWARD_LINKS :8 ALL_LINKS;
`>
`FORWARD.PACKET(SCOUT.PACKET,FORWARD.LINKS);
`FORWARD_PACKET(SCOUT_PACKET,FORWARD_LINKS) ;
`-- SET UP KECHAMZSM FOR EXTRACTING ROUTES FROM SCOUT PACKET
`—- SET UP MECHANISM FOR EXTRACTING ROUTES FROM SCOUT PACKET
`ACK_SCOUT_TIMER(SOURCE.ID,SCOUT.LABEL) :« CURRENT.TIME +
`ACK_SCOUT_TIMER(SOURCE_ID,SCOUT_LABEL) :- CURRENT_TIME +
`ACK.SCOUT.PERIOD;
`ACK_SCOUT_PERIOD;
`NULL;
`BROADCAST.ROUTING.TABLE(SOURCE.ID,SCOUT.LABEL).SEND.TO
`BROADCAST_ROUTING_TABLE(SOURCE_ID,SCOUT_LABEL) .SEND_TO :- NULL;
`TIME.TO.INSTALL.ROUTES
`CURRENT.TIME + ACK.SCOUT.PERIOD;
`TIME_TO_INSTALL_ROUTES :- CURRENT_TIME + ACK_SCOUT_PERIOD;
`SCHEDULE.TIME.TO.INSTALL.ROUTES(SCOUT.LABEL);
`SCHEDULE_TIME_TO_INSTALL_ROUTES(SCOUT_LABEL) ;
`END GENERATE_7L00D_BR0ADCAST;
`END IGENERATE_ILOOD_BROADCAST;
`
`FIG. 6
`FIG.6
`
`PROCEDURE RECEIVE_ACK_SCOUT(ACK.SCOUT.PACKET,LINK.ARRIVED.ON) IS
`raocznunz RECEIVE_ACK_SCOUT(ACK_SCOiJT_PACKET,LINK_ARRIVED_ON) 1s
`BEGIN
`azcnz
`ACK_SCOUT_PACKET.SOURCE_ID;
`SOURCE.ID
`sooner-:31: =- ACK_SCOUT_PACKET.SOURCE_ID;
`SCOUT.LABEL :» ACK.SCOUT.PACKET.SCOUT.LABEL;
`SCOUTJABEL =- ACK_SCOUT_PACKET.SCOUT_LA8EL;
`IF (CURRENT.TIME <» ACK_SCOUT_TIMER(SOURCE.ID,SCOUT.LABEL)) THEN
`1r (emu-r3114: <- ACK_SCOUT_TIMER(SOURCE_ID,SCOU'I‘_LABEL) ) THEN
`BROADCAST_ROUTING_TABLE(SOURCE.ID,SCOUT.LABEL).SEND.TO :>
`BROADCAST_ROUTING_TABLE(SOURCE_ID,SCOUT_LABEL) .smm_ro =
`BROADCAST.ROUTING.TABLE(SOURCE.ID,SCOUT.LABEL).SEND.TO +
`BROADCAST_ROUTING_TABLE(SOURCE_ID,SCOU'1'_LABEL) .s1.=:m>_ro +
`LINK.ARRIVED.ON;
`1.1ux_mnrvzn_on;
`END IF;
`mm IF;
`END RECEIVE.ACK.SCOUT;
`mm RECEIVE_ACK_SCOUT;
`
`FIG.7
`FIG?
`
`PROCEDURE INSTALL_ROUTES_EVENT(SCOUT.LABEL) IS
`pnoczmmn INSTALL_ROUTES_EVBNT(SCOUT_LABEL) 1s
`BEGIN
`amen:
`CURRENT.ROUTES :« SCOUT.LABEL;
`CURRENT_ROUTES :- scan-Luau;
`ROUTES_LAST_UPDATED_TIME :» CURRENT.TIME;
`nourzs_usr_urnuzn_nnz :- CURRENT_TIME;
`— BROADCAST PACKETS WHICH WERE PUT ON HOLD BECAUSE NO ROUTES
`-- BROADCAST nexus waxca van: PUT on new news: no nou'rzs
`— WERE AVAILABLE
`-- wan: AVAILABLE
`WHILE (MORE.PACKETS.ON.HOLD) LOOP
`wan: monz_ncxxrs_on_noz.n) LOOP
`RELEASE.PACKETS.ON.HOLD(DATA.UNIT);
`RELEASE_PACXETS_ON_HOLD(DATA_UNI'1‘) ;
`GENERATE.NON.FLOOD.BROADCAST(CURRENT.ROUTES,DATA.UNIT);
`GENERA'I'E_NON_I'LOOD_BROADCAS‘I'(CURRENT_ROUTES,DATA_UNIT) ;
`END LOOP;
`END LOOP;
`END INSTALL.ROUTES.EVENT;
`mm xns-mm._noms_zvzm-;
`
`-
`
`FIG. 8
`FIGS
`
`

`

`U.S. Patent
`U.S.- Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 6 of 10
`Sheet 6 of 10
`
`5,056,085
`5,056,085
`
`PROCEDURE GENERATE_NON_FLOOD_BROADCAST(SCOUT_LABEL,DATA.UNIT)
`IS
`PROCEDURE GENERATE_NON_FLOOD_BROADCAST(SCOUT_LABEL,DATA_UNIT) IS
`BEGIN
`BEGIN
`SOURCE.ID :• OWN.ID J
`SOURCE_ID :II OWN_ID;
`PREPARE_BROADCAST_PACKET(SOURCE.ID,SCOUT.LABEL,DATA.UNIT,PACKET);
`PREPARE_BROADCAST_PACKET(SOURCE_ID,SCOUT_LABEL,DATA_UNIT,PACKET) ;
`TORWARD.LINKS :« BROADCAST.ROUTING.TABLE(SOURCE.ID,
`FORWARD_LINKS :- BROADCAST_ROUTING_TABLE(SOURCE_ID,
`SCOUT.LABEL).SEND.TO;
`SCOUT_LABEL) .SEND_TO;
`FORWARD.PACKET(PACKET,FORWARD.LINKS);
`FORWARD_PACKET(PACKET,FORWARD_LINKS) ;
`END GENERATE.NON.rLOOD.BROADCAST;
`END GENERATE_NON_I'LOOD_BROADCAST;
`
`FIG. 9
`FIG. 9
`
`PROCEDURE PROPAGATE.NON.TLOOD.BROADCAST(PACKET,LINK.ARRIVED.ON) IS
`PROCEDURE PROPAGATE_NON_I'LOOD_BROADCAST(PACKET,LINK_ARRIVED_ON) IS
`BEGIN
`BEGIN
`SOURCE.ID :« PACKET.SOURCE.ID; •
`SOURCE_ID :- PACKET.SOURCE_ID;
`SCOUT.LABEL
`PACKET.SCOUT.LABEL;
`SCOUT_LABEL :- PACKET-SCOUT_LABEL;
`IF (BROADCAST.ROUTING.TABLE(SOURCE_ID,SCOUT_LABEL).RECEIVED.FROM -
`I!‘ (BROADCAS'I'_ROUTING_TABLI(SOURCE_ID,SCOUT_LABEL) .RECEIVED_FROM I
`LINK.ARRIVED.ON) THEN
`LINK_ARRIVED_ON) THEN
`ACCEPT_PACKET{PACKET);
`ACCEPT_PACKET(PACKET) ;
`.
`TORWARD.LINKS :• BROADCAST.ROUTING.TABLE(SOURCE.ID,
`FORWARD_LINKS :8. BROADCAST_ROUTING_TABLE(SOURCE_ID,
`SCOUT.LABEL).SEND.TO;
`SCOUT_LAHEL) -SEND__'1‘O;
`FORWARD.PACKET(PACKET,TORWARD.LINKS);
`FORWARD_PACKET(PACKET,FORWARD_LINKS) ;
`END IT;
`END I1‘;
`END PROPAGATE.NON.TLOOD.BROADCAST;
`END PROPAGATE_NON_I'LOOD_BROADCAST;
`
`FIG. 10
`FIG. IO
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 7 of 10
`Sheet 7 of 10
`
`5,056,085
`5,056,085
`
`5 O 1
`100-
`
`80-
`
`GO
`
`PERCENTAGE OF LINKS
`
`60-
`03 O 1
`Ll_
`o
`UJ
`o
`^40-
`z
`UJ
`o
`520-
`N o l
`
`QL
`
`—FLOOD-AND-FORWARD
`——FLOOD—AND—FORWARD
`—CONSTRAINED FLOODING
`—I—CONSTRAINED FLOODING
`
`I
`/
`/
`/
`
`S y
`
`/
`
`f
`
`J
`
`f
`/
`/
`
`J
`s
`/
`/
`/
`y'
`
`0-K
`T
`I
`T
`T
`T
`T
`T
`T
`T
`I
`.
`no
`0.0 Oil
`o.'2 0T3 0.4 0.5 0:6 0:7 0T8 0T9 |.o
`0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
`BANDWIDTH CONSUMPTION
`BANDWIDTH CONSUMPTION
`FIG. II
`
`100-
`
`— FLOOD-AND-FORWARD
`-—- FLOOD-AND-FORWARD
`— CONSTRAINED FLOODING
`—-CONSTRAINED FLOODING
`
`60-
`m 0 1
`
`PERCENTAGE OF PACKETS
`
`CO
`(D o l
`f- 80-
`UJ
`o
`<1
`Q_
`&
`UJ
`o
`^ 40-
`UJ
`o
`cr
`UJ 20-
`8
`D.
`
`/
`/
`
`/
`/
`/
`/
`/
`/
`/
`
`/
`/
`/
`/
`/
`•
`
`/
`
`0
`!
`I
`o
`0.14
`0.12
`0J2 0.l4
`
`J
`I
`l
`I
`1
`I
`I
`l
`I
`I
`I
`I
`0.26 0.28 0.30
`0.18 0.20 0.22 0.24
`0.16
`0.26 0.28
`0.30
`0.l8
`0.20 0.22 0.24
`0.l6
`END-TO-END DELAY (SEC)
`END-TO- END DELAY (SEC)
`FIG.12
`FIG.|2
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 8, 1991
`0a. 8,1991
`
`Sheet 8 of 10
`Sheet 8 of 10
`
`5,056,085
`5,056,085
`
`100-
`
`— FLOOD-AND-FORWARD
`---—— FLOOD-AND-FORWARD
`— CONSTRAINED FLOODING
`——- CONSTRAINED FLOODING
`
`/
`/
`
`/
`/
`
`60-
`
`PERCENTAGE OF PACKETS
`
`to
`I- 80-
`UJ
`•XL
`O <
`a.
`u_
`o
`UJ e>
`< 40-
`UJ o
`cr
`CD 20
`Q_
`
`0
`0
`
`/
`/
`/
`/
`/
`/
`/
`/
`/
`/
`/
`/
`
`_
`
`T
`T
`vI
`I
`I
`.03
`.02
`.01
`.03
`.02
`.0|
`END-TO-END QUEUE DELAY (SEC)
`END-TO-END QUEUE DELAY (SEC)
`FIG. 13
`
`T
`I
`.04
`.04
`
`£<3 ANALYTICAL PROJECTION
`- m ANALYTICAL PROJECTION .
`
`/•*
`
`863
`'06.}
`80.8
`80.8
`
`.
`
`-
`
`—
`
`100
`I00
`5^2223
`Q
`5 91:2
`93.2
`UJ
`•c
`5 a0
`0 80
`<
`“<5
`UJ
`cr
`C!
`to
`(D
`z
`O 60-
`5 s0
`2
`<
`E
`to 40-
`a’? 40
`UJ
`LL]
`o
`Q
`Ll. o
`LL
`0
`UJ 20
`us 20
`o
`<9.
`,3
`Z
`UJ
`‘6’
`0
`o 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.10
`bk.
`cc.
`33
`0.01
`0.02 0.03 0.04 0.05 0.06 0.07 0.00 0.09 0.10
`UJ
`PACKET ERROR RATE
`Q_
`PACKET ERROR RATE
`FIG. 14
`FIG. I4‘
`
`69.9
`
`64.9
`'M 60.3
`
`56.0
`
`52.0
`
`48.2
`
`75.2
`
`r? •V
`$
`V •v
`
`CL
`
`.
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 9 of 10
`Sheet 9 of 10
`
`5,056,085
`5,056,085
`
`FLOOD-AND-FORWARD
`-<>- FLOOD-AND-FORWARD
`-•-CONSTRAINED FLOODING
`-—'-CONSTRAINED FLOODING
`
`_
`
`""" - •
`
`o-
`
`\ F
`
`T
`0.02
`_ 0 0
`
`_ w
`
`T
`0.10
`
`0.12
`
`_ u C I
`T
`T
`T
`0.08
`0.06
`0.04
`PACKET ERROR RATE
`FIG. 15
`\ mu .m \
`\ E O S \ 8
`\ R 5 + h \
`\ -m m mm x ‘M
`FLOOD-AND-FORWARD
`\ 0. W O \ O
`CONSTRAINED FLOODING
`6
`\ , m m \\
`k :m m m L. \\ 1m
`\ 0 AN“ M \3 O
`3 IR m M a \o I".
`
`\ 6 mun . . _ \ 6
`
`O ‘ x
`
`Inv. R G _ lo. 0 E H \ 0
`4 m \ 4
`
`T k .\
`M m k.‘ M
`x*
`
`o
`
`"O1
`
`-0
`
`""V
`
`N.
`
`\
`X
`
`\
`\
`\
`\
`
`a
`UJ 100.0-
`X o <
`UJ
`^ 99.8-
`co
`z o
`5 99.6-1
`z
`CO
`w 99.4-
`Q
`Sfe
`UJ o 99.2-
`z
`UJ y 99.0
`OC
`UJ
`Q_
`
`T
`0.00
`
`655m £22253 .6 ww?zwuma < < .h: h.
`
`m w w w w w m; 8 8m 5 51 o $352K
`
`AW. 6.0. .r h. .r 0 w w w w w W m
`
`a
`-m. k ‘m
`
`o . 0
`
`[m 1%
`
`£ 100-
`co
`<
`o
`Q 90-<
`o
`OC
`CD
`80-
`o
`UJ U-
`CC 70-
`UJ Q_
`u_
`o 60-
`UJ
`o <
`t= 50-
`z UJ
`o
`£
`
`40-
`
`S
`
`\
`\
`\
`\
`\
`
`T
`0.10
`
`0.12
`
`T
`0.00
`
`T
`0.02
`
`T
`T
`T
`0.08
`0.06
`0.04
`PACKET ERROR RATE
`PACKET ERROR RATE
`FIG.16
`FIG. I6
`
`

`

`U.S. Patent
`US. Patent
`
`Oct. 8, 1991
`Oct. 8, 1991
`
`Sheet 10 of 10
`Sheet 10 of 10
`
`5,056,085
`5,056,085
`
`v
`\t RECEIVER
`RECEIVER
`
`CPU
`CPU
`
`V
`TRANSMITTER j/
`TRANSMITTER
`
`TIMER
`TIMER
`I
`
`MEMORY
`MEMORY
`____-____'_-_____
`BROADCAST
`I CONSTRAINT
`BROADCAST
`CONSTRAINT
`I
`ROUTING
`I
`TABLE
`ROUTING
`TABLE
`I
`TABLE
`I
`TABLE
`i
`FIG. 17
`F I G. I7
`
`TRANSMITTING NODE
`TRANSMITTING NODE
`
`RECEIVING NODE
`RECEIVING NODE
`
`I
`STRAlNES" FLOOD I
`l
`SET ACKNOWLEDGEMENT TIIIIER
`SET ACKNOWLEDGEMENT TIMER
`I
`I
`
`f9 4
`4.
`5
`5
`/_// 6 1
`6
`
`I
`INHIBIT
`INHIBIT
`RECORD IN SEND TO COLUMN OF
`RECORD IN SEND m COLUMN 0F <- —- — — —_
`BROADCAST ROUTING TABLE
`BROADCAST ROUTl/NG TABLE
`
`\
`
`/
`DESIGNATE A SCOUT PACKET WITH
`DESIGNATE A scouT PACKET wITII
`SOURCE IDENTIiIEQE‘IEON AND scouT f/
`SOURCE IDENTIFICATION AND SCOUT /
`LABLE
`I
`[2 .
`TRANSMIT SCOUT PACKET IN CON-
`TRANSMH' SCOUT PACKET m c N_
`STRWFLOQD
`o
`.-
`
`'__ —'_
`
`3\
`DETERMINE WHETHER THIS SCOUT
`DETERMINE WHETHER THIS SCOUT
`PACKET HAS BEEN RECEIVED
`PACKET HAS BEEN RECEIVED "_
`PREVIOUSLY
`PREVIOUSLY
`
`10
`/0\ DISCARD +———
`DISCARD *
`YES
`YES
`
`PASS TO NEXT HIGHER LAYER
`“55 To "EXT “'G'IER LAYER
`
`LOG IN CONSTRAINT TABLE
`LOG IN CONSTRAINT TABLE
`
`"0
`NO
`k-
`b-
`I4
`
`SEND ACKNOWLEDGEMENT
`SEND ACKNOWLEDGEMENT +
`
`.
`
`I -
`TRANSMIT REGULAR BROADCAST
`'TRAIIsIIIT REGULAR BRoAncAsT
`PACKETS TO NODES RECORDED IN
`PACKETS T0 NODES RECORDED IN
`SEND TO COLUMN OF BROADCAST
`SEND To coLumI 0F BRoAocAsT
`ROUTING TABLE
`ROUTING TABLE
`
`7
`7 »\
`RECORD IN RECEIVED FROM
`RECORD IN RECEIVED FROM
`COLUMN OF BROADCAST ROUTING
`COLUMN OF BRoAucAsT ROUTING
`TABLE
`TABLE
`
`I<-—~
`
`8
`
`FIG. 18
`
`TRANSMIT TO ALL NODES EXCEPT
`TRANSMIT TO ALL NODES EXCEPT ‘
`THE NODE FROM WHICH RECEIVED •*
`THE NODE FROM WHICH RECEIVED
`
`

`

`1 .
`
`A
`
`A
`
`4
`
`1
`FLOOD-AND-FORWARD ROUTING FOR
`FLOOD-AND-FORWARD ROUTING FOR
`BROADCAST PACKETS IN PACKET SWITCHING
`BROADCAST PACKETS IN PACKET SWITCHING
`NETWORKS
`NETWORKS
`
`5,056,085
`5,056,085
`2
`2
`rithms is described, for example, in Computer Networks,
`rithms is described, for example, in Computer Networks,
`by A. S. Tanenbaum, Prentice Hall, Englewood Cliffs,
`by A. S. Tanenbaum, Prentice Hall, Englewood Cliffs,
`N.J., 1981, and in "Reverse Path Forwarding of Broad­
`N.J., 1981, and in “Reverse Path Forwarding of Broad
`cast Packets," by Y. K. Dalai and R. M. Metcalfe, Com-
`cast Packets," by Y. K. Dalal and R. M. Metcalfe, Com
`5 munications of the ACM, Vol. 21, pp. 1040-1048, De­
`munications of the ACM, Vol. 21, pp. 1040-1048, De
`This invention was made with United States govern­
`cember 1978.
`•
`This invention was made with United States govern
`cember 1978.
`'
`ment support under contract No. F30602-86-C-0224.
`One such existing algorithm is known as separate
`ment support under contract No. F30602-86-C-O224.
`One such existing algorithm is known as separate
`The United States government has certain rights in this
`The United States government has certain rights in this
`destination addressing. If the network
`is already
`destination addressing. If the network is already
`invention.
`invention.
`equipped with a point-to-point routing algorithm, the
`equipped with a point-to-point routing algorithm, the
`10 obvious approach to broadcast routing is to have the
`obvious approach to broadcast routing is to have the
`BACKGROUND OF THE INVENTION
`BACKGROUND OF THE INVENTION
`source generate a copy of the broadcast packet for each
`source generate a copy of the broadcast packet for each
`Communication between distant stations or nodes,
`Communication between distant stations or nodes,
`destination and then to use point-to-point routing to
`destination and then to use point-to-point routing to
`for example communication between nodes in a satellite
`for example communication between nodes in a satellite
`deliver each copy. This approach makes good use of
`deliver each copy. This approach makes good use of
`network orbiting the earth, presents many requirements
`network orbiting the earth, presents many requirements
`existing hardware; however, since routes to different
`existing hardware; however, since routes to different
`that have not previously been encountered in communi- 15 destinations often overlap, most relaying nodes will
`that have not previously been encountered in communi
`destinations often overlap, most relaying nodes will
`cation or computer networks. Most such communica-
`receive, process and transmit the same packet over and
`cation or computer networks. Most such communica
`receive, process and transmit the same packet over and
`tion networks are expected to be based in space and to
`over again The abundanCe 0f duplicates represents a
`tion networks are expected to be based in space and to
`over again. The abundance of duplicates represents a
`consist of thousands of satellites orbiting the earth at
`consist of thousands of satellites orbiting the earth at
`waste of bandwidth and is likel t0 create a high leveI of
`waste of bandwidth and is likely to create a high level of
`various altitudes and inclinations Such satellites are
`various altitudes and inclinations. Such satellites are
`.
`especially in areas close to the source,
`co
`congestion, especially in areas close to the source.
`constantly moving m and out of line of sight of each 20 Another a ^ to broadcast routing is to carry
`constantly moving in and out of line of sight of each
`20
`Another approach to broadcast routing is to carry
`other and when engaged in a battle, are subject to al
`other and, when engaged in a battle, are subject to all
`multi le destination addresses with each packet. When
`multiple destination addresses with each packet. When
`kinds or threats, ranging from link lamming to total
`kinds of threats, ranging from link jamming to total
`,
`• t
`a broadcast packet is generated or received at a node, it
`u
`J
`*
`i * •
`* J
`•
`J *
`J
`•*
`a broadcast packet is generated or received at a node, it
`,
`destruction. The dynamic and volatile nature of such
`TM.
`J
`•
`j
`r
`t
`A...
`^
`. .
`,. ^
`r ,
`.
`.
`.
`destruction. The dynamic and volatile nature of such
`partitions the remaining list of destinations, grouping
`partitions the remaining list of destinations, grouping
`.
`networks poses a great challenge to network manage-
`i
`* u i i
`. i
`f
`, it_
`'
`.
`f
`networks poses a great challenge to network manage
`i
`•
`together destinations that map to the same outgoing link
`together destinations that map to the same outgoing link
`i. •
`.i
`i
`ment, requiring techniques that adapt to topological 25 . ®
`,
`%
`.
`,
`.
`.
`/, , „
`ment, requiring techniques that adapt to topological
`, 6 , &
`25
`in its point-to-point routing table. For each such group
`changes and that can survive threats
`" lts PO"11"10'?01"1 ^^.ng table. For each such group
`changes and that can survive threats.
`In some situations, it may be desired to transmit a
`the node generates a copy of the broadcast packet,
`the "ode generates a copy of the broadcast packet,
`In some situations, it may be desired to transmit a
`attaches the group’s destination list, and forwards the
`packet of data from one node to one specific other node.
`s destination hst, and forwards the
`Packet on ll!e sfected outgoing link. As the broadcast
`theu
`packet of data from one node to one speci?c other node.
`packet on the selected outgoing link. As the broadcast
`Such transmissions are referred to as "point-to-point".
`Such transmissions are referred to as “point-to-point”.
`In other situations, it may be desired to send data from 30 ProPagates farther away from the source, the destina-
`propagates farther away from the source, the destina
`In other situations, it may be desired to send data from
`30
`a sensor node in the network to all other nodes in the
`tion list gets smaller until there is no destination remain
`tlon llst Sets smaller untl1 there 15 no destination remain-
`a sensor node in the network to all other nodes in the
`network, or to all the nodes in a subnetwork of the
`ing. The packets follow the branches of a spanning tree
`lng' The Packets follow the branches of a spanning tree
`network, or to all the nodes in a subnetwork of the
`network. By way of illustration, in a defensive military
`r00ted at the source'. although information on the span-
`rooted at the source, although information on the span
`network. By way of illustration, in a defensive military
`environment, a subnetwork of sensor nodes may be in
`ning tree is not explicitly stored at each node.
`n'n8 tree 's not explicitly stored at each node,
`environment, a subnetwork of sensor nodes may be in
`high earth orbits, as depicted in FIG. 1, while a subnet- 35
`Forwarding broadcast packets along branches of a
`Forwarding broadcast packets along branches of a
`high earth orbits, as depicted in FIG. 1, while a subnet
`35
`work of weapon nodes may be in low earth orbits, as
`spanning tree has the advantage of generating an opti-
`spanning tree has the advantage of generating an opti
`work of weapon nodes may be in low earth orbits, as
`depicted in FIG. 2. It may be necessary to broadcast a
`mal number of packet copies; this number is exactly
`ma' number of packet copies; this number is exactly
`depicted in FIG. 2. It may be necessary to broadcast a
`packet of data from a sensor node in the high earth orbit
`equal to the number of reachable destinations. How-
`equal to the number of reachable destinations. How
`packet of data from a sensor node in the high earth orbit
`to every weapon node in the low earth orbit. Such a
`ever, the disadvantage of multidestination addressing
`ever, the disadvantage of multidestination addressing
`to every weapon node in the low earth orbit. Such a
`transmission from one node to every node of a subnet- 40 ''es 'n ^e long destination field. A bit map implementa­
`lies in the long destination ?eld. A bit map implementa
`transmission from one node to every node of a subnet
`40
`tion requires as many bits as there are nodes. For net­
`work rather than to a specific one or few of those nodes,
`tion requires as many bits as there are nodes. For net
`work rather than to a speci?c one or few of those nodes,
`works with thousands of nodes, the high ratio of over­
`is referred to as a "broadcast"; i.e., a transmission from
`works with thousands of nodes, the high ratio of over
`is referred to as a “broadcast”; i.e., a transmission from
`head bits to data bits is a drawback that is not easy to
`the one node that is "broadcast" to all those other
`head bits to data bits is a drawback that is not easy to
`the one node that is _“broadcast” to all those other
`overcome. Furthermore, the performance of this algo-
`nodes. In the following description, then, "broadcast" ...
`overcome. Furthermore, the performance of this algo
`...
`nodes. In the following description, then, “broadcast”
`refers to such a transmission from one node intended for 45 rithm is tied to that of the underlying point-to-point
`rithm is tied to that of the underlying point-to-point
`refers to such a transmission from one node intended for
`45
`routing algorithm. If the point-to-point routes are in­
`all of a network or subnetwork of nodes.
`routing algorithm. If the point-to-point routes are in
`all of a network or subnetwork of nodes.
`consistent, unstable or slow to adapt, the same effects
`In a broadcast mode, packets of data can be guided by
`consistent, unstable or slow to adapt, the same effects
`In a broadcast mode, packets of data can be guided by
`will be exhibited in the broadcast routes.
`a broadcast routing algorithm installed at each node to
`will be exhibited in the broadcast routes.
`a broadcast routing algorithm installed at each node to
`Constrained flooding is a technique in which an arriv-
`relay the data packets from node to node over point-to-
`Constrained flooding is a technique in which an arriv
`relay the data packets from node to node over point-to
`point links so as to be received by all nodes that are 50 inS packet that has not been seen before is copied and
`ing packet that has not been seen before is copied and
`point links so as to be received by all nodes that are
`50
`forwarded on all outgoing links except the link on
`reachable from the source node. This mode of broad-
`forwarded on all outgoing links except the link on
`reachable from the source node. This mode of broad
`which it arrived. Packets that have been seen are simply
`casting has been done before in military or commercial
`which it arrived. Packets that have been seen are simply
`casting has been done before in military or commercial
`discarded. To keep track of already seen packets, a
`packet switching networks. However, in some defense
`discarded. To keep track of already seen packets, a
`packet switching networks. However, in some defense
`sequence number is assigned to each packet by the
`scenarios, data generated by all the sensor sources can
`sequence number is assigned to each packet by the
`scenarios, data generated by all the sensor sources can
`total hundreds of thousands of packets per second. As- 55 source node, and a constraint table or bit map is main­
`total hundreds of thousands of packets per second. As
`source node, and a constraint table or hit map is main
`55
`tained at each node to log received packets. The log for
`sured broadcasting of such a quantity of data requires
`tained at each node to log received packets. The log for
`sured broadcasting of such a quantity of data requires
`a particular packet has to remain in the constraint table
`that, in addition to being adaptive and survivable, the
`a particular packet has to remain in the constraint table
`that, in addition to being adaptive and survivable, the
`for some time, at least for the duration of the broadcast,
`broadcast routing algorithm be able to handle a very
`broadcast routing algorithm be able to handle a very
`for some time, at least for the duration of the broadcast,
`before the log can be cleared and reused. The size of the
`high traffic load without exacting a heavy toll from the
`high traf?c load without exacting a heavy toll from the
`before the log can be cleared and reused. The size of the
`60 constraint table is thus proportional to this predefined
`network resources.
`constraint table is thus proportional to this prede?ned
`network resources.
`There are many existing algorithms for routing
`time for packets t