IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 1 of 185
`
`

`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 2 of 185
`
`

`
`EXHIBIT A
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 3 of 185
`
`

`
`Adaptive Strategies For Routing In
`
`Dynamic Networks
`
`Peter John Shoubridge
`
`Bachelor of Engineering in Electronic Engineering
`
`School of Physics and Electronic Systems Engineering
`
`Faculty of Information Technology
`
`University of South Australia
`
`Thesis submitted for the degree of Doctor of Philosophy
`
`December(cid:2) 
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 4 of 185
`
`

`
`Contents
`
` Introduction
`
` (cid:2) Thesis Objectives (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
` (cid:2) Achievements (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
` (cid:2) Thesis Outline (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
` Cost of Routing in Networks
`
`(cid:2) Routing in Communication Networks (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Classications of Routing Procedures (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(cid:2)(cid:2) Deterministic and stochastic routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2)(cid:2) Centralised and distributed routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2)(cid:2) Hierarchical and nonhierarchical routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2)(cid:2) Adaptive and nonadaptive routing
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Collaborative and independent procedures (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Shortest Path Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Flood Search Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Overheads Associated with Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Overheads in centralised and distributed routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Overheads in hierarchical and nonhierarchical routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Overheads in adaptive and nonadaptive routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Routing table maintenance in adaptive schemes
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Cost comparison of ooding and shortest path routing (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Routing Cost and Network Capacity (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
` Combining Routing Procedures
`
` 
`
` (cid:2) Future Demands on Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`i
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 5 of 185
`
`

`
` (cid:2) Background of Combined Routing Procedures
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Constituent Protocols for Combined Routing Strategies (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) (cid:2) Distributed minimum hop algorithm (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) (cid:2)
`
`Jae(cid:8)Moss algorithm implemented as minimum hop (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) (cid:2) Flood search algorithm (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Multiple Protocol Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2)(cid:2) Operating multiple protocols in one network (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2)(cid:2) Problems with alternating between routing protocols
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) The Proposed Hybrid Routing Scheme (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` Modelling of the Routing Strategy
`
`
`
`(cid:2) Methodology (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Development of the Simulation Model (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Network and trac models (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Modelling dynamic network behaviour
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Models of routing procedures
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Comments on Interpretation of Simulation Results (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` Performance of Hybrid Routing
`
`
`
`(cid:2) Performance of Minimum Hop and Flooding Protocols
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) (cid:2)
`
`Static network conditions
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) (cid:2) Verication of the simulation model under static conditions (cid:2) (cid:2) 
`
`(cid:2) (cid:2) Eects of dynamic network conditions
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)
`
`Implications of the Results to Multiple Protocol Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Performance of the Proposed Hybrid Routing Scheme (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Eect of Network Size and Connectivity (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` Modications to Hybrid Routing
`
` 
`
`(cid:2) Next Best Path Strategy (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) (cid:2) Delay throughput performance (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) (cid:2) Comparison with hybrid routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Prioritised Routing Table Updates (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) The priority mechanism (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`ii
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 6 of 185
`
`

`
`(cid:2)(cid:2) Performance comparison using priority (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` Verifying Performance Robustness of Hybrid Routing
`
` 
`
`(cid:2) Expected Routing Algorithm Performance (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Verication Through Simulation Modelling (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Large Changes to Topology (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) (cid:2) Results of network simulation (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Regional and Time Varying Link Cost Change Intensity (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2)
`
`Simulation results (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Topology Change in a Mobile Radio Network (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Mobile packet radio node model (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2)(cid:2) Topology control
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2)(cid:2) Modelling a multiple access scheme (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)(cid:2) Routing performance (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` Conclusions
`
` 
`
`(cid:2)
`
`Identifying Dominant Routing Costs
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) A Solution to Routing Table Uncertainty (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Recommendations for Further Study (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`Bibliography
`
`A Routing Power Calculations
`
` 
`
` 
`
`B Dynamic Scenario for the Mobile Packet Radio Network Model 
`
`C Publications
`
` 
`
`iii
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 7 of 185
`
`

`
`List of Figures
`
` (cid:2) Routing performance subject to a changing topology (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`
`
`(cid:2) Shortest path spanning tree for destination d (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Delay versus throughput for an MM queue (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Delay versus throughput for network of queues (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Relative performance of routing procedures (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Location of node v in the network G (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Routing overheads as the network becomes more dynamic (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Multiple protocol routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Primary node functions required for protocol switching (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
` (cid:2) Local broadcast hybrid routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Deriving a simulation model
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Network model (cid:11)  nodes with connectivity of degree  (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Delay using ooding and minimum hop in static network (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`
`
`(cid:2) Determining the maximum operating point(cid:14) n (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Queue length with ooding and minimum hop in static network (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Verication of minimum hop in static network (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Verication of constrained ooding in static network
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Delay using ooding with increasing intensity of change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Delay using minimum hop with increasing intensity of change
`
`(cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Dominance of retransmissions with increasing intensity of change (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Probability of success using minimum hop with increasing intensity
`
`of change
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Delay using hybrid routing with increasing intensity of change (cid:2) (cid:2) (cid:2) (cid:2) 
`
`iv
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 8 of 185
`
`

`
`(cid:2) Relative routing transmission overheads (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2)  Comparative performance over varying intensity of change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Comparative performance (cid:8)  nodes with connectivity of degree  (cid:2) (cid:2) 
`
`(cid:2)  Hybrid routing performance with increased connectivity (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2)  Comparative performance (cid:8)  nodes with connectivity of degree  (cid:2) 
`
`(cid:2)  Hybrid routing performance with increased network size
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Delay using next choice with increasing intensity of change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Probability of success using next choice with increasing intensity of
`
`change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Relative routing transmission overheads (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Comparative performance over varying intensity of change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Priority queueing model for packets transmitted on link l (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Minimum hop routing with prioritised table updates (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Hybrid routing with prioritised table updates
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Minimum hop routing with increased degree of topology change (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Hybrid routing with increased degree of topology change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Comparative performance with increased degree of topology change (cid:2) 
`
`(cid:2) Region of dynamic change shaded area moving across the network (cid:2) 
`
`(cid:2) Minimum hop routing with regional topology change
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Hybrid routing with regional topology change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Comparative performance with regional topology change (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Delaunay triangles and some of their circumscribing circles (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Minimum hop routing performance in the mobile radio network model 
`
`(cid:2) Flooding performance in the mobile radio network model (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Hybrid routing performance in the mobile radio network model (cid:2) (cid:2) (cid:2) (cid:2)
`
`B(cid:2) Stationary nodes and nodes travelling at kmhr (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`B(cid:2) Nodes travelling at kmhr and kmhr (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`B(cid:2) Delaunay triangulation of initial node positions
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`v
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 9 of 185
`
`

`
`List of Tables
`
`(cid:2) Routing Algorithm Performance (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Relative Routing Cost
`
`(cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
` (cid:2) Distance and Routing Tables for Node v (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`(cid:2) Throughput and Delay Comparison with Hybrid Routing (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Comparison of Minimum Hop Routing with and without Priority (cid:2) (cid:2)
`
`(cid:2) Comparison of Hybrid Routing with and without Priority (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2)
`
`(cid:2) Routing power performance in the mobile radio network model (cid:2) (cid:2) (cid:2) (cid:2) 
`
`A(cid:2) Routing Power (cid:11)  Nodes with Connectivity of Degree  (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`A(cid:2) Routing Power (cid:11)  Nodes with Connectivity of Degree  (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`A(cid:2) Routing Power (cid:11)  Nodes with Connectivity of Degree  (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`A(cid:2) Routing Power (cid:11) Prioritised Routing Table Update Messages (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`A(cid:2) Routing Power (cid:11)  Nodes(cid:13)  Degree Connectivity(cid:13) D (cid:14) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) 
`
`A(cid:2) Routing Power (cid:11)  Nodes(cid:13)  Degree Connectivity(cid:13) Regional Change (cid:2) 
`
`vi
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 10 of 185
`
`

`
`Abbreviations
`
`ACK
`
`Acknowledgment
`
`ARPANET
`
`Advanced Research Projects Agency Network
`
`ARQ
`
`ATM
`
`AT(cid:2)T
`
`CDMA
`
`CSMA
`
`CUP
`
`DAR
`
`DNHR
`
`FDMA
`
`FLD
`
`IP
`
`IUP
`
`LAN
`
`MSG
`
`OSPF
`
`RIP
`
`SP
`
`TDMA
`
`TSMR
`
`Automatic Repeat Request
`
`Asynchronous Transfer Mode
`
`American Telephone (cid:2) Telegraph
`
`Code Division Multiple Access
`
`Carrier Sense Multiple Access
`
`Coordinated Update Procedure
`
`Dynamic Alternative Routing
`
`Dynamic Nonhierarchical Routing
`
`Frequency Division Multiple Access
`
`Flooding
`
`Internet Protocol
`
`Independent Update Procedure
`
`Local Area Network
`
`Message
`
`Open Shortest Path First
`
`Routing Information Protocol
`
`Shortest Path Routing
`
`Time Division Multiple Access
`
`Trunk Status Map Routing
`
`vii
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 11 of 185
`
`

`
`Abstract
`
`In modern communication systems(cid:2) especially those with mobile radio compo(cid:3)
`
`nents(cid:2) the distribution of trac loads and network topologies may vary from nearly
`
`static to very dynamic(cid:5) The dynamic behaviour may vary both in space i(cid:5)e(cid:5) aect
`
`only regions of a network and in time(cid:5) Commonly known routing algorithms tend
`
`to be well suited for specic networking environments(cid:5) For example(cid:2) algorithms
`
`based on the shortest path principle tend to work well with quasi(cid:3)static networks(cid:2)
`
`and random search or ood based algorithms are better suited to networks with
`
`dynamically changing topologies(cid:5) As a result(cid:2) it is very dicult to select a single
`
`routing algorithm that will be most appropriate for a given network(cid:2) if the network
`
`is subject to varying degrees of dynamic behaviour(cid:5) Usually(cid:2) what works well for
`
`some regions of a network(cid:2) will be inecient for other regions(cid:5) Similarly(cid:2) the routing
`
`eciency will vary in time(cid:5) An intuitive solution to this problem(cid:2) namely switching
`
`between a number of routing procedures depending on network behaviour(cid:2) requires
`
`a set of switching criteria and decision making procedures which are extremely dif(cid:3)
`
`cult to dene and implement for networks with a distributed mode of operation
`
`and control(cid:5)
`
`This thesis develops a routing strategy that smoothly adapts to a changing net(cid:3)
`
`work topology dened by links failing and subsequently recovering by combining
`
`two dierent routing principles into one hybrid routing procedure(cid:5) The proposed
`
`routing procedure does not require any specic measures of the network dynamics
`
`to be computed by network nodes and then used to decide on the routing principle(cid:5)
`
`Instead(cid:2) by deciding locally on the basis of routing information normally available
`
`at each node(cid:2) the way in which a next node is to be reached(cid:2) the hybrid routing
`
`strategy exhibits a smooth change from minimum hop routing to constrained ood(cid:3)
`
`ing(cid:2) as the behaviour of the network or regions within changes from static to very
`
`dynamic(cid:5)
`
`viii
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 12 of 185
`
`

`
`Declaration
`
`I declare that this thesis does not incorporate without acknowledgment any ma(cid:2)
`
`terial previously submitted for a degree or diploma in any university(cid:3) and that to
`
`the best of my knowledge it does not contain any materials previously published or
`
`written by another person except where due reference is made in the text(cid:4)
`
`Peter John Shoubridge
`
`ix
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 13 of 185
`
`

`
`Acknowledgments
`
`I am very grateful for the support and guidance provided by several people in
`
`undertaking this research program(cid:2) Firstly(cid:3) 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(cid:4)
`
`uate study environment they provided(cid:2) Also(cid:3) I wish to thank my employers(cid:3) Mr Neil
`
`Bryans(cid:3) Dr Tony Bedford(cid:3) Dr Stephen Cook and Mr Manfred Heigl at the Defence
`
`Science and Technology Organisation for providing the opportunity and exibility
`
`to undertake this study(cid:2)
`
`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(cid:2) Finally(cid:3) I would like to thank
`
`Jonathon Shewchuk from the School of Computer Science at Carnegie Mellon Uni(cid:4)
`
`versity for permission to use his software to calculate the Delaunay triangulations
`
`used in Chapter (cid:2)
`
`x
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 14 of 185
`
`

`
`Chapter
`
`Introduction
`
`Communication networks enable users to exchange information through the sharing
`
`of switching and transmission resources(cid:2) Routing provides an essential function in
`
`ensuring that information transmitted from a source can successfully nd a path
`
`through a network to its desired destination(cid:2) Generally the routing function seeks
`
`to optimise some performance criteria such as network utilisation or throughput(cid:4) or
`
`perhaps average delay(cid:2) As networks increase in size(cid:4) with more users demanding
`
`seamless connectivity(cid:4) mobility and a high level of availability(cid:4) the task of routing
`
`becomes an increasingly complex problem to network providers(cid:2)
`
`For ecient routing(cid:4) nodes require at least some knowledge of network topology(cid:2)
`
`Links may fail or become congested(cid:4) nodes or users could be mobile(cid:4) resulting in
`
`changes to the source(cid:6)destination paths within the network(cid:2) Information regarding
`
`these changes must be conveyed to network nodes so that appropriate routing can
`
`take place(cid:2) This information exchange consumes network resources that could oth(cid:6)
`
`erwise be used for user trac and represents a cost in maintaining up to date routing
`
`information in network nodes(cid:2) As topology or trac loads change more frequently(cid:4)
`
`the network becomes dynamic and maintaining accurate routing information at in(cid:6)
`
`dividual nodes comes at a higher cost(cid:2)
`
`In addition to transmission capacity(cid:4) routing procedures consume other network
`
`resources such as processing time to execute algorithms and memory to store rout(cid:6)
`
`ing tables(cid:2) Generally(cid:4) in dynamic networks employing radio transmission bearers(cid:4)
`
`processing power and memory within network nodes are of relatively low cost when
`
`compared to transmission resources which are often costly and limited(cid:2)
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 15 of 185
`
`

`
` (cid:2) Thesis Objectives
`
`Typically(cid:2) when shortest path routing algorithms are utilised to maintain routing
`
`look up tables stored within network nodes(cid:2) they contribute zero transmission costs
`
`when making a routing decision(cid:3) In forwarding a user packet(cid:2) a node simply deter(cid:4)
`
`mines the most appropriate outgoing link from the routing table(cid:3) However(cid:2) these
`
`shortest path algorithms do consume resources every time the network changes in
`
`bringing all the routing tables throughout the network up to date(cid:3) If routing deci(cid:4)
`
`sions are based on inaccurate information stored in routing tables(cid:2) retransmissions
`
`or reattempts caused by higher layer end(cid:4)to(cid:4)end transport protocols typically occur
`
`as a result of the excessive delays or lost trac(cid:3) This places additional load on the
`
`network further consuming transmission resources(cid:3)
`
`Flooding based routing procedures(cid:2) on the other hand(cid:2) do not maintain routing
`
`tables and therefore do not require any table update procedures(cid:3) As such they
`
`contribute zero update cost but do consume large amounts of network capacity
`
`through broadcasting each time a routing decision is required(cid:3) Overheads resulting
`
`from these types of routing procedure are generally independent from the frequency
`
`of changes occurring within a network(cid:3) Instead overheads are related to the extent
`
`of the ooding process(cid:3)
`
`While shortest path algorithms are less costly to operate in a reasonably static
`
`network environment(cid:2) ooding may be required for very dynamic networks(cid:3) This is
`
`certainly true if shortest path algorithms are ineective in maintaining accurate
`
`routing tables due to high rates of change in network topology(cid:3) Unfortunately
`
`ooding is inecient(cid:2) resulting in very low network utilisation(cid:3) If network conditions
`
`can vary from static to very dynamic(cid:2) better routing strategies are required for
`
`greater network utilisation(cid:3) Identifying more ecient routing strategies under such
`
`conditions is the prime objective of this thesis(cid:3)
`
` Shortest path algorithms determine the best(cid:3) paths through a network as dened by arbitrary
`
`criteria(cid:5) Full descriptions of such algorithms are presented in later chapters(cid:5)
`
`
`
`IPR2016-00726-ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1020 , p. 16 of 185
`
`

`
` (cid:2) Achievements
`
`With many routing algorithms operating eciently for only one class of network(cid:3)
`
`either nearly static or very dynamic(cid:3) the task of selecting a single most appropri(cid:4)
`
`ate routing algorithm can be very dicult because the dynamic nature of a given
`
`network can vary(cid:5) Operating shortest path routing algorithms in dynamic networks
`
`is not possible due to the associated high routing cost(cid:5) It has been established in
`
`this thesis that a dominant constraint limiting the use of minimum hop routing one
`
`particular form of shortest path routing(cid:3) in a network subjected to increasingly fre(cid:4)
`
`quent link failures and subsequent recoveries(cid:3) is the routing table uncertainty(cid:5) While
`
`routing table update protocol overheads were found substantial(cid:3) they are far less sig(cid:4)
`
`nicant(cid:5) This observation opens an opportunity for considerable improvement to the
`
`algorithm(cid:9)s performance by overcoming the problem of uncertainty in routing tables(cid:5)
`
`It is possible to achieve signicantly improved performance over a wider range of
`
`dynamic conditions by combining dierent existing routing procedures into a new
`
`hybrid routing procedure(cid:5)
`
`A hybrid routi