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 Cho et 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 as claim 1, and additionally requires that each network
`
`participant fon/vards broadcast messages that it receives to its neighbor participants.
`
`See the discussion of claim 1 for the description of those steps. Note, however, that
`
`Steele does not disclose that each network participant fon/vards 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 how that affects
`
`network configuration. The system taught by Steele remains silent regarding the actual
`
`passing of data between nodes. Nonetheless, flood routing (i.e. broadcasting
`
`messages from each node to each neighboring node in a network) is well known, as
`
`I evidenced by Cho.
`
`In a similar art, Cho discloses that flood routing is well known (p.
`
`1418, Introduction, 1] 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 advantages of using flood routing to send information between nodes in
`
`the system taught by Steele, because flood routing is a very reliable and robust method
`
`of data transmission (see Cho, p. 1418, Introduction, 1] 1). Therefore, it would have
`
`been obvious to use flood routing to pass information in the network taught by Steele.
`
`BUNGIE - EXHIBIT 1002 P211“: 5 of 5
`
`1206
`
`1206
`
`BUNGIE - EXHIBIT 1002 Part 5 of 5
`
`

`

`Application/Control Number: 09/629,570
`
`Page 6
`
`Art Unit: 2153
`
`In considering claim 33, Steele further discloses that each participant is
`
`connected to 4 participants (See Figs. 5-6, wherein each participant is connected to 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. (US. Patent No. 6,490,247, hereinafter “Gilbert”) in view
`
`of Hughes et al. (US. 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 (see col. 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.
`
`in a similar art, Hughes discloses a network for
`
`1207
`
`1207
`
`

`

`Application/Control Number: 09/629,570
`
`Page 7
`
`Art Unit: 2153
`
`interconnecting nodes for communication across the network, wherein the nodes can be
`
`connected in a hypercube-type topology, or in some other type 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
`
`obvious to use the technique disclosed by Gilbert for connecting new participants in a
`
`system such as the one taught by Hughes.
`
`In considering claim 2, Hughes further discloses that each participant is
`
`connected to 4 participants (col. 14, lines 25-30, “hypercube”; col. 15, lines 45-52,
`
`“nodes 2 are connected in an arbitrary manner to up to a fixed number n 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 that is
`
`contacted by the additional node does not matter," and can simply be “the first node on
`
`1208
`
`1208
`
`

`

`Application/Control Number: 09/629,570
`
`Page 8
`
`Art Unit: 2153
`
`the list"). Although Gilbert does not explicitly state that selection is done randomly, the
`
`node is effectively being selected randomly, since any node can be first on the list. The
`
`same result would be achieved by selecting a node randomly from somewhere else 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.
`
`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 nodes in 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 whichever node is arbitrarily and thus randomly
`
`selected).
`
`In considering claim 5, Gilbert further discloses that when a participant (“primary
`
`node”) receives the message, it sends the message to a selected participant to which it
`
`is connected (“adjacent node," col. 6, lines 50-59). However, Gilbert does not disclose
`
`that the message is sent to a randomly selected participant. Nonetheless, Gilbert
`
`discloses that the actual initial 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 as it 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/Control Number: 09/629,570
`
`Page 9
`
`Art Unit: 2153
`
`over the other, is thus a matter of preference, and does not render the 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 computer to 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
`
`connected participant 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 nodes is then between the 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 network in the participant adding system
`
`taught by Gilbert and Hughes to be the 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
`
`Page 10
`
`Art Unit: 2153
`
`In considering claim 12, although Hughes does not explicitly teach TCP/IP,
`
`Examiner takes official notice that TCP/IP is a standard well known protocol 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 nodes of the graph that are connected where p is half of m
`
`(p. is 1, see col. 6, lines 30-42, wherein a pair of adjacent nodes is identified);
`
`Disconnecting the nodes of each identified pair from each other (col. 7, lines 7-8),
`
`and
`
`Connecting each node of the 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
`
`graph is at least 4-connected and 4-regular. Nonetheless, the use of 4-connected and
`
`4-regular networks wherein nodes can be added to the network is well known, as
`
`1211
`
`1211
`
`

`

`Application/Control Number: 09/629,570
`
`Page 11
`
`Art Unit: 2153
`
`evidenced by Hughes.
`
`In a similar art, Hughes discloses a network for interconnecting
`
`nodes for communication across the network, wherein the nodes can be connected in a
`
`hypercube-type topology, or in some other type 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 extending the node
`
`addition method taught by Gilbert (i.e. disconnecting p pairs of nodes node connections
`
`and connecting the newly disconnected links 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 that is
`
`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 can be first on the list. The
`
`same result would be achieved by selecting a node randomly from somewhere else on
`
`1212
`
`1212
`
`

`

`Application/Control Number: 09/629,570
`
`Page 12
`
`Art Unit: 2153
`
`the list. Thus, the limitation of selecting the node randomly does not render the claimed
`
`invention patentably distinct over the method taught by Gilbert.
`
`In considering claim 16, Hughes further discloses that the nodes are computers
`
`and the connections are point-to-point connections (abstract).
`
`In considering claim 17, both Gilbert and Hughes further 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 Cho et al. (“A Flood
`
`Routing Method for Data Networks," lClCS ’97, hereinafter “Cho”).
`
`In considering claim 32, the claim contains a computer readable medium for
`
`performing the same steps as claim 1, and additionally requires that each network
`
`participant fon/vards broadcast messages that it receives to its neighbor participants.
`
`See the discussion of claim 1 for the description of those steps. Note, however, that
`
`neither Gilbert nor Hughes disclose that each network participant fonivards broadcast
`
`messages that it receives to its neighbor participants. Nonetheless, flood routing (i.e.
`
`broadcasting messages from each node to each neighboring node in a network) is well
`
`known, as evidenced by Cho.
`
`In a similar art, Cho discloses that flood routing is well
`
`known (p. 1418, Introduction, 1] 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/Control Number: 09/629,570
`
`Page 13
`
`Art Unit: 2153
`
`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 advantages of using flood routing to send information between nodes in
`
`the system taught by Gilbert and Hughes, because flood routing is a very reliable and
`
`robust method of data transmission (see Cho, p. 1418, lntroduction,1l 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, Hughes further discloses that each participant is
`
`connected to 4 participants (col. 14, lines 25-30, “hypercube”; col. 15, lines 45-52,
`
`“nodes 2 are connected in an arbitrary manner to 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 that is
`
`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 can be first on the list. The
`
`same result would be achieved by selecting a node randomly from somewhere else 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
`
`Page 14
`
`Art Unit: 2153
`
`In considering claim 35, 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 nodes in 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 whichever node is arbitrarily and thus randomly
`
`selected).
`
`In considering claim 36, Gilbert further discloses that when a participant (“primary
`
`node”) receives the message, it sends the message to a selected participant to which it
`
`is connected (“adjacent node,” col. 6, lines 50-59). However, Gilbert does not disclose
`
`that the message is sent to a randomly selected participant. Nonetheless, Gilbert
`
`discloses that the actual initial 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 as it 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
`
`over the other, is thus a matter of preference, and does not render the 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 computer to 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”).
`
`1215
`
`1215
`
`

`

`Application/Control Number: 09/629,570
`
`Page 15
`
`Art Unit: 2153
`
`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 connected participant 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 nodes is then between the primary node
`
`and an adjacent node to the primary node”).
`
`Allowable Subject Matter
`
`7.
`
`As allowable 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 be allowable if rewritten to include all of the limitations of
`
`the base claim and any intervening claims, and if the base claims were rewritten to
`
`overcome the rejection(s) under 35 U.S.C. 112, second paragraph, set forth in this
`
`Office action.
`
`The following is a statement of reasons for the indication of allowable subject
`
`matter:
`
`the prior art of record falls 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
`
`Page 16
`
`Art Unit: 2153
`
`The prior art made of record and not relied upon is considered pertinent to
`
`Conclusion
`
`applicant’s disclosure.
`
`Any inquiry concerning this communication or earlier communications from the
`
`examiner should be directed to Bradley Edelman whose telephone number is (703) 306-
`
`3041. The examiner can normally be reached on Monday to 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 where this application or proceeding is assigned are as follows:
`
`For all correspondences: (703) 872-9306.
`
`Any inquiry of a general nature or relating to the status of this application or
`
`proceeding should be directed to the receptionist whose telephone number is (703) 305-
`
`3900.
`
`BE
`
`January 6, 2004
`
`1217
`
`1217
`
`

`

`
`
`Notrce of References Cited
`
`Application/Control No.
`
`if.
`
`09/629570
`Examiner
`Bradley Edelman
`U.S. PATENT DOCUMENTS
`
`Applicant(s)/Patent Under
`Reexamination
`HOLT ET AL.
`Art unit
`2153
`
`Page 1 0f2
`
`
`c...t3%:::::t.t:m:; “
`us-eAgo-w B1
`us-6,553,02081
`us-esow B1
`us-wwm
`mow-063A
`us-6.505.28981
`L's-5.09923“
`Uta-5.732086
`us-smzzA
`use-WM
`
`
`
` A
`
`C
`
`F G H
`
`J
`
`CCC
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`Document Number
`Country Code-Number—Kind Code
`
`Date
`MM-YYYY
`
`COWW
`
`.
`.
`C'ass'ficat'on
`
`
`
`
`
`
`
`
`
`June 1996, 1996 IEEE International Conference on Communications, Vol. 3, pp. 1581-1585.
`
`NON-PATENT DOCUMENTS
`
`Include as applicable: Author. Title Date, Publisher, Edition or Volume, Pertinent Pages)
`
`Cho et al., "A Flood Routing Method for Data Networks," September 1997, Proceedings of 1997 lntemational Conference on
`Information, Communications and Signal Processing, Vol. 3, pp. 1418-1422.
`
`Bandyopadhyay et al., "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 Computer Science,
`1992, pp. 70-79.
`
`Shiokawa et al., "Performance Analysis of Network Connective Probability of Multihop Network under Correlated Breakage,"
`
`'A copy of this reference is not being furnished with this Office action. (See MPEP § 707,05(a).)
`Dates in MM-YYYY format are publication dates. Classifications may be US or foreign.
`US. Patent and Trademark Office
`PTOv892 (Rev. 01-2001)
`
`Notice of References Cited
`
`Part of Paper No. 9
`
`1218
`
`1218
`
`

`

` Applicant(s)/Patent Under
`
`09/629,570
`
`
`Application/Control No. ‘
`Reexamination
`HOLT ET AL.
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`—
`
`I I
`
`-
`I -
`I -
`Ifl-
`IE-
`I-
`I-
`I-
`II-
`I-
`I-
`I-
`I
`_
`FOREIGN PATENT DOCUMENTS
`
`
`
`IEEE GLOBECOM '90, 'Communications: Connecting the Future,‘ Vol. 1, pp. 459-463.
`
`II
`I
`
`Komine et al., "A Distributed Restoration Algorithm for Multiple-Link and Node Failures of Transport Networks," December 199
`
`'A copy of this reference is not being furnished with this Office action. (See MPEP § 707.05(a).)
`Dates in MM-YYYY format are publication dates. Classifications may be US or foreign.
`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 Procsslng
`ICICS '97
`Singapore, 9-12 September 1997
`
`BFHA
`
`A Flood Routing Method for Data Networks
`
`Jaihyung Cho
`
`Monash University
`Clayton 3168, Victoria
`Australia
`
`jaihyung@dgs.monash.edu.au
`
`James Breen
`
`Monash University
`Clayton 3168, Victoria
`Australia
`
`jwb@dgs.monash.edu.au
`
`Abstract
`
`In this paper, a new routing algorithm based on a
`flooding method
`is
`introduced.
`Flooding
`techniques have been used previously, e.g.
`for
`broadcasting the routing table in the ARPAnet [l]
`and,other special purpose networks [3][4][5].
`However, sending data using flooding can often
`saturate the network [2] and it is usually regarded
`as
`an
`inefficient broadcast mechanism. Our
`
`approach is 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.
`'
`’
`
`1. Introduction
`
`technique which
`Flooding is a data broadcast
`sends the duplicates of a packet to all neighboring
`nodes in 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/31000 © 1997 IEE
`
`data
`for
`inappropriate method
`generally
`transmission, our approach is to take advantage of
`the simplicity and robustness of flooding for
`routing purposes. Very short packets are sent over
`all possible routes to search for the optimal route
`of the requested QoS and the data path is
`established via the selected route. Since the Flood
`Routing
`algorithm strictly
`controls
`the
`unnecessary
`packet
`duplication.
`the
`traffic
`overhead caused from the flooding traffic is
`minimal.
`
`Use of flooding for routing purposes has been
`suggested before [3][4][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 reduces the earlier problems.
`
`the procedure for
`Chapter 2 explains
`establishment
`and the simulation results
`
`route
`are
`
`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 l. 3, 4 show the stepwise procedure of the
`route establishment.
`
`the host A is requesting a
`In the Figure 1,
`connection set up to the target host 8. In the initial
`
`‘1418
`
`1220
`
`1220
`
`

`

`stage, a short connection request packet (CREQ)
`is delivered to the first hop router I and router 1
`starts the flood of the CREQ packets.
`
`
`
`Figure 2 CREQ Packet Format
`
`Figure 2 shows the format of the CREQ packet.
`The CREQ packet contains a connection difficulty
`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 number is 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 Queue to see if the same packet has
`been received before. If the CREQ packet is 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 packet the
`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 of the 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 most recently 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 I as the
`best candidate link. If one of them is requested
`for the path to the source node A. the router will
`use this 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
`time install the virtual circuit via the Optimal route.
`Finally, when the source host receives the CACC
`packet, the host may initiate data transmission.
`
`
`
`Figure 4
`
`Note that bandwidth reservation occurs during the
`relay of the CACC packet. It is possible that the
`available QoS will have dropped below the
`requested level in one or more links... In this case,
`the source may either accept the lower QoS, or]
`close the connection and tryagain.
`_
`
`More implementation details of the flooding
`protocol can be found in [9].
`
`3. Simulation Result
`
`One concern of Flood Routing is whether it will
`lead to congestion of the network by the signalling
`
`traffic. A simulation was carried out using various
`network conditions. Figure 5 shows the number of
`flooding packets produced in a connection trial in
`a normal traffic condition on a network consisting
`of 5 switching nodes, 9 hosts and 16 links. The
`simulation tested the event of 2000 seconds.
`
`The graph shows that the total number of flooding
`packets per connection converges on the lower
`bound 18 with some exceptions. This is slightly
`higher than the number of 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
`network links.
`
`Considering the small size of the flooding packet,
`the bandwidth consumed by the 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 (= l 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 number of the
`flooding packets depends on the network topology
`and the traffic condition. If the network is simple
`topology such as a tree or a star shape, the average
`number 'of the flooding packets is nearly identical
`to the number of 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.
`
`Number of Flooding Packets
`
`
`
`1200
`
`1400
`
`1600
`
`1800
`
`2000
`
`- 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 resources efficiently.
`
`4. Advantages of the Flood! Routing
`
`The distinctive features of the Flood- Routing
`method are:
`4
`
`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 shows this example.
`
`
`
`SUBNET—l
`
`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 l 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 reach the destination. Once a flooding
`
`packet reaches 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.
`
`(:1) 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].
`
`(c) 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