Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 5
`
`4.
`
`Claims 32-33 are rejected under 35 U.S.C. 103(a) as being unpatentable over
`
`Steele, in view of Choet al. (“A Flood Routing Method for Data Networks,” ICICS ‘97,
`
`hereinafter “Cho”).
`
`In considering claim 32, the claim contains a computer readable medium for
`
`performing the samesteps as claim 1, and additionally requires that each network
`
`participant forwards broadcast messagesthatit receivesto its neighborparticipants.
`
`See the discussion of claim 1 for the description of those steps. Note, however, that
`
`Steele does not disclose that each network participant forwards broadcast messages
`
`that it receives to its neighbor participants. This is because Steele is only concerned
`
`with how nodes are added and/or subtracted to the network and howthataffects
`
`network configuration. The system taught by Steele remains silent regarding the actual
`
`passing of data between nodes. Nonetheless,flood routing (i.e. broadcasting
`
`messagesfrom each node to each neighboring node in a network)is well known, as
`
`_ evidenced by Cho. Ina similar art, Cho discloses that flood routing is well known(p.
`
`1418, Introduction, f] 1) and further describes a network system with multiple
`
`interconnected nodes (see Figs. 1, 3) that uses flood routing to pass information
`
`between nodes(p. 1418-1419, § 2, “Flood Routing Mechanism’). Given the teaching of
`
`Cho, a person having ordinary skill in the art would have readily recognized the
`
`desirability and advantagesof using flood routing to send information between nodesin
`
`the system taught by Steele, because flood routing is a very reliable and robust method
`
`of data transmission (see Cho, p. 1418, Introduction, {] 1). Therefore, it would have
`
`been obvious to use flood routing to pass information in the network taught by Steele.
`
`BUNGIE - EXHIBIT 1002 Part 5 of 5
`1206
`
`1206
`
`BUNGIE - EXHIBIT 1002 Part 5 of 5
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 6
`
`In considering claim 33, Steele further discloses that each participantis
`
`connected to 4 participants (See Figs. 5-6, wherein each participant is connectedto at
`
`least 4 participants).
`
`5.
`
`Claims 1-5, 7, 8, and 11-17 are rejected under 35 U.S.C. 103(a) as being
`
`unpatentable over Gilbert et al. (U.S. Patent No. 6,490,247, hereinafter “Gilbert”) in view
`
`of Hughesetal. (U.S. Patent No. 6553,020, hereinafter “Hughes’).
`
`In considering claim 1, Gilbert discloses a computer-based method for adding a
`
`participant (“node”) to a network of participants, the method comprising:
`
`Identifying a pair of participants of the network that are connected(col. 6, lines
`
`26-49, wherein the additional node contacts the two participants), disconnecting the
`
`participants of the identified pair from each other(col. 7, lines 7-8, “the two adjacent
`
`nodes drop connection to one another”), and connecting each participant of the
`
`identified pair of participants to the added participant(col. 7, lines 13-19, “the additional
`
`node connects with each of the adjacent nodes’).
`
`However, Gilbert does not disclose that each participant is connected to three or
`
`more other participants. Gilbert discloses instead, a ring-type network, wherein each
`
`node is connected to two other nodes(seecol. 3, lines 25-36). Nonetheless, the use of
`
`other types of networks to connect participants, wherein each participant is connected
`
`to three or more participants, and wherein participants can be added to the network,is
`
`
`
`well known, as evidenced by Hughes. !nasimilar art, Hughes discloses a networkfor
`
`1207
`
`1207
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 7
`
`interconnecting nodes for communication across the network, wherein the nodes can be
`
`connected in a hypercube-type topology, or in someothertype of topology such that
`
`each node is connected to 4 other nodes, wherein nodes can be added to the network
`
`(col. 14, lines 25-30, 67; col. 15, lines 1-5, 45-52; col. 4, lines 6-9, “additional users can
`
`be added later as demand grows’). Given the teaching of Hughes, a person having
`
`ordinary skill in the art would have readily recognized the desirability and advantages of
`
`using a similar technique as taught by Gilbert (i.e. disconnecting certain node
`
`connections and connecting the newly disconnected links to the added node) to connect
`
`additional participants in the system taught by Hughes, in order to maintain the network
`
`topology for added nodes, thereby maintaining the interconnectivity and reliability
`
`associated with hypercube and 4-connected networks. Therefore, it would have been
`
`obviousto use the technique disclosed by Gilbert for connecting new participants in a
`
`system such as the one taught by Hughes.
`
`In considering claim 2, Hughesfurther discloses that each participant is
`
`connected to 4 participants (col. 14, lines 25-30, “hypercube”; col. 15, lines 45-52,
`
`“nodes 2 are connectedin an arbitrary mannerto up to a fixed numbern of nearest
`
`nodes... where n=4...”; Fig. 9).
`
`In considering claim 3, Gilbert further discloses that the pair of nodes selected for
`
`disconnection is selected arbitrarily (col. 6, lines 37-40, “the actual node thatis
`
`contacted by the additional node does not matter,” and can simply be “the first node on
`
`1208
`
`1208
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 8
`
`the list’). Although Gilbert does not explicitly state that selection is done randomly, the
`
`nodeis effectively being selected randomly, since any node can befirst on thelist. The
`
`same result would be achieved by selecting a node randomly from somewhereelse on
`
`the list. Thus, the limitation of selecting the node randomly doesnot renderthe claimed
`
`invention patentably distinct over the method taught by Gilbert.
`
`In considering claim 4, Gilbert further discloses that arbitrarily selecting the pair
`
`includes sending a message through the network on an arbitrarily selected path (col. 6,
`
`lines 30-31, 37-40, “an additional node contacts two adjacent nodesin the network,”
`
`wherein “the actual nodethat is contacted by the additional node does not matter,” such
`
`that the path selected will be the path to whichever nodeis arbitrarily and thus randomly
`
`selected).
`
`In considering claim 5, Gilbert further discloses that when a participant (“primary
`
`node”) receives the message,it sends the messageto a selected participant to whichit
`
`is connected (“adjacent node,”col. 6, lines 50-59). However, Gilbert does not disclose
`
`that the messageis sent to a randomly selected participant. Nonetheless, Gilbert
`
`discloses that the actualinitial nodes contacted do not matter(see col. 6, lines 37-40).
`
`It follows then that the selection of the adjacent node also doesn’t matter, so long asit is
`
`adjacent (note that Gilbert does not specify which adjacent node is selected). Selecting
`
`an adjacent node randomly, rather than, say, selecting one particular adjacent node
`
`1209
`
`1209
`
`

`

`Application/Contro! Number: 09/629,570
`Art Unit: 2153
`
`Page 9
`
`overthe other, is thus a matter of preference, and does not renderthe claimed invention
`
`patentably distinct over the method taught by Gilbert.
`
`In considering claim 7, Gilbert further discloses that the participant to be added
`
`requests a portal computerto initiate the identifying of the pair of participants (col. 6,
`
`lines 45-47, “additional node 100 would contact node 10, and node 10 would provide
`
`additional node 100 information regarding node 16”).
`
`In considering claim 8, Gilbert further discloses that the initiating of the identifying
`
`of the pair of participants includes the portal computer sending a message to a
`
`connectedparticipant requesting an edge connection (col. 6, lines 53-57, “primary
`
`node... receives all incoming calls from other nodes wishing to enter the network. The
`
`point of entry in the network for these other nodesis then betweenthe primary node
`
`and an adjacent node to the primary node”).
`
`In considering claim 11, Hughes further discloses that the participants are
`
`connected via the Internet(col. 1, line 14, “Internet”; col. 14, lines 55-59, “Internet web-
`
`browsing”).
`
`It would have been obvious for the networkin the participant adding system
`
`taught by Gilbert and Hughesto bethe Internet, so that the participants could
`
`communicate with other users anywhere in the world. Therefore, it would have been
`
`obvious to use the participant adding system taught by Gilbert and Hughes on the
`
`Internet network.
`
`1210
`
`1210
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 10
`
`In considering claim 12, although Hughes doesnotexplicitly teach TCP/IP,
`
`Examinertakes official notice that TCP/IP is a standard well knownprotocol used for
`
`Internet communications. Therefore, it would have been obvious to connect the
`
`participants via TCP/IP for the same reasons as connecting participants via the Internet
`
`— i.e. to allow global communications on the existing Internet network.
`
`In considering claim 13, Gilbert further discloses that the participants are
`
`computer processes(“nodes”).
`
`In considering claim 14, Gilbert discloses a computer-based method for adding
`
`nodes(“nodes”) to a graph that is m-regular and m-connected (see Fig. 1, which is 2-
`
`regular and 2-connected) to maintain the graph as m-regular, the method comprising:
`
`Identifying p pairs of nodesof the graph that are connected wherep is half of m
`
`(p. is 1, see col. 6, lines 30-42, wherein a pair of adjacent nodesis identified);
`
`Disconnecting the nodesof eachidentified pair from each other(col. 7, lines 7-8);
`
`and
`
`Connecting each node ofthe identified pair of nodes to the added node (col. 7,
`
`lines 13-19).
`
`However, Gilbert does not disclose that m is four or greater, and thus that the
`
`graphis at least 4-connected and 4-regular. Nonetheless, the use of 4-connected and
`
`4-regular networks wherein nodes can be added to the networkis well known, as
`
`1211
`
`1211
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 11
`
`evidenced by Hughes.
`
`In a similar art, Hughes discloses a networkfor interconnecting
`
`nodes for communication across the network, wherein the nodes can be connected in a
`
`hypercube-type topology, or in someothertype of topology such that each nodeis
`
`connected to 4 other nodes, wherein nodes can be added to the network(col. 14, lines
`
`25-30, 67; col. 15, lines 1-5, 45-52; col. 4, lines 6-9, “additional users can be addedlater
`
`as demand grows’). Given the teaching of Hughes, a person having ordinary skill in the
`
`art would have readily recognized the desirability and advantages of extending the node
`
`addition method taught by Gilbert (i.e. disconnecting p pairs of nodes node connections
`
`and connecting the newly disconnectedlinks to the added node) to more highly
`
`connected (i.e. 4-connected) networks, in order to maintain the network topology for
`
`added nodes, thereby maintaining the interconnectivity and reliability associated with
`
`hypercube and 4-connected networks. Therefore, it would have been obvious to use
`
`the technique disclosed by Gilbert for connecting new participants to the 4-connected
`
`system taught by Hughes.
`
`In considering claim 15, Gilbert further discloses that the pair of nodes selected
`
`for disconnection is selected arbitrarily (col. 6, lines 37-40, “the actual node thatis
`
`contacted by the additional node does not matter,” and can simply be “the first node on
`
`the list”). Although Gilbert does not explicitly state that selection is done randomly, the
`
`node effectively is being selected randomly, since any node canbefirst on the list. The
`
`sameresult would be achieved by selecting a node randomly from somewhere else on
`
`1212
`
`1212
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 12
`
`the list. Thus, the limitation of selecting the node randomly doesnot renderthe claimed
`
`invention patentably distinct over the method taught by Gilbert.
`
`In considering claim 16, Hughesfurther discloses that the nodes are computers
`
`and the connections are point-to-point connections (abstract).
`
`In considering claim 17, both Gilbert and Hughesfurther disclose that m is even
`
`(i.e. 2 or 4).
`
`6.
`
`Claims 32-36, 38, and 39 are rejected under 35 U.S.C. 103(a) as being
`
`unpatentable over Gilbert in view of Hughes, and further in view of Choet al. (“A Flood
`
`Routing Method for Data Networks,” ICICS ’97, hereinafter “Cho’).
`
`In considering claim 32, the claim contains a computer readable medium for
`
`performing the same steps asclaim 1, and additionally requires that each network
`
`participant forwards broadcast messagesthat it receives to its neighbor participants.
`
`See the discussion of claim 1 for the description of those steps. Note, however, that
`
`neither Gilbert nor Hughesdisclose that each network participant forwards broadcast
`
`messagesthatit receivesto its neighbor participants. Nonetheless,flood routing(i.e.
`
`broadcasting messages from each nodeto each neighboring nodein a network) is well
`
`known, as evidenced by Cho. Ina similar art, Cho disclosesthat flood routing is well
`
`known (p. 1418, Introduction, {| 1) and further describes a network system with multiple
`
`interconnected nodes(see Figs. 1, 3) that uses flood routing to pass information
`
`1213
`
`1213
`
`

`

`Application/Contro! Number: 09/629,570
`Art Unit: 2153
`
`Page 13
`
`between nodes(p. 1418-1419, § 2, “Flood Routing Mechanism”). Given the teaching of
`
`Cho, a person having ordinary skill in the art would have readily recognized the
`
`desirability and advantagesofusing flood routing to send information between nodesin
`
`the system taught by Gilbert and Hughes, becauseflood routing is a very reliable and
`robust method of data transmission (see Cho, p. 1418, Introduction, f] 1). Therefore,it
`
`would have been obvious to use flood routing to pass information in the network taught
`
`by Gilbert and Hughes.
`
`In considering claim 33, Hughesfurther discloses that each participantis
`
`connected to 4 participants (col. 14, lines 25-30, “hypercube”; col. 15, lines 45-52,
`
`“nodes 2 are connected in an arbitrary mannerto up to a fixed number n of nearest
`
`nodes... where n=4...”; Fig. 9).
`
`In considering claim 34, Gilbert further discloses that the pair of nodes selected
`
`for disconnection is selected arbitrarily (col. 6, lines 37-40, “the actual node thatis
`
`contacted by the additional node does not matter,” and can simply be “the first node on
`
`the list”). Although Gilbert does not explicitly state that selection is done randomly, the
`
`nodeeffectively is being selected randomly, since any node can befirst on the list. The
`
`sameresult would be achieved by selecting a node randomly from somewhereelse on
`
`the list. Thus, the limitation of selecting the node randomly does not render the claimed
`
`invention patentably distinct over the method taught by Gilbert.
`
`1214
`
`1214
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 14
`
`In considering claim 35, Gilbert further discloses that arbitrarily selecting the pair
`
`includes sending a messagethrough the network on an arbitrarily selected path (col. 6,
`
`lines 30-31, 37-40, “an additional node contacts two adjacent nodesin the network,”
`
`wherein “the actual node that is contacted by the additional node does not matter,” such
`
`that the path selected will be the path to whichevernodeis arbitrarily and thus randomly
`
`selected).
`
`In considering claim 36, Gilbert further discloses that when a participant(“primary
`
`node”) receives the message, it sends the messageto a selected participant to whichit
`
`is connected(“adjacent node,”col. 6, lines 50-59). However, Gilbert does not disclose
`
`that the messageis sent to a randomly selected participant. Nonetheless, Gilbert
`
`discloses that the actualinitial nodes contacted do not matter (see col. 6, lines 37-40).
`
`It follows then that the selection of the adjacent node also doesn’t matter, so long asit is
`
`adjacent (note that Gilbert does not specify which adjacent nodeis selected). Selecting
`
`an adjacent node randomly, rather than, say, selecting one particular adjacent node
`
`overthe other, is thus a matter of preference, and does not renderthe claimed invention
`
`patentably distinct over the method taught by Gilbert.
`
`In considering claim 38, Gilbert further discloses that the participant to be added
`
`requests a portal computertoinitiate the identifying of the pair of participants (col. 6,
`
`lines 45-47, “additional node 100 would contact node 10, and node 10 would provide
`
`additional node 100 information regarding node 16’).
`
`1215
`
`1215
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 15
`
`In considering claim 39, Gilbert further discloses that the initiating of the
`
`identifying of the pair of participants includes the portal computer sending a message to
`
`a connectedparticipant requesting an edge connection (col. 6, lines 53-57, “primary
`
`node... receives all incoming calls from other nodes wishing to enter the network. The
`
`point of entry in the network for these other nodesis then betweenthe primary node
`
`and an adjacent node to the primary node’).
`
`Allowable Subject Matter
`
`7.
`
`Asallowable subject matter has been indicated, applicant's reply must either
`
`comply with all formal requirements or specifically traverse each requirement not
`
`complied with. See 37 CFR 1.111(b) and MPEP § 707.07(a).
`
`Claims 9 and 40 would beallowable if rewritten to include all of the limitations of
`
`the base claim and anyintervening claims, andif the base claims were rewritten to
`
`overcomethe rejection(s) under 35 U.S.C. 112, second paragraph, setforth in this
`
`Office action.
`
`The following is a statement of reasonsfor the indication of allowable subject
`
`matter:
`
`the prior art of record fails to disclose or render obvious all of the limitations of
`
`the claims, including the claimed distance-related selection steps described in claims 9,
`
`and 40.
`
`1216
`
`1216
`
`

`

`Application/Control Number: 09/629,570
`Art Unit: 2153
`
`Page 16
`
`The prior art made of record and not relied upon is considered pertinentto
`
`Conclusion
`
`applicant’s disclosure.
`
`Any inquiry concerning this communication or earlier communications from the
`
`examiner should be directed to Bradley Edelman whose telephone numberis (703) 306-
`
`3041. The examiner can normally be reached on Mondayto Friday from 8:30 AM to
`
`5:00 PM.
`
`If attempts to reach the examiner by telephone are unsuccessful, the examiner's
`
`supervisor, Glen Burgess can be reached on (703) 305-4792. The fax phone numbers
`
`for the organization wherethis application or proceeding is assigned are asfollows:
`
`Forall correspondences: (703) 872-9306.
`
`Anyinquiry of a general nature orrelating to the status of this application or
`
`proceeding should be directed to the receptionist whose telephone numberis (703) 305-
`
`3900.
`
`BE
`January 6, 2004
`
`1217
`
`1217
`
`

`

`HOLT ET AL.
`
`
`Classification
`June 1996, 1996 IEEE International Conference on Communications, Vol. 3, pp. 1581-1585.
`
`
`
`
`
`
`
`Cc|US-6,603,742 B1 08-2003 Steele etal. 370/254
`
`US-5,471,623 A
`
`11-1995
`
`Napolitano, Jr., Leonard M.
`
`709/243
`
`ifussrzaz2a|ost992_|Hauptscheineta,|8025
`
`
`||fussioreaoa|03-1992_|shinetal
`Pfkefes
`
`pfefes
`
`
`||
`aee
`oo
`
`Document Number
`Country Code-Number-Kind Code
`
`Date
`MNM-YYYY
`
`FOREIGN PATENT DOCUMENTS
`
`.
`
`.
`
`|||||||
`
`_|
`
`NON-PATENT DOCUMENTS
`
`Include as applicable: Author, Title Date, Publisher, Edition or Volume, Pertinent Pages)
`
`Cho etal., "A Flood Routing Method for Data Networks,” September 1997, Proceedings of 1997 International Conference on
`Information, Communications and Signal Processing, Vol. 3, pp. 1418-1422.
`
`Bandyopadhyayetal., “A Flexible Architecture for Multi-Hop Optical Networks,” October 1998, 7th International Conference on
`Computer Communications and Networks, 1998, pp. 472-478.
`
`Hsu, “On Four-Connecting a Triconnected Graph,” October 1992, Annual Symposium on Foundations of ComputerScience,
`1992, pp. 70-79.
`
`Shiokawaetal., "Performance Analysis of Network Connective Probability of Multinop Network under Correlated Breakage,"
`
`*A copyofthis referenceis not being furnished with this Office action. (See MPEP § 707.05(a).)
`Dates in MM-YYYY format are publication dates. Classifications may be USorforeign.
`U.S. Patent and Trademark Office
`PTO-892 (Rev. 01-2001)
`
`Notice of References Cited
`
`Part of Paper No. 9
`
`1218
`
`||
`
`Application/Control No.
`09/629,570
`
`im°
`
`Applicant(s)/Patent Under
`Reexamination
`
`U.S. PATENT DOCUMENTS
`
`
`Date
`Document Number
`MM-YYYY
`Country Code-Number-Kind Code
`
`
`
`.
`|
`Classification
`
`
`
`
`
`US-6,490,247 B1 12-2002|Gilbert et al. 370/222
`
`
`
`
`
`
`
`|B|US-6,553,020 BI 04-2003|Hughesetal. 370/347
`
`||||||[
` a
`
`1218
`
`

`

`
`
`
`
`Application/Control No.
`
`09/629,570
`
`
`Applicant(s)/Patent Under
`Reexamination
`HOLT ET AL.
`
`
`
`IEEE GLOBECOM'90, ‘Communications: Connecting the Future,’ Vol. 1, pp. 459-463. *A copyofthis reference is not being furnished with this Office action. (See MPEP § 707.05(a).)
`
`Date
`MM-YYYY
`
`Classification
`
`Komineetal., "A Distributed Restoration Algorithm for Multiple-Link and Node Failures of Transport Networks," December 199
`
`Dates in MM-YYYYformatare publication dates. Classifications may be US orforeign.
`U.S. Patent and Trademark Office
`PTO-892 (Rev. 01-2001)
`
`Notice of References Cited
`
`Part of Paper No. 9
`
`1219
`
`1219
`
`

`

`International Conference on
`Information, Communications and Signal Processing
`ICICS '97
`Singapore, 9-12 September 1997
`
`3F1.4
`
`A Flood Routing Method for Data Networks
`
`Jaihyung Cho
`
`James Breen
`
`Monash University
`Clayton 3168, Victoria
`Australia
`jaihyung@dgs.monash.edu.au
`
`Monash University
`Clayton 3168, Victoria
`Australia
`jwb @dgs.monash.edu.au
`
`Abstract
`
`data
`for
`inappropriate method
`generally
`transmission, our approachis to take advantage of
`the simplicity and robustness of flooding for
`In this paper, a new routing algorithm based on a
`routing purposes. Very short packets are sent over
`flooding method
`is
`introduced.
`Flooding
`all possible routes to search for the optimal route
`techniques have been used previously, e.g.
`for
`of the requested QoS and the data path is
`broadcasting the routing table in the ARPAnet[1]
`established via the selected route. Since the Flood
`and other special purpose networks {3][4][5).
`
`
`Routing algorithm—strictly controls the
`
`However, sending data using flooding can often
`unnecessary
`packet
`duplication,
`the
`traffic
`saturate the network (2] andit is usually regarded
`overhead caused from the flooding traffic is
`as
`an
`inefficient broadcast mechanism. Our
`minimal.
`approachis to flood a very short packet to explore
`an optimal
`route without
`relying on a: pre-
`‘established routing table, and an efficient flood
`control algorithm to reduce the signalling traffic
`overhead. This is an inherently robust mechanism
`in the face of a network configuration change,
`achieves automatic load sharing across alternative
`routes,
`and
`has
`potential
`to
`solve many
`contemporary
`routing
`problems.
`An_
`earlier
`version of
`this mechanism was
`originally
`developed for virtual circuit establishment in the
`experimental Caroline ATM LAN [6](7)
`at
`‘Monash University.
`—
`
`Use of flooding for routing purposes has been
`suggested before [3][4J(5], and it has been noted
`that it can be guaranteed to form a shortest path
`route[10]. And an earlier protocol was proposed
`and implemented for the experimental local area
`ATM network
`(Caroline [6][7]). However the
`earlier protocol had problems with scaling timer
`values, and also required complex mechanism to
`solve potential race and deadlock problem. Our
`proposal
`greatly
`simplifies
`the
`previous
`mechanism and reducesthe earlier problems.
`
`route
`the procedure for
`Chapter 2 explains
`are
`establishment
`and the simulation results
`presented in chapter 3. The advantages of the
`Flood Routing are reviewed specifically in chapter
`4, Chapter 5 concludes this paper with suggesting
`some possible application area and the future
`study issues.
`
`2. Flood Routing Mechanism
`
`Figure 1, 3, 4 show the stepwise procedure of the
`route establishment.
`
`the host A ‘is Tequesting a
`In the Figure 1,
`connectionset up to the target host B. In the initial
`
`1. Introduction
`
`technique which
`Flooding is a data broadcast
`sends the duplicates of a packet to all neighboring
`nodesin a network.It is a very reliable method of
`data transmission because many copies of the
`original data are generated during the flooding
`phase, and the destination user can double check
`the correct reception of the original data. It is also
`a robust method because no matter how severely
`the network is damaged, flooding can guarantee at
`least one copy of the data will be transmitted to
`the destination, provided a path is available.
`
`While the duplication of packets makes flooding a
`
`0-7803-3676-3/97/$10.00 © 1997 IEEE
`
`‘1418
`
`1220
`
`1220
`
`

`

`stage, a short connection request packet (CREQ)
`is delivered to the first hop router 1 and router 1
`
`Starts the flood of the CREQ packets.
`
`Figure 1
`
`
`
`
`
`
`
`
`QS
`
`
`
`
`Figure 2 CREQ Packet Format
`
`Figure 2 shows the format of the CREQ packet.
`The CREQ packet contains a connectiondifficulty
`metric (CDM)
`field, QoS parameters and the
`source & destination addresses and connection
`number. The metric can be any accumulative
`measure representing the route difficulty, such as
`hop
`count, delay,
`buffer
`length,
`etc. The
`connection numberis chosen by the source host to
`distinguish the different packet floods of the same
`source and destination.
`
`the
`When a router receives the CREQ packet,
`router matches the packet
`information with the
`internal Flood Queueto see if the same packet has
`been received before. If the CREQ packetis new,
`it records the information in the Flood Queue,
`increases the CDM value, and forwards the packet
`to all output links with adequate capacity to meet
`the QoS except the received one. Thus the flood
`of CREQ packets propagate through the entire
`network.
`
`The Flood Queue is a FIFO list which contains the
`
`information relating to the best CREQ packetthe
`router has received for each recent flood. As the
`flood packet of a new connection arrives and the
`information is pushed into the Flood Queue, the
`old information gradually moves to the rear and
`eventually is removed. The queueing delay from
`the insertion to the deletion depends on the queue
`size and the call frequency, and provided this
`delay is enough to cover the time for network
`wide flood propagation and reply, there is no need
`for a timer to wait to the completion ofthe flood.
`
`Since the CDM value is increased as the CREQ
`packet passes
`the routers,
`the metric value
`represents the route difficulty that
`the CREQ
`packet has experienced. Because of the repeated
`duplication of the packet, a router may receive
`another copy of the CREQ packet.In this case, the
`router compares the metric values of the two
`packets and if the mostrecently arrived packet has
`the better metric value, it updates the information
`in the Flood Queue and repeats the flood action.
`Otherwise
`the
`packet
`is
`discarded. As
`a
`consequence,all the routers keep the record of the
`best partial route and the output link to use for
`setting up the virtual circuit.
`
`Figure 3 shows the intermediate routers 2, 7, 8
`have chosen the links toward the router 1 as the
`best candidate link. If one of them is requested
`for the path to the source node A,the router will
`usethis link for the virtual circuit set up.
`
`
`
`Figure 3
`
`receives a CREQ
`When the destination host
`packet,
`it opens a short time-window to absorb
`‘possible further arriving CREQ packets. The
`expiration of the timer triggers the sending of the
`
`1419
`
`1221
`
`1221
`
`

`

`connection acceptance (CACC) packet-along the
`best links indicated by the CREQ packet with the
`lowest CDM. The CACC packet is relayed back
`to the source host by the routers which at the same
`timeinstall the virtual circuit via the optimal route.
`Finally, when the source host receives the CACC
`
`traffic. A simulation was carried out using various
`network conditions. Figure 5 shows the numberof
`flooding packets produced in a connectiontrial in
`a normaltraffic condition on a network consisting
`of 5 switching nodes, 9 hosts and 16 links. The
`simulation tested the event of 2000 seconds.
`
`packet, the host mayinitiate data transmission.
`
`Figure 4
`
`Note that bandwidth reservation occurs during the
`relay of the CACC packet. Itis possible that the
`available QoS will have dropped below the
`requested level in one or morelinks..In this case,
`the source may either accept the lower QoS, or,
`close the connection and try again.
`|
`
`More implementation details of the flooding
`protocol can be foundin [9].
`
`3. Simulation Result
`
`One concern of Flood Routing is whetherit will
`lead to congestion of the network bythe signalling
`
`The graph showsthatthe total number of flooding
`packets per connection converges on the lower
`bound 18 with some exceptions. This is slightly
`higher than the numberof the network links (16).
`This shows how the flood control mechanism is
`efficient in that the routers usually generate only
`one flooding packet per output
`link and this
`duplication process is rarely repeated again. As a
`result, the total number of flooding packets per
`connection is nearly same as the number of
`networklinks.
`
`Considering the small size of the flooding packet,
`the bandwidth consumed bythe signalling traffic
`is small. Suppose an ATM network using the
`Flood Routing generates 1000 calls per seconds,
`the bandwidth consumption by the signalling
`traffic will only be about 424 Kbps (= 1 K * 53
`byte) per
`link and this does not
`include any
`additional route management traffic such as the
`routing table update.
`
`the
`is observed that
`it
`From the simulation,
`average number and the maximum numberof the
`flooding packets depends on the network topology
`and thetraffic condition. If the network is simple
`topology such asa tree or a star shape,the average
`numberofthe flooding packets is nearly identical
`to the numberof the network links. If the network
`is a complex topology such as a complete mesh
`topology, and there is a high traffic load,
`the
`routers tend to generate more packets because of
`the racing of the flooding packets.
`
`Numberof Flooding Packets
`
`aBREEB
`
`
`
`Figure 5
`
`1420
`
`1222
`
`1222
`
`

`

`The connections established by Flood Routing
`successfully avoid busy links and disperse the
`communication paths to all possible routes. This
`reduced the chance of congestion and utilizes all
`network resourcesefficiently.
`
`4. Advantages of the Flood Routing
`
`The distinctive features of the Flood. Routing
`method are :
`
`It facilitates the load sharing of available
`(a)
`network resources. If many possible routes exist
`between two end points in a network, the Flood
`Routing can disperse different connections over
`different routes to share the network load. Figure
`6 showsthis example.
`
`
`
`SUBNET-1
`
`SUBNET-2
`
`Figure 6 Example of Multipath Connection
`
`In the sample network, there are more than two
`links exist between node A and H, and the node A
`used all
`links
`for different connections with
`balancing the load. More than two exterior routers
`are connecting the subnet | and the subnet 2, and
`the node H distributed the connections to all
`exterior
`routers. Therefore,
`all
`the network
`resources are utilized fully in Flood Routing
`network. This load sharing capability has been
`considered to be a difficult problem in table based
`routing algorithms.
`
`It automatically adapts to changes in the
`(b)
`network configuration. For example, if the overall
`traffic between two end points has been increased,
`the network bandwidth can simply be expanded
`by adding more links between routers. The Flood
`Routing algorithm can recognize the additional
`links and use them for sharing the load in new
`connections.
`
`(c) The method is robust. The Flood routing can
`achieve a successful connection even when the
`network is severely damaged, provided flooding
`packets can reachthe destination. Once a flooding
`
`packetreaches the destination, the connection can
`be established via the un-damaged part of the
`network which was searched by the packet. This is
`very useful property in
`networks which are
`vulnerable but which require high reliability, such
`as military networks.
`
`(d) The method is simple to manage, as it makes
`no use of routing tables. This table-less routing
`method
`does
`not
`have
`the
`problem like
`“Convergence
`time” of
`the Distance Vector
`routing [8].
`
`(e) It is possible to find the optimal route of the
`requested bandwidth or the quality of service.
`While the packet flood is progressing, bandwidth
`requirement and QoS constraints specified in the
`flooding packets are examined by the routers and
`the links that does not meet the requirements are
`excluded from the routing decision. As a result,
`the route constructed with the qualified links can
`meet the bandwidth and the QoS requirements,
`usually in the first attempt.
`
`(f) It is a loop-free routing algorithm. The only
`possible cas