MASSIVELY REPLICATING SERVICES IN
`W IDE-AREA INTERNETW ORKS
`
`by
`
`K atia Obraczka
`
`A Dissertation Presented to the
`FACULTY OF TH E GRADUATE SCHOOL
`UNIVERSITY OF SOUTHERN CALIFORNIA
`In Partial Fulfillment of the
`Requirements for the Degree
`DOCTOR OF PHILOSOPHY
`(Electrical Engineering)
`
`December 1994
`
`Copyright 1995 K atia Obraczka
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 1 of 140
`
`

`
`UMI Number: DP28279
`
`All rights reserved
`
`INFORMATION TO ALL USERS
`The quality of this reproduction is dependent upon the quality of the copy submitted.
`
`In the unlikely event that the author did not send a complete manuscript
`and there are missing pages, these will be noted. Also, if material had to be removed,
`a note will indicate the deletion.
`
`DJsssrlaiDtt P_bl.;J*n„
`
`UMI DP28279
`Published by ProQuest LLC (2014). Copyright in the Dissertation held by the Author.
`Microform Edition © ProQuest LLC.
`All rights reserved. This work is protected against
`unauthorized copying under Title 17, United States Code
`
`ProQuest LLC.
`789 East Eisenhower Parkway
`P.O. Box 1346
`Ann Arbor, Ml 48106-1346
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 2 of 140
`
`

`
`UNIVERSITY OF SOUTHERN CALIFORNIA
`THE GRADUATE SCHOOL
`UNIVERSITY PARK
`LOS ANGELES, CALIFORNIA 90007
`
`imimmua
`
`jwwiwi*
`
`0 1 3
`
`This dissertation, w ritten by
`
` Dissertation
`under the direction of hCT.
`Committee, and approved by all its members,
`has been presented to and accepted by The
`Graduate School, in partial fulfillm ent of re­
`quirements for the degree of
`D O CTO R OF PHILOSOPHY
`
`Dean of Graduate Studies
`
`Date December 7 1994
`
`DISSERTATION COMMITTEE
`
`Chairperson
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 3 of 140
`
`

`
`Dedication
`
`To my husband, grandparents,
`parents, sister, and brothers.
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 4 of 140
`
`

`
`Acknowledgments
`
`This was the most difficult and at the same tim e the most enjoyable section to
`write. As I write it, I realize that it could well be the longest section in the disser­
`tation, since I would like to acknowledge all the wonderful people I have m et and
`interacted throughout my life. Unfortunately, for lack of space, I do not explicitly
`m ention all their names.
`First and foremost, I would like to express my sincere thanks to my advisor, Dr.
`Peter Danzig, for his guidance, encouragement, support, and friendship. I was very
`fortunate to have had the opportunity to work with him during the past 4 years.
`He has contributed greatly to this dissertation and my m aturity as a researcher. I
`cannot imagine how a professor could be more dedicated to his students. He will
`always serve as a model to me.
`I wish to thank the members of my qualifying and dissertation committees: Deb­
`orah Estrin, Clifford Neumann, Shahram Ghandeharizadeh, and John Silvester. I
`would especially like to thank Professors Estrin and Silvester for their helpful com­
`ments and discussions.
`I would also like to acknowledge the Brazilian Education M inistry which provided
`me with a four-year graduate fellowship as a starting PhD student. This research
`was supported by the Advanced Research Projects Agency under contract number
`DABT63-93-C-0052.
`Several people have assisted in this research. I would like to acknowledge Dante
`DeLucia for his im plem entation of flood-d and mirror-d. Kitinon W angpattana-
`mongkol has im plemented the logical topology calculation algorithm, and Steve
`Miller has developed the simulation package I used to build my simulators.
`I sincerely thank all the members, old and new, faculty and students, of the
`Network and D istributed Systems Laboratory at USC. I was fortunate enough to
`be a member of this friendly, enjoying, and stim ulating research community. They
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 5 of 140
`
`

`
`definitely made these years at USC a lot more fun. In particular, I would like to
`thank Prof. Rafael Saavedra, Gene Tsudik, Abhjit Khale, Lee Breslau, Steve Hotz,
`Doug Fang, Danny Mitzel, Ron Cocchi, Sugih Jamin, Shih-Hao Li, Jong-Suk Ahn,
`Daniel Zappala, Brenda Tim m erm an, John Noll, Kraig Meyer, Louie Ramos and
`Ari Medvinski. Finally, Gary Frenkel, whose memory provided inspiration to move
`on and face whatever challenges may appear.
`I also wish to thank several friends, and fellow graduate students, whose friend­
`ship and support made the cultural chock effects resulting from going to graduate
`school in a foreign country a learning instead of a painful experience. I would es­
`pecially like to thank Justine Gilman, Patricia Goldweic, Alfredo Weitzenfeld, Eve
`Schooler, Bob Felderman, and Steve Schrader.
`I was also very fortunate to have a family that has always encouraged and sup­
`ported me. I will always be grateful to my parents, B ertha and Jayme, who have
`always given me more than I could ever have asked for. My sister Sandra, and my
`brothers Marcelo, Ricardo, and Eduardo have always contributed and participated
`in whatever I set out to accomplish.
`Finally, I would also like to thank my husband, Mendel, for the love, support,
`and encouragement which made it possible for me to overcome the obstacles in the
`life of a graduate student. He has put up with my fears and frustrations, and my
`finishing the PhD program is as much his accomplishment as it is mine.
`
`IV
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 6 of 140
`
`

`
`Contents
`
`D ed ica tio n
`
`A ck n ow led gm en ts
`
`L ist O f T ables
`
`L ist O f F igu res
`
`A b stract
`
`ii
`
`iii
`
`viii
`
`ix
`
`xiii
`
`1
`
`In trod u ction and M otivation
`1.1 D ata C o n sisten cy ..................................................................................................
`1.2 W hat Current Algorithms L a c k ......................................................................
`1.3 Tim estam ped, Anti-Entropy R e p lic a tio n .....................................................
`1.4
`Internet M ulticast and M ulticast Transport P ro to c o ls .............................
`1.5 Dissertation Overview and O u t l i n e ...............................................................
`
`1
`2
`4
`6
`7
`8
`
`11
`2 A H ierarchical, N etw ork-C ognizant R ep lication A rch itectu re
`2.1 O verview ................................................................................................................... 12
`2.1.1 Groups and Network T opology............................................................ 13
`2.1.2 Flooding and Peer S e le c tio n ............................................................... 13
`2.1.3 Consistency Between G ro u p s............................................................... 14
`2.1.4 Consistency State S i z e .......................................................................... 14
`2.1.5 Updating Logical T opologies............................................................... 15
`2.2 Physical T opology.................................................................................................. 16
`2.2.1 Topology D iscovery................................................................................. 16
`2.2.2 Estim ating Physical T o p o lo g y ............................................................ 18
`Im p lem en tatio n ..................................................................................................... 19
`2.3.1 F l o o d - d ..................................................................................................... 19
`2.3.2 M irro r-d ...................................................................................................... 21
`
`2.3
`
`24
`3 E valu atin g N etw ork T op ology E stim ation
`3.1 W ide-Area E x p e rim e n ts .................................................................................... 25
`
`v
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 7 of 140
`
`

`
`............................................................................................. 26
`3.2 Latency Estim ates
`3.3 Bandw idth E stim a te s......................................................................................... 31
`3.4 S u m m a r y .............................................................................................................. 35
`
`36
`4 Logical T op ologies
`4.1 D efinitions.............................................................................................................. 37
`4.2 Statem ent of the P r o b le m ............................................................................... 37
`4.3 Related W o r k ....................................................................................................... 38
`4.3.1 Steiglitz’s A lg o rith m ............................................................................. 38
`4.4 Topology Calculation A lg o rith m ..................................................................... 39
`4.4.1 Generating a Starting T o p o lo g y ......................................................... 40
`4.4.2 Applying Local T ransform ations........................................................ 43
`4.4.3 A n n e a lin g .................................................................................................. 44
`4.4.3.1 Objective F u n c tio n s ............................................................ 45
`4.4.3.2 Annealing P a r a m e te r s ......................................................... 47
`4.5 R e s u lts..................................................................................................................... 47
`4.5.1 Setting the Annealing P a ra m e te rs ..................................................... 48
`4.5.2 Objective Functions and Transformation P ro b ab ilities................. 54
`4.5.3 O ther A pproaches.................................................................................... 60
`4.5.3.1
`Fully-Connected Initial T o p o lo g y ................................... 60
`4.5.3.2 Adding Selected E d g e s ....................................................... 61
`4.5.3.3 Deleting Selected E d g e s ..................................................... 63
`Summary and D iscussion.................................................................................. 64
`
`4.6
`
`67
`5 R ep lica tio n G roups and Logical U p d a te T op ologies
`5.1 Consistency State Size and Propagation T i m e ........................................... 68
`5.1.1 Anti-Entropy R a t e ................................................................................. 68
`5.1.2 Replica A vailability.........................................................................
`
`70
`5.2 C o s t ........................................................................................................................ 80
`.............................................................................................................. 82
`5.3
`Summary
`
`87
`6 E x p lo itin g In tern et M u lticast
`6.1
`Internet M u lticast................................................................................................ 88
`6.2 M ultipoint Transport P r o to c o ls .................................................................... 89
`6.2.1 Reliable Broadcast P r o to c o l............................................................... 90
`6.2.2 M ulticast Transport P r o to c o l ............................................................ 91
`6.2.3 Reliable M ulticast Protocol
`............................................................... 92
`6.2.4 Uniform Reliable Group Communication P r o to c o l...................... 93
`6.2.5 Propagation Graph A lg o rith m ............................................................ 93
`6.2.6 M u s e ............................................................................................................ 93
`6.2.7
`I m m ............................................................................................................ 94
`6.2.8 A Transport Service for a D istributed W h iteb o ard ...................... 94
`6.2.9 Adaptive File Distribution P ro to c o l................................................. 95
`
`vi
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 8 of 140
`
`

`
`95
`.
`6.3 A M ulticast Transport Protocol for Weakly Consistent Applications
`6.3.1 Transport-Level R eliab ility ................................................................... 96
`6.3.2 Flow and Congestion C o n t r o l............................................................ 98
`6.3.3 Resource R eserv atio n ............................................................................. 99
`6.3.4 Application-Level F u n c tio n a lity ........................................................... 100
`6.4 M ulticast and Replication G ro u p s ........................................................................ 101
`6.5 S im u la tio n s ............................................................................................................... 102
`6.5.1 R e su lts............................................................................................................103
`................................................. 105
`6.5.2 Simulation Modeling Considerations
`6.5.2.1
`Source T raffic ............................................................................106
`6.5.2.2 M ulticast Drop R a t e ..............................................................107
`6.5.2.3
`Transport-Level Mechanisms
`.............................................107
`6.5.2.4 B a n d w id th ............................................................................... 108
`6.6 S u m m a r y ...................................................................................................................109
`
`Sum m ary and C onclusions
`7.1 C o n trib u tio n s .............................................
`7.2 Continuing Work and Future Directions
`
`111
`112
`115
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 9 of 140
`
`

`
`List Of Tables
`
`4.1 Logical topology costs before (BA) and after (AA) annealing. The
`initial tem perature is set at 0.08, and as cost function, we use total
`edge cost and diam eter in edge cost................................................................. 56
`4.2 Logical topology costs before (BA) and after (AA) annealing. The ini­
`tial tem perature is set at 200, and we use total edge cost as objective
`function...................................................................................................................... 58
`4.3 Logical topology costs before (BA) and after (AA) annealing. The
`initial tem perature is set at 0.08, and we use total edge cost and
`diam eter in hop count as objective function.................................................. 58
`4.4 Logical topology costs before (BA) and after (AA) annealing. The
`initial topology is fully-connected, and we use total edge cost as ob­
`jective function. The initial tem perature is set at 200
`............................ 61
`4.5 Logical topology costs after adding 10 extra edges to the initial topol­
`ogy. Links are added according to diam eter in edge cost.......................... 62
`4.6 Logical topology costs after adding 10 extra edges to the initial topol­
`ogy. Links are added according to diam eter in hop count........................ 63
`4.7 Logical topology costs after adding 10 extra edges to the initial topol­
`ogy. Links are added according to diam eter in hop count. The cheap­
`est link is selected every tim e............................................................................. 64
`
`6.1 Reliable m ultipoint transport protocol for weakly-consistent applica­
`tions: features and mechanisms.............................................
`
`110
`
`vm
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 10 of 140
`
`

`
`List Of Figures
`
`1.1 D ata Consistency Spectrum .................................................................................
`
`2
`
`2.1 Replication groups showing logical versus physical topologies.................. 13
`2.2 Example flood-d site and group configuration................................................ 21
`2.3 Flood-d’s group monitoring tool......................................................................... 22
`2.4 M irror-d m aster and slave copies........................................................................ 23
`
`3.1 Flood-d’s latency estim ates and traceroute’s round-trip tim e measure­
`m ents.......................................................................................................................... 27
`3.2 Flood-d’s latency estimates and traceroute’s round-trip time m easure­
`m ents.......................................................................................................................... 29
`3.3 Flood-d’s latency estimates and traceroute’s round-trip time measure­
`m ents.......................................................................................................................... 30
`3.4 Flood-d’s bandw idth estim ates........................................................................... 31
`3.5 Flood-d’s bandw idth estim ates........................................................................... 33
`3.6 Flood-d’s bandw idth estim ates........................................................................... 34
`
`4.1 Generating a feasible starting topology................................................................. 41
`4.2 Checking topology feasibility............................................................................... 42
`4.3 Possible Transform ations....................................................................................... 44
`4.4 The annealing algorithm ....................................................................................... 46
`4.5 The effects of the initial tem perature T0 in the annealing process. For
`T0 — .08, T0 = .8, and T0 = 8, we plot total edge cost, diam eter, and
`diam eter in hop count when generating 2-connected graphs using the
`combination of edge cost and diam eter as objective function.................. 49
`4.6 The effects of the initial tem perature To in the annealing process. For
`T0 = .08, To = .8, and To = 8, we plot total edge cost, diam eter, and
`diam eter in hop count when generating 3-connected graphs using the
`combination of edge cost and diam eter as objective function.................. 50
`4.7 The effects of the initial tem perature T0 in the annealing process. For
`T0 = .08, T0 = .8, and T0 = 8, we plot total edge cost, diam eter,
`and diam eter in hop count when generating 2-connected graphs using
`only edge cost as objective function................................................................. 51
`
`IX
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 11 of 140
`
`

`
`4.8 The effects of initial tem perature T in the annealing process. For
`T = .08, T = .8, and T = 8, we plot total edge cost, diam eter, and
`diam eter in hop count when generating 3-connected graphs using only
`edge cost as objective function........................................................................... 52
`4.9 The effects of tem perature decrease rate D in the annealing process.
`For D — .4, D = .1, and D = .01, we plot total edge cost, diam eter,
`and diam eter in hop count when generating 2-connected graphs using
`the combination of edge cost and diam eter as objective function. . . . 53
`4.10 The effects of tem perature decrease rate D in the annealing process.
`For D = .4, D = .1, and D — .01, we plot total edge cost, diam eter,
`and diam eter in hop count when generating 2-connected graphs using
`only edge cost as objective function................................................................. 54
`4.11 The effects of different transform ation probabilities in the annealing
`process. We plot total edge cost (log scale), diam eter, and diam eter
`in hop count using different transform ation probabilities for D = 0.01
`and D = 0.4. To is set at 0.08, and as cost function, we use total edge
`cost and diam eter in edge cost........................................................................... 55
`4.12 The effects of different transform ation probabilities in the annealing
`process. We plot total edge cost (log scale), diam eter, and diam eter
`in hop count using different transform ation probabilities for D = 0.01
`and D = 0.4. To is set at 200, and we use total edge cost as objective
`function...................................................................................................................... 57
`4.13 The effects of different transform ation probabilities in the annealing
`process. We plot total edge cost (log scale), diam eter, and diam eter
`in hop count using different transform ation probabilities for D = 0.01
`and D = 0.4. T0 is set at 0.08, and we use total edge cost and diam eter
`in hop count as objective function.................................................................... 59
`
`5.1 Average consistency state size (in number of update messages), tim e
`to propagate updates and acknowledgments for different group sizes.
`In all 3 graphs, the x-axis is the simulation tim e scale in multiples
`of when updates are generated. The global update, anti-entropy, and
`failure rates were kept constant......................................................................... 69
`5.2 Average consistency state size sample paths (in num ber of update
`messages) for different group sizes. In both graphs, the x-axis is the
`simulation tim e scale in multiples of when updates are generated. The
`upper graph employs a faster anti-entropy rate (ae ra te )............................ 71
`5.3 Cum ulative probability distribution for propagating updates to all
`replicas consistently.
`In both graphs, the x-axis is the simulation
`tim e scale in multiples of when updates are generated. The upper
`graph employs a faster anti-entropy rate (ae rate)........................................ 72
`
`x
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 12 of 140
`
`

`
`5.4 Cum ulative probability distribution for receiving acknowledgments
`from all replicas and purging consistency state. In both graphs, the
`x-axis is the simulation time scale in multiples of when updates are
`generated. The upper graph employs a faster anti-entropy rate (ae
`rate)............................................................................................................................. 73
`5.5 Average consistency state size (in num ber of update messages).
`In
`all three graphs, the x-axis is the simulation tim e scale in multiples
`of when updates are generated. In the middle and bottom plots, the
`global anti-entropy rate (ae rate) is 2 and 4 times the rate of the top
`p lo t.............................................................................................................................. 74
`5.6 Cum ulative probability distribution for propagating updates to all
`replicas. In all three graphs, the x-axis is the simulation tim e scale in
`multiples of when updates are generated.In the middle and bottom
`plots, the global anti-entropy rate (ae rate) is 2 and 4 times the rate
`of the top plot.......................................................................................................... 75
`5.7 Cum ulative probability distribution for receiving acknowledgments
`from all replicas.
`In all three graphs, the x-axis is the simulation
`tim e scale in multiples of when updates are generated.In the middle
`and bottom plots, the global anti-entropy rate (ae rate) is 2 and 4
`times the rate of the top plot.............................................................................. 76
`5.8 Average consistency state size (in num ber of update messages).
`In
`both graphs, the x-axis is the simulation tim e scale in multiples of
`when updates are generated. In the bottom graph, replicas stay down
`longer than in the upper graph.......................................................................... 77
`5.9 Cum ulative probability distribution for propagating updates to all
`replicas. In both graphs, the x-axis is the simulation tim e scale in
`multiples of when updates are generated. In the bottom graph, repli­
`cas stay down longer than in the upper graph.............................................. 78
`5.10 Cum ulative probability distribution for receiving acknowledgments
`from all replicas. In both graphs, the x-axis is the sim ulation tim e
`scale in multiples of when updates are generated.
`In the bottom
`graph, replicas stay down longer than in the upper graph...................... 79
`5.11 Cum ulative probability distributions for the total cost of propagating
`updates to all replicas using cost-based and random partner selection
`policies for different group sizes.......................................................................... 81
`5.12 Cum ulative probability distributions for the time to propagate up­
`dates to all replicas using cost-based and random partner selection
`policies for different group sizes......................................................................... 83
`5.13 Cum ulative probability distributions for the total cost of propagating
`updates to all replicas using cost-based and random partner selection
`policies for different group sizes.......................................................................... 84
`
`XI
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 13 of 140
`
`

`
`5.14 Cumulative probability distributions for the tim e to propagate up­
`dates to all replicas using cost-based and random partner selection
`policies for different group sizes......................................................................... 85
`
`6.1 Total communication cost for propagating messages to all replicas in
`a replication group as a function of the m ulticast drop rate using cost-
`based and random partner selection policies. The top, middle, and
`bottom graphs use 50-, 100-, and 200-replica groups, respectively.
`. . 104
`6.2 Total communication cost for propagating messages to all replicas in
`a replication group as a function of the m ulticast drop rate using cost-
`based and random partner selection policies. The middle and bottom
`graphs use update rates 2 and 4 times higher than the top graph,
`respectively.................................................................................................................. 105
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 14 of 140
`
`

`
`Abstract
`
`Existing and future Internet information services will provide large, rapidly evolv­
`ing, highly accessed, yet autonomously managed information spaces. Internet news,
`perhaps, is the closest existing precursor to such services. It perm its asynchronous
`updates, is replicated at thousands of autonomously managed sites, manages a large
`database, yet presents adequate response time. It gets its performance through mas­
`sive replication. O ther Internet services, such as archie, and W W W /M osaic m ust
`massively replicate their data to deliver reasonable performance.
`The problem of replicating information th at can be partitioned into autonomously
`m anaged subspaces has well-known solutions. Naming services such as the Domain
`Name Service (DNS) and Grapevine use adm inistrative boundaries to partition their
`hierarchical name space into domains. These domains need only be replicated in a
`handful of services for adequate performance.
`On the other hand, efficient massive replication of wide-area, flat, yet autonomously
`m anaged data is yet to be dem onstrated, since existing replication algorithm s do not
`address the scale and autonomy of today’s internetworks. They either ignore net­
`work topology issues entirely, or rely on system adm inistrators to hand-configure
`replica topologies over which updates travel. Lampson’s widely cited Global Name
`Service (GNS) propagates updates over manually configured topologies. However,
`the complexity of manually configuring fault-tolerant update topologies th at use the
`underlying physical network efficiently increases with the scale of today’s internet­
`works.
`Furtherm ore, GNS-like replication mechanisms also manage single, flat groups of
`replicas. W hile this is appropriate for applications with 20 to 30 replicas th at operate
`within single adm inistrative boundaries, it is unrealistic for wide-area, massively
`replicated services whose replicas spread throughout the Internet’s thousands of
`adm inistrative domains.
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 15 of 140
`
`

`
`This research investigates scalable replication mechanisms for wide-area, au­
`tonomously m anaged services. We propose a new architecture th at extends existing
`replication mechanisms to explicitly address scalability and autonomy. We target
`replication degrees of thousands or even tens of thousands of weakly-consistent repli­
`cas.
`
`Im itating the Internet’s adm inistrative domain routing hierarchy, the proposed
`architecture organizes replicas into m ultiple replication groups. Organizing replicas
`into m ultiple groups limits the size of the consistency state each replica keeps. It
`also preserves autonomy, since it insulates replication groups from other groups’
`adm inistrative decisions.
`We argue th at efficient replication algorithms keep replicas weakly consistent
`by flooding data between them. Our architecture autom atically builds a logical
`update flooding topology over which replicas propagate updates to other replicas in
`their group. Replicas in a group estim ate the underlying physical topology. Using
`the estim ated network topology, we compute a logical update topology th a t is k-
`connected for resilience, tries to use the physical network efficiently, and yet restricts
`update propagation delays. Replication groups com pute and adopt a new update
`topology every tim e they detect changes in group membership and network topology.
`We describe our architecture in detail and its im plem entation as a hierarchical,
`network cognizant replication tool, which we im plemented as part of the Harvest
`resource discovery system. Through simulations, we investigate the benefits of us­
`ing hierarchical replication groups and distributing updates over the logical update
`topologies our architecture computes. We present the results from the wide-area
`experim ents we conducted to evaluate our network topology estim ation strategy.
`We also present our logical topology calculation algorithm in detail, and the results
`obtained when running our algorithm over random ly generated topologies. Finally,
`we explore the use of internet m ulticast as the underlying update propagation mech­
`anism. We argue th a t since having a single m ulticast group with all replicas of a
`service will not scale, each replication group can be m apped to a m ulticast group.
`Through corner replicas, updates in one group make their way to all groups.
`Lampson’s Global Name Service has been widely accepted as the solution to
`the problem of replicating wide-area, distributed, weakly-consistent applications.
`However, almost 10 years ago, when Lampson wrote “... The system I have in mind
`
`xiv
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 16 of 140
`
`

`
`is a large one, large enough to encompass all the computers in the world and all the
`people that use them ...” , he did not anticipate that the Internet would grow as fast
`as it did. The main contribution of this dissertation is to make GNS-like services
`work in today’s exponentially-growing, autonomously-managed internetworks.
`
`xv
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1010, p. 17 of 140
`
`

`
`Chapter 1
`
`Introduction and Motivation
`
`Existing and future Internet information services will provide large, rapidly evolving,
`highly accessed, yet autonomously managed information spaces. Achieving adequate
`perform ance demands th at these services and their data be replicated in hundreds
`or thousands of autonomous networks.
`it manages a
`Take the Internet news distribution system [31] as an example:
`highly dynamic, weakly consistent, gigabyte database replicated at thousands of
`autonomous adm inistrative domains, yet responds to queries in seconds. In contrast,
`archie [22], a directory service for Internet FT P archives, can take fifteen minutes
`to answer queries against a much smaller, 150 megabyte database. The difference
`between archie’s and network news’ performance is massive replication; there are
`only about 30 replicas of archie. As W W W /M osaic [2], archie and other upcoming
`applications