SUBMITTED TO THE DEPARTMENT OF r;LF;CTRI(.AL ENGINEnm,G AND THE COMMITTEE ON GRADUATE Ht:DlES

3.1 Introduction •••• 3.2 Separately Addressed Packets

Table of Contents 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 Addressing Multi-Destination Hot Potato Forwarding Source Based Forwarding Reverse Path Forwarding Forwarding along a Spanning Tree Reliability of Broadcast Routing Protocols Global vs Subgroup Broadcast Routing Algorithms Conclusions • • •

4.1 Introduction ••••• 4.2 Performance Measures 4.3 Regular Graphs ••• 4.4 Separately Addressed Packets (SAP) 4.5 Multi-Destination Addressing (MDA) and Source Based Forwarding (SBF) Hot Potato Forwarding Reverse Path Forwarding Minimal Spanning Tree Forwarding Comparison of the Different Schemes Performance in the ARPANET Conclusions •••••••• 4.6 4.7 4.8 4.9 4.10 4.11

Table of Contents 5.3 5.4 5.5 File Migration •• Multiple Copies of a File Conclusions

Acknowledgments I am very grateful for the support and guidance provided by several people in undertaking this research program Firstly I would like to thank Professor Michael Miller and Professor Ken Lever from the Institute for Telecommunications Research at the University of South Australia for their enthusiasm and the excellent postgrad uate study environment they provided Also I wish to thank my employers Mr Neil Bryans Dr Tony Bedford Dr Stephen Cook and Mr Manfred Heigl at the Defence Science and Technology Organisation for providing the opportunity and exibility to undertake this study I wish to extend a very special thanks to my supervisor Dr Arek Dadej for the many constructive discussions we have had and his enthusiastic support that has been invaluable towards producing this thesis Finally I would like to thank Jonathon Shewchuk from the School of Computer Science at Carnegie Mellon Uni versity for permission to use his software to calculate the Delaunay triangulations used in Chapter 

network  This algorithm seeks to optimise global delay for the entire network whereas the ARPANET algorithms minimise delay for individual users Merlin and Segall proposed an algorithm  following Gallagers approach using distributed computation to ensure that loop free paths are established through the network   The problem of packets looping back and revisiting previous nodes can arise in distributed techniques during update periods while a distributed algorithm converges to the true shortest path Packet looping as described here is undesirable because it increases trac load and packet delay in the network Under certain conditions such as link failure occurring in a chain of nodes nodes uptree from the destination can become isolated This results in packet looping because nodes exchange new distance values incremented by a link cost unit each cycle unaware that the destination is actually isolated This is often referred to as the countingtoinnity problem which is evident if no upper nite bound is placed on the distance values  p  In addition to being loop free the MerlinSegall algorithm is also event driven with each destination triggering the distributed updates for all routes to that destina tion Formal description and validation of distributed network protocols including the MerlinSegall algorithm have been published    Another distributed al gorithm using link change events to trigger an update protocol rather than using periodic updates is described and proven correct by Tajibnapis   Jae and Moss proposed a distributed shortest path algorithm oering improved performance in speed of convergence and ensuring loop free paths after a change in topology  This algorithm consisted of two procedures an Independent Update Procedure

based on a distributed version of FordFulkersons algorithm    pp   Future Internet routing is expected to use the Open Shortest Path First

algorithms It is reasonable to conclude that while distributed nonhierarchical shortest path al gorithms are less costly to operate in a reasonably static environment ooding may consume less resources in a very dynamic network This is especially true if the shortest path algorithm is unable to maintain accurate routing tables due to high rates of change in link cost and topology By quantifying the relative routing costs between these two classes of routing procedure it may be possible to identify the point at which the rate of change in a network is such that it is preferable to use one type of algorithm over another The objective in the above is to maximise the probability of successfully reaching a destination in a large and possibly very dy 

work conditions A shortest path algorithm is considered suitable for operation in static and quasistatic environments although it is anticipated that this type of al gorithm will either be unable to keep up with rapid changes in network conditions or do so with a high routing cost So a ood search routing procedure is selected to provide improved characteristics under the more dynamic conditions A distributed minimum delay shortest path algorithm exhibits superior surviv ability characteristics over centralised schemes and by incorporating output queue length metrics into the link cost function network congestion can be reduced How ever incorrect trac load information leading to the choice of inferior more con gested routes typically has less serious consequences than incorrect topological information resulting in the possible choice of nonexistent routes  p  Therefore a minimum hop shortest path algorithm is adopted throughout this the sis where link costs are set to constant values  link available or link failed

I also, together with a number of my colleagues at M.I.T., developed Chord, one of the four original distributed hash tables protocols, which address a fundamental problem in peer-to-peer networks (how to efficiently locate a node that stores particular data items).

Since long before the patent applications were filed, graph theory has been actively applied in a variety of industries and fields, including integrated circuit design, operations research (scheduling), and computer networks.

A regular graph has all of its edges uniformly distributed; therefore, reducing the probability of the occurrence of bottlenecks.”) Also, long before July 2000, a POSITA would have known the generalized formulas for maintaining an m-regular non-complete topology when adding or subtracting a node.

Shoubridge also demonstrates familiarity with the use of flooding for broadcasting information to all (rather than just one) nodes in the network as evidenced by its citation to Ex. 1007 (John M. McQuillan, et al., “The New Routing Algorithm for the ARPANET,” IEEE Transactions Comms., Vol.

A POSITA would have been motivated to do so for any number of reasons that were also well known in the art, including, for example, ensuring the compatibility and usefulness of the disclosed communications network, given the popularity and mass reach of the Internet at the time.

Pursuant to 37 C.F.R. §§ 42.6(e) and 42.105(a), this is to certify that on March 11, 2016, I caused to be served a true and correct copy of the foregoing

password for the thumb drive is: winstonIPRs*

Respectfully submitted, /Andrew R. Sommer/ Andrew R. Sommer (Reg. No. 53,932) Counsel for Petitioners Activision Blizzard, Inc., Electronic Arts Inc., Take-Two Interactive Software, Inc., 2K Sports, Inc., and Rockstar Games, Inc.

If a portal computer is located at that search depth with a process that is fully connected to the broadcast channel, then the routine returns an indication of success.

In block 1108, the routine sets the expected number of holes (i. e., empty internal connections) for this process based on the received response.

In blocks 1804-1807, the routine loops attempting to send a connection edge search call internal message (i. e., connection_edge_search_call) to a randomly selected neighbor.

Examples of client/server middleware systems include remote procedure calls (“RFC”), database servers, and the common object request broker architecture (“CORBA”).

As discussed below in detail, the broadcast technique uses a hashing algorithm to select the port number order, which may result in improved performance.