UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Optimizing cloud gaming service delivery Cai, Wei 2016

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2016_may_cai_wei.pdf [ 4.4MB ]
JSON: 24-1.0300241.json
JSON-LD: 24-1.0300241-ld.json
RDF/XML (Pretty): 24-1.0300241-rdf.xml
RDF/JSON: 24-1.0300241-rdf.json
Turtle: 24-1.0300241-turtle.txt
N-Triples: 24-1.0300241-rdf-ntriples.txt
Original Record: 24-1.0300241-source.json
Full Text

Full Text

OPTIMIZING CLOUD GAMING SERVICE DELIVERYbyWei CaiB.Eng., Xiamen University, China, 2008M.Sc., Seoul National University, Korea, 2011A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)April 2016c© Wei Cai 2016AbstractThe high-profit digital gaming industry has merged with the increasing interest intransforming everything into cloud services, which leads to a novel concept called cloudgaming. In this thesis, we aim to investigate the optimization of quality of experience(QoE) for cloud gaming system, while considering different challenges, system constraintsand service requirements.First, we investigate video compression technologies based on existing cloud gamingsystem, in which the cloud hosts the game engine and streams rendered gaming videos toplayers through the Internet. We propose to cooperatively encode cloud gaming videos ofdifferent players in the same game session, in order to leverage inter-gamer redundancy.This is based on an observation that game scenes of close-by gamers have non-trivialoverlapping areas, and thus adding inter-gamer predictive video frames may improve thecoding efficiency. Selected games are analyzed and the trace-driven simulationsdemonstrate the efficiency of proposed system.Second, we introduce a novel decomposed cloud gaming paradigm, which supportsflexible migrations of gaming components between the cloud server and the players’terminals. We present the blueprint of the proposed system and discussed the cognitiveresource optimization for the proposed decomposed cloud gaming system under distincttargets. This includes the minimization of cloud, network, and terminal resources andresponse delay, subject to QoE assurance, which is formulated as a graph partitioningproblem that is solved by exhaustive searches. Extensive simulation results show theiiAbstractfeasibility of cognitive resource management in a cloud gaming system to efficiently adaptitself to variations in the service environments, while satisfying different QoErequirements for gaming sessions.Finally, we explore the practical approach for the decomposed cloud gamingparadigm. We design the system framework and seek the engineering solutions forpractical issues. Following these discussions, we implement the very first experimentaltestbed called ubiquitous cloud gaming platform. Three game prototypes are built on ourtestbed, which can demonstrate the feasibility and efficiency of our proposal.Experiments have been conducted to show that intelligent partitioning leads to bettersystem performance, such as lower response latency and higher frame rate.iiiPrefaceThis thesis is based on the research I conducted under the supervision of Dr. Victor C.M.Leung. The result of this research was several articles that have been either accepted orpublished, or are under review. I developed the ideas for these articles and wrote themunder the supervision of Dr. Leung, who also helped in revising them. For the articlerelated to Chapter 2, Mr. Zhen Hong helped in conducting the simulations. For theconference publication of Chapter 3, Mr. Conghui Zhou and Mr. Minchen Li helpedin prototype developing and Dr. Xiaofei Wang helped in addressing comments from thereviewers. For the articles related to Chapter 4, Dr. Henry C.B. Chan helped in problemformulation. In the following, the list of these publications are provided.Publication related to Chapter 1• Wei Cai, Ryan Shea, Chun-Ying Huang, Kuan-Ta Chen, Cheng-Hsin Hsu, JiangchuanLiu and Victor C. M. Leung, “A Survey on Cloud Gaming: Future of ComputerGames”, submitted to a peer-reviewed journal.• Wei Cai, Min Chen and Victor C.M. Leung, “Towards Gaming as a Service”, InternetComputing, IEEE , vol.18, no.3, pp.12-18, May-June, 2014.• Wei Cai, Victor C.M. Leung and Min Chen, “Next Generation Mobile CloudGaming”, Proceeding of IEEE 7th International Symposium on Service OrientedSystem Engineering (SOSE2013), pp.551-560, Hotel Sofitel, San Francisco Bay,ivPrefaceUSA, March 25-28, 2013.Publication related to Chapter 2• Wei Cai, Zhen Hong, Xiaofei Wang, Henry C.B. Chan and Victor C.M. Leung,“Quality of Experience Optimization for Cloud Gaming System with Ad-hocCloudlet Assistance”, IEEE Transaction on Circuits and Systems for VideoTechnology, vol.25, no.12, pp.1-14, December, 2015.• Wei Cai, Victor C.M. Leung and Long Hu, “A Cloudlet-Assisted Multiplayer CloudGaming System”, ACM/Springer Mobile Networks and Applications (MONET),Vol.19, No.2, pp.144-152, April 2014.• Wei Cai and Victor C.M. Leung, “Multiplayer Cloud Gaming System withCooperative Video Sharing”, Proceeding of 4th IEEE International Conference onCloud Computing Technology and Science (CloudCom2012), pp.640-645, Taipei,Taiwan, December 3-6, 2012.Publication related to Chapter 3• Wei Cai, Henry C.B. Chan, Xiaofei Wang and Victor C.M. Leung, “CognitiveResource Optimization for Decomposed Cloud Gaming Platform,” IEEETransaction on Circuits and Systems for Video Technology, vol.25, no.12, pp.1-14,December, 2015.• Wei Cai, Min Chen, Conghui Zhou, Victor C.M. Leung and Henry C.B. Chan,“Resource Management for Cognitive Cloud Gaming,” Proceeding of The 2014IEEE International Conference on Communications (ICC2014), pp.3462-3467,Sydney, Austrailia, June 10-14, 2014Publication related to Chapter 4vPreface• Wei Cai, Conghui Zhou, Minchen Li, Xiuhua Li and Victor C.M. Leung, “MCGTest-bed: An Experimental Test-bed for Mobile Cloud Gaming,” Proceeding of The13th International Conference on Mobile Systems, Applications and Services(MobiSys2015), Florence, Italy, May 18-22, 2015.• Wei Cai, and Victor C.M. Leung, “Decomposed Cloud Games: Design Principles andChallenges,” Proceeding of The 2014 IEEE International Conference on Multimediaand Expo (ICME2014), Chengdu, China, July 14-18, 2014.• Wei Cai, Conghui Zhou, Victor C.M. Leung and Min Chen, “Environment Perceptionfor Cognitive Cloud Gaming,” Proceeding of The 4th International Conference onCloud Computing (CloudComp2013), Wuhan, China, Octorber 17-19, 2013.• Wei Cai, Conghui Zhou, Victor C.M. Leung and Min Chen, “A Cognitive Platformfor Mobile Cloud Gaming,” Proceeding of The IEEE 5th International Conference onCloud Computing Technology and Science (CloudCom2013), pp.72-79, Bristol, UK,December 2-5, 2013.Publication related to Chapter 5• Wei Cai, Ryan Shea, Chun-Ying Huang, Kuan-Ta Chen, Jiangchuan Liu, Victor C.M. Leung, and Cheng-Hsin Hsu, “The Future of Cloud Gaming,” Proceedings of theIEEE, vol.104, no.4, pp.687-691, April, 2016.viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.1 System Construction . . . . . . . . . . . . . . . . . . . . . . . . . . 81.1.2 Interaction Latency . . . . . . . . . . . . . . . . . . . . . . . . . . 101.1.3 Quality of Experience . . . . . . . . . . . . . . . . . . . . . . . . . 141.1.4 Data Compression on Communications . . . . . . . . . . . . . . . . 161.1.5 Adaptive Transmission . . . . . . . . . . . . . . . . . . . . . . . . 181.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.3 Research Questions and Challenges . . . . . . . . . . . . . . . . . . . . . . 25viiTable of Contents1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System . . . . . 292.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2.1 Ad Hoc Cloudlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2.2 Correlations of Videos Frames . . . . . . . . . . . . . . . . . . . . 322.2.3 Real-time Video Encoding . . . . . . . . . . . . . . . . . . . . . . . 332.3 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4 System Modeling and Formulation . . . . . . . . . . . . . . . . . . . . . . 352.4.1 Avatar behavior Model . . . . . . . . . . . . . . . . . . . . . . . . 352.4.2 Encoding Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.3 Terminal Mobility Model . . . . . . . . . . . . . . . . . . . . . . . 392.4.4 Network Quality of Service Model . . . . . . . . . . . . . . . . . . 402.4.5 Video Encoding Solution . . . . . . . . . . . . . . . . . . . . . . . 412.5 Optimization Target . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.5.1 QoE Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.5.2 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.6 Heuristic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492.6.1 Local Greedy Approach . . . . . . . . . . . . . . . . . . . . . . . . 492.6.2 One-Hop Restricted Local Greedy Approach . . . . . . . . . . . . . 502.7 An Experimental Case Study: Diablo II . . . . . . . . . . . . . . . . . . . 512.8 Trace-Driven Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 532.8.1 Study on Intra-Stream P-Frame Size . . . . . . . . . . . . . . . . . 532.8.2 Study on Inter-Stream P-Frame Size . . . . . . . . . . . . . . . . . 55viiiTable of Contents2.8.3 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 572.8.4 Effects of Number of Players . . . . . . . . . . . . . . . . . . . . . 592.8.5 Effects of Maximum Communication Range between Terminals . . 602.8.6 Effects of Maximum Number of Hops Allowed . . . . . . . . . . . . 612.8.7 Effects of NQoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 Cognitive Cloud Gaming Platform . . . . . . . . . . . . . . . . . . . . . . 643.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.3 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.3.1 Conceptual Framework . . . . . . . . . . . . . . . . . . . . . . . . 663.3.2 Cognitive Resource Management . . . . . . . . . . . . . . . . . . . 673.4 System Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693.4.1 Game Components . . . . . . . . . . . . . . . . . . . . . . . . . . . 693.4.2 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 713.4.3 Optimal Partitioning Solution . . . . . . . . . . . . . . . . . . . . . 723.5 Cloud Resource Management . . . . . . . . . . . . . . . . . . . . . . . . . 793.5.1 QoS Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793.5.2 Optimization Targets . . . . . . . . . . . . . . . . . . . . . . . . . 823.6 Heuristic Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.6.1 Local Greedy Approach . . . . . . . . . . . . . . . . . . . . . . . . 853.6.2 Genetic Algorithm-base Approach . . . . . . . . . . . . . . . . . . 863.7 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.7.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.7.2 Discussion on Game Design . . . . . . . . . . . . . . . . . . . . . . 91ixTable of Contents3.7.3 System Performance Evaluation . . . . . . . . . . . . . . . . . . . 963.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014 Decomposed Ubiquitous Cloud Gaming System . . . . . . . . . . . . . . 1024.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024.2 System Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1034.3 Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.3.1 Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.3.2 System Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1084.3.3 Dynamic Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 1094.3.4 Response Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1104.3.5 Partial Offline Execution . . . . . . . . . . . . . . . . . . . . . . . 1124.4 Framework Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134.4.1 Execution Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . 1154.4.2 Performance Prober . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.4.3 Cognitive Decision Engine . . . . . . . . . . . . . . . . . . . . . . . 1184.4.4 Onloading Manager . . . . . . . . . . . . . . . . . . . . . . . . . . 1184.4.5 Partitioning Coordinator . . . . . . . . . . . . . . . . . . . . . . . 1204.4.6 Synchronization Controller . . . . . . . . . . . . . . . . . . . . . . 1214.5 Testbed Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1224.5.1 Enabling Technologies . . . . . . . . . . . . . . . . . . . . . . . . . 1224.5.2 Deployment Directory . . . . . . . . . . . . . . . . . . . . . . . . . 1234.5.3 Application Programming Interface . . . . . . . . . . . . . . . . . . 1244.5.4 The Administration Center . . . . . . . . . . . . . . . . . . . . . . 1254.6 Prototype Development and Experiments . . . . . . . . . . . . . . . . . . 1264.6.1 Development Challenges . . . . . . . . . . . . . . . . . . . . . . . . 126xTable of Contents4.6.2 Gobang Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1294.6.3 3D Skeletal Game Engine . . . . . . . . . . . . . . . . . . . . . . . 1324.6.4 Robocode Tank Game . . . . . . . . . . . . . . . . . . . . . . . . . 1354.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1385 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 1395.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 1415.2.1 Cloud Gaming Engages More Multiplayer Games . . . . . . . . . . 1415.2.2 Novel Gaming Paradigm Convergence in Cloud . . . . . . . . . . . 144Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147AppendicesA Proof of Theorem 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155xiList of Figures1.1 Illustration of Conventional Cloud Gaming Architecture . . . . . . . . . . . 21.2 A Modularized Cloud Gaming Program . . . . . . . . . . . . . . . . . . . . 221.3 Comparisons among the three types of cloud gaming platforms . . . . . . . 232.1 Ad Hoc Cloudlet-Assisted Multiplayer Cloud Gaming System . . . . . . . . 342.2 Correlation of Inter-Video Frames (Diablo III) . . . . . . . . . . . . . . . . 372.3 Frames Correlation in Real-time Multiplayer Game Videos . . . . . . . . . 382.4 Markov Process for the Change of NQoS Level . . . . . . . . . . . . . . . . 412.5 A Run-Time Screenshot for Concurrent Players in Diablo II . . . . . . . . 512.6 Video Frame Sizes of Diablo2 for Two Players . . . . . . . . . . . . . . . . 522.7 An Illustration of Distributions of Inter-stream P-frame Sizes . . . . . . . . 542.8 Exponential Fitting of Inter-stream P-frame Size . . . . . . . . . . . . . . . 562.9 Inter-stream P-frame Size Defined by P(e) . . . . . . . . . . . . . . . . . . 572.10 Effects of Number of Players on QoE . . . . . . . . . . . . . . . . . . . . . 592.11 Effects of Maximum Communication Range of Terminals on QoE . . . . . 612.12 Effects of Maximum Number of Hops Allowed on QoE . . . . . . . . . . . 622.13 Effects of NQoS on QoE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.1 Cognitive Cloud Gaming Platform . . . . . . . . . . . . . . . . . . . . . . . 673.2 A Running Instance for Cognitive Cloud Gaming . . . . . . . . . . . . . . 683.3 Components Partitioning for Proposed Cognitive Platform . . . . . . . . . 69xiiList of Figures3.4 A Minimum Spanning Tree with N components . . . . . . . . . . . . . . . 733.5 A Complete Graph with N components . . . . . . . . . . . . . . . . . . . . 743.6 A General Graph with N components . . . . . . . . . . . . . . . . . . . . . 773.7 Chromosome Encoding Method for Cloud Resource Management . . . . . . 873.8 Chromosome Crossover for Cloud Resource Management . . . . . . . . . . 873.9 Chromosome Mutation for Cloud Resource Management . . . . . . . . . . 883.10 Effect of Number of Components on Overall Cost . . . . . . . . . . . . . . 923.11 Effect of Component Communication Probability on Overall Cost . . . . . 923.12 Comparison on Terminal Incapable Rate . . . . . . . . . . . . . . . . . . . 933.13 Effect of Communication Probability on Response Delay . . . . . . . . . . 943.14 Effect of Communication Variance on Response Delay . . . . . . . . . . . . 953.15 Tradeoff between cloud cost and terminal cost . . . . . . . . . . . . . . . . 963.16 GA convergence on evolutionary generations . . . . . . . . . . . . . . . . . 973.17 Performance Evaluation on Network Cost Minimization . . . . . . . . . . . 993.18 Performance Evaluation on Cloud Resource Cost Minimization . . . . . . . 1003.19 Variance of Local Greedy Scheme Simulation Results . . . . . . . . . . . . 1014.1 Architecture Framework for Cognitive Mobile Cloud Gaming . . . . . . . . 1034.2 Fine-Grained Decomposition Example . . . . . . . . . . . . . . . . . . . . 1064.3 Coarse-Grained Decomposition Example . . . . . . . . . . . . . . . . . . . 1074.4 Work Flow of Decomposed Ubiquitous Cloud Gaming Platform . . . . . . 1084.5 Sequence Diagram for Cognitive Engine . . . . . . . . . . . . . . . . . . . . 1104.6 A Component Communication Tree . . . . . . . . . . . . . . . . . . . . . . 1114.7 Redirection Service in Disconnection to the Cloud . . . . . . . . . . . . . . 1134.8 Decomposed Ubiquitous Cloud Gaming Platform . . . . . . . . . . . . . . 1144.9 Mobile Agent Dispatch for Performance Prober . . . . . . . . . . . . . . . 117xiiiList of Figures4.10 Deployment Directory of UBCG Testbed . . . . . . . . . . . . . . . . . . . 1234.11 Screenshot of Administration Center of UBCG Testbed . . . . . . . . . . . 1254.12 Screenshot for Gobang Game . . . . . . . . . . . . . . . . . . . . . . . . . 1304.13 Response Latency Comparison in Gobang Game Prototype . . . . . . . . . 1314.14 Screenshot for 3D Skeletal Game Engine . . . . . . . . . . . . . . . . . . . 1334.15 Game QoS (FPS) Comparison in 3D Skeletal Game Engine . . . . . . . . . 1354.16 Screenshot for Robocode Tank Game . . . . . . . . . . . . . . . . . . . . . 1364.17 Game QoS (FPS) Enhancement for Robocode Tank Game . . . . . . . . . 137xivList of Abbreviations2D Two-Dimensional3D Three-DimensionalAMD Advanced Micro DevicesCSS Cascading Style SheetsCMR-MOS Cloud Mobile Rendering - Mean Opinion ScoreCPU Central Processing UnitDSC Distributed Source CodingEaaS Everything as a ServiceEJS Embedded JavaScriptGaaS Gaming as a ServiceGA Genetic AlgorithmGMOS Game Mean Opinion ScoreGOP Gourp of PicturesGUI Graphical User InterfaceGPU Graphics Processing UnitGPS Global Positioning SystemIaaS Infrastructure as a ServiceIPTV Internet Protocol televisionMGUE Mobile Game User ExperiencexvList of AbbreviationsMOS Mean opinion scoreNQoS Network Quality of ServiceMVC Model-View-ControllerP2P Peer-to-PeerPaaS Platform as a ServicePC Personal ComputerPDA Personal Digital AssistantPSNR Peak Signal to Noise RatioQoS Quality of ServiceQoE Quality of ExperienceRTT Round Trip TimeSDK Software Development KitSaaS Software as a ServiceUBCG ubiquitous cloud gamingVM Virtual MachineVR Virtual RealityWLAN Wireless Local Area NetworkWWAN Wireless Wide Area NetworkxviAcknowledgmentsFirst of all, I would like to express my deep gratitude to my supervisor, Dr. Victor C.M.Leung, for providing the opportunity to study the Ph.D. program at UBC, which helpedme to learn a lot about my field of study and also about myself. I also want to thank himfor his invaluable support and guidance over the past years.I would like to declare special thanks to Dr. Henry C.B. Chan and Dr. Kuan-Ta(Sheng-Wei) Chen for providing the opportunities to visit The Hong Kong PolytechnicUniversity and Academia Sinica for a period during my research. I am grateful for theircomments and advice through my research which helped in preparing my thesis.Also, I would like to extend my appreciation to my colleagues and friends for their helpand supports during the past years.Most importantly, I feel indebted to my great family for their everlasting love andsupport not only during my studies at UBC but also throughout my entire life.This work was supported by The University of British Columbia Four-Year-Fellowshipand the Natural Sciences and Engineering Research Council (NSERC) of Canada.xviiDedicationTo my familyxviiiChapter 1IntroductionOver the past years, digital game has become of the most profitable products in the softwaremarketplace and is considered the main beneficiary of digital video industry over their rivalcinema. Driven by the latest designed consoles and computer games, there is an increasingpopulation of players involved in this kind of entertainment. Moreover, total time consumedin digital games has dramatically raised, thanks to universal mobile devices and diversifiedmobile games. Among the most popular downloads in the application market, mobile gamesnow dominate digital entertainment resources as a way for people to spend their idle time.According to Newzoo’s Global Games Market Report, worldwide video game revenues isprojected to reach $107 billion in 2017. The market becomes more engaging when the gamedevelopers start to deliver the same gaming contents through different platforms, whereplayers are able to access identical gaming contents from different devices, at anywhere,anytime. Ideally, the controlling manner and graphical user interface (GUI) should beconsistent on different platforms. We refer this kind of service paradigm as ubiquitousgaming.The heterogeneous infrastructures of users’ terminals (e.g., networks, operatingsystem, input devices and screen size), introduce many research challenges andopportunities. One of the most critical concerns is the diversity of hardware constraintsof terminals: some of them have sufficient power to render complicated three-dimensional(3D) gaming scenes (e.g., game consoles and desktop personal computers (PCs)), whileothers still need improvement in executing sophisticated video games for gaming1Chapter 1. Introductionenthusiasts (e.g., smart phones, tablet and laptop). In addition, the installations ofgames are becoming burdens for the limited internal storage in a mobile terminal. Also,heavy battery consumption for mobile games is another significant consideration,especially when battery drain is always a big concern for smartphone users.Figure 1.1: Illustration of Conventional Cloud Gaming ArchitectureRealizing the cloud’s virtually infinite processing power, cloud gaming becomes one ofthe most active research topics [1]. As an emerging software solution, it transformstraditional gaming software into Gaming as a Service (GaaS). In general, the concept ofcloud gaming refers to the approach of offloading [2] game engines to the cloud server, sothat the players’ terminals can utilize the rich resources from the cloud to enhance theirfunctionality. In other words, cloud gaming offers a thin-client approach for computergames by having all game data stored in the cloud’s data centers and enablingcomputation-intensive tasks to be offloaded to the cloud. With this paradigm, it enablesplayers to gain full access to their personalized game environments from any mobile2Chapter 1. Introductiondevice and virtually anywhere. Therefore, players can overcome the intrinsic constraintsof their substandard terminals, such as incompatible operating system, limited storage,insufficient computational capacity and battery drain problem. For instance, you caneven play World of Warcraft on a tablet! Fig. 1.1 illustrates the conventional cloudgaming architecture.Same as most cloud computing applications, cloud gaming services have advantagesover traditional software systems. For example, Scalability to overcome the constraints ofterminal hardware, including processing capacity, data storage and battery in mobiledevices; Ubiquitous and Cross-Platform Support to provide immersive gaming experience;Cost-effectiveness for system development and software distribution; etc. Moreover, cloudgaming model exhibits more attractive features, which include: i) Effective Anti-PiracySolution: Since the binary code is hosted on a secure cloud server, GaaS model is apotential solution to the long-time troubling piracy problems. In the meantime,transforming from game developing companies to game service providers is considered amore efficient and advanced business model, and as a result brings in higher profit. ii)Click-and-Play : Installation time is saved for players since the game copies do not needto be downloaded and set up in game terminals anymore. Nowadays, the size of gamingprograms is significantly increased, yet many games are hardly, or even ever, played afterthey are installed 1. As a result, “Click-and-Play” attracts more potential player’sattention.The industry has started to seize opportunities for cloud gaming. G-Cluster2, OnLive3,and Gaikai4 were the most famous ones among the commercial providers. G-cluster hasbeen building cloud gaming services since the early 2000’s. In particular, G-cluster publicly1http://www.gamespot.com/articles/37-percent-of-steam-games-have-never-been-played-report/1100-6419022/2http://www.g-cluster.com/3http://www.onlive.com/4http://www.gaikai.com/3Chapter 1. Introductiondemonstrated live game streaming5 over WiFi to a Personal Digital Assistant (PDA) in2001, and a commercial game-on-demand service in 2004. G-cluster’s service has to betightly coupled with several third-party companies, including game developers, networkoperators, and game portals. This can be partially attributed to the less mature Internetconnectivity and data centers, which force G-cluster to rely on network quality of service(QoS) supports from network operators. In the late 2000’s, emerging cloud computingcompanies started offering cloud gaming services over the Internet, represented by OnLiveand GaiKai. OnLive was made public in 2009 to provide a subscription based service,and hosted its servers in several states within the US, as a mean to control geographicallatency. OnLive ran into financial difficulty in 2012 and ceased operations in 2015 afterselling their patents to Sony. Gaikai, on the other hand, offered cloud gaming service usinga different business model. They allowed users to try new games without purchasing andprompted the options for users to buy the game at the end of each gameplay. Therefore,GaiKai is more of an advertisement service to game developers for boosting sales. GaiKaiwas acquired by Sony in 2012, which led to a new cloud gaming service, Play Station Now,that launched in 2014.In these commercialized cloud gaming system, video games are hosted on cloudservers and the gaming video frames are encoded by the streaming server before beingtransmitted over the Internet to the clients, which include interactive televisions, desktopPCs, smartphones, etc. In turns, the players’ inputs are delivered to a cloud server andaccepted by the game content server directly [3]. In this context, the cloud is intrinsicallyan interactive video generator and streaming server, while the mobile devices function asthe event controller and video player that can run sophisticated games despite theirrestricted hardware. Nevertheless, those cloud-based video games still suffer from thebandwidth bottleneck of Internet access. The bandwidth constraints restrict the bit rate5At that time, the term cloud is not yet well-known.4Chapter 1. Introductionof gaming videos, while the jitter and delay affect the quality of experience (QoE) for theplayers. Therefore, technologies regarding real-time video rendering, compressing, andtransmission quality of service (QoS) control become the most critical issues for systemdesign [4][5]. The QoE becomes even poorer with the scenario of portable terminals withmobile networks. Even though stream-based cloud gaming service providers claim thatstreaming gaming videos to mobile devices can eliminate the hardware constraints ofmobile devices, they also have to admit that the QoS of the existing system can not beguaranteed, since real-time video transmission requires low-latency and high-bandwidthnetwork access. Yet, the unstable quality of the Internet infrastructure still affects alldevice users [6][5]. On the other hand, the capacity of mobile terminals has maderemarkable enhancements, thanks to the rapid development of hardware design andtechnologies. Under this circumstance, another approach in providing cloud gamingservices is browser game [7], which requires reliance on online social network sites with amassive number of users (e.g., FarmVille on Facebook). In a typical browser game, thegaming contents, including data and all of the gaming procedures, are stored andexecuted within the cloud, while the gaming graphics and videos are rendered by thebrowser, instructed by the returns from the cloud server. Compared to the normalsolution of cloud-based video games, browser games leave the presentation functionalityto the browsers, in order to eliminate the high bandwidth consumption for gaming videotransmission. According to the study of above two types of cloud gaming, we identifythat browser game is more efficient in the use of communication resources, at the expenseof a heavier computation load in the user’s device.As stated in [8], the distinction between commercial video streaming and browser gamesare the different proportion of offloading: the former offloads everything into the cloud,while the latter only offloads the game logic.5Chapter 1. Introduction1.1 Related WorksMany researchers from all over the world have already contributed to this topic. Thefirst literature [1] that introduced the cloud gaming model to the academia was publishedin 2009, nine years after the G-cluster’s demonstration of cloud gaming technology atElectronic Entertainment Expo (E3). The authors describe gaming as cloud computing’skiller application and depict the blueprint of novel gaming delivery paradigm, proposed byAdvanced Micro Devices (AMD), that computes a game’s graphics, compress them, andsends them out over the Internet so that online gamers can run the results on platformsthat are too computationally puny to render the graphics on their own. This is the mostpopular definition of cloud gaming adopted by most of the research work in this area.However, a recent publication [9] provides a more general definition, by envisioning a newcloud-based computer game architecture that leverages abundant and inexpensive cloudresources to support improved rendering techniques, and ensure shorter response times,better precision and higher fairness. It enables workload distribution among multiple cloudservers and game clients. Stepping forward, another work [8] explores the partitioning ofthe essence of cloud games into inter-dependent components, thus, defines cloud gaming asleveraging cloud resources to execute several gaming modules, thereby reducing terminalworkload and increasing efficiency. According to different integration approach of cloud,the authors identify and discuss the research directions of three cloud gaming architecturalframeworks: Remote Rendering, Local Rendering and Cognitive Resource Allocation.After the successful official launch of OnLive in March 2010, the business model forcloud gaming becomes a hot topic in the research community. Riungu-kalliosaari et al.[10] conducted interview-based qualitative study to observe the dynamics related to theadoption of cloud computing within small and medium sized gaming organizations. Withgrounded theoretical method, the authors find that cloud gaming is relatively well-known6Chapter 1. Introductionin the game organizations, yet they still need more clear business models and success storiesto convince them to adopt cloud computing services and technology. To this end, Ojalaet al. [11] started their investigations on developing business models for cloud gamingservices. As a case study for software as a service (SaaS), the authors selected G-cluster,one of the most famous cloud gaming company, and analyzed its business model over fiveyears from 2005 to 2010. They concluded that cloud gaming leads to a business modelthat is simpler and has fewer factors, which increases the revenue per user. In addition,they also suggested that cloud gaming could make piracy of gaming software practicallyimpossible. Another work [12] considered the mobile cloud convergence in cloud gamingfrom a business model proposition. The authors discussed the first sketch of a possiblebusiness model of Kusanagi project, an end-to-end infrastructure, from domains of service,technology, organization and financial, and compared these domains with those of the threecloud examples, including G-Cluster, Gaikai and OnLive.During the past decade of cloud gaming development, there have been several cloudgaming systems and services appearing in the market. A number of research teams surveythese systems and investigate the opportunities, challenges and directions in this area.These literature, i.e., [13], [14], [15], [8], [9], [16], [17] , cover most of the commercial andacademic platforms, while their concerns of open issues are greatly overlapped among thetopics of response time minimization, graphical video encoding, network aware adaption,quality of experience (QoE) optimization, and cloud resource management.Besides these common focuses, each group has particular interests and directions. Theresearch group [13] at the University of California San Diego concentrates on developingdevice-aware scalable applications, which involves the open issues of extending cloud towireless networks. Soliman et al. [14] briefly revealed related legal issues, including patents,ownership concerns, guaranteed service levels and pricing schemes. On the other hand,7Chapter 1. Introductionpiracy and hacking may be avoided, since the code is no longer delivered to the users. Wuet al. [15] explored cloud gaming architecture from the aspect of cloud computing’s threelayers, including Infrastructure as a Service (IaaS), SaaS and Platform as a Service (PaaS).They identify security as a potential challenge in cloud gaming, especially data protectionand location. Another publication [8] examines the features of different game genres todetermine their impacts on systematic design for cloud gaming service. In addition, theyprovided a vision on GaaS provisioning for mobile devices. Mishra et al. [9] explainedhow to integrate techniques from cloud and gaming research communities into a completearchitecture for enhanced online gaming quality. Featured topics include the interplaybetween QoS and QoE metrics, game models and cloud expansion. Chen et al. [16]pointed out some unique research directions in cloud gaming, such as game integration,visualization, user interface, server selection, and resource scheduling. Chuah et al. [17]studied cloud gaming from a green media perspective. They discuss green designs of majorcloud gaming subsystems: a cloud data center, graphics rendering, video compression andnetwork delivery.1.1.1 System ConstructionThe system construction for cloud gaming can be categorized into two classes: (i) Black-box Platforms that run unmodified games and (ii) Augmented Platforms that require coderecompilation and/or augmentation. These two classes of cloud gaming platforms haveadvantages and disadvantages, and we describe representative studies in individual classesbelow.The black-box platforms support unmodified games from different softwaredevelopers, which reduce the cost of deploying new games, at the expense of potentiallysuboptimal performance. Depasquale et al.[18] presented a cloud gaming platform based8Chapter 1. Introductionon the RemoteFX extension of Windows remote desktop protocol. Modern Windowsservers leverage graphics processing unit (GPU) and Hyper-V virtual machines to enablevarious remote applications, including cloud games. Their experiments reveal thatRemoteFX allows Windows servers to better adapt to network dynamics, but still suffersfrom a high frame loss rate and inferior responsiveness. Another work [19] proposesanother cloud gaming platform, which consists of a distributed service platform, adistributed rendering system, and an encoding/streaming system. Their platformsupports isolated audio/video capturing, multiple clients, and browser-based clients. Realexperiments with 40 subjects have been done, showing high responsiveness. As the firstopen source black-box cloud gaming platform, GamingAnywhere [20] is designed to beextensible, portable, configurable, and open. It supports cloud servers on Windows andLinux, and its client runs on Windows, Linux, Mac OS, and Android.On the other hand, the augmented platform [21–23] requires augmenting andrecompiling existing games to leverage unique features for better gaming experience,which may potentially be time-consuming, expensive, and error-prone. For example,current games can be ported to Google’s Native Client technology6 or to Mozilla’s asm.jslanguage7. Several other studies focus on integrating new techniques with cloud gamingplatforms for better gaming experience. Shi et al. [21] introduced a 3D image warpingassisted real-time video coding method for satisfying the QoS demands of mobile cloudgaming, in terms of lower bandwidth, higher video quality, and better responsiveness.Their system selects key frames from the rendered video frames, and uses 3D imagewarping algorithms to interpolate the non-key frames using graphics contexts. An H.264encoder is used to encode both key frames and residue images of non-key frames. As acase study, they integrate their system with an open source 3D tank game, and6https://developer.chrome.com/native-client7http://asmjs.org/9Chapter 1. Introductiondemonstrate a higher coding efficiency. Nan et al. [22] proposed a joint video andgraphics streaming system for higher coding efficiency as well. Moreover, they present arate adaptation algorithm to further minimize the bandwidth consumption. Lee et al.[23] presented a system to improve the responsiveness of mobile cloud gaming bycompensating network delay. In particular, their system pre-renders potential futureframes based on some prediction algorithm and delivers the rendered frames to mobileclients when the network conditions are good. These frames are then used to compensatefor late video frames due to unstable networks. They integrate the proposed system withtwo open source games, and conduct a user study of 23 subjects. The subjects reportgood gaming experience under nontrivial network delay, as high as 250 ms.1.1.2 Interaction LatencyInteraction latency is one of most important QoS factors that impacts players’experience. Claypool et al. [24] measured the contents variety of different game genres indetails. 28 games from 4 perspectives, including First-Person Linear, Third-PersonLinear, Third-Person Isometric, and Omnipresent, were selected to analyze their scenecomplexity and motion, indicated by average Intra-coded Block Size (IBS) andPercentage of Forward/backward or Intra-coded Macroblocks (PFIM), respectively.Measurements conducted by the authors suggest that Microsoft’s remote desktopachieves better bitrate than NoMachine’s NX client, while the NX client has a higherframe rate. The work [25] investigates OnLive’s network characteristics, such as the datasize and frequency being sent and the overall downlink and uplink bitrates. The authorsreveal that the high downstream bitrates of OnLive games are very similar to the one inlive videos; nevertheless, OnLive’s upstream bitrates are much more moderate, which arecomparable to traditional game upstream traffic. They also indicate that the game traffic10Chapter 1. Introductionfeatures are similar for three types of game genres, including First-Person, Third-Person,and Omnipresent, while the total bitrates can vary by as much as 50%. Anotherimportant finding is that OnLive does not demonstrate its ability in adapting bitrate andframe rates to network latency.Chen et al. [6] analyzed a cloud gaming system’s response delays and segmented itinto three components: network delay, processing delay, and playout delay. With thisdecomposition, the authors propose a methodology to measure the latency componentand apply the methodology on OnLive and StreamMyGame, two of the most popularcloud gaming platforms. The authors identify that OnLive system outperformsStreamMyGame in terms of latency, due to the different resource provisioning strategybased on game genres. A following work [26] by the same group extends the model byadding game delay, which represents the latency introduced by the game program toprocess commands and render the next video frame for the game scene. They also studyhow system design and selective parameters affect responsiveness, including scenecomplexity, updated region sizes, screen resolutions, and computation power. Theirobservation in network traffics is inline with previous work reported in [25]. Obviously, alower network quality, including a higher packet loss rate and insufficient bandwidth, willimpose a negative impact on both of OnLive and StreamMyGame, resulting lower framerates and worse graphic quality. Moreover, by quantifying the streaming quality, theauthors further reveal that OnLive implements an algorithm to adapt its frame rate tothe network delay, while StreamMyGame does not.Manzano et al. [27] collected and compared network traffic traces of OnLive andGaikai, including packet inter-arrival times, packet size, and packet inter-departure time,to observe the difference between cloud gaming and traditional online gaming from theperspectives of network load and traffic characteristics. The authors reveal that the11Chapter 1. Introductionpacket size distributions between the two platforms are similar, while the packetinter-arrival times are distinct. Afterward, the same group published a paper [28] thatclaims to be the first research work on specific network protocols used by cloud gamingplatforms. They focus on conducting a reverse engineering study on OnLive, based onextensive traffic traces of several games. The authors further propose a per-flow trafficmodel for OnLive, which can be used for network dimensioning, planning optimizationand other studies.Shea et al. [29] measured the interaction delay and image quality of the OnLivesystem, under diverse games, computers, and network configurations. The authorsconclude that cloud procedure introduces 100 to 120 ms latency to the overall system,which requires future developments in both video encoders and streaming software.Meanwhile, the impact of compression mechanism on video quality is quite noticeable,especially under the circumstance with lower available bandwidth. These authors laterpresented an experimental study [30] on the performance of existing commercial gamesand ray-tracing applications with GPUs. According to their analysis, gaming applicationsin virtualized environments demonstrate poorer performance than the instancesexecuting in non-virtualized bare-metal base-line. Detailed hardware profiling furtherreveals that the pass-through access introduces memory bottleneck, especially for thosegames with real-time interactions. Another work [31], however, has opposite observationsfrom more advanced virtualization technologies. In the authors’ measurement work,rendering with virtualized GPUs may achieve better performance than pass-throughones. In addition, if the system adopts software video coding, the central processor unit(CPU) may become the bottleneck, while hypervisor will no longer be the constraint ofthe system performance. Based on this analysis, the authors conclude that currentvirtualization techniques are already decent for cloud gaming.12Chapter 1. IntroductionSuznjevic et al. [32] measured 18 games on GamingAnywhere to analyze the correlationbetween the characteristics of the games played and their network traffic. The authorsobserve highest correlation values for motion, action game and shooter games, while thecorrelation values of majority of strategy games are relatively low. In contrast, for spatialmetrics, the situation is reversed. They also conclude that the bandwidth usage for mostgames are within the range of 3 and 4 Mbit/s, except that strategy games consume fewernetwork resources. Another notable finding is that, gamers’ action rate introduces a slightpacket rate increase, but does not affect the generated network traffic volume.Lampe et al. [33] conducted experimental evaluations of user-perceived latency incloud games and locally executed video games. Their results, produced by asemi-automatic measurement tool called GALAMETO.KOM, indicate that cloud gamingintroduces additional latency to game programs, which is approximately 85% to 800%higher than local executions. This work also highlights the significant impact ofround-trip time. The measurement results confirm the hypothesis that the geographicallocations of cloud data centers are important elements in determining response delay,specifically when the cloud gaming services are accessed through cellular networks.The authors of [34] conducted a passive and an active measurement study forCloudUnion, a Chinese cloud gaming system. The authors characterize the platform fromthe aspects of architecture, traffic pattern, user behavior, frame rate and gaming latency.Observations include: (i) CloudUnion adopts a geo-distributed infrastructure; (ii)CloudUnion suffers from a queuing problem with different locations from time to time;(iii) the User Datagram Protocol (UDP) outperforms the Transmission Control Protocol(TCP) in terms of response delay while sacrificing the video quality; and (iv) CloudUnionadopts a conservative video rate recommendation strategy. By comparing CloudUnionand GamingAnywhere, the authors observe four common problems. First, the uplink and13Chapter 1. Introductiondownlink data rates are asymmetric. Second, low-motion games suffer from a periodicaljitter at the interval of 10 seconds. Third, audio and video streams experiencesynchronization problems. Fourth, packet loss in network transmission degrades gamingexperiences significantly.1.1.3 Quality of ExperienceMaintaining an acceptable QoE is the main criteria of the proposed cognitive platform formobile cloud gaming. However, measuring, modeling, and predicting cloud gaming QoEare not easy tasks because QoE metrics are subjective.Chang et al. [35] presented a measurement and modeling methodology on cloud gamingQoE using three popular remote desktop systems. Their experiment results reveal thatthe QoE (in gamer performance) is a function of frame rate and graphics quality, and theactual functions are derived using regression. They also show that different remote desktopsystems lead to quite diverse QoE levels under the same network conditions. Jarschel etal. [36, 37] presented a testbed for a user study on cloud gaming services. Mean OpinionScore (MOS) values are used as the QoE metrics, and the resulting MOS values are foundto depend on QoS parameters, such as network delay and packet loss, and contexts, suchas game genres and gamer skills. Their survey also indicates that very few gamers arewilling to pay a monthly fee for cloud gaming. Hence, better business models are criticalfor long-term success of cloud gaming. Another team [38] also conducted a subjectivetest in the laboratory, and considered 7 different MOS values: input sensitivity, videoquality, audio quality, overall quality, complexity, pleasantness, and perceived value. Theyobserve complex interactions among QoE metrics, QoS metrics, testbed setup, and softwareimplementation. For example, the rate control algorithm implemented in cloud gamingclient is found to interfere with the bandwidth throttled by a traffic shaper. Several open14Chapter 1. Introductionissues are raised after analyzing the results of the user study, partially due to the limitednumber of participants. Slivar et al. [39] carried out a user study of in-home cloud gaming,i.e., the cloud gaming servers and clients are connected over a LAN. Several insights arerevealed, e.g., switching from a standard game client to in-home cloud gaming client leadsto QoE degradation, measured in MOS values. Moreover, more skilled gamers are lesssatisfied with in-home cloud gaming.Some other QoE studies focus on the response delay, which is probably the most crucialperformance metric in cloud gaming, where servers may be geographically far away fromclients. Lee et al. [40] found that response delay imposes different levels of implications onQoE with different game genres. They also develop a model to capture this implication asa function of gamer inputs and game scene dynamics. Another group [41] makes similarconclusions after conducting extensive experiments, e.g., gamers playing action games aremore sensitive to high response delay. Claypool et al. [42] performed user studies tounderstand the objective and subjective effects of network latency on cloud gaming. Theyfind that both MOS values and gamer performance degrade linearly with network latency.Moreover, cloud gaming is very sensitive to network latency, similar to the traditionalfirst-person avatar games. Raaen et al. [43] designed a user study to quantify the smallestresponse delay that can be detected by gamers. It is observed that some gamers canperceive less than 40 ms response delay, and half of the gamers cannot tolerate greaterthan 100 ms response delay.Huang et al. [44] performed extensive cloud gaming experiments using both mobileand desktop clients. Their work reveals several interesting insights. For example, gamersare more satisfied with the graphics quality on mobile clients, while they are more satisfiedwith the control quality on desktop clients. Furthermore, the bitrate, frame rate, andnetwork latency significantly affect the graphics and smoothness quality, while the control15Chapter 1. Introductionquality only depends on the client type (mobile or desktop). Wang et al. [3, 45] built amobile cloud gaming testbed in their laboratory for subjective tests. They propose a GameMean Opinion Score (GMOS) model, which is a function of the game genre, streamingconfiguration, measured Peak Signal to Noise Ratio (PSNR), network latency, and packetloss. The derivations of model parameters are done via offline regression, and the resultingmodels can be used for optimizing mobile cloud gaming experience. Along this line, Liuet al. [46] proposed a Cloud Mobile Rendering - Mean Opinion Score (CMR-MOS) model,which is a variation of GMOS. CMR-MOS has been used in selecting detail levels of remoterendering applications, like cloud games.1.1.4 Data Compression on CommunicationsAfter game scenes are computed on cloud servers, they have to be captured in properrepresentations and compressed before being streamed over networks. Despite theconventional real-time video compression techniques that are widely applied tovideo-on-demand services, compression approaches for cloud gaming can be categorizedinto two schemes: (i) video compression, which encodes two-dimensional (2D) renderedvideos and potentially auxiliary videos (such as depth videos) for client sidepost-rendering operations, (ii) graphics compression, which encodes 3D structures and 2Dtextures, and (iii) hybrid compression, which combines both video and graphicscompression.Video compression utilizes graphics contexts to reduce the server transmission rate.The work [21] introduces a video encoder that selects a set of key frames in the videosequence and uses the 3D image warping coding to interpolate other non-key frames. Thisapproach takes advantage of the pixel depth, rendering viewpoints, camera motion patternsand even the auxiliary frames that do not actually exist in the video sequence to assist16Chapter 1. Introductionvideo coding. Another work [47] rectifies the camera rotation to produce video framesthat are more motion estimation friendly. On client computers, the rectified videos arecompensated with some camera parameters using a light-weight 2D process. In addition,a new interpolation algorithm is designed to preserve sharp edges, which are common ingame scenes.Graphics compression is proposed for better scalability, because 3D rendering is doneon individual client computers. Compressing graphics data, however, is quite challengingand may consume excessive network bandwidth. Lin et al. [48] designed a cloud gamingplatform based on graphics compression. Their platform has three graphics compressiontools: (i) intra-frame compression, (ii) inter-frame compression, and (iii) caching. Thesetools are applied to graphics commands, 3D structures, and 2D textures. Another work[49] also developed a similar platform for mobile devices, where the graphics are sent fromcloud servers to proxy clients, which then render game scenes for mobile devices. Theyalso propose three graphics compression tools: (i) caching, (ii) lossy compression, and(iii) multi-layer compression. Generally speaking, tuning cloud gaming platforms based ongraphics compression for heterogeneous client computers is non-trivial, because mobile (oreven stationary) computers may not have enough computational power to locally rendergame scenes.Hybrid Compression attempts to fully utilize the available computational power onclient computers to maximize the coding efficiency. Chuah et al. [17] proposed to applygraphics compression on simplified 3D structures and 2D textures, and send them to clientcomputers. The simplified scenes are then rendered on client computers, which is calledthe base layer. Both the full-quality video and the base-layer video are rendered on cloudservers, and the residue video is compressed using video compression and sent to clientcomputers. This is called the enhancement layer. Since the base layer is compressed as17Chapter 1. Introductiongraphics and the enhancement layer is compressed as videos, the proposed approach is ahybrid scheme.1.1.5 Adaptive TransmissionEven though data compression techniques have been applied to reduce the networktransmission rate, the fluctuating network provisioning still results in unstable servicequality to the players in cloud gaming system. These unpredictable factors includebandwidth, round-trip time, jitter, etc. Under this circumstance, adaptive transmission isintroduced to further optimize players’ QoE. It is based on common sense that, playerswould rather sacrifice video quality to gain smoother playing experience with poornetwork connections.The first work in adaptive transmission for cloud gaming was introduced by a jointwork of a Finnish research group and G-cluster in 2006 [50]. They explore the approachto adapt the gaming video transmission to available bandwidth. This is accomplished byintegrating a video adaptation module into the system, which estimates the network statusfrom network monitor in real-time and dynamically manipulates the encoding parameters,such as frame rate and quantization, to produce specific adaptive bit rate video stream.The authors utilize round trip time (RTT) jitter value to detect the network congestion,thus, decide if the bit rate adaptation should be triggered. To evaluate this proposal, thefollowing work [51] conducted experiments on a normal television with an Internet Protocoltelevision (IPTV) set-top-box. The authors simulated the network scenarios in home andhotels to verify that the proposed adaptation performed notably better.Another series of investigations, conducted by a research group from University ofCalifornia, San Diego, focus on the adaptation in mobile scenarios. Their first work [52]decomposed the cloud gaming system’s response time into sub-components: server delay,18Chapter 1. Introductionnetwork uplink/downlink delay, and client delay. Among the optimization techniquesapplied, rate-selection algorithm provides a dynamic solution that determines the timeand the way to switch the bit rate according to the network delay. As a further step,work [5] studies the potential of rendering adaptation. The authors identify the renderingparameters that affect a particular game, including realistic effect (e.g., colour depth,multi-sample, texture-filter and lighting mode), texture detail, view distance andenabling grass. Afterward, they analyze these parameters’ characteristics ofcommunications and computation costs and propose their rendering adaptation scheme,which consists of optimal adaptive rendering settings and level-selection algorithm. Withthe experiments conducted on commercial wireless networks, the authors demonstratethat acceptable mobile gaming user experience can be ensured by their renderingadaption technique. Thus, they claim that their proposal is able to facilitate cloudgaming over the mobile network. Subsequent works, including [46, 53], provide more solidexperiments to support their claims and further extend their application scenarios tocloud mobile rendering for rich multimedia applications.Other aspects of transmission adaptation have also been investigated in the literature.He et al. [54] considered adaptive transmission from the perspective of multi-player. Theauthors calculate the packet urgency based on buffer status estimation and propose ascheduling algorithm. In addition, they also suggest an adaptive video segment requestscheme, which estimates media access control (MAC) queue as an additional informationto determine the request time interval for each gamer, for the purpose of improving theplayback experience.Bujari et al. [55] provided a Vegas Over Access Point (VoAP) algorithm to address theflow coexistence issue in wireless cloud gaming service delivery. This research problem isintroduced by the concurrent transmissions of TCP-based and UDP-based streams in the19Chapter 1. Introductionhome scenario, where the downlink requirement of gaming video exacerbates the operationof above-mentioned transport protocols. The authors’ solution is to dynamically modifythe advertised window, in such way the system can limit the growth of the TCP flow’ssending rate.Wu et al. [56] presented a novel transmission scheduling framework dubbed AdaPtiveHFR vIdeo Streaming (APHIS) to address the issue in cloud gaming video delivery throughwireless networks. The authors first propose an online video frame selection algorithmto minimize the total distortion based on network status, input video data, and delayconstraint. Afterward, they introduce an unequal forward error correction (FEC) codingscheme to provide differentiated protection for Intra (I) and Predicted (P) frames withlow-latency cost. The proposed APHIS framework is able to appropriately filter videoframes and adjust data protection levels to optimize the quality of high frame rate (HFR)video streaming.Hemmati et al. [57] proposed an object selection algorithm to provide an adaptivescene rendering solution. The basic idea is to exclude less important objects from thefinal output, thus consuming less processing time for the server to render and encode theframes. In such a way, the cloud gaming system is able to achieve a lower bit rate tostream the resulting video. The proposed algorithm evaluates the importance of objectsfrom the game scene based on the analysis of gamers’ activities and does the selectionwork. Experiments demonstrate that this approach reduces streaming bit rate by up to8.8%.1.2 MotivationsAs discussed before, cloud gaming is a gaming system that leverages the cloud to enhancethe service provisioning for players. To avoid confining ourselves into a specific20Chapter 1. Introductionarchitectural design and technology, we investigate the essence of cloud gaming designfrom the perspective of a software program. Essentially, a game is a software programwritten in programming languages. Despite object-oriented or procedure-oriented design,we consider gaming as a loop procedure that enables the interaction between players andgame logic. This particular procedure might contain different input/output (I/O)methods and involve information exchange between multiple players. However, ingeneral, a game program is considered to be constructed by a series of modules withdistinct functionality.Fig. 1.2 illustrates a modularized game. We can see that a multi-player game consistsof four main modules: the Input Module receives control messages from players; theGame Logic Module is in charge of manipulating gaming content; the Networking Moduleexchanges various information with the game server, including the interactions with otherplayers; the Rendering Module renders the game video and presents to its player. In fact,if we look into the details of the Game Logic Module, we can further divide it into anumber of components. These components invoke one another and interact with thenetwork interface, rendering engine and I/O interface, to facilitate the gaming procedure.The set of red arrows in the figure demonstrates one of the interactions between theplayer and the game system during a gaming session. The player’s instructions arerelayed to component 5 by the Input Module. Afterward, the processed information isdelivered to component 7, where the Networking Module is invoked to conductinformation exchange. After the successive processes by component 6 and component 3,the Rendering Module generates and transmits the gaming video to the player’s screen.Based on this analysis, we classify development directions of cloud gaming system intothree types:• Type I: adopts a black-box approach, where unmodified games run along with cloud21Chapter 1. IntroductionFigure 1.2: A Modularized Cloud Gaming Programgaming servers. The rendered audio and video are captured, compressed, andstreamed by cloud gaming servers to cloud gaming clients as if they are standardaudio/video streams. Most commercial cloud gaming platforms take the black-boxapproach, probably because of its simplicity and short time-to-market. Suchapproach, however, leaves limited rooms for optimization. According to Fig. 1.2,Type I cloud gaming is associated with cut 1, the terminal only contains theInputModule, while the cloud hosts all of the remaining modules/components.• Type II: refers to the cloud games that utilize terminals’ computational power forgraphical rendering. The rendering functions can fully or partially rely on theplayers’ devices, which are associated with cut 2 and cut 3 in Fig. 1.2, respectively.Type II cloud gaming servers may perform more efficient data compression by using22Chapter 1. Introductiongraphical information of the game scenes, and thus significantly reduce the networktransmission cost. However, this requires augmentation of game software to exposein-game contexts, such as camera location and orientation, for better interactionlatency and graphics quality.• Type III: dictates future programming paradigms, where games are re-written usingcloud gaming Software Development Kits (SDKs). The cut between modules hostedin the player’s device and those hosted in the cloud in Fig. 1.2 can be anywhere,according to the overall system optimization. While new programming paradigmsoffer more rooms for optimization, they are not compatible with existing games andimpose steep learning curves for game developers.Figure 1.3: Comparisons among the three types of cloud gaming platforms23Chapter 1. IntroductionThus far, we have briefly discussed some pros and cons of the three types of cloudgaming platforms. Fig. 1.3 compares these cloud gaming platforms from the aspects of:(i) players, (ii) developers, and (iii) terminals. For game players, the Type I approachoffers almost every existing game but at lower quality. For game developers, Type IIIleads to higher development overhead. For terminals, Type II requires the most capablehardware, as it needs to decode graphical information and perform scene rendering locally.In general, Type III, representing the future programming paradigm approach, appears tooffer more optimization opportunities at the expense of higher implementation complexity.It is, therefore, interesting to see if the gamers’ demand for high gaming experience justifiesthe additional cost due to the implementation complexity.We believe commercial cloud gaming services will start to implement Type II cloudgaming services, which leverage in-game contexts to either optimize the gaming experienceor reduce the hardware cost. The multimedia research communities have proposed context-aware optimization algorithms for cloud gaming videos, which can be readily deployed oncommercial cloud gaming platforms. Moving from Type II to Type III may happen later,due to the high implementation complexity. Web games, facilitated by centralized remoteserver processing and ubiquitous local browser rendering, can be considered the primarystep in this direction. How soon this will happen totally depends on the development oftechnology and whether there are strong demands on high-fidelity cloud gaming.Currently, these three types of cloud gaming paradigms will coexist for a period of time,as their advantages and disadvantages are complementary to each other. In this thesis, weoptimize players’ QoE for Type I and Type III, focusing on video encoding and softwaredecomposition, respectively.First, motivated by interactive multi-view streaming system [58], we consider exploringthe correlations between video frames among multiple players in the same game scenario.24Chapter 1. IntroductionWith the proposed cooperative video sharing system, in-game context (similar objects andbackground in the same scenes) are leveraged to better compress the gaming video, whilethe game programs running in the cloud remain unmodified.Second, motivated by the diverse hardware capacity of players’ terminals andubiquitous gaming scenarios among different platforms, we consider a future paradigmthat enables decomposition on game programs during their development. In this case,components with independent functions from one single game program can migratebetween cloud and terminals, in order to dynamically adapt its service to the features ofthe components and the various system environment. In particular, the platformmonitors the real-time environment status, sets an optimization target (e.g., the overallinteraction latency, computational resource upper bound, bandwidth ceiling) and achievethe target through dynamic partitioning.1.3 Research Questions and ChallengesVideo sharing cooperative cloud gaming reduces bandwidth consumption by furthercompressing the video frames with additional references from peering devices. However,it also imposes several challenges and research issues. First, while the correlation betweenframes within single video streams have been extensively studied, the frame correlationmodel among different players in the same scene is still unknown. Being subject togaming contents (e.g., the map size, avatar behavior), the similarity levels among peerplayers’ frames will directly affect the encoding efficiency for the inter-video frames.Second, the foundation of video sharing requires an additional peer to peer (P2P)network, which supports the exchanges of complementary frames among players’terminals. Given a secondary ad hoc network as this infrastructure, the network topologyand stability for engaging devices are yet to be investigated. System performance in the25Chapter 1. Introductionpresence of device mobility could also be an important issue. Third, the fast responsivenature of digital games makes real-time encoding and decoding mandatory. The latencyintroduced by ad hoc networks and additional cooperative decoding needs to beformulated and restricted. We address these issue in Chapter 2.To enable decomposed cloud gaming, dynamic code partitioning is the most criticalissue. Assuming the system can derive all accurate statistics from the cloud and terminal,there are still many challenging issues in making real-time partitioning decisions for runninggame instance. First, a prediction based on current state is necessary, as the goal is toadapt the service level to the ever changing environment. Second, the optimization targetsunder distinct circumstances are not always the same. How to model these targets withquantitative approaches is still unknown in this area. Third, system optimization can onlybe performed under the constraint that the QoE of all players are satisfied. The system,at least, needs to guarantee an acceptable QoE for most cases, which should be formulatedas restrictions in all decision makings. We provide our approaches to these challenges inChapter 3.Decomposed cloud gaming platform is presented as the future direction of cloudgaming. However, from a practical view, the novel idea of decomposition on a gameprogram also brings multiple research questions on implementation. First, how toconduct decomposition on a game program is still an open issue. Second, to supportinstant play without installation, the proposed system should support a dynamic codemigration mechanism, with which the components in the cloud can be dispatched toplayers’ terminals during the gaming sessions. Third, the invocation among components,especially remote components, requires an efficient message protocol. We still need extraefforts on developing a solution that implements global variables for decomposedfunctions. Fourth, the cognitive engine that makes a real-time decision for dynamic26Chapter 1. Introductioncomponent partitioning requires accurate and up-to-date information on systemenvironment, terminal status and game states. An explicit implementation solution tofacilitate this is yet to come. We address above issues in Chapter 4.1.4 ContributionsIn this section, we outline the contributions in this thesis to address the above-mentionedchallenges. The main contributions are summarized as follows:• In Chapter 2, we investigated a cooperative video compression technique on Type Iblack-box paradigm. To the best of our knowledge, this is the very first empirical workstudying the correlation model of gaming videos among multiple players in the samegaming scene. Also, this is the first cooperative encoding attempt for multiplayergames. We employed the frame sharing techniques in multi-view videos to gamingapplications, focusing on QoE optimizations for gamers.• In Chapter 3, we presented a cognitive cloud gaming paradigm that balancesresource utilization between cloud and terminals, facilitated by decomposedsoftware architecture and flexible migration of gaming components. This is the firstdecomposition study for game programs that require extremely low response delay.Focusing on this feature, we model the inter-component relationship as a graph tofurther formulate the resource optimization as a graph partitioning problem. Wealso conducted the very first work in analyzing the feasibility of decomposition forprograms.• In Chapter 4, we investigated the principles in software decomposition and designthe blueprint from the engineering perspective. We introduced a novel performanceprobing solution, which utilizes the dispatch procedure of mobile agent to conduct27Chapter 1. Introductionthree independent tasks together, which include collecting data from terminals tocloud, estimating the hardware capacity of terminals and measuring real-timenetwork status. By this innovative approach, the system is capable of measuringthe environmental context (e.g., network and hardware) and players’ behaviors.With discussions of all practical issues and solutions, we implement the very firstproposed testbed and develop three game prototypes to validate the feasibility ofcomponent based game programs and provide the first-hand experimental results.1.5 Thesis OrganizationThis thesis is organized as follows. In Chapter 2, we discuss a cooperative video sharingsystem among multiple players in the same crowd playing the same game via a secondaryad-hoc network. The goal is to encourage exploiting the similarities of video framesamong players to improve players’ overall QoE. Afterward, we present the theoreticalidea of a decomposed cloud gaming in Chapter 3. We provide a novel cognitive resourceoptimization for the decomposed cloud gaming system under diverse targets. Extensiveexperiments have been performed to show that intelligent partitioning leads to bettersystem performance, such as overall latency. In Chapter 4, we discuss the challenges indeveloping such decomposed cloud gaming system with cognitive code migrationcapacity. We present a practical design methodology and implement the proposedplatform. Prototype games have demonstrated the validation and efficiency of ourproposal. The conclusion and some potential future work are presented in Chapter 5.Finally, the Appendices present the assumptions for the channel models and the proofsfor the theorems.28Chapter 2Ad hoc Cloudlet-AssistedMultiplayer Cloud Gaming System2.1 IntroductionAs discussed in Chapter 1, a conventional Type I cloud gaming system relies on a gaming-on-demand model. This paradigm employs a remote rendering architecture, whereby thecloud gaming service providers host their video games in cloud servers and stream thegaming video frames to the players’ terminals over the Internet. In reverse, the interactionsfrom game players are transmitted to the cloud servers over the same networks [20]. Inthis context, the cloud intrinsically becomes an interactive video generator and streamingserver, while the users’ terminals function as the event controllers and video displays. Withthis approach, the cloud gaming service enables the players to run sophisticated gamesdespite the restricted hardware capacity of the terminals, at the expenses of higher costsand energy consumption in communications to access the Internet. It is obvious that videoframe transmissions via the Internet can consume a huge amount of network resources,which can lead to long delays in game responses [6]. Even though there have been plentyof efforts devoted to the data compression on communications (discussed in Section 1.1.4),due to the constraints imposed by existing network infrastructure and mobile networks’charging policies, gaming-on-demand has yet to reach its promised potential.In the same time, another trend for the game industry is the online multiplayer scenario.29Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemNowadays, game players are no longer satisfied with enjoying the games alone but preferto connect to others. The interaction between players brings more challenges in the designof game servers.In this chapter, we consider these two trends together to come up with the novel ideaof improving players’ QoE. We study the correlations of the gaming videos in multi-playergaming scenarios and propose an ad hoc cloudlet-assisted cloud gaming system to exploitthe correlations among peer players’ gaming video. Inspired by the idea of peer-to-peersharing between multiple players in the same game, we investigated a multiplayer cloudgaming system with cooperative video sharing. Mobile devices are connected to the cloudserver for real-time interactive game videos while sharing the received video frames withtheir peers via a secondary ad hoc network.We consider the whole system from the following aspects: i) Server TransmissionRate: an intuitive approach to improving system performance is to substantially reducethe transmission rate from cloud server to the game clients in order to overcome thebottleneck of Internet access, which ensures the decode frame rate with poor Internetconnections; ii) Mobility Issue: the proposed system assumes an ideal case in which thenetwork bandwidth within the ad hoc cloudlet is unlimited; this is not realistic aswireless communications constrain the sharing of video frames only among mobile devicesthat are within a certain distance of each other, which form a time-variable group due tothe mobility of terminals. iii) Network Diversity Issue: the previous work assumes thatall mobile devices access the cloud through a common network with the same quality ofservice (QoS); however, the networks between individual terminals and the cloud mayhave different QoS due to differences in network traffic levels and channel conditionsexperienced by the terminals. Variations of network quality of service (NQoS) willstrongly affect the overall system performance. iv)User Quality of Experience (QoE): the30Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemproposed system only focuses on the optimization of server transmission rate withoutconsidering the effect of NQoS. In fact, optimizing encoding to minimize servertransmissions may result in poor QoE as devices receiving larger frames from the cloudwhile experiencing a low network bandwidth might degrade gaming video decoding at allplayers’ terminals. To this end, we investigate a QoE-oriented multiplayer cloud gamingsystem with ad-hoc cloudlet assistance.The reminder of the chapter is organized as follows. We review related work inSection 2.2 and provide a system overview with modeling in Section 2.3. Then, weformulate the system and its QoE optimization problem in Sections 2.4 and 2.5,respectively. We propose two heuristic algorithms to obtain sub-optimal solutions withlower computational complexity in Section 2.6. Empirical experiments and trace-drivensimulations, respectively, demonstrate the superior system performance compared withexisting systems in Sections 2.7 and 2.8. Section 2.9 concludes the chapter.2.2 Related Work2.2.1 Ad Hoc CloudletAn ad hoc cloudlet is defined as a cooperative cloudlet formed by a group of terminals viamulti-homed ad hoc network connections [59] [60] [61]. We stress that our assumption ofdevices being connected to multiple networks simultaneously, such as wireless wide areanetwork (WWAN) to gaming cloud and ad hoc cloudlet to neighbor peers, is a commonone in the literature [62–64] and realizable in practice (e.g., with smartphones), wheredifferent optimizations are performed exploiting the multi-homing property. It is shownin [62] that aggregation of an ad hoc group’s WWAN bandwidths can speed up individualpeers’ infrequent but bursty content downloads just like web access. An integrated cellular31Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemand ad hoc multicast architecture is proposed in [63], where the cellular base stationdelivers packets to proxy devices with good channel conditions and then the proxy devicesutilize local ad hoc wireless local area network (WLAN) to relay packets to other devices.Recently, [64] utilizes a secondary ad hoc WLAN network for local recovery of WWANbroadcast/multicast packets lost during WWAN transmissions by exploiting cooperationamong peers. Our proposal extends this body of work on cooperative multi-homed networksto interactive light field streaming by exploiting the correlation between requested imagesand content residing in peers’ caches to lower server transmission rate.2.2.2 Correlations of Videos FramesAn inter-frame, e.g., P-frame, is a frame in a video compression stream, which is expressedin terms of one or more neighbor frames. In contrast to an Intra-frame (I-frame) codingthat performs compression relative to information contained only within the current frame,the “inter” part of the term refers to the use of inter-frame prediction. Its size, which affectsthe system performance, is subject to the correlations between the encoded video frames.The light field [65] and multiview [66] video streaming have conducted studies on this topic.The light field is a large set of spatially correlated images of the same static scene capturedusing a 2D array of closely spaced cameras. The correlations of light field images are studiedand formulated in [67], which indicates that the correlation between two different viewsto a static scene is related to the geographical distances between each other. Interactivemultiview video switching [58] designs a pre-encoded frame representation of a multiviewsequence for a streaming server, so that streaming clients can periodically request desiredviews for successive video frames in time. However, compared to light field and multiviewswitching, the modeling of correlations between players’ views is more complicated. Thereare infinite numbers of views as the players are adjusting their personal views while they32Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemare walking through the scene and participating in a battlefield. The dynamic switchingmakes the correlation model hard to predict.2.2.3 Real-time Video EncodingUnlike light field and multiview switching, video encoding for cloud gaming is essentially areal-time process. The cloud encodes video frames immediately after the game scenes arerendered. The fundamental idea of encoding is very simple: it starts with an intra-codedframe, e.g., I-frame, and then followed by a certain number of interframes, such as P-frames[68], distributed source coding (DSC) frames [69], etc. Therefore, in order to achieve thedesired trade-off between bit rate and error rate, how to determine the sequence of varioustypes of frames has become one of the most critical problems in video encoding. In recentvideo encoding research, the GOP (Group of Pictures) [70] length is set to be adaptive,which implies a structure with one I-frame and a variable number of inter frames.2.3 System ArchitectureThe architectural framework of proposed cloudlet-assisted multiplayer cloud gaming systemis illustrated in Fig. 2.1. Similar to the existing cloud gaming work, instances of GameEngine are hosted in the cloud to provide gaming services to players. They are connectedto a Multiplayer Game Server in conventional fashion to facilitate interactions betweenavatars.The novelty of the proposed system is to introduce two additional components: 1)Video Encoder Server is acting as a gateway, which exploits the correlations betweenvideo frames for different players to perform centralized encoding with the purpose ofminimizing server transmission rate. In this work, we consider cloud as an infinite resourceprovider. Therefore, the computational power of the encoder server is unlimited. 2)33Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemCloudGame Engine Game Engine Game Engine Game EngineVideo Encoder Server……………………Ad Hoc CloudletMultiplayer Game ServerFigure 2.1: Ad Hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemAd Hoc Cloudlet is a cooperative ad hoc cloudlet constructed by the participatingmobile devices. They utilize a secondary network, e.g., WiFi ad hoc network, to share thevideo frames they received from the cloud server. Similar to previous studies [71][72][73],we assume the network bandwidth within the ad hoc cloudlet is sufficiently large for allmobile devices in the immediate neighborhood to share their frames when needed. Thus,the bandwidth constraint inside the cloudlet will not be explicitly modeled.34Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System2.4 System Modeling and FormulationIn this section, we model the ad-hoc cloudlet-assisted cloud gaming system, and formulatethe reputation-based multiplayer fairness problem.2.4.1 Avatar behavior ModelWe choose to model the avatar behavior in a third person game, since this is the most classicand popular model, as summarized in [24]. We define the gaming map as a 2D map with anm×m screen. On this particular map, we set all avatars’ initial positions to the center of themap and model the walking strategies of n players’ avatars as random walk and group chasewith probabilities prw and pgc , respectively. This is an observation result of multiplayergames: players are randomly moving and hunting in the world (random walk), however,they are also prone to gather together with their teammates or opponents, in order toperform teamwork or competition (group chase). For random walk movements, an avatareither holds its position with probability ph or moves in its adjacent nadj directions withidentical possibilities pc. To simplify the model, we set ph = pc =prwnadj+1. For group chasemovements, an avatar randomly selects another avatar in the scene and move towardsit for a certain period of time tchase. Let the probability of group chase movement bepgc = 1− prw, then the probabilities of any other n− 1 target avatars to be chased will allequal to pappr =pgcn−1 . Note that we set the moving unit for each avatar in a unit time to bek pixels and denote w and h as the width and height of the gaming screen in pixels. Giventhat the system restricts the avatar to be in the center of the screen, all avatars’ positioncoordinates will be restricted to (x, y), where x ∈ [0, (m−1)wk], y ∈ [0, (m−1)hk].With this model, we formulate the locations of all n avatars into two 1 × n vectorsX and Y , in which (Xi, Yi) indicates the ith avatar’s coordinate. With this approach, allavatar behavior models can be represented by the changes of vectors X and Y .35Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System2.4.2 Encoding StructureIn this section, we study the frame size for two types of P-frames: Intra-stream P-frameand Inter-stream P-frame. We denote Intra-stream P-frames as video frames that predictto their previous frames in the same video stream and the Inter-stream P-frames as thosepredict to peer game videos’ frames.Intra-stream P-frame: Frame size of Intra-stream P-frame is subjected to thevariance of the game video content. Apparently, if the avatar is experiencing a moredynamic scene, the P-frame size will be larger. For example, when the players areparticipating in a large Diablo battlefield, where many “wizards” and “demon hunters”are casting magnificent full-screen magics, the video content’s amplitude of variation willbe dramatic.Inter-stream P-frame: Pinter, the frame size of Inter-stream P-frame, is subjected tothe correlation between two videos for two peering game players. Before modeling Pinter,we need discuss the types of multiplayer games: first-person game, second-person game andthird-person game. In video games, first-person refers to a graphical perspective renderedfrom the viewpoint of the player character, such as Counter-Strike. The second-person issimilar to first-person but rendered from the back of the player character, which means theplayer can see their avatar on the screen, e.g., Grand Theft Auto. In contrast, third-persongames provide the players a sky view, so-called God-view, to easily observe surroundingenvironment of the avatar and make a quick response. Classic third-person games includeDiablo, Command & Conquer, FreeStyle, etc. For first-person and second-person, thegame video is generated from the view of the avatar, where the correlation model of videoframes are similar to a dynamic light field streaming. In contrast, the correlation modelfor third-person games is much simpler: the videos for peering players are very similar,or even identical, when their avatars are geographically close to each other. In fact, the36Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemmost popular multi-player games nowadays are usually designed to be third-person, sincethey provide clearer environmental information to the players. The most representativeones include League of Legend (LoL), Defense of the Ancients (DotA), and Diablo. To thisend, we consider third-person games in this work. Since the players are all in God-view,we calculate the overlap of the two video with the avatars’ coordinates, given most of thethird-person games rolls the map with an avatar-centric manner. Fig. 2.2 demonstratestwo correlated videos for player 1 and player 2.Figure 2.2: Correlation of Inter-Video Frames (Diablo III)Fig. 2.3 shows an example of frame dependency in a four players’ scenario. The squaresrepresent video frames in video streaming, in which the paired number (t, i) denotes aframe according to the time slot t and player i. The arrows represent the frame encodingdependencies: as depicted, the video frames are able to be encoded in two dimensions.Intra-stream P-frame are those predicted by their previous frames in the same video stream,while the Inter-stream P-frames are those predicted by peer game videos’ frames. For37Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systeminstance, Pintra[(1, 2)→ (0, 2)] indicates player 2’s second Intra-stream P-frame is predictedfrom player 2’s first decoded image, while Pinter[(1, 3)→ (1, 2)] indicates player 3’s secondinter-stream P-frames is predicted from player 2’s second decoded image.Figure 2.3: Frames Correlation in Real-time Multiplayer Game VideosThe size Pa of an Intra-stream P-frame is subject to the variance of the game videocontent. In contrast, the size Pe of an Inter-stream P-frame is subject to the correlationbetween two video streams for corresponding peering game players i and j with coordinatesof (Xi, Yi) and (Xj, Yj), which is formulated as a function Pe(Xi, Yi, Xj, Yj). Note that thisfunction ensures that all avatar behavior models can be reflected in the Inter-stream P-frame’s size. With Pa and Pe, we define the video frame correlation matrix P . Thus, anelement Pij, i 6= j stores the frame size of an Inter-stream P-frame to decode ith player’svideo frame by predicting jth player’s. In contrast, Pkk saves the frame size of an Intra-stream P-frame, which enables the kth player to decode his/her current video by predictingthe proceeding frame of his/her own video.38Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemNoted that, to simplify the estimation of server transmission rate, we assume that theGOP length is infinite in the present work. Thus, the encoded video stream consists ofa sequence of P-frames, after the first I-frame transmission. In fact, inserting I-framesto the original encoding will increase the original video frame size, which provide moreopportunities for our proposed algorithm to optimize.2.4.3 Terminal Mobility ModelTo demonstrate the mobility of user terminals, we set up a square area of r × r m2 inwhich n game players are confined. The i-th player’s physical position is represented as(ui, vi), where i = 1, 2, ..., n and ui ∈ [0, r], vi ∈ [0, r] are the X- and Y- coordinates of thelocation. In a typical gaming engagement, players are initially gathered in the center ofthe area and then randomly move within s meters in both directions every 30 seconds, i.e.,∆ui ∈ [−s, s],∆vi ∈ [−s, s] where ∆ui and ∆vi represent the movements of the ith playerin X- and Y- directions in every 30 seconds. The maximum inter-device communicationdistance, or the device communication range, is c meters.Based on this model, we formulate the relationship between n players’ terminals as ann × n matrix E. The numeric value of an element in matrix E is defined to be either 0or 1, where Eij = 1 represents that the ith player’s terminal is within the communicationrange of jth player’s terminal. The matrix E is derived by:Eij = 1, Dij ≤ c0, otherwise (2.1)whereDij =√(ui − uj)2 + (vi − vj)2 (2.2)39Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemis the distance between the ith and jth players. To use the matrix E to represent theconnectivity reveals the possible problem of link quality varying by dramatic changes inad hoc network topologies. For example, in the encoding phase, the server uses E todesign an encoding solution that Player 1 decodes its frame by predicting Player 2’s frame.However, the connectivity between Player 1 and Player 2 is lost in the decoding phase, asthe matrix E has been altered according to the terminals’ mobility. In this case, Player1’s frame is not decodable. While this problem can occur, its probability can be keptsufficient low by explicitly controlling the latency between encoding and decoding of videoframes to be within some acceptable levels (e.g., 200ms is “maximal tolerable” and 120msis “hardly noticeable.”, as stated in [37]). In general, the mobility of terminals will notcause dramatic network topology change in such a short time interval. Therefore, thisproblem is negligible.2.4.4 Network Quality of Service ModelIn practical scenarios, the players may access the cloud over different WWANs andexperience different NQoS, according to the network traffic load, wireless signal strength,channel propagation condition, etc. According to a previous study [74], the players’ QoEare impacted by several NQoS factors, such as network bandwidth ξb, network latency ξl,network delay variance ξv, and network loss rate ξr. These factors can be formulated intoan abstract and unified NQoS level η as a function:η = K(ξb, ξl, ξv, ξr) (2.3)We can always find a function K that converts the NQoS parameters to an integervalue η within the range [1, nq], where nq represents the best NQoS level. According to themobile devices’ mobility and the wireless signal coverage, a mobile terminal’s NQoS level40Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemis expected to change from one level to another over time.!"#$ !" !"%$&&& &&&'("#)*"+ '("*",)+'("*"#)+ '(",)*"+'("*"+Figure 2.4: Markov Process for the Change of NQoS LevelIn reality, the change of NQoS is affected by many unpredictable factors. In this work,we assume these changes are continuous, thus, the QNoS level in the next time slot dependsonly on the current QNoS level. Based on this assumption, we model the variations of NQoSlevel as a Markov process in which η transits from level a to b with probability p(a, b), asillustrated in Fig. 2.4.According to this model, each terminal device is associated with one NQoS level η,which varies from time to time. Thus, a 1×n vector U is sufficient to represent the NQoSfor n players. However, to simplify our formulation and optimization in following sections,we formulate the NQoS diversity as an n × n matrix N , which is an expansion of U byN = [U,U, ..., U ]. Note that, ∀x, i ∈ [1, ..., n], Nix = Ui represents the NQoS level η of theith player.2.4.5 Video Encoding SolutionFor the proposed system, the most critical issue is to find an optimal video encoding solutionthat fulfills the requirements. In this chapter, we represent a video encoding solution byan n× n matrix M , where n represents the number of players. Each element in matrix Mcan take a numeric value of either 0 or 1, where Mij = 1 represents that the ith player’s41Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemvideo frame is decoded by predicting to jth player’s. Thus, an element Mkk = 1 impliesthat the kth player’s terminal will download an Intra-stream P-frame from the cloud, whileMij = 1, i 6= j represents that the ith player’s terminal is able to exploit the correlationsfrom the jth player’s decoded video frame, and hence its video frame is decoded by thecombination of Inter-stream P-frame downloaded from cloud and a decoded DSC videoframe DSC-frame received from the jth player’s terminal via the ad hoc network.To guarantee that the solution represented by a particular M can be adopted as asystem encoding solution, a validation of the solution is required.Information IntegrityIn the distributed decoding system facilitated by the ad hoc cloudlet, obviously at leastone player needs to download an Intra-stream P-frame from the cloud, in order to providea future reference for the peer terminals. Thus, the first condition is that at least one ofthe diagonal elements of M is 1:tr(M) =n∑i=1Mii ≥ 1 (2.4)where tr(M) denotes the trace of square matrix M .Decoding ReliabilityAll players’ terminals require either Intra-stream P-frame or Inter-stream P-frame todecode their video frames. Hence, a second condition is that the sum of elements in eachrow of M is equal to 1:∀i ∈Mij,n∑j=1Mij = 1 (2.5)42Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemLoop-FreeWith the above checks, a solution is still not guaranteed to be valid. A problem calleddecoding loop can cause invalid solutions in the system. To solve this problem, we considernon-zero elements in M as the decoding vectors for n players and further represent thesevectors by a graph G = (V,E), where finite sets V and E contain the nodes and directededges, respectively. Some notations are defined as follows for the analysis.• Node: Each player is represented as either an inter-node γx or an intra-node λx. If aplayer will download images from the server via Intra-stream P-frame, the player isrepresented as an intra-node; otherwise, the player is represented as an inter-node.The set of all nodes V = {γ1, γ2, ..., γm, λ1, λ2, ..., λn} contains m inter-nodes and nintra-nodes.• Edge: Each edge connects two nodes and has a direction. An edge pointing from γ1to γ2 is represented as (γ1, γ2). If players 1 and 2 are represented as inter-nodes γ1and γ2, respectively, then (γ1, γ2) indicates that player 1 will download images fromplayer 2 via an Inter-stream P-frame.• Path: A finite sequence of edges connecting distinct nodes forms a path. For example,Px = (γ1, γ2, ..., λn) is a path with a starting point γ1 and an end point λn. An isolatedintra-node (no edge pointing in) is on a zero-path Py = (λn).• Loop: A path combined with an edge pointing from the end point of the path to thestarting point of the path is called a loop. For Px = (γ1, γ2, ..., γn), Cy = Px+(γn, γ1)is a loop with n nodes {γ1, γ2, ..., γn}.• Valid Path: A path ending at an intra-node is called a valid path. A zero-path isalso a valid path.43Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System• Decoding Dependance: An intra-node decodes its image by default (by downloadingdirectly from the server, which is not shown in our analysis.) An inter-node decodesits image only if it is on a valid path.• Valid System: If each node in the system can decode its image, then this system isa valid system.We here make the statement that, if a graph G contains a loop, its correspondingencoding solution M is not able to be decoded in the ad hoc cloudlet. The proof is asfollows:Lemma 1 No intra-node or valid path is on a loop.Proof Since any intra-node does not point to any other node, it must not be in a loop.For the same reason, since any valid path ends at an intra-node that is not in a loop, thispath must not be in a loop.Theorem 1 If a system is valid, then no loop is present in the system.Proof Since the system is valid, each inter-node must be on a valid path. By Lemma 1,no intra-node or inter-node is in a loop, so no loop is present in the system.Theorem 2 If no loop is present in a system, the system is valid.Proof Suppose to the contrary that a system with no loop is not valid. Then, thereexists an inter-node γx in the system such that by choosing γx to be the starting point,we can always find a longest path Px = (γx, γx+1, ..., γx+n) with n edges. Since Px is thelongest path (i.e., γx+n cannot point to an (n + 2)th node) and inter-node γx+n has anedge pointing out, there must exist an edge (γx+n, γx+k) such that γx+n must point to γx+kwhere k = 0, 1, 2, ..., n− 1. Then (γx+k, γx+k+1, ..., γx+n) + (γx+n, γx+k) form a loop, whichis contradictory to our assumption. Therefore, the theorem has been proven.44Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemTherefore, a system is valid if and only if no loop is present in a system.In order to provide a loop-free solution, it is mandatory that M satisfies the followingequation:∀p ∈ {1, 2, ..., n}, tr(Mp) = tr(M) (2.6)Proof: Please refer to Appendix A.Mobility ConstraintsThe decoding procedure is constrained by the wireless connectivity in the ad hoc network,which is specified by the neighboring matrix E in our system definition.However, in an ad hoc network, the mobile terminals may also communicate with eachother over multiple hops. Denote h as the maximum number of hops allowed, we derivethe h-hop neighboring matrix Ê as:Êij = pos(E˜ij) = 1, E˜ij > 00, otherwise (2.7)whereE˜ = Eh (2.8)Hence, we hereby formulate the mobility constraints into the validation of solution M ,as shown in following equation:M = M  Ê (2.9)45Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemMulti-hop Decoding ConstraintsWith the proposed encoder, we are able to determine the optimal solution for inter-videoencoding. However, there is a practical issue to be addressed when realizing the system:since the encoder efficiently groups correlated video frames and constructs a tree todescribe the dependency of the video frames, a multi-hop decoding might occur at theusers’ terminals. For example, in time slot t, given an Intra-stream P-framePintra[(t, 1) → (t − 1, 1)] for player 1 and two Inter-stream P-frames Pinter[(t, 2) → (t, 1)]and Pinter[(t, 3) → (t, 2)] for players 2 and 3, player 3 can only decode the video frameafter player 2 has decoded the frame by receiving the decoded image from player 1, whichintroduces larger system latency. However, gaming applications are very sensitive tolatency. Therefore, multi-hop decoding might affect the players’ QoE.To address this issue, we provide a solution that restricts the dependency of Inter-stream P-frame decoding to one-hop to guarantee an acceptable level of decoding latency.This One-Hop Inter-Stream Encoding is enforced by introducing constraints on solutionM .Define n vector V by:Vj = pos(n∑i=1Mij) = 1,∑ni=1 Mij > 00, otherwise(2.10)A solution M satisfies One-Hop Inter-Stream Encoding if and only if:∀i ∈Mii,Mii = Vi (2.11)46Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System2.5 Optimization Target2.5.1 QoE FactorThe main focus of cloud gaming system optimization is to minimize the expected servertransmission rate from the cloud. Apparently, exploiting similarities from peer players’video frames with Inter-stream P-frame of smaller packet size is generally moreadvantageous in terms of data transmission speed, power consumption, data expense andothers. However, the server transmission rate is not the only factor that impacts thesystem performance. Regarding QoE control for all players participating in thiscooperative ad hoc cloudlet, there are more variables involves such as NQoS, devicecomputing capacity, etc. For instance, with a specific encoding matrix M that minimizestransmissions, player i may be selected as the reference to which other peering terminalsdepend on for frame decoding, while it is struggling with poor NQoS or low computingcapacities. As a consequence, its delay on video image construction introduces additionallatency to the whole ad hoc cloudlet system.To this end, we introduce a novel measure QoE factor θ as an index of systemperformance, where a smaller value of QoE factor θ represents a better QoE. Thanks tothe recent development of hardware, most terminals have the computing power toperform complicated computations nowadays. Therefore, the QoE factor only considersthe two most critical parameters: server transmission load and the user’s NQoS. Theserver transmission load R is represented by an n × n matrix, where n is the number ofplayers, with elements Rij given byRij = Mij · Pij (2.12)where Pij is defined as encoding structure stated in Section 2.4.2 and Rij represents the47Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemdata size of server transmission when ith player’s video frame is decoded by predicting tojth player’s. We expect the value of the QoE factor θ to be proportional to the expectedserver transmission load R and inversely proportional to the NQoS level N . Hence, wemay consider R and N as the demand and supply [75] of the proposed system, respectively.Referring to [75], we defineθ = F(R,N) (2.13)where R and N can be negatively correlated. In this work, without loss of generality, wechoose the inverse proportional relationship between them. For instance,θ =n∑i=1n∑j=1(Rij/Nij) (2.14)However, it is possible to adapt the above model to various cases of the proposed system.2.5.2 Objective FunctionWe can now formally define the search for the optimal encoding structure as an optimizationthat finds video encoding solution M , using the calculation of video correlation matrix Pand NQoS N , in the feasible space Φ that possesses the smallest possible expected QoEfactor θ, while all constraints on the encoding solution are observed. We formulate thisoptimization problem using the following objective function:Minimize: O(M,P,N) =n∑i=1n∑j=1(Mij · Pij/Nij)Subject to: (2.4)(2.5)(2.6)(2.9)(2.11)(2.15)Note that, (2.11) represents the restriction of multi-hop decoding, which is optional inoptimizations for different purposes.48Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System2.6 Heuristic ApproachGiven a cloud gaming session with n participants, deriving the optimal encoding solutionfor all terminals incurs a complexity of 2n, which indicates a high computational costthat increases exponentially with the number of terminals accessing the cloud for gamingservices. To address this issue, we investigate two heuristic approaches to support quickQoE optimization with lower computational complexity.2.6.1 Local Greedy ApproachA local greedy approach reaches a sub-optimal encoding solution by always looking forthe smallest QoE factor in the solution space, as shown in Algorithm 2.1. It follows theprinciple of a pruning algorithm to achieve the local optima.Algorithm 2.1 Local Greedy Encoding Algorithm1: Given correlation matrix P and NQoS matrix N2: Initiate all-0 video encoding solution matrix M3: Initiate search space matrix S = P/N4: repeat5: for each Mmn! = 0 do6: Search smallest Sxy in Sii and Sim7: if exist multiple smallest Sxy then8: Search smallest Six for each Sxy9: Select Sxy with smallest Six10: end if11: Set 1→Mxy12: Set null→ Sxi13: end for14: until ∀i ∈Mij,n∑j=1Mij = 115: return MAccording to the Algorithm 2.1, the computational complexity is reduced to n2, whichis significantly lower than 2n. Note that if there exist multiple smallest Sxy, the algorithm49Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemwill further consider their potential usage as others’ references to derive a relatively betterencoding method.2.6.2 One-Hop Restricted Local Greedy ApproachTo solve the multi-hop decoding problem, another one-hop encoding algorithm as shownin Algorithm 2.2 is proposed in this section. The solution is basically the same as the localgreedy approach but it does not consider multi-hop dependency in encoding structures.Algorithm 2.2 One-Hop Local Greedy Encoding Algorithm1: Given correlation matrix P and NQoS matrix N2: Initiate all-0 video encoding solution matrix M3: Initiate search space matrix S = P/N4: repeat5: for each Mmn! = 0 and m = n do6: Search smallest Sxy in Sii and Sim7: if exist multiple smallest Sxy and x = y then8: Search smallest Six for each Sxy9: Select Sxy with smallest Six10: else11: if exist one smallest Sxy and x = y then12: Select Sxy with smallest Six13: end if14: else15: if exist multiple smallest Sxy and x! = y then16: Randomly select a Sxy17: end if18: end if19: Set 1→Mxy20: Set null→ Sxi21: end for22: until ∀i ∈Mij,n∑j=1Mij = 123: return MAccording to Algorithm 2.2, with the same value of Sxy, we set up a higher priorityto Intra-stream P-frame rather than Inter-stream P-frame, since an Inter-stream P-frame50Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemwill never be a future reference for other players with one-hop decoding restriction.2.7 An Experimental Case Study: Diablo IIThe performance of proposed system may subject to different games, since theoptimization results rely on the video correlations, which is strongly related to thevariance of contents and the camera positions of different players. In this work, we selectDiablo II to conduct our case study, since it is considered one of the most popular andrepresentative multiplayer action role-playing games in history. To simplify our model,two players (as a sorceress and an assassin) are connected to each other over a WLANand start their ventures simultaneously, as illustrated in Fig. 2.5.(a) Player 1: Sorceress (b) Player 2: AssassinFigure 2.5: A Run-Time Screenshot for Concurrent Players in Diablo IIIn order to understand the video features, we capture their gaming screen (with aresolution of 800 × 600) as lossless videos using Fraps8 and encode the videos into videoframes by FFmpeg9, which is an H.264 codec widely used in online video streaming andalso cloud gaming systems [20]. We set the encoding frame rate to 30 frames per second8http://www.fraps.com/9https://www.ffmpeg.org/51Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System(fps), number of B-frames to 0, and leave all default parameters in FFmpeg. With infiniteGOP, the frame sizes of the encoded video sequence are recorded as Intra-stream P-frameset. Note that in order to eliminate the interference from I-Frame sizes, we do not recordthe size of the first I-frame encoded by FFmpeg. On the other hand, we extract imagesequences from the two gaming videos, and again use the FFmpeg codec with identicalsettings to encode Player 2’s images into P-frames by predicting from player 1’s concurrentimage. Thus, a set of Inter-stream P-frames of Player 2 depending on Player 1 is derived.Following general research in related topics [58], we set the target video quality in terms ofpeak signal-to-noise ratio (PSNR) to 40dB. According to our measurements on the resultingvideos, the average PSNR values for the two encoded Player 2’s videos are 51.7130dB and49.2430dB, which indicate acceptable and comparable image quality for these two encodingmethods.0 1000 2000 3000 4000 5000 6000 7000 8000 9000010203040506070Time Elapsed (second)Frame Size (kilobyte)  Player 1Player 2Optimized Player 2Figure 2.6: Video Frame Sizes of Diablo2 for Two PlayersWith the numeric number of Intra-stream and Inter-stream P-frames, it is trivial to52Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemcalculate the optimal encoding solution, given Player 2 is eligible to explore the similaritybetween its video sequence and Player 1’s. As shown in the five-minute frame size tracein Fig. 2.6, the blue line indicates the real-time frame sizes of Player 1, while the red lineindicates those of Player 2. From the figure, we can see that the two players’ frame sizesfluctuate in the range of 0 to 70 kilobytes as time progresses. On the other hand, we derivethe Inter-stream P-frames of Player 2 and compare their sizes to the frame size of Player 2(red line). The smaller value between these two lines in a specific time slot is considered theoptimal frame size for Player 2, which is depicted by the green line in the figure. Clearly,Player 2 can benefit greatly from exploiting the frame similarities, resulting in a significantreduction in network transmission by 23.26% (from 111906600 bytes to 85871751 bytes).Moreover, it is also remarkable that the optimized frame sizes are smoother, in comparisonto original Intra-stream P-frame. This will enhance the QoE for cloud gaming participants,especially when network bandwidth is scarce.2.8 Trace-Driven SimulationsIn this section, we conduct trace-driven simulations to evaluate the performance of thecloud gaming system and our proposed algorithms. We first study the size of P-frames inreal scenarios and then simulate gaming sessions to evaluate the QoE optimization for theproposed system.2.8.1 Study on Intra-Stream P-Frame SizeTo obtain empirical models of Intra-Stream P-Frame size, we conduct video measurementexperiments for three different games: Diablo II, League of Legend (LoL) and NBA2K14.We played several sessions of these games and captured their videos for analysis. To simplythe comparison, we set the screen resolution of Diablo II and NBA2K14 to 800×600, while53Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemthe LoL screen is set to 1024× 768, which is the lowest game mode. After H.264 encodingwith FFmpeg, we obtain the Probability Distribution Function (PDF) of the frame sizesfor these games, as depicted in Fig.2.7.0 20 40 60 80 100 120 140 160 180 20000.511.522.53 x 10−4Intra−Stream P−Frame Size (KB)ProbabilityData Fitting for Diablo2  Diablo 2 Intra−Stream P−Frame SizeFitting Result(a) Intra-Stream P-frame Size for Diablo II0 20 40 60 80 100 120 140 160 180 20000.511.522.53 x 10−4Intra−Stream P−Frame Size (KB)ProbabilityData Fitting for LoL  LoL  Intra−Stream P−Frame SizeFitting Result(b) Intra-Stream P-frame Size for LoL0 20 40 60 80 100 120 14000.511.5x 10−4Intra−Stream P−Frame Size (KB)ProbabilityData Fitting for NBA2k14  NBA2K14  Intra−Stream P−Frame SizeFitting Result(c) Intra-Stream P-frame Size for NBA2K14Figure 2.7: An Illustration of Distributions of Inter-stream P-frame Sizes54Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemAs we can see from the figures, the PDFs of video frames demonstrate different patternsfrom game to game. This implies that we cannot represent all types of games with a singlemodel. To support our subsequent simulations, we conduct curve-fitting for Diablo II toobtain the following piecewise function:f(x) =a1x2 + b1x+ c1, 2.03 ∗ 10−3 ≤ x ≤ 0.91a2x2 + b2x+ c2, 0.91 ≤ x ≤ 9.62a3eb3x, 9.62 ≤ x ≤ 193.36(2.16)where a1 = −1.136 ∗ 10−3, b1 = 1.234 ∗ 10−3,1 = −9.428 ∗ 10−5, a2 = 2.101 ∗ 10−6, b2 =−2.092 ∗ 10−5, c2 = 7.765 ∗ 10−5, a3 = 1.907 ∗ 10−4, b3 = −0.1178. The three R-squaredvalues for the goodness of fit are R21 = 0.8968, R22 = 0.6013 and R23 = 0.9437. Based onthis equation, we create a random frame size generator x = f−1(y) to simulate the varietyof Intra-stream P-frames.2.8.2 Study on Inter-Stream P-Frame SizeAs stated in our system model, we assume that the distances between avatars are positivelycorrelated to the frame sizes of Inter-stream P-Frames. In this section, we conduct a two-player experiment based on Diablo II to verify this assumption and quantitatively measuretheir relationships.The experiment was conducted as follows. An amazon (Player 1) stands still in abattlefield and a necromancer (Player 2) walks around the amazon at a certain pace, fromnear toward far. For each move, both players capture screenshots for future comparison.With 26 collected screenshots, we encoded Player 1’s images as I-frames, while Player 2’simages were encoded as Inter-stream P-Frames predicted from the corresponding I-frames.The data sizes of these Inter-stream P-Frames are depicted in Fig. 2.8.55Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System0 200 400 600 800 100005101520253035Distance in Gaming Map (Pixels)P−Frame Size (KB)  Data SetFitting ResultFigure 2.8: Exponential Fitting of Inter-stream P-frame SizeBased on these experimental data, we investigate the relationship between frame sizeand viewing distance by curve-fitting the P-frames sizes as follows.f(x) = a(1− b× e−xc ) (2.17)where a = 37, b = 0.9231, c = 13.89 and the R-squared for goodness of fit is 0.731. Withthis approach, we derive the function of Pe() as follows:Pe(Xi, Yi, Xj, Yj) = a ∗ (1− b ∗ e−√(Xi−Yj)2+(Xi−Yj)2c ) (2.18)Fig. 2.9 illustrates the function of Pe(), in which the size of Inter-stream P-frame isdirectly associated with the gaming scene’s coordinate system.56Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemFigure 2.9: Inter-stream P-frame Size Defined by P(e)2.8.3 Experimental SetupTo validate the performance of our proposed system and encoding schemes, we set up thefollowing experiments. The expectation of Intra-stream P-frame µ comes from the averagevalue of P-frame size in the Stanford Bunny light field. Since our previous work [76]has performed studies on avatars’ interactional model, this chapter focuses on the otherparameters that impacts the QoE. To emulate the network coverage and wireless channelin real world, we simplify the model in simulations by enforcing state transitions of NQoSto neighboring levels as follows:η(i) =i, p(i, i)i+ 1, p(i, i+ 1)i− 1, p(i, i− 1)(2.19)57Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming SystemIn our experiments, we initiate all players’ devices with random values of NQoS levelfollowing a uniform distribution and renew these values by the above equation in every 20seconds, according to the movement interval of players. In each iteration of thesimulation, we assign the terminals with different random values of Markov chaintransition probabilities p(i, i), p(i, i + 1), p(i, i − 1), which represent their distinct NQoStransition. Other default values of the simulation parameters are shown in Table 2.1.Table 2.1: Default Simulation Parametersnumber of players n 8player gaming region r 100 metersplayer movement unit s 5 metersbest NQoS level nq 10terminal maximal allowed hops h 1terminal maximal communication range c 25 meterssimulation time T 600 secondsfps (frame per second) 25map size m×m 12screen width w 800 pixelsscreen height h 600 pixelsunit step pixels k 32 pixelsadjunction direction nadj 8random walk probability prw 0.4chase time tchase 5 secondsAll experiments are conducted with random seeds. For comparisons, we derive theaverage QoE factors of five schemes: Intra-only represents the traditional encoding methodwithout ad hoc cloudlet assistance, Optimal represents the global optimal QoE with ouroptimization, Optimal (One-hop) represents the global optimal QoE with one-hop encodingrestriction, while Greedy and Greedy (One-hop) represents the simulation results derivedby our proposed greedy algorithms with and without one-hop encoding restriction.58Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System2.8.4 Effects of Number of PlayersWe first evaluate the effects of the number of players on QoE Performance. With a fixed sizegaming map and avatar behavior model, more game participants will increase the chance ofcorrelated videos generated in the cloud server that exploits better encoding schemes withthe help of Inter-stream P-frames. Since expected server transmission rate is proportionalto our defined QoE factor, it is obvious that lower expected server transmission rate resultsin smaller QoE factor.2 3 4 5 6 7 850100150200250300350400Total Number of PlayersQuality of Experience (QoE) Factor  Intra−onlyGreedy(one−hop)Optimal(one−hop)GreedyOptimalFigure 2.10: Effects of Number of Players on QoEAs illustrated in Fig. 2.10, the values of the QoE factor for Intra-only remainunchanged as the number of game players increases, while those of the other 4 schemeskeep decreasing. The Optimal solution exhibits the most improvement on QoE, droppingfrom 230 to 100 when the number of players increases from 2 to 8. As a sub-optimalsolution, the Greedy algorithm also demonstrates a great performance byunderperforming the Optimal algorithm by only around 3%. With the one-hop decoding59Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming Systemrestriction, Optimal (One-hop) encoding reduces the values of the QoE factor by 27.3%to 65.9% compared to Intra-only. Again, Greedy (One-hop) only slightly underperformsthe corresponding optimal scheme, reducing the QoE factor by up to 65.6% compared toIntra-only. Another interesting phenomenon shown by this figure is that, as the numberof players increases, the QoE factor of Optimal decreases more significantly than Optimal(One-hop) does. The reason is that, when more players are collaboration over thecloudlet, multiple hop correlations between gaming videos are more likely to occur, whichbenefits the Optimal scheme but not the one-hop restricted scheme.2.8.5 Effects of Maximum Communication Range betweenTerminalsThe terminals’ connectivity to each other is an important factor that affects the packetexchange in the ad hoc cloudlet, which impacts the cooperative Inter-stream P-framesharing in QoE optimization. In this section, we evaluate the five schemes over differentmaximum communication ranges between the terminals’, ranging from 0 to 80.As illustrated in Fig. 2.11, the values of QoE factor for Intra-only are not affected bychanges in the maximum communication range, while the QoE factors of the other 4schemes with ad hoc cloudlet assistance keep reducing along with the increase ofcommunication range from 0 to 50 meters. Note that, the QoE factor of the Optimalscheme drops from 480 to 170 when the communication range is increased from 0 to 25meters, which is a 72.9% improvement in QoE. In fact, at a communication range of 25meters, even the Greedy(one-hop) solution can achieve a 64.6% reduction in the QoEfactor compared to the Intra-only scheme. However, increasing the maximumcommunication range to longer than 50 meters does not yield further QoE improvements.60Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System0 10 20 30 40 50100150200250300350400450500Terminal Maximal Communication Range (Meters)Quality of Experience (QoE) Factor  Intra−onlyGreedy(one−hop)Optimal(one−hop)GreedyOptimalFigure 2.11: Effects of Maximum Communication Range of Terminals on QoE2.8.6 Effects of Maximum Number of Hops AllowedAnother factor that impacts the efficiency of the ad hoc cloudlet is the maximum number ofhops allowed. As discussed in Section 2.4.5, the multi-hop packet relay in ad hoc networks isa key element of constructing the neighbor matrix E, which determines if a Inter-stream P-frame sharing between terminals is possible. Allowing more hops for terminals to exchangevideo frames increases the chances of exploiting correlations between peering devices.Fig. 2.12 compares the performance of the 5 schemes by simulations, in which themaximum number of hops allowed is varied from 0 to 6. Intuitively, allowing more hopsin the ad hoc cloudlet should benefit the QoE optimization. However, in our experimentalsettings, these improvements are not significant, especially when we further consider thelatencies introduced by multi-hop relays.61Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System0 1 2 3 4 550100150200250300350400450Terminal Maximal Allowed HopsQuality of Experience (QoE) Factor  Intra−onlyGreedy(one−hop)Optimal(one−hop)GreedyOptimalFigure 2.12: Effects of Maximum Number of Hops Allowed on QoE2.8.7 Effects of NQoSAs discussed in Section 2.4.4, the variation of NQoS is a critical element in QoEoptimization. Avoiding the download of large frames from devices with poor NQoS couldbenefit all game participants in the cloud gaming system. In this section, we enumeratecombinations of p(i, i + 1) and p(i, i − 1) settings in the range of [0, 0.5] to evaluate theeffects of NQoS.As shown in Fig. 2.13, both Intra-only and Optimal reach a peak value at p(i, i+ 1) =0, p(i, i − 1) = 0.5, since this setting makes all terminals’ NQoS to become worse, whichsubstantially degrades the overall QoE. Note that with the same NQoS parameters, theproposed Optimal solution outperforms the conventional Intra-only scheme with lowervalues of QoE factor. More importantly, the QoE improvement of our proposed ad hoccloudlet system is especially pronounced in the scenarios where NQoS is poor; it yields apeak QoE factor of around 1000, which is a 40% of the result for the Intra-only solution.62Chapter 2. Ad hoc Cloudlet-Assisted Multiplayer Cloud Gaming System00. p(i,i+1)p(i,i−1) Quality of Experience (QoE) Factor Upper Mesh: Intra−onlyLower Mesh: OptimalFigure 2.13: Effects of NQoS on QoE2.9 SummaryIn recent years, cooperative video sharing with the support of ad hoc cloudlets has beeninvestigated as a bandwidth-efficient solution in streaming-based cloud gaming systems. Inthis work, we have improved the system model in our previous work by considering terminalmobility and the variations of NQoE. We have formulated the QoE-oriented optimizationproblem, with and without multi-hop decoding restriction. Heuristic solutions have alsobeen proposed to reduce computational complexity and enable quick encoding in real-time gaming video streaming. Results from empirical studies on Diablo II and extensivegaming trace-drive simulations have been presented to demonstrate the effectiveness of theproposed QoE optimization scheme and the efficiency of the heuristic algorithms.63Chapter 3Cognitive Cloud Gaming Platform3.1 IntroductionAs stated in Section 1.2 of Chapter 1, the main distinction between the two existingcloud-based gaming models is the proportion of offloading. However, both of them arestill of insufficient flexibility, given the various scenarios of playing cloud games onterminals. In fact, some procedures other than graphical rendering, e.g., frequent andsimple calculations, can be executed locally to reduce the latency of responses and alsoreduce the cloud workload. In this chapter, we present a cognitive and flexible cloudgaming platform, which learns the player’s environment (i.e., the combination of terminaland access network) and adapts the cloud gaming service to these evaluations. This kindof platform decomposes the game program into inter-dependent components that can bedistributed to either the cloud or local terminal for execution, which achieves flexibleresource allocation. Accordingly, the adaptive, interactive, contextual, iterative andstateful paradigm of cognitive computing [77] has motivated us to build a context-awarescheme that learns players’ behavior during their gaming sessions, which enables thescheme to adapt the cloud-terminal workload to the run-time environment to optimizethe use of cloud, network and terminal resources while meeting the quality of service(QoS) objectives of the gaming sessions. The remaining sections of the chapter areorganized as follows. We review related work in Section 3.2 and propose the framework inSection 3.3. Then, in Section 3.4, we model and formulate the decomposed cloud games64Chapter 3. Cognitive Cloud Gaming Platformas a graph partitioning problem and perform theoretical analysis on optimal solutions.QoS requirements and the optimization targets for cognitive cloud resource managementare described in Section 3.5. We further suggest two heuristic approaches for scalableimplementations, based on local greedy and genetic algorithm (GA) approaches, inSection 3.6. Results of simulations are presented in Sections 3.7. Section 3.8 summarizesthe chapter.3.2 Related WorkThe resource allocation optimization problem considered in this chapter belongs to agroup of dynamic partitioning problems for multiple devices. Studies on the dynamicpartitioning between cloud and users’ mobile terminals have been conducted forgeneral-purpose applications. The work [78] first introduced a K-step algorithm tocompute partitioning on-the-fly, when a phone connects to the server, and specified itsresources and requirements. Furthermore, the work [79] formulated the dynamicpartitioning problem and discussed the supporting platform that facilitates it. A dynamicpartitioning system named CloneCloud was designed in [80]. As a flexible applicationpartitioner and execution runtime, CloneCloud enables unmodified mobile applicationsrunning in an application-level virtual machine to seamlessly offload part of theirexecution from mobile devices onto device clones operating in a computational cloud.Similar to MAUI [81], CloneCloud partitions applications using a framework thatcombines static program analysis with dynamic program profiling and optimizesexecution time or energy consumption using an optimization solver. For offloadedexecution, MAUI performs method shipping with relevant heap objects, but CloneCloudmigrates specific threads with relevant execution state on demand and can mergemigrated state back to the original process. However, a basic requirement of these two65Chapter 3. Cognitive Cloud Gaming Platformworks is that identical application copies must be placed in both cloud and terminal sidesa priori, which conflicts with our design principles of “click-and-play” for the cloud-basedgames. Moreover, the mandatory static analysis of both MAUI and CloneCloud requiresall programs to be hosted a priori in the platform for the static analysis. This procedureextracts the relationships of components, which is necessary information for dynamicprofiling and also potentially increases the efficiency of dynamic adaption. However, thestatic analysis needs additional code instruments, which further complicates the programdevelopment. In contrast, on-the-fly adaptation simplifies the program development,while its real-time estimation and optimization features may introduce system overheads,such as increased resource consumption and latency. Our proposed platform supportsboth static and on-the-fly partitioning, since a dynamic measurement method for thecomponents’ performances is introduced. Moreover, we also enable cross-platform gamingexperience by adopting JavaScript language.3.3 System OverviewFig. 3.1 illustrates a two-layer conceptual framework that facilitates the dynamicpartitioning.3.3.1 Conceptual FrameworkThe first layer is designed for the component-based games. These game components areable to migrate from the cloud to the mobile terminal via the network under theinstruction of the Onloading Manager. Serving as a message gateway betweencomponents, the Partitioning Coordinator intelligently selects destination components,locally or remotely, to achieve dynamic resource allocation. The SynchronizationController is designed to guarantee the synchronization of data in identical components66Chapter 3. Cognitive Cloud Gaming PlatformFigure 3.1: Cognitive Cloud Gaming Platformdistributed in the cloud and mobile terminals. Note that the Onloading Manager,Partitioning Coordinator and Synchronization Controller work with the Cognitive Enginefor the purpose of maintaining an acceptable QoS for players.As an infrastructure, the cognitive platform collects information from cloud, terminaland networks. Afterward, this information is forwarded to Cognitive Engines hosted inboth cloud and terminal sides. Of course, these two engines might have different roles: theone in the terminal acts as the first filter for data, while the one in the cloud can performsophisticated analysis that supports decision making of dynamic partitioning. Nevertheless,both of them are imperative for the system.3.3.2 Cognitive Resource ManagementIn this section, we provide an overview of the proposed cognitive resource management. Asa cognitive system, it is cognitive of resources and characteristics of the cloud, the access67Chapter 3. Cognitive Cloud Gaming Platformnetwork, and the end-user devices, to enable dynamic utilization of these resources. To thebest of our knowledge, a QoE-oriented cognitive system is not yet investigated for cloudgaming systems.Figure 3.2: A Running Instance for Cognitive Cloud GamingIn a typical scenario, the GaaS cloud hosts a number of terminals with a diversity ofuser-end devices and frequent changes in network QoS and cloud responses. TheCognitive Resource Manager monitors and assesses all terminals’ working status anddynamically determines partitioning solution for each of them according to the systemstatus, e.g., the available network bandwidth and remaining resources in the cloud, inorder to provide cognitive capabilities across the cloud gaming system. As shown in Fig.3.2, the four terminals host a different number of components locally, since their devicestatus is distinct from each other. In the meantime, the Cognitive Resource Manager68Chapter 3. Cognitive Cloud Gaming Platformschedules the Virtual Machine 2 and 3 to dispatch components to their correspondingterminals, since the available bandwidth allows the background downloads.3.4 System ModelingIn this section, we model the resource management problem from the perspectives of gamecomponents, QoS constraints and optimization targets.3.4.1 Game ComponentsIn the cognitive cloud gaming platform, games consist of inter-dependent componentsthat work collaboratively to provide gaming services for players. Similar to application’sconsumption graph in [78], Fig. 3.3 depicts an intuitive illustration that denotes thedependency of game components as a directed graph.Figure 3.3: Components Partitioning for Proposed Cognitive PlatformWe model the dependent game components by a directed graph G = {V,E}, where eachvertex in V represents a game component vi and each edge ei,j in E indicates a dependency69Chapter 3. Cognitive Cloud Gaming Platformbetween vi and vj. Each component vi is characterized by the parameters listed in Table3.1.Table 3.1: Modeling NotationSymbol Definitionri the resource consumption of visi the size of the compiled code of vifi the execution frequency of vioi,j the amount of output data from vi to vjfti,j the frequency that vi sends data output to vjOnce the mobile terminal fetches the game components from the cloud, the PartitioningCoordinator works with the Cognitive Decision Engine to solve the dynamic partitioningproblem to provide a QoS-oriented resource optimization. In this framework, all input andoutput data from the components are sent to the Partitioning Coordinator, which providesa routing service to invoke messages by intelligently selecting the destination componentswhen an application cycle is determined.As depicted in Fig. 3.3, the partitioning problem intrinsically seeks to find a cut inthe component graph such that some components of the game run on the client side andthe remaining ones run on the cloud side. The optimal cut maximizes or minimizes anobjective function O, which expresses the general goal of a partition such as minimizingthe end-to-end interaction time between the mobile terminal and the cloud, minimizingthe resource consumption in the cloud, or minimizing the data transmissions for the gameterminals. Therefore, the resource management problem is to seek an optimal set of allconnecting terminals’ partitioning solutions in discretized search space, which meets thesystem’s optimization target.70Chapter 3. Cognitive Cloud Gaming Platform3.4.2 FormulationTo formulate the costs associated with partitioning of the game components, whichproperties are listed in Table 3.1, we further define specific parameters, including resourceconsumptions, code migration cost, and output transmission cost, as shown in Table 3.2.Note that the term “cost” in this chapter is used as a measure of resource utilization orconsumptions in terms of how they impact system performance. For our practicalimplementation, the cost is given by the actual latency.Table 3.2: Formulation NotationSymbol Definitionσ the set of components allocated in cloudτ the set of components allocated in terminalti execution cost of vi in terminalci execution cost of vi in cloudmi migration cost of vi from cloud to terminalpi execution probability of viαi,j communication cost from vi to vj, i, j ∈ σβi,j communication cost from vi to vj, i, j ∈ τλi,j communication cost from vi to vj, i ∈ σ, j ∈ τθi,j communication cost from vi to vj, i ∈ τ , j ∈ σqi,j probability that vi sends data output to vjNote that ti and ci denote the component execution costs in the terminals and thecloud, which give an overall evaluation of resource consumptions ri in CPU, memory andenergy, etc., mi denote the overall transmission cost of migrating component i from cloudto terminal, which depends on code size si, network quality and expected gaming sessiontime, etc., αi,j, βi,j, λi,j and θi,j denote message communication costs between components,subject to the amount of output data oi,j, network QoS parameters, etc. Also, pi is subjectto fi, and qi,j is subject to fi,j. Accordingly, we formulate the optimal partitioning problemto minimize the overall cost Co, which is a sum of execution costs for all components Ce,71Chapter 3. Cognitive Cloud Gaming Platformcommunications cost between all components Cc and code migration costs Cm as follows:Co = Ce + Cc + Cm (3.1)According to our definitions in Table 3.2, we derive:Ce =∑vi∈τtipi +∑vi∈σcipi (3.2)Cc =∑vi∈σvj∈σαi,jqi,j +∑vi∈τvj∈τβi,jqi,j +∑vi∈σvj∈τλi,jqi,j +∑vi∈τvj∈σθi,jqi,j (3.3)Cm =∑vi∈τmi (3.4)3.4.3 Optimal Partitioning SolutionThe minimum overall cost Co is subject to the various costs parameters denoted in Table3.2. In this section, we derive the minimum cost for a special case, where the parametersfor all vi and ei in Table 3.2 are all identical: we denote their constant values ast, c,m, p, α, β, λ, θ, q, respectively. Consequently, the directed graph for componentpartitioning is transformed to a connected and undirected graph with identical weight(λ + β) · q for the edges. We derive the minimum cost for different graph topologies withN components, including minimum spanning tree, complete graph and general graph. Asa practical constraint, at least one component is executed in each player’s terminal,acting as the player’s command receiver and transmitter.72Chapter 3. Cognitive Cloud Gaming PlatformPartitioning for Minimum Spanning treeA minimum spanning tree (MST) or minimum weight spanning tree is a spanning treewith weight less than or equal to the weight of every other spanning tree. In our context,it refers to a connected graph topology that contains N − 1 edges, as illustrated by theexample in Fig. 3.4.13 4 N... ...( t, c, m, p ) ( α, β, ƛ, θ, q )2Figure 3.4: A Minimum Spanning Tree with N componentsAssume k ∈ [1, n − 1] cuts in the MST GM(N) to split the N components so thatx ∈ [1, N − 1] components are placed in the terminal and N − x components are placed inthe cloud. This leads to the following cost functions:Ce = x · t · p+ (N − x) · c · p (3.5)Cm = m · x (3.6)Cc = [(x− 1) · β + (N − x− 1) · α+ k · (λ+ θ)] · q (3.7)Since (λ+β) ·q ≥ 0, to minimize the Co, the value of k should be set to 1, the minimum73Chapter 3. Cognitive Cloud Gaming Platformvalue. The derivative of the function Co at x is shown in the following equation.C ′o = [(t− c) · p+m+ (β − α) · q]× 2 (3.8)Therefore, we see that if C ′o ≥ 0, the value of x should be the minimum, i.e., 1, in orderto minimize Co. On the other hand, if C′o < 0, the value of x should be the maximum,i.e., N − 1. In general cases, the terminals’ computational efficiency is always lower thanthe computational efficiency of the cloud. Hence, we define t > c and β > α, which makesC ′o ≥ 0. Accordingly, the optimal partitioning for MST is to only migrate the necessarycomponents to the terminal, while executing all of the others in the cloud. However, ifthe cloud server is suffering from an extremely heavy workload, the computational powerin terminals may exceed the cloud, then the system should migrate all components to theterminal when C ′o < 0, where the parameters satisfies:m < (c− t) · p+ (α− β) · q (3.9)Partitioning for Complete GraphA complete graph is a simple undirected graph in which every pair of distinct vertices isconnected by a unique edge as illustrated in Fig. 3.5.... ...( t, c, m, p ) ( α, β, ƛ, θ, q )2 N31Figure 3.5: A Complete Graph with N components74Chapter 3. Cognitive Cloud Gaming PlatformIn fact, a complete graph GC(N) with N components contains N(N − 1)/2 edges.Assume there are x ∈ [1, N−1] components executed in the terminal and N−x componentsexecuted in the cloud, we derive Ce and Cm as (3.5) and (3.6), and Cc is formulated asfollows.Cc = [β · x(x− 1)/2 + α · (N − x)(N − x− 1)/2+ (λ+ θ) · (N − x)x] · q(3.10)Therefore, we derive Co = Ce + Cm + Cc. In general cases, α, β  λ, θ, which leads toα + β − 2λ − 2θ < 0, which indicates that Co has a downward slope. Consequently, theminimum value of Co is when either x = 1 or x = N − 1. Given Co = f(x), here we derive∆ = f(N − 1)− f(1) as follows:∆ = (N − 2)[q · (β − α)(N − 1)/2 + p · (t− c) +m] (3.11)GivenN > 2, we see that if ∆ ≥ 0, in order to minimize Co, the value of x should be 1. If∆ < 0, the value of x should be N−1. In general cases, the terminals are less computationalefficient than the cloud; thus t > c and β > α, which makes ∆ ≥ 0. Accordingly,the optimal partitioning is that only the necessary single component is migrated to theterminal, while all of the others are executed in the cloud. However, if the cloud server issuffering from an extremely heavy workload such that the computational power in terminalsexceeds the cloud, the system will host all components at the terminals when ∆ < 0, wherethe parameters satisfy:m < (c− t) · p+ (α− β) · (N − 1) · q/2 (3.12)75Chapter 3. Cognitive Cloud Gaming PlatformPartitioning for General GraphA general graph refers to a connected graph topology in which vertices are connected by anarbitrary set of edges. In this section, we discuss the overall cost for an arbitrary connectedgeneral graph GR(N) with N vertices and {E|2(N−1) < E < N(N−1)/2} directed edges.Theorem 3 Given a specific N , and connected graph GA is a subgraph of GB, and GAand GB share the same partitioning solution P , the overall cost of Co satisfies: Co(GA) <Co(GB)Proof Since GA is a subgraph of GB with specific N , and GA and GB share the samepartitioning solution P , we have Ce(GA) = Ce(GB) and Cm(GA) = Cm(GB). Since GA isa subgraph of GB, we denote a link set L = L(GB)− L(GA), where LGA and LGB are thelink sets of GA and GB, then we derive ∆Cc = Cc(GB)− Cc(GA) as follows:∀vi, vj ∈ L,∆Cc =∑vi∈σvj∈σαi,jqi,j +∑vi∈τvj∈τβi,jqi,j +∑vi∈σvj∈τλi,jqi,j +∑vi∈τvj∈σθi,jqi,jTherefore, when ∆Cc > 0, Cc(GB) > Cc(GA) is true. Since Co = Ce + Cc + Cm, weobtain Co(GA) < Co(GB). The theorem is proved.Theorem 4 Given a specific N , and connected graph GA is a subgraph of GB, the minimaloverall cost of Cmo satisfies: Cmo (GA) < Cmo (GB)Proof Denote GA as a subgraph of GB, where Cmo (GA) is the minimal overall cost of GAwith the optimal partitioning of P (A), and Cmo (GB) is the minimal overall cost of GB withoptimal partitioning solution P (B). Suppose Cmo (GA) ≥ Cmo (GB) is true. Trim GB to76Chapter 3. Cognitive Cloud Gaming PlatformGB′ , where GB′ = GA. According to Theorem 3, we have Cmo (GB) > Co(B′), where Co(B′)is the overall cost of GB′ with partitioning solution P (B). Therefore Cmo (GA) > Cko (GA),where Cko (GA) is the overall cost of GA with the partitioning solution P (B). It contradictsthe assumption that Cmo (GA) is the minimal overall cost of GA. The theorem is proved.Since GM(N) is a subgraph of GR(N) and GR(N) is a subgraph of GC(N), accordingto Theorem 2, we derive:Co(GM(N)) < Co(GR(N)) < Co(GC(N)) (3.13)Take a general graph with N vertices as an example. Assume there is a complete graphwith A vertices and another complete graph with B = N −A vertices. Also assume thereis one edge between vertex A and B, as illustrated in Fig. 3.6. It is mandatory thatcomponent A is hosted in the cloud and component B is executed in a terminal.... ...( t, c, m, p ) ( α, β, ƛ, θ, q )1 3B2... ...3 1A2Figure 3.6: A General Graph with N componentsAssume there are x ∈ [1, N − 1] components executed in the terminal and N − xcomponents executed in the cloud, with Ce and Cm derived in (3.5) and (3.6), the minimizedCc is formulated as follows.77Chapter 3. Cognitive Cloud Gaming PlatformFor xl < B,Cc(xl) =A(A− 1)αq2+(B − x)(B − x− 1)αq2+ αq+ (λ+ θ)x(B − x)q + x(x− 1)βq2(3.14)For xe = B,Cc(xe) =A(A− 1)αq2+ (λ+ θ)q +B(B − 1)βq2(3.15)For xg > B,Cc(xg) =x(x− 1)αq2+ (λ+ θ)(N − x)(x−B)q+(x−B)(x−B − 1)2βq +B(B − 1)2βq + βq(3.16)Given Co = f(x), we have ∆l = f(xe) − f(xl). In general, c ≈ t and α, β  λ, θ. Tothis end, we consider the minimum Co(xe) < Co(xl) when the values of the parameterssatisfies:m(xe − xl) < [xl(B − xl)− 1](λ+ θ)q (3.17)Similarly, we derive ∆g = f(xe)− f(xg) as follows:∆g = [(t− c)p+m](xe − xg)+ [1− (N − xg)(xg −B)](λ+ θ)q+ [A(A− 1)2− xg(xg − 1)2]αq+ [(xg −B)(xg −B − 1)2− 1]βq (3.18)Since c ≈ t and α, β  λ, θ, we can easily derive that ∆g < 0, thus minimum Co(xe) <Co(xg). In conclusion, Co reaches the minimum value when x = B and m(xe − xl) <[xl(B − xl)− 1](λ+ θ)q.78Chapter 3. Cognitive Cloud Gaming PlatformThis example illustrates that it is a critical challenge to derive the solution thatminimizes the overall cost for a general graph with a variety of edges. The computationalcomplexity of seeking an optimal cut for a general graph is 2N .3.5 Cloud Resource ManagementAs an assumption in previous sections, the execution and communication costs areconsidered identical constants. Nevertheless, real-world scenarios generally involvevarious values of execution and communication costs, which further complicate theoptimization problem on graph partitioning. In addition, we also need to extend theproblem by considering the capacity constraints of cloud and players’ terminals. In thissection, we formulate the QoS controls in cloud resource management and introduce a setof optimization targets.3.5.1 QoS ConstraintsAs a gaming service provision system, satisfying all players’ QoS is a fundamentalrequirement. To this end, we formulate the QoS constraints with additional notations inTable 3.3.Terminal Cost ConstraintThe terminal device needs sufficient resources to host the set of downloaded gamingcomponents. To simplify our model, we take execution and intra-terminal communicationas the consumers of processing resources. The terminal processing resource consumption79Chapter 3. Cognitive Cloud Gaming PlatformTable 3.3: QoS NotationsSymbol Definition{d|d ∈ D} the set of supported D terminal devicesni,j(d) network consumption between vi and vj for terminal dlp(d) expected process latency for terminal dlc(d) expected communication latency for terminal dLM(d) maximal tolerable latency for terminal dTRTT (d) Round Trip Time for terminal dFC cost-time factor for cloud processingFT cost-time factor for terminal processingFN cost-time factor for network communicationsPT (d) available processing resources in terminal dNT (d) available network resources in terminal dPC available processing resources in the cloudNC available network resources in the cloudfor terminal d is formulated as:µ(d) =∑vi∈τti(d)pi(d) +∑vi∈τvj∈τβi,j(d)qi,j(d) (3.19)Then the constraint on terminal processing resource is formulated as:∀d ∈ D,µ(d) ≤ PT (d) (3.20)Terminal Network ConstraintThe remote invokes of components introduce network cost, e.g., bandwidth, to the gamingprocedure. To guarantee the QoS for players, the system needs to control all terminals’gaming throughput. We formulate the network resource consumption between component80Chapter 3. Cognitive Cloud Gaming Platformvi ∈ τ and vj ∈ σ for terminal d as:ni,j(d) = λj,i(d) · qj,i(d) + θi,j(d) · qi,j (3.21)and the constraint on terminal network resource is formulated as:∀d ∈ D,∑vi∈τvj∈σni,j(d) +∑vi∈τmi(d) ≤ NT (d) (3.22)Cloud Resources ConstraintAs a service provider, the cloud consumes its processing resources to host a set ofcomponents for M terminals. Therefore, to guarantee the continuous resourceprovisioning is a critical issue in QoS assurance. The cloud processing resourceconsumption for terminal d is formulated as:ν(d) =∑vi∈σvi(d)pi(d) +∑vi∈σvj∈σαi,j(d)qi,j(d) (3.23)With the same notations, we formulate the constraint on cloud resources as:∑d∈Dν(d) ≤ PC (3.24)Cloud Network ConstraintDuring the gaming session, the cloud handles network connections from the terminals. Wealso need to formulate the constraint on the overall network throughput as follows:∑d∈D(∑vi∈τvj∈σni,j(d) +∑vi∈τmi(d)) ≤ NC (3.25)81Chapter 3. Cognitive Cloud Gaming PlatformResponse Delay ConstraintResponse delay represents the time interval between players’ input and the system response.In cloud gaming system, the latency is caused by processing latency and networking latency.And hence in this work, the expected processing latency lp(d) is formulated as the sum ofprocessing time which is proportional to the sum of processing resource consumptions inboth terminal and cloud with efficient factor FT and FC , respectively. Note that, to predictand to model the burst of component and communication costs in real game sessions willbe our next step of work.lp(d) = f(µ(d), ν(d), FT , FC) (3.26)The expected networking latency ln(d) is formulated as the sum of communicationdelays for all remote invocations between components, which is proportional to theirnetwork resource consumption with efficient factor FN .ln(d) =∑vi∈τvj∈σg(ni,j(d), TRTT (d), FN) (3.27)where g is the function to calculate the latency from specific communication packageand RTT. Accordingly, we conclude the constraint on response relay as∀d ∈ D, ln(d) + lp(d) ≤ LM(d) (3.28)3.5.2 Optimization TargetsAs a cognitive system, the cloud gaming service is adaptable to all kinds of terminals,accessible through different networks and can be hosted by clouds provided by differentvendors. In this work, we design a set of optimization targets to demonstrate the flexibility82Chapter 3. Cognitive Cloud Gaming Platformand efficiency of the proposed system.Cloud Resource Cost MinimizationCloud is not a free resource and its capacity is still restricted by existing visualizationtechniques. Therefore, minimizing the cloud resource utilization is crucial from theeconomic perspective. To this end, Cloud Resource Cost Minimization allocates morecomponents to selected terminals to reduce its own resource consumption. Note that, theselecting procedure should be under the supervision of the QoS constraints, thus, toguarantee QoS satisfactory for all players.Minimize:∑d∈Dν(d)Subject to: (3.20)(3.22)(3.24)(3.25)(3.28)Network Cost MinimizationThe cloud gaming relies largely on the network quality. Players who access gamingservices via paid mobile network also concern their bill amount. Hence, the systemnetwork throughput is an important factor that impacts both players’ QoS and users’interests on cloud gaming service. Consequently, another optimization target NetworkCost Minimization dynamically determines an optimized partitioning solution tominimize the terminals’ average network cost.Minimize:∑d∈D(∑vi∈τvj∈σni,j(d) +∑vi∈τmi(d))Subject to: (3.20)(3.22)(3.24)(3.25)(3.28)83Chapter 3. Cognitive Cloud Gaming PlatformTerminal Resource Cost MinimizationTerminals are considered relatively weak devices, especially when they are mobile devicespowered by batteries. Therefore, minimizing the terminal resource utilization is anotherimportant optimization factor we need to consider. For this purpose, an optimization targetTerminal Resource Cost Minimization seeks optimal partitioning solution to minimize theterminals’ average resource cost, thus, provides lower energy consumption rate on players’devices.Minimize:∑d∈Dµ(d)Subject to: (3.20)(3.22)(3.24)(3.25)(3.28)Response Delay MinimizationThe response delay to players’ commands in gaming systems is defined as the time differencebetween the time when a player initiates a command and the time when the player receivesthe response from the game program. As one of most key factors that impact players’ QoS,the response delay should be strictly controlled under a threshold (e.g., 200ms is “maximaltolerable” and 120ms is “hardly noticeable”, as stated in [37] ) to ensure acceptable gamingprocedure. As indicated in [82], calculation of the response delay is completely differentfrom conventional cloud gaming system. We provide Response Delay Minimization modeto minimize the terminals’ average response delay with selected partitioning solutions.Minimize:∑d∈Dln(d) + lp(d)Subject to: (3.20)(3.22)(3.24)(3.25)(3.28)84Chapter 3. Cognitive Cloud Gaming Platform3.6 Heuristic SolutionsThe optimizations presented in the previous section may not scale to more complexsystems with large numbers of game players due to the computational complexity ofsearching for the optimal solutions. Suppose the cloud-based game consists of Ccomponents and provides its cloud gaming service for N terminals, the number ofpotential component allocation solutions is 2NC , which implies that an exhaustive searchapproach has an extremely high computational complexity. To address this issue, wesketch two possible heuristic solutions here: a local greedy approach and a moresophisticated and efficient GA-based [83] approach, which have the potential to realizethe advantages of the cognitive resource optimization proposed in this chapter inreal-time scalable implementations.The two proposed heuristic algorithms can be executed at either the run-time (on-the-fly) or pre-published stage (static approach) of a game. In contrast to on-the-fly execution,the static approach simulates offline all possible combinations of the network and terminalstates on a testing platform in the pre-published stage, in order to find the preferredsolutions for the game in any given set of conditions. With this approach, we can create adictionary that enables the run-time system to pick up the preferred solution according tostates of the system (cloud, network and terminal) in real-time.3.6.1 Local Greedy ApproachThe intuitive motivation for considering a local greedy approach, which partitions theoptimization problem into a set of sub-problems for all terminals, is its computationalsimplicity. After solving these sub-problems separately, the system concatenates all ofthe sub-solutions into a complete solution for the global problem. The computationalcomplexity of the local greedy approach is significantly reduced to 2N . Note that, since the85Chapter 3. Cognitive Cloud Gaming Platformsystem needs to consider all QoS constraints, which include the bottleneck of the wholesystem, the concatenated solution might not fulfill the QoS requirements, thus, can notbe considered global optimal. Besides, users are not independent of each other in the useof system resources, hence, the concatenated solution might not give the global optimalsolution.3.6.2 Genetic Algorithm-base ApproachIn contrast, a Genetic Algorithm [83] (GA) is an adaptive heuristic search algorithmbased on the evolutionary theory of genetics and natural selection, which simulates thesurvival of the fittest principle. This approach evolves a series of adaptive solutions, eachdescribed by a chromosome representing a particular genetic instance of the system,towards a desirable solution. The potential benefits of the GA approach include but notlimited to: 1) controllable computational complexity: the system needs to response forsituations in reasonable time, therefore, sub-optimal solutions with controllable decisiontime are required; 2) GA fits the distributed nature of cloud computing data centres: thechromosome operations can be processed in distributed manner and merged to a result,which is the essential idea of map-reduce algorithm; 3) GA produces a number ofhigh-quality chromosomes according to the selection criterion. Therefore, thesechromosomes are reusable when new the environment changed, which tends to speed upthe convergence.Encoding: In a GA system, each solution to the problem is described as a chromosome,an individual with a particular genetic instance in the nature. In this work, we devise achromosome consisting of N × C bits: “1” represents the corresponding component ishosted in the cloud while “0” represents the component is executed in the terminals. Fig.3.7 shows an illustrative example for the substantiation of solution encoding. With the86Chapter 3. Cognitive Cloud Gaming Platformchromosome, the system places a component for execution, e.g., the Y th component ofterminal X, by looking up the bit C ∗ (X − 1) + Y in the chromosome.00 11 10... ...Terminal 110 01 1Terminal 20Figure 3.7: Chromosome Encoding Method for Cloud Resource ManagementCloning: The cloning operation is to simulate the growth of chromosome based on theinitial population. In our algorithm, initial population K is created by random proceduresfor the purpose of gene diversity, while the cloning is a copying process that producesredundant chromosome, according to the expending factor Fe. In general, we set Fe = 2,implying the chromosome quantity is doubled in one cloning operation.00 11 10 ... ...Terminal 110 01 0Terminal 2100 11 10 ... ...Terminal 110 01 1Terminal 20Gene 1Gene 200 11 10 ... ...Terminal 110010Terminal 2100 11 10 ... ...Terminal 110011Terminal 20Gene 1Gene 2Figure 3.8: Chromosome Crossover for Cloud Resource ManagementCrossover: A crossover operator is a key component in GA. It imitates the way of87Chapter 3. Cognitive Cloud Gaming Platformnatural biological evolution. There are several crossover schemes have been proposed, suchas one-point crossover[84] and multi-point crossover[85]. In our approach, the crossover isapplied to two random chromosomes G1, G2 with a probability of Pcrossover, as shown inFig. 3.8. We randomly select two integers r1, r2 ∈ [0, N ×C) to represent the starting andending bit of the crossover segment and switch the corresponding segments in G1 and G2.00 11 10... ...Terminal 110 11 1Terminal 2000 11 10... ...Terminal 110 01 1Terminal 20Figure 3.9: Chromosome Mutation for Cloud Resource ManagementMutation: The mutation operator is used to accommodate the variety of the genesso that the discovery of new (hopefully better) solutions is possible. In our approach,mutation is performed on duplicated chromosomes with a probability of Pmutation. Theoperator randomly selects an element in the chromosomes and switches its value to theopposite: “1” to “0” or “0” to “1”, as illustrated in Fig. 3.9.Correction: After crossover and mutation operations, some chromosomes might notbe valid anymore, according to the system setting. For instance, some components aremandatory to be executed in the terminals, e.g., the input processing module, while someothers are forced to be implemented in the cloud, e.g., the networking module. Therefore,a correction operator is required to ensure that all chromosomes are valid. In this work, acheck process in special bits will be performed as the correction operator.Selection: The chromosome selection is to simulate the survival of “stronger”88Chapter 3. Cognitive Cloud Gaming Platformchromosomes from the nature selection. Those chromosomes with better genes, accordingto the selection criterion, will be the parents of next generation of populations. In thiswork, we rank all chromosomes with the result value of fitness function and retain topgenes of initial K population for reproducing the offspring generation.Fitness Function: A fitness function is the selecting criteria that representing aspecific optimization target for the chromosomes. As a cognitive system, the fitnessfunction is always dynamic and adaptable to the overall system performance.3.7 Simulations3.7.1 Simulation SetupTo validate the performance of the cognitive resource management of the proposed gamingplatform, we set up the following simulations. Regarding the calculation of the ProcessingLatency lp(d) and Networking Latency ln(d), we assume the function f and g described inSection 3.5.1 follows the formula below:f(µ(d), ν(d), FT , FC) = µ(d) · FT + ν(d) · FC (3.29)g(ni,j(d), TRTT (d), FN) = ni,j(d) · TRTT (d) · FN (3.30)We design a set of random components and random communications to simulate adecomposed cloud gaming system. The default parameters for the decomposed game is asshown in Table 3.4. Note that, Communication Probability is defined as the probability of acommunication occurs between two components. Higher valued Communication Probabilitybetween two components indicates a higher possibility that the two components will invoke89Chapter 3. Cognitive Cloud Gaming Platformeach other. This is determined by the functionality of the components and their executionsequences. In contrast, Data Transmission Probability denotes the transmission probabilitybetween two components, given the invocation between these two components existed. Itindicates the how often one component will invoke the other during the game execution.It is determined by the functionality of the components and also the players’ behaviors inplaying the games. We can also notice from the table that, the communication cost fromthe terminal to the cloud is a bit larger than the one from the cloud to the terminal, sincewe assume that the terminal needs to cost more energy to initiate a data transmission,especially when they are powered by batteries.Table 3.4: Parameters for Decomposed GamesParameter ValueNumber of Components 10Component Execution Cost (Cloud) 1∼50Component Execution Cost (Terminal) 1.05∼50.25Component Execution Probability 0.1∼0.7Component Migration Cost 1∼10Communication Probability 0.25Data Transmission Probability 0.01∼0.3Communication Cost (Cloud to Terminal) 0.1∼200Communication Cost (Terminal to Cloud) 0.105∼310Communication Cost (Cloud to Cloud) 0.002∼4Communication Cost (Terminal to Terminal) 0.003∼6The default simulation parameters of terminal devices are listed in Table 3.4, whichrepresents the wide range of terminals, from stationary computers to mobile devicesconnected to wireless networks.All random variables listed in above tables follow the uniform distribution. To simplifythe QoS measurement, we set 120 milliseconds(ms) as the maximal tolerable latency valueas the indicator of QoS. All simulations are repeated for 2000 times with distinct randomseeds to yield an average value.90Chapter 3. Cognitive Cloud Gaming PlatformTable 3.5: Parameters for Terminal DevicesParameter ValueRound Trip Time (TRTT ) 10ms∼25msAvailable Network Resource 200∼500Available Computing Resource 100∼400FC 0.001FT 0.002FN 0.0053.7.2 Discussion on Game DesignIn our experiments, we realize that the game design, including the resource consumptionof each component and the data communication between components, will substantiallyimpact the system performance. Hence, the first part of our experimental work is toinvestigate the features of diverse genres of games to further explore the optimizationpotential of the cloud-based gaming system. In the simulation model, we first performthe cost minimization to come up with a candidate partitioning scheme, and then checkwhether this candidate solution is feasible or not in terms of whether it meets the QoSconstraints.Overall Cost BoundaryIn this section, we study the overall cost of a specific game in different partitioning solutions.As depicted in Fig. 3.10, the overall cost increases along with the number of components.However, the increasing speed of the maximum value is faster than the minimum value.Note that, not all partitioning schemes are feasible in our proposed system, from theperspective of the QoS restriction. Therefore, we also depict those maximum and minimumfeasible values for a distinct number of components. As we can see from the figure, the gapbetween maximum and minimum feasible values is becoming smaller when the number ofcomponents increases.91Chapter 3. Cognitive Cloud Gaming Platform5 6 7 8 9 10 11 12 13 14 151002003004005006007008009001000Number of ComponentsOverall Cost  minimum feasibleminimummaximum feasiblemaximumFigure 3.10: Effect of Number of Components on Overall Cost0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1020040060080010001200Component Communication ProbabilityOverall Cost  minimum feasibleminimummaximum feasiblemaximumFigure 3.11: Effect of Component Communication Probability on Overall CostThe similar trend is also discovered in Fig. 3.11, which illustrates the effect ofcomponent communication probability on overall cost. Apparently, increased92Chapter 3. Cognitive Cloud Gaming Platformcommunication probability indicates the increases in network costs in optimalpartitioning, which exclude more infeasible schemes with higher overall cost from theresults. We also plot the error bar for these two figures, with the confidential interval of95%.Effect on Terminal Incapable RateIn our simulation, the games’ component structures are randomly created. Hence, someof them might not have a feasible partitioning scheme to fulfill the QoS requirements. Inthis chapter, we define Terminal Incapable Rate to indicate the ratio that the cloud serverand terminals are incapable of supporting a game session. For various of game structures,we compare Pure-Cloud, the conventional partitioning solutions for cloud gaming, to ourproposed cognitive solutions over the Terminal Incapable Rate.0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Communication ProbabilityTerminal Incapable Rate  Pure−CloudCognitive SolutionFigure 3.12: Comparison on Terminal Incapable Rate93Chapter 3. Cognitive Cloud Gaming PlatformAs shown in Fig. 3.12, as the communication probability arises, more networkcommunications cause higher overall response delay. For the component communicationprobability of 0.5 and 0.6, The Terminal Incapable Rate for Terminal Incapable Ratedramatically increased to 0.78 and 0.95, while our cognitive solution provides a muchlower rate at around 0.15 and 0.3. This illustrates the advantage of utilizing cognitiveresource allocation for decomposed cloud games: more game genres are supported.Effect of Communication Probability0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8020406080100120Component Communication ProbabilityResponse Delay  Pure−CloudNetwork MinimizationCloud  MinimizationDelay MinimizationFigure 3.13: Effect of Communication Probability on Response DelayFig. 3.13 illustrates the impact of communication probability on decomposed gamesto the average response delay. Apparently, the average response delay becomes largerwhen the communication probability increases. In order to demonstrate the differentoptimization targets, we optimize the system from the aspects of terminal, network, cloudand delay. In fact, the terminal minimization is the Pure-Cloud mode. As we can see,94Chapter 3. Cognitive Cloud Gaming PlatformDelay optimization achieves the best performance comparing to other schemes.Effect of Component Degree VarianceHowever, other than communication probability, the density and skewness of thecommunication links between components are also very important factors to impact thegame performance. In order to describe the communication density and skewness, wecalculate all communication degrees for each component and derive their communicationvariance as an evaluation criterion. As depicted by Fig. 3.14, we derive the average valueof the response delays for all four optimization schemes at different variance intervals. Inour experimental settings, the four optimization schemes reach their peaks at minimumvariance interval of 0 to 2, while they all decreased to the bottom value at the maximalvariance of 10 to 12. This simulation result implies that the more imbalance thecommunication network is, the lower responsive delay our cognitive system achieve.[0,2) [2,4) [4,6) [6,8) [8,10) [10,12]051015202530Component Degree VarianceResponse Delay  Pure−CloudCloud MinimizationNetwork MinimizationDelay MinimizationFigure 3.14: Effect of Communication Variance on Response Delay95Chapter 3. Cognitive Cloud Gaming PlatformTradeoff study: cloud and terminalsHere we study the correlations among cloud and terminal cost in a particular partitioningsolution. In contrast to optimized solution selection, we listed all possible solutions andcalculated their cloud, network and terminal costs to illustrate their relationships. Westudied that the cloud cost is inversely proportional to terminal cost, as shown by thelinear fitting in Fig. 3.15.10 20 30 40 50 60 70 80 90−100102030405060708090Cloud CostTerminal CostTradeoff between cloud cost and terminal cost  Figure 3.15: Tradeoff between cloud cost and terminal cost3.7.3 System Performance EvaluationIn this section, we evaluate the system performance based on the two proposed algorithms.The default simulation parameters for genetic evolution are listed in Table 3.6 below.96Chapter 3. Cognitive Cloud Gaming PlatformTable 3.6: Parameters for Genetic Algorithms SimulationParameter ValuePopulation 50Evolution Iterations 100Expanding Factor 2Crossover Ratio 0.9Mutation Ratio 0.3Cloud Network Resource 12000Cloud Computing Resources 6000Number of Game Components 10GA ConvergenceWith 60 devices, we conduct an experiment on minimizing the response delay with theproposed GA solution. As shown in Fig. 3.16, the system reaches the theoretical boundaryof minimal response delay after 450 offspring generations. This is an evidence of theconvergence of the proposed GA solution.50 100 150 200 250 300 350 400 450 5001012141618202224GA Evolutionary GenerationsResponse Delay  Theoretical BoundaryGA MinimizationFigure 3.16: GA convergence on evolutionary generations97Chapter 3. Cognitive Cloud Gaming PlatformNetwork Cost MinimizationWe first evaluate the performances of local greedy approach and GA solution regarding thenetwork cost minimization. With extensive random seeds, we derive the average networkcost achieved by the local greedy algorithm and GA with various generation iterations of100, 200, and 300, respectively. For comparison, we also illustrate the average network costof Pure-Cloud solution, and Optimal, the systemic minimal average network cost. Notethat, in order to eliminate 2CN search for optimal solutions, we set up an infinite loopfor GA iteration. If an additional 2000 iterations yield the same result, we consider theGA converges to the optimal solution. This value is then adopted as the optimal value.Note that, the local greedy and GA running times for different iterations increase alongwith the quantity of devices. We measure these execution times in our ASUS windows 7personal computer (PC) with Intel Pentium G630 @2.70GHz CPU and 4.0 GB InternalMemory (RAM). According to our experimental settings, even though for 100 devices,local greedy and GA with 100 and 200 iterations can be completed within 1 second, whileGA of 300 iterations can be done in 2 seconds. In contrast, the 2000 iterations of GAconsume around 28 seconds with 100 devices, while only 1 second for 10 devices’ scenario.In fact, the algorithms’ running time depends on the hardware capacity. If we upgrade thecomputer and apply parallel processing, these execution times can be further shortened.As shown in Fig. 3.17, with large scale simulations, the local greedy algorithm providesaround 19.5% to 10.5% decrease in average network cost compares to the Pure-Cloudsolution, while the series of GA solutions demonstrates even higher efficiency in optimizingthe average network cost. It can be observed that when the device quantity is relativelysmall, e.g., 10, a small number of generation iterations (e.g., 100) is able to achieve theoptimal solution with a 27.6% cost decline. On the other hand, when the device quantityincreases, more generation iterations for GA are required to approach the optimal results.98Chapter 3. Cognitive Cloud Gaming Platform10 20 30 40 50 60 70 80 90 10095100105110115120125130135140Device QuantityAverage Network Cost  Pure−CloudOptimalLocal GreedyGA−I−100GA−I−200GA−I−300Figure 3.17: Performance Evaluation on Network Cost MinimizationNote that, optimized average network cost grows as the device quantity increases. Thereason is that the system needs to sacrifice the performance to fulfill the requirementsof supporting more terminals: some of the optimal partitionings with minimum responsedelay might not be qualified as feasible solutions. In our experimental settings, with 6000overall cloud computing resources, the optimization on average network cost will be affectedwhen the quantity of terminal devices is larger than 60.Cloud Resource Cost MinimizationWe also perform simulation on the optimization target of cloud resource cost minimizationto compare the efficiency of Pure-Cloud solutions, local greedy algorithm and series of GAschemes.Fig. 3.18 shows the comparison on the average throughput for the terminal devices.Apparently, for Pure-Cloud mode, the cloud cost is proportional to the device quantity.99Chapter 3. Cognitive Cloud Gaming Platform10 20 30 40 50 60 70 80 90 1000100020003000400050006000700080009000Device QuantityCloud Cost  Pure−CloudOptimalLocal GreedyGA−I−100GA−I−200GA−I−300Figure 3.18: Performance Evaluation on Cloud Resource Cost MinimizationIn order to support 100 terminals, the gaming server needs to request around 9000 unitscomputational resource. In contrast, with cloud resource cost minimization, the overallcost of the cloud is significantly reduced: to achieve the optimal value, only around 6800units are required, which is only 75.5% of conventional Pure-Cloud mode. Given thehigher computational complexity of iterative GA solution, the local greedy approach alsobrings the cloud cost down to 3000 units, which yields a 22.2% decline in our experimentalsettings. Similar to the network cost minimization, the cloud resource cost minimizationis also constrained by the QoS requirements when the terminal device quantity exceedsa certain threshold. In our experimental settings with 12000 cloud network resource, theresource optimization achieves the best performance when device quantity is 60, where theLocal Greedy algorithm reduce the cloud cost from 5300 units to 2800 units and the GAsolution only consumes 1500 units, representing declines of 47% and 71.7%, respectively.Similar to the previous simulation, for the purpose of illustrating the variance, we depict100Chapter 3. Cognitive Cloud Gaming Platformthe box plot for selected local greedy scheme in Fig. 3.19.02000400060008000100001200014000160001 2 3 4 5 6 7 8 9 10Device QuantityCloud CostFigure 3.19: Variance of Local Greedy Scheme Simulation Results3.8 SummaryThe decomposed cloud gaming platform introduces a flexible component allocationsolution to optimize cloud gaming service provision. In this chapter, we have presentedsystem modeling and simulation results to show that the cognitive platform can providegreat efficiency in terms of resource minimization and throughput optimization whileguaranteeing the QoS requirements for game sessions. The studies in this work is limitedto the lack of explicit modeling for component characteristics in game program, which isstill blank in this area. Therefore, future research in this topic should be led by tracemeasurements of real systems.101Chapter 4Decomposed Ubiquitous CloudGaming System4.1 IntroductionAs discussed in Chapter 3, decomposition provides a potential solution for cognitivecloud gaming. By decoupling the creation of rendering instructions from its executionand transmitting only small-sized rendering instructions over the Internet, thecommunication burden caused by video transmissions is eased, hence meeting thechallenges caused by the limitations of the mobile networks. However, how to design sucha decomposed software system for games is still an unanswered question, given a numberof critical issues in system implementations. In this chapter, we discuss all of thesedetailed issues from an engineering perspective and develop testbed and game prototypesto validate our theoretical proposal in Chapter 3. The outline of this chapter is asfollows. We discuss the design objectives and principles of the cognitive platform forubiquitous cloud games in Section 4.2 and 4.3, respectively. The design andimplementation of the cognitive platform are described in Section 4.4 and 4.5,respectively. Experiments on optimizing the overall latency and enabling partial offlineexecution are conducted in Section 4.6. Section 4.7 summarizes the chapter.102Chapter 4. Decomposed Ubiquitous Cloud Gaming System4.2 System ObjectivesFigure 4.1: Architecture Framework for Cognitive Mobile Cloud GamingCognitive systems [86] are attractive for the heterogeneous environment we areconsidering. The situation-aware architecture of cognitive system monitors and assessesthe working environment to predict and make decisions for the providing services, andrefine future decisions by learning from the achieved results. To the best of ourknowledge, a QoE-oriented cognitive system is not available for cloud gaming systems.To provide cognitive capabilities across the cloud gaming system, we need to overcomethe diversity of user-end devices and frequent changes in network QoS and cloud103Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemresponses. We use the concept of cognitive system design (i.e., act, learn, adapt) torealize our proposed situation-aware cloud gaming platform. Our objective is to developan architectural framework that is cognitive of resources and characteristics of the cloud,the access network, the end-user devices and the players’ behaviors, to enable dynamicutilization of these resources.As shown in Fig. 4.1, we envision a cognitive platform with a novel capability to learnabout the game players’ environment (i.e., the combination of terminal and access network)and adapt the running of the game to maintain an acceptable QoE. The proposed platformshould be able to fulfill the requirement listed in Table Design Principles4.3.1 DecompositionDecomposition is an intrinsic requirement of the proposed cognitive platform, since thesystem aims to dynamically manage the workload balance between cloud and terminalsby migrating a selected set of game components from the cloud to the terminals. Thereare different types of “Decomposition” defined in computer sciences. In this chapter,the term of decomposition is defined as “breaking a large system down into progressivelysmaller classes or objects that are responsible for some part of the problem domain”. Infact, algorithmic decomposition is a necessary part of the object-oriented analysis anddesign [87]. Due to the distributed nature of cloud computing resource infrastructure,decomposition of an application program provides the potential improvement on intra-cloud execution efficiency. In this section, we discuss two level of decomposition for ourproposed system.104Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemTable 4.1: High-Level System RequirementRequirement Definition ResponsiveSR 1 Click-and-PlayTo enable immediately game play when theplayers select their favourite game from platformportalOnloadingManagerSR 2PerformanceEvaluationTo measure, evaluate and predict the overallsystem performance, including CPU load,memory usage, link bandwidth utilization, andspecialized application-layer metrics, such as thenumber of players, spatial distribution of theplayer population, or game state computationdelayPerformanceEvaluatorSR 3InteractionModelingTo statistically understand the interaction modelbetween the game instance and players: theinteraction model between components, includingthe frequency of execution and probability ofcommunications.InteractionMonitorSR 4 CognitiveAdaptionTo intelligently adapt its gaming services tosystem performance, such as changing networkconditions (QoS) and different players’ distinctbehaviors, to keep user QoE above a prescribedthreshold.CognitiveEngineSR 5 PartialOfflineExecutionTo lessen the dependency on network connectionby facilitating partial offline gaming in specificscenes.MessageRedirector105Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemFine-Grained DecompositionFine-grained decomposition refers the design patterns that segment the whole gameprogram into tiny components, i.e. function/methods, as depicted by an example in Fig.4.2.Figure 4.2: Fine-Grained Decomposition ExampleIn this program, method b() and c() are invoked by the function a() with if and whileconditions, respectively. Given method a() is executed in a resource-restricted mobileterminal, hosting b() and c() in the cloud might be beneficial, if the computational costof b() and c() are relatively higher than their overall communication costs with a(). Fine-grained decomposition provides a huge quantity of tiny components, therefore, it exhibitsmost flexible partitioning schemes, which leads to more opportunities in seeking optimalcomponent allocation solution.Nevertheless, the fine-grained decomposition model is also limited in some respects.The most critical issue in method-level decomposition is the state migration problem.Conceptually, if a component remotely invokes another one, i.e. a terminal hostedcomponent calls a method executing in the cloud, the component need to collect nativecontext for transfer as well. However, the complexity of serializing this information for106Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemnetwork transfer and also the complexity of parsing these data after transmission to thedestination are significantly higher, given processor architecture differences, differences infile descriptors, etc. As a result, the CloneCloud system proposed in [80], which adoptsthe fine-grained decomposition modality, only supports migrating at execution pointswhere no native state (in the stack or the heap) need be collected and migrated.Coarse-Grained DecompositionIn contrast to fine-grained decomposition, a coarse-grained decomposition partitions thegame program into a number of functional independent and stateless components. Thesecomponents are often composed of a set of objects and methods, which work collaborativelywithin the scope of the component. See Fig. 4.3 for an illustration.Figure 4.3: Coarse-Grained Decomposition ExampleIn this program, the instance of Component B is activated by a control instructionfrom the player. After processing with its designated class and methods, it calls its107Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemconsequent component, which is Component A in this context, for further manipulation.After successive processing by Component C after Component D, the player received theresulting gaming content. Since these components are in charge of relatively independentfunctionalities, their native states are always invisible to each other, which eliminates thestate transfer problem in fine-grained decomposition.However, the coarse-grained decomposition still has open issues in game development.In comparison to fine-grained design, the coarse-grained decomposition results in fewercomponents, which might affect the efficiency of cognitive resource allocation. Inaddition, it is relatively difficult for game developers to write the game program, sincethese components are strong coupling to each others. This requires the softwarearchitects to abstract the main building blocks of a specific game in prior and topre-define all unified interfaces between the components.4.3.2 System WorkflowFigure 4.4: Work Flow of Decomposed Ubiquitous Cloud Gaming PlatformFig. 4.4 illustrates a workflow of proposed cognitive ubiquitous cloud gamingplatform. In the first stage, the Cognitive Ubiquitous Cloud Gaming platform shouldprovide API support for game developers. With APIs, the game developers write anddeploy the source codes before the game instances are launched for the connection108Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemrequests from the players. During the gaming sessions, the Performance Evaluator focuseson collecting the execution efficiency parameters, such as execution latency, networkround-trip time, etc. Meanwhile, the User Behavior Identifier learns players’ interactionswith components by performing statistical analysis on inter-components invocations. Theresults of performance evaluation and players’ user behavior are sent to the CognitiveEngine as the references of dynamic partitioning. In other words, the cognitive enginewill dynamically assign a set of components to be executed in the cloud, while migratesthe others to the terminals, in order to maximize the overall system performance.4.3.3 Dynamic PartitioningTo help readers of this chapter understand the dynamic partitioning of UBCG Testbed,we illustrate a sequence diagram for the cognitive engine of UBCG Testbed in Fig. 4.5.To start the gaming, the cloud server first dispatches a JavaScript engine (including asmall portion of game instance) to the terminal, while launching the game instance in thecloud. During the gaming session, the gaming instance in terminal keep sending statusstatistics to the Cognitive Engine, which analyze the system performance and acknowledgethe Partitioning Coordinator its decision of partitioning. This decision will instruct thePartitioning Coordinator to redirect all control messages and inter-component messages,in order to facilitate dynamic partitioning. In other words, this is the key mechanismthat enables the proposed environment-aware adaption. Note that, there is an optionalonloading process when Partitioning Coordinator receives decisions from Cognitive Engine.This process works if the terminals are a lack of sufficient components to perform optimalpartitioning.109Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemFigure 4.5: Sequence Diagram for Cognitive Engine4.3.4 Response DelayThe game program is a latency-sensitive interactive system. The response delay toplayers’ commands is defined as the time difference between the time when player initiatea command and the time when player receive the response from the game program. Ingeneral, the maximal tolerate response delay dtolerate is 120 ms. Therefore, to guaranteethe response delay is a critical issue in cloud gaming system.The work [6] segments response delay of a conventional RR-GaaS cloud gaming systeminto three components: network delay, processing delay and playout delay. However, to110Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemcalculate the response delay in a decomposed cloud game is completely different.Figure 4.6: A Component Communication TreeTake the communication tree in Fig. 4.6 as an example, where the edges’ weightrefers to their communication costs. Denote Component 1 and Component 8 as the inputcomponent and output component in a decomposed gaming system, we hereby define amessage path through Component 1 to Component 8 as a Response Cycle. Accordingly,there are 4 response cycles in Fig. 4.6. Therefore, we formulate the response delay dc forresponse cycle c as:dc =∑n∈cen +∑i∈c,j∈cci,j (4.1)where c ∈ C is the set of response cycle in the game program, en is the executionlatency for component n and ci,j is the communication latency between component i andcomponent j. However, the response delay can be various, according to the content ofthe command, the parameters of the gaming scenes and the reacting logics defined in thecomponents. Therefore, to satisfy the restrictions of maximal tolerate response delay, thesystem need to locate the response cycle with maximal response delay dmax by traversing111Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemall response cycle in C:dmax = maxc∈Cdc (4.2)Hereby we denote the constraints of response delay on a decomposed cloud game as:dmax ≤ dtolerate (4.3)4.3.5 Partial Offline ExecutionOne of the most critical problems for mobile cloud gaming is the conflict between strongnetwork dependency and unstable network connectivity. In all existing cloud gamingframeworks, the gaming session will be suspended or even destroyed, once the mobiledevice loses its network connection to the cloud. However, players are not interactingwith each other all the time during the gaming session, even in those multi-player games.In a typical Massively Multiplayer Online Role-Playing (MMORPG) game, the avatarspends a remarkable amount of time in monster hunting by him/her-self, for the sake oflevel-up and outfit gathering [88]. The players will never be happy if they lose valuableitems in the battlefield due to the network access problem. Our proposed platform focuson the solution to these scenarios.Fig. 4.7 demonstrates a case of redirection service provided by the proposed platform:the mobile-executed component 7 is trying to activate component 3 in the cloud with anoutput message, while the network connection to the cloud is temporarily lost. Rather thansuspending the gaming session, the terminal locates component 3 on the mobile device andredirects the output message to this local copy. Thus, the player will not be disturbed by thetemporary disconnection of Internet. This approach is called “Partial Offline Execution”.Note that once the mobile device recovers its network access, a Synchronization Controller,112Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemFigure 4.7: Redirection Service in Disconnection to the Cloudwhich is aware of the data modifications, should perform data synchronization with thecloud server.4.4 Framework DesignGiven the above requirements, we define the main building blocks of the architecturalframework on both the cloud-side and terminal-side, and identify the prevalent standardsthat are applicable to the interfaces between these building blocks.Fig. 4.8 illustrates the elements of the proposed cognitive platform that facilitate thedynamic partitioning. Execution Monitors implemented on both the cloud and mobilesides monitor the execution information of each component in the cloud, access networkand mobile terminal. The surveillance data, including memory usage, CPU percentage,execution time, are reported to the Cognitive Decision Engine, where cognitive resource113Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemFigure 4.8: Decomposed Ubiquitous Cloud Gaming Platformmanagement strategies are made. The Cognitive Decision Engine also requestsinformation from the Performance Prober, which periodically reports its results inprobing the Cloud-Network-Terminal environmental parameters. Games designed for thecognitive platform consist of a number of inter-dependent game components. Thesecomponents are able to migrate from the cloud to the mobile terminal via the networkunder the instruction of the Onloading Manager. Serving as a message gateway between114Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemcomponents, the Partitioning Coordinator intelligently selects destination components,locally or remotely, to achieve dynamic resource allocation. The SynchronizationController is designed to guarantee the synchronization of data in identical componentsdistributed in the cloud and mobile terminals. Note that the Onloading Manager,Partitioning Coordinator and Synchronization Controller work with the PerformanceEvaluator and Local Analyzer for the purpose of maintaining an acceptable QoS forplayers.4.4.1 Execution MonitorOne of the most critical problems for the decomposed cloud gaming platform is to designa practical mechanism to measure the execution status, e.g., component execution costs,execution probability, and communication costs. In our design, we introduce a ExecutionMonitor and a latency-based estimation solution to derive these parameters. The ExecutionMonitors on both the cloud and mobile sides monitor resource usage of each component,whether in cloud or terminal, and save the execution information in a statistics database.This execution information includes the property of each component in each invocation,including memory consumption, CPU usage percentage, execution time, output data size,execution environment, etc.Table 4.2: Table of Execution InformationComponent Memory CPU Time Output ... Environment3 22MB 5% 20ms 3KB ... Terminal1 42MB 1% 10ms 9KB ... Cloud5 2MB 0.3% 4ms 23KB ... Terminal4 7MB 3% 9ms 7KB ... Terminal1 42MB 1% 12ms 9KB ... Cloud... ... ... ... ... ... ...115Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemWith the execution information database, the system is able to retrieve the invocationtrees between the components, including the relationship between components and theexecution frequency of each component. Apparently, players with different gaming behaviormight produce different invocation frequencies for these components. Hence, this databasenot only stores the measurement information from the perspective of cloud gaming system,but also facilitates proposed system’s cognitive capability to learn the players’ interactionalbehaviors.4.4.2 Performance ProberHowever, the information extracted from the execution information database is notsufficient for the proposed platform to perform cognitive adaption, since the system needsto evaluate the execution performance of each component both in cloud and terminal.This might not be possible in the real system, since the platform can never migrate allcomponents to the terminals for the tests. Furthermore, the platform also needs tomeasure the network quality between the cloud and terminals. Therefore, we design amobile agent [89] based Performance Prober to probe the Cloud-Pipe-Terminalenvironmental parameters.A mobile agent is a composition of computer software and data, which is able to migrate(move) from one computer to another autonomously and continue its execution on thedestination computer. In this context, the game components are encapsulated as mobileagents and dispatched from the cloud to mobile devices. In our design, we set up amobile agent component with designated iterations and measure the component’s executioninformation in the cloud. afterward, the component is dispatched and executed in theterminal. Its execution information is measured and report to the Performance Prober inthe cloud. An illustration of mobile agent prober is depicted in Fig. 4.9. Note that, this116Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemFigure 4.9: Mobile Agent Dispatch for Performance Proberprocess involves two network transmissions, in which the system are able to calculate thenetwork quality parameters, including, round-trip time and data transmission rate. Withthis approach, the Performance Prober is able to compare the computational efficiency ofcloud and terminals, consequently, estimate the execution information for all componentswith computation. In our implementation, we denote the cloud computational efficiency asEc, terminal computational efficiency as Et, therefore, we are able to compute the efficiencyratio RE = Ec/Et. With RE, we can estimate the execution information that we couldnot measure from the system. For instance, the cloud execution time for a particularcomponent can be estimated as Et ×RE.In order to minimize the overhead of probing, the Performance Prober is designed towork collaboratively with Execution Monitor. As mentioned in Section 4.4.1, the cognitivesystem calculates the execution probability of each component in a statistical approach.Hence, a traverse in both cloud and terminals’ database is necessary. Meanwhile, thestatistics in the terminal should be reported to the cloud periodically. Accordingly, the117Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemmobile agent component in Performance Prober is designed as the database informationretriever and carrier to improve the system efficiency.In our implementation, the system dispatches Performance Prober to the terminals inan interval of TI and save the probing results in a database. Table 4.3 illustrates someentities of the database. In fact, with real-time data analysis, the interval TI can also bea variable subject to the variety of the terminal, e.g., the network quality.Table 4.3: Table of Performance InformationCloud Proc. Terminal Proc. Code Trans.Time Records Time Records Time Length20ms 100 11ms 30 28ms 3KB42ms 208 19ms 51 22ms 3KB78ms 376 26ms 70 33ms 3.2KB102ms 512 40ms 92 32ms 3.3KB... ... ... ... ... ...4.4.3 Cognitive Decision EngineCognitive Decision Engine is a unit that cognitively determines the system strategy afterperiodically analyzing the information from the Execution Monitor and PerformanceProber. The main strategies include component onloading for Onloading Manager,dynamic partitioning for Partitioning Coordinator and data synchronization forSynchronization Controller. The decision making for the engine is discussed in details inChapter Onloading ManagerSince the cognitive platform supports click-and-play, none of the game components existsin the mobile client at the beginning of a gaming session. In this case, the cloud server118Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemshould be capable to transmit executable components to the mobile terminal, in orderto enable dynamic resource allocation. The Onloading Manager employs the concept ofthe mobile agent to realize this process: components are stringified and dispatched to theterminals as messages. Note that, the onloading process could either be performed beforegaming session starts or be running in the background during the gaming session. It isscheduled by the Onloading Manager, which assigns each game component a priority basedon the overall assessment of the particular component. In this context, the priority pi forthe ith game component is modeled by Equation 4.4. Nevertheless, the priority of a gamecomponent is also associated with its functionality. Some key components should have ahigher priority in the onloading process, since they provide featured benefits in the mobileterminal.pi = f(ri, ci, fi,∑jftj,i · tj,i, ,∑jfti,j · ti,j) (4.4)To simplified the system, we implement three types of onloading in our platform: i) thesystem administrator is able to onload specific components to the client manually from theCloud Configuration Center (as shown in Fig.4.11); ii) the platform is able to randomlydispatch selected components to the client, when the network connection between the cloudand mobile devices are idle; iii) the client is able to request and fetch specific componentsfrom the cloud, once the optimal solution is determined and some of the componentsrequired by the client are still missing. In our experiments, since the code length of thecomponents are short, their transmission cost is negligible in the experimental results, weadopt the third mode.119Chapter 4. Decomposed Ubiquitous Cloud Gaming System4.4.5 Partitioning CoordinatorTo facilitate dynamic partitioning, a flexible invocation routing mechanism should beimplemented in the proposed platform. In other words, the proposed system shouldsupport component positioning and transparent message forwarding for components. Inour design, all input and output data from the components are sent to the pair ofPartitioning Coordinators, which provide routing service for all invoke messages byintelligently selecting the destination components.With the information from Execution Monitor and Performance Prober, the CognitiveDecision Engine construct a component invocation graph, as depicted in Fig. 3.3. Inorder to provide a QoE-oriented resource optimization, the dynamic partitioning problemintrinsically seeks to find a cut in the component invocation graph such that somecomponents of the game execute on the client side and the remaining ones on the cloudside. The optimal cut maximizes or minimizes an objective function O, which expressesthe general goal of a partition, e.g., minimizing the end-to-end interaction time betweenthe mobile terminal and the cloud, minimizing the amount of exchanged data, orminimizing the latency in a gaming session.In designing the objective function O, we need to satisfy the user’s QoE requirement,including resource constraints in mobile devices and tolerable latency for each interactioncycle:∑k∈mobilerk ≤ RMobile (4.5)Denote components set Sc involved in each gaming interaction cycle, for all i, j ∈ Sc,∑i∈mobile,j∈cloud(ftj,i · tj,i + fti,j · ti,j)B+ TSc ≤ Tm (4.6)120Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemwhere RMobile represents the available resource in the mobile device, TSc denotes thetransaction delay of the components, B denotes the average bandwidth, and Tm denotesthe average maximum delay that the players can tolerate.Table 4.4: Cost Table of Candidate SolutionsCloud Terminal Bandwidth Memory CPU Latency1,2,3 4,5,6,7 30kbps 102MB 12% 89ms1,2,4,5 3,6,7 60kbps 230Mb 25% 142ms1,3,4,5,6,7 2 10kbps 150Mb 17% 105ms... ... ... ... ...In our implementation, the platform enumerates all possible partitioning solutions forthe involving components and estimate their overall resource costs, including bandwidthconsumption, memory usage, CPU percentage, overall latency, etc. Based on theestimation, the platform creates a cost table of candidate solutions, from which theoptimal solution is determined. Table 4.4 shows an example of cost table of candidatesolutions for 7 components.4.4.6 Synchronization ControllerThe remote distribution of game components results in the data synchronizationproblem. To address this problem, the Synchronization Controller is employed to updateall parameters in the gaming environment. However, the synchronization process alsointroduces a non-negligible network overhead. Consequently, we design the synchronizingmechanism following the principle of “Sync-Only-If-Necessary” to minimize thetransmission cost.121Chapter 4. Decomposed Ubiquitous Cloud Gaming System4.5 Testbed ImplementationIn order to validate our proposal, we implement a ubiquitous cloud gaming testbed (UBCGTestbed) and develop game prototypes on this testbed. In this section, we discuss theimplementation issues and our solutions.4.5.1 Enabling TechnologiesTo implement the proposed cognitive platform for mobile cloud games, we seek to enabletechnologies that facilitate the migration and partitioning of game components. JavaScriptis adopted as the programming language, which is originally implemented as a part ofweb browsers so that client-side scripts could interact with the user, control the browser,communicate asynchronously, and alter the document content that was displayed. Morerecently, however, its use has become common in both game development and the creationof desktop applications.Node.js10 is a server-side software system designed for writing scalable Internetapplications, notably web servers. Programs on the server side are written in JavaScript,which enables web developers to create an entire web application in JavaScript, bothserver-side and client-side. This feature facilitates the game components, JavaScriptgaming code in this context, to migrate from the cloud to user-end, and to be executedon cloud server and client as a mobile agent.For the mobile client, we embed a WebKit-based browser into the cognitive engine forparsing and executing the JavaScript mobile agent from the cloud server. In ourimplementation, the WebKit browser is built on Android smartphone. However, allmobile operating systems supporting browsers are able to run our cognitive platformafter a small number of modifications. We are also looking for alternative solutions to10http://nodejs.org/122Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemimplement the mobile client as native applications on JavaScript. As the state-of-the-art,Microsoft already supports native application development with JavaScript on itsmetro-style interface.4.5.2 Deployment DirectoryFigure 4.10: Deployment Directory of UBCG TestbedAs depicted in Fig. 4.10, besides the standard elements of Node.js project (package.json,npm-debug.log and node modules directory that imports dependent Node.js libraries), theUBCG Testbed project is organized by Express11, a Node.js web application frameworkfollowing Model-View-Controller (MVC) software architectural pattern. Following is thedeployment of our testbed:• game.js : as the entrance of UBCG Testbed, game.js creates and launches a Node.jsweb server that listens to players’ commands and responses corresponding messagesor documents to them.• /views : as the portal of UBCG Testbed, Embedded JavaScript (EJS) template filesin directory of views provide views for the game server, including home.ejs,confignavi.ejs and config.ejs. The home.ejs lists existing games on the testbed, sothat the players can click through the icons to access the game.11http://expressjs.com/123Chapter 4. Decomposed Ubiquitous Cloud Gaming System• /route: as the testbed’s core, the controllers and models designed in the directoryof route enable the proposed dynamic partitioning. While route.js functions as theentrance to different views and api.js interprets the API invocations in applications,the combination of engine.js and client-engine-plugin.js are in charge ofinter-component message redirection, following the partitioning decisions made bytheir built-in algorithms.• /public: as the container of plug-ins and accessaries, the directory of public loads allclient-side third-party Cascading Style Sheets (CSS) and JavaScript files to players’terminal. Since our target is to develop a responsive, mobile first gamingenvironment, all layout designs adopt the Metro UI CSS12, which is a set ofWindows 8 template extended from Bootstrap13 framework.• /application: for our application developers, their applications should contains atleast one EJS view app.ejs and its accessorial components. Their codes will bedeployed to the directory of programs, with name extensions of .application (e.g.,tank.application). Note that, the components within directory of common can beaccessed by all applications.• /results : as a full-access directory, results enables the application developers towrite intermediate data into binary files. In our following experiments, we saves allresulting data produced by prototype programs here.4.5.3 Application Programming InterfaceAs a testbed that supports component-based games, UBCG testbed provides a set ofAPIs to encapsulate lower layer partitioning for game developers. To acknowledge a12http://metroui.org.ua/13http://getbootstrap.com/124Chapter 4. Decomposed Ubiquitous Cloud Gaming Systeminter-component invocation in UBCG Testbed, the developers should simply add a “$$”mark before the name of the components when they are invoked in the code (e.g.,$$componentX({msg : args}); stands for an invocation of componentX with aparameter of args passing as a message).4.5.4 The Administration CenterFigure 4.11: Screenshot of Administration Center of UBCG TestbedFig. 4.11 illustrates a screenshot of the UBCG Testbed administration center(rendered by config.ejs). The administrator can browse all ongoing gaming sessions herefrom the TERMINALS list session. For each terminal, the partitioning and loading125Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemstatus of all components are illustrated in graphical user interface. Note that, if theAUTO OPTIMIZATION SWITCH turns to off, we can even manually control eachcomponent’s execution environment by a simple click. This feature supports ourfollowing experiments that test the efficiency of different task allocation schemes. Inaddition, the administration center also depicts real-time figures for terminal status,including network bandwidth, usage of client CPU, memory, battery, etc.4.6 Prototype Development and ExperimentsTo demonstrate the feasibility and efficiency of UBCG testbed, we develop and deploythree prototypes in this section, including a Gobang game, a 3D skeletal game engine, anda Robocode tank game.4.6.1 Development ChallengesWe first discuss the challenges in developing decomposed game prototypes.Global VariableGlobal variables commonly exists in program design, as they can be accessed anytimeanywhere while the program is running. However, the nature of component-basedplatform requires the system should be decomposed into independent components. In ourimplementation, they are basically JavaScript functions. In this case, once a componentcompletes its life cycle and terminates its execution by invoking other components, allvariables defined within its scope will be destroyed. In order to facilitate global variable,we investigate two different solutions.The first approach is to save the variable into a JavaScript object named global, ofwhich the lifetime is as long as the program. Because global is a JavaScript object itself,126Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemthen without any doubts that it can save any JavaScript variables in it. However, thisobject can not be existing on both cloud and terminals, which means the variables definedin global by a component executing on the client couldn’t be accessed by a componentexecuting on the server. Moreover, if the component migrates from terminal to server orreverse, all the variables saved in global will not be available, which leads the system tocrash. To this end, JavaScript object global can be utilized to cover all kinds of JavaScriptvariables, while its global variables can only be shared among components in either clientside or server side, not both.The second solution is to save the variable into a JSON object named context andutilize the object as an argument being passed to the next component when one componentinvokes another. This approach, in fact, localizes the global variables as parameters, thus,solves the problem of sharing variables between cloud and terminals. However, it alsohas two unavoidable disadvantages: i) The context object can only carry JSON variables.Those user-defined JavaScript variables containing references to other variables or functionobjects cannot be saved into context as they are not JSON object. ii) The context objectcarries all global variables in all component invocations, while only a small proportion ofthem are accessed in most of the cases. This introduces remarkable overheads on networktransmission when the object are passed between cloud and terminals.In our development, we adopt a hybrid solution: some static global variables areimplemented in JavaScript object global, while the others are converted into JSONobjects for context transfer. This feature makes it difficult for us to employ third-partylibraries to our prototypes. Hence, we give up the JavaScript physics engine OimoJS andCannonJS, since they all define a large number of non-JSON variables. Instead, we onlyutilize a small proportion of JavaScript render engine ThreeJS for basic rendering, whilemost of the rendering and simplified animation algorithms are implemented by ourselves,127Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemwhere we adopt context as variables.For the future improvement, we are targeting a synchronization mechanism for aglobal object, which updates themselves between cloud and terminals. However, thisapproach requires a novel system performance evaluation method, so that cognitiveengine can still work. Another direction is to investigate the solution that encapsulatesarguments transmission other than JSON object, which makes our platform bettercompatible to the third-party libraries. We are also considering a compress anddecompress mechanism to minimize the data size in object transfer. This will reduce theburden of network transmission, while introducing more computational cost forcompression and decompression.Synchronization of Input and Output (I/O) StatesMost browser-based programs handle I/O with a local interrupt mechanism. Once theuser triggers a mouse or keyboard event, there will come up an interrupt which will beresponded by the browser by calling corresponding predefined processing functions. Asour prototypes are designed as component-based, the global variables are conveyed amongcomponents, which means that one single I/O event may need multiple handling functionsin different components. Nevertheless, due to the asynchronization between the I/O eventand the main control flow of the program, there might be a data hazard called WAR (Writeafter Read) as it is in computer architecture. For instance, our prototype is running arendering component to calculate parameters, e.g., normal vectors, when the user dragshis/her mouse to change the viewpoint, then I/O component will be triggered to receiveand respond I/O event by saving the new state into his own context object. Afterward,the rendering component finished its execution and transfer the control flow back to I/Ocomponent with its out-of-date context object. In this case, the mouse dragging event willbe ignored thoroughly without any handling, which basically is the WAR data hazard.128Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemTo avoid WAR data hazard, our solution is to save the I/O state information intoglobal object when an I/O event comes up, since the global object won’t be destroyed whilecontrol transferring between components. Next, right after the control transferred back toI/O component, we copy the I/O state information in global object into I/O component’scurrent context object, then these I/O state information can be transferred forward to thefollowing components to trigger the processing functions, which also makes I/O handlingprocess synchronized with the execution of the program.But this is not good enough since our I/O should only be processed once each time theevent comes up while our handling functions are examining the I/O state information toprocess in every main loop execution. So we should reset the I/O state variables in contextobject every time an event has been handled, because handling functions are everywhereand their global objects are not synchronized. But these reset states will be overwrittenby the global object in I/O component due to our above mechanism to avoid WAR. Sothe final solution is to create an additional property IOSynch in context object to signifywhether the I/O event has just been handled. Every time when an I/O event is handling,we set the bit of this I/O state to 1. When the I/O component takes over the control flow,we first examine every IOSynch: If it is set to 0, then we copy this I/O state in globalobject into context object, while if it is 1, we reset its value to Gobang GameGobang game (also known as Gomoku or Five in a Row) is an abstract strategy board gamethat players alternate in placing a checker of their color on an empty intersection of thechessboard. The winner is the first player to get an unbroken row of five stones horizontally,vertically, or diagonally. We developed the Gobang game prototype for UBCG Testbed todemonstrate the efficiency of offloading game engine’s computational complexity, artificial129Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemintelligence (AI) in this context, to the cloud. Therefore, we implement the AI moduleas a component, which is feasible to migrate between cloud and players’ terminals andexecute in these two different environments. A screenshot for developed Go Bang game isillustrated in Fig. 4.12;Figure 4.12: Screenshot for Gobang GameThree types of devices are employed in our evaluation, including an ASUS windows 7personal computer (PC) with Intel Pentium G630 @2.70GHz CPU and 4.0 GB InternalMemory (RAM), an Apple iPad mini tablet with 1 GHz dual-core ARM Cortex-A9 CPUand 512 MB DDR2 RAM, and a LG G2 mobile phone with 2.26 GHz quad-core Snapdragon130Chapter 4. Decomposed Ubiquitous Cloud Gaming System800 processor, 2.0 GB RAM and Long-Term Evolution (LTE) networks module. Throughpublic Wi-Fi network at UBC Vancouver campus and Fido LTE cellular data networkservice in Vancouver, these devices are utilized as players’ terminals to access the Gobanggame deployed on UBCG Testbed hosting in Amazon Elastic Compute Cloud (EC2)14.PC−WiFi iPad−WiFi Mobile−WiFi Mobile−LTE00.511.522.5x 104Time (ms)  AI−AutoLatency−AutoAI−CloudLatency−CloudAI−TerminalLatency−TerminalFigure 4.13: Response Latency Comparison in Gobang Game PrototypeBy repeating the Gobang game plays with certain chess steps, we conduct theexperiments with schemes iterating different combination of devices and networks, suchas PC-WiFi, iPad-WiFi, Mobile-WiFi and Mobile-LTE. For each scheme, we iterate threeexecution models (Testbed automatic optimization, all cloud execution and all terminalexecution) and record two critical data: AI execution time and Player ExperiencedLatency. AI execution time is calculated by subtracting AI component invocation timefrom AI completing time, while the Player Experience Latency is a measurement of thetime difference between the time a player placing a chess and the time the AI placing a14http://aws.amazon.com/ec2/131Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemchess. These measurements are depicted as six schemes in Fig. 4.13.Apparently, the numeric value of AI-Auto is closed to Latency-Auto, since theirdifferences are caused by two-time network communications between terminals and thecloud. According to our measurement, WiFi and LTE network introduce additional344.37 ms and 485.25 ms delay in average, respectively. These delays are negligible inthese experiments. This is the reason that Mobile-WiFi exhibits nearly identical patternto Mobile-LTE. The most remarkable phenomenon is that the cloud schemes reduce ahuge proportion of response time in comparison to terminal schemes, this indicates thehigh computational complexity of designed AI components. Apparently, the AIcomponent’s feature of high resource consumption makes it better to be executed in thepowerful cloud. This conclusion is proved by another observation in our experimentalseries: all automatic optimization solutions choose to do this, resulting comparableperformances between Auto and Cloud solutions.4.6.3 3D Skeletal Game EngineThe 3D skeletal engine, our second prototype, aims to challenge UBCG Testbed’s capacityon rendering 3D game scenes. Besides the complexity of AI, modern games are also proneto create fantastic game scenes that consume a huge amount of terminal resources. Recentwork [49] has explored the possibility of partial offloading for game scene renderings. The3D skeletal engine is our understanding in this perspective. A 3D skeletal system (alsoknow as the bone system) is a common technique used to create skeletal animations in videogames. As the foundation of generating acting units, a skeletal animation consists of a skinmesh and an associated bone structure, so that the movement of the mesh is associatedwith the vertices of the bone, following an exactly same pattern in reality: human beingshave a skeletal structure covering with muscles and skin on it. The developed 3D Skeletal132Chapter 4. Decomposed Ubiquitous Cloud Gaming SystemGame Engine consists of an animation editor and a 3D rendering module, which computesand draws action animations for a human and a dog, respectively. With Separate Skinningmethod and Forward Kinematics in OpenGL basic bone system15, the implementationscreenshot of a four-component prototype is illustrated in Fig. 4.14.Figure 4.14: Screenshot for 3D Skeletal Game EngineTo validate and demonstrate the UBCG Testbed’s feature of cognitive task allocation tothe network quality, we conduct experiments to measure the fluency of rendered animationsby the numeric value of frame per second (FPS). In order to explicitly control the network15http://content.gpwiki.org/OpenGL:Tutorials:Basic Bones System133Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemparameters between the cloud and terminals, we employ two identical computers to serveas cloud and client, which are equipped with Intel(R) Core(TM) i7-4770 CPU @ 3.40GHzprocessor, 8.00 GB installed memory (RAM) and 64-bit Windows 7 operating system. Onthe “cloud” side, we installed NetBalancer16 to control the bandwidth of NodeJS processin the cloud, for the purpose of simulating the variance of network quality in real-worldcases.We design our experiments in two aspects. First, there should be comparisonsbetween automatic optimization and all potential partitioning schemes. Since 3D skeletalgame engine contains four components, an iteration of their possible partitioning makes24 = 16 schemes. Therefore, we divide the total experiment time into equal 16 slides foreach scheme. Second, we also concern about the engine’s different performance overdifferent network bandwidth. Hence, we repeat the experiments three times, withbandwidth settings of 1000 KB/S, 500 KB/S and 100 KB/S, respectively.Fig.4.15 shows the results of above experiments. The average FPS of each time slot (5seconds per slot) indicates the fluency of rendered animation at the specific time period.We can conclude from the comparison between different bandwidth schemes that,network quality plays an important role in the proposed real-time rendering prototype.The resulting FPS decrease from around 48 to around 18, when the bandwidth falls from1000 KB/S to 500 KB/S. Things get worse if the network bandwidth is reduced to 100KB/S, UBCG Testbed can only render the 3D skeleton at FPS rate of 5, which is only10% of the 1000KB/S case. The good part of this experiment is that, it proves theefficiency of UBCG Testbed. Under all three network conditions, the cognitive enginedoes a great job in seeking optimal partitioning solutions for the prototype: Auto seriesoutperforms Iteration series almost all the time. In addition, we derive very similarpatterns from the three iteration schemes: the 1st, 5th, 6th, 8th, 9th, 11th, 12th, 16th16https://netbalancer.com/134Chapter 4. Decomposed Ubiquitous Cloud Gaming System0 10 20 30 40 50 60 7005101520253035404550Time Slots (5 seconds per slot)Average Frames Per Seccond (FPS)  Auto−1000 Iteration−1000 Auto−500 Iteration−500 Auto−100 Iteration−100Figure 4.15: Game QoS (FPS) Comparison in 3D Skeletal Game Engineallocations reach the optimal FPS rate, while the rests fall to the bottom. This is a resultof allocation strategy and the communication methodology between components.4.6.4 Robocode Tank GameThe idea of the third game prototype, Robocode Tank, comes from a famous open sourceeducational game Robocode17, which is a programming game to develop a robot battle tankto battle against other tanks in Java or .NET. The robots are controlled by competitors’AI codes and their battles are running in real-time and on-screen. Our Robocode Tank17http://robocode.sourceforge.net/135Chapter 4. Decomposed Ubiquitous Cloud Gaming Systemgame prototype inherits all features of Robocode and places an additional tank controlledby players into the battlefield. Screenshot for implemented tank game is illustrated in Fig.4.16.Figure 4.16: Screenshot for Robocode Tank GameSince the system performance of Robocode tank game is subject to the complexitiesof tank AIs, we only demonstrate the cognitive capacity of UBCG Testbed with 3 gamingsessions. We create 4 AI controlled tanks as four components, running on the samecanvas for competition. Each tank conducts itinerary planning algorithm with random136Chapter 4. Decomposed Ubiquitous Cloud Gaming System0 5 10 15 20 25 30 35 40 45 50 55020406080Time Elapsed (second) : Player 1FPS0 5 10 15 20 25 30 35 40 45 50 5501020304050Time Elapsed (second) : Player 2FPS0 5 10 15 20 25 30 35 40 45 50 5501020304050Time Elapsed (second) : Player 3FPSFigure 4.17: Game QoS (FPS) Enhancement for Robocode Tank Gamecomputational load, which is simulated by a loop repeating from 1 to 10000 times withuniform distribution. In our experiment, UBCG testbed is hosted in the EC2 UbuntuLinux instance at us-west-2a zone, accessing through UBC Vancouver campus WiFinetwork. All of these three gaming sessions are conducted in a Google Chrome browseron a Windows 2012R2 PC with Intel Core i5-4670 @3.40GHz CPU and 6.0 GB InternalMemory (RAM). As shown in Fig. 4.17, these players all experienced very low FPS rateat the beginning of the gaming sessions, while the testbed eventually provided an optimalpartitioning solutions for them (around 60 FPS). Note that, the solution search time forthese three players are distinct from each other, because of the ever-changing real-timesystem status.137Chapter 4. Decomposed Ubiquitous Cloud Gaming System4.7 SummaryIn this chapter, we have proposed a cognitive, flexible and promising gaming platform formobile cloud gaming, which supports click-and-play, intelligent resource allocation andpartial offline execution. Unlike previous work on cloud games, we have proposed acomponent-based game structure and designed specific mechanisms to facilitate theenvisioned objectives, such as dynamic onloading process, partitioning, synchronizationand redirection services for partial offline execution. We discussed the enablingtechnology and implemented the proposed platform as a pure JavaScript solution.Extensive experiments were performed to show that the adaptive partitioning is able toprovide an optimal solution in terms of overall latency. For the future work, we focus onthe following directions: i) To better scheduling and resource management, we need tomeasure the computational performance of game components, both in the cloud andmobile devices. In addition,the communication between these components should also bemeasured. ii) The platform should accurately, timely and efficiently measure, evaluateand predict the real-time system environment, to provide a reference for QoE-orientedadaption. iii) Instead of overall latency, we should consider more sophistic models withmore impact factors, such as computational performance, network bandwidth, batterypercentage, etc.138Chapter 5Conclusions and Future WorkIn this chapter, we conclude the presented works in this thesis and also suggest severaltopics for future work.5.1 Conclusions• In Chapter 2, we have investigated a novel cloud gaming framework in whichmultiple players in the same game scene can share their video frames with eachother. It is facilitated by an ad hoc cloudlet, which consists of a secondary P2Pnetwork. We have investigated the feasibility of video sharing by modeling thecorrelations among video frames from different players and the avatars’ behaviors inthe gaming sessions. Furthermore, we have explicitly formulated the proposedsystem, including mobility of terminal devices and diversity of network quality ofservice for distinct players. Optimal encoding schemes and heuristic algorithmsthat derive scalable solutions have been introduced in our work. An empirical studyon Diablo II and extensive trace-driven simulation results have been presented todemonstrate the effectiveness of the proposed QoE optimization scheme and theefficiency of the heuristic algorithms. This study has demonstrated the potential ofoptimizing players’ QoE by exploring correlations among peer devices’ gamingvideos. For future research, the correlations among videos from different gamegenres, e.g., the first-persons and the second-persons, should be investigated. In139Chapter 5. Conclusions and Future Workaddition, improving the encoding efficiency in the cloud and the decoding capacityin the terminals are also critical challenges.• In Chapter 3, we have presented the idea of decomposed cloud gaming systems andmodeled the cognitive resource management for decomposed cloud gaming. As thecore of the proposed system, the resource management issues were formulated as anoptimal cut problem in a weighted graph. By theoretical analysis and simulations,we have demonstrated the flexibility of the proposed system over diverseoptimization targets. In order to efficiently derive the optimal solutions withdifferent optimization targets, two heuristic algorithms have been proposed andevaluated. We have presented extensive simulations and testbed-based experimentalresults to show that the cognitive platform provides great efficiency in terms ofresource minimization and throughput optimization while guaranteeing the QoSrequirements for game sessions. We learned from this research that decompositionand dynamic partitioning methodologies can be applied to gaming programs.However, the inter-component communications in these programs should satisfycertain requirements. The next step of this study should be the empiricalmeasurements of game software, emphasizing on the invocation features amongindependent modules.• In Chapter 4, we have discussed the design issues in developing decomposed cloudgaming system and presented a design of a cognitive and flexible system forubiquitous cloud gaming, which supports click-and-play, intelligent resourceallocation and partial offline execution. Unlike previous work on cloud games, wehave proposed a component-based game structure and designed specific mechanismsto facilitate the envisioned objectives, such as dynamic onloading process,partitioning, synchronization and redirection services for partial offline execution.140Chapter 5. Conclusions and Future WorkWe discussed the enabling technology and implemented the very first testbed in apure JavaScript solution. Three prototype games have been developed to validatethe feasibility and efficiency of the proposed decomposed cloud gaming system. Oneof the most important lessons we learnt from this study is that there are still anumber of difficulties in the development of decomposed software. Future work inthis topic should investigate better encapsulation methods for independent modules.5.2 Suggestions for Future WorkIn the following, we consider several interesting possibilities for extension of the currentwork.5.2.1 Cloud Gaming Engages More Multiplayer GamesThe gaming industry has seen a shift towards games with multiplayer facilities. A largerpercentage of games on all types of platforms include some form of competitive onlinemultiplayer capability. However, researchers in cloud gaming have yet to explore the hugepotential of cloud gaming in multiplayer scenarios, which involve more than one players inthe same game environment at the same time. In such scenarios, players can interact witheach other in partnership, competition, or rivalry, which provide them with opportunitiesfor social communication that is absent in single-player games. We define multiplayergames as either massively multiplayer online role-playing games (MMORPGs) (e.g., Worldof Warcraft, Lineage) or small-scale networked games (e.g., StarCraft, Diablo, Leagueof Legends). Due to the rapid developments in both computer and broadband networktechnologies, MMORPGs have become a very important part of the online entertainmentindustry nowadays. Game players tend to get connected to play games with a group of peersinstead of against artificial intelligence. This change enhances the gameplay experience and141Chapter 5. Conclusions and Future Workmakes more players become attached to this type of entertainment. Similarly, small-scalenetworked games are also attracting many players, due to their flexibility to form groupsto conduct short sessions of gaming. In fact, applying cloud gaming concept to multiplayergaming introduces additional benefits as follows:1. Nature of Connectivity: A critical drawback of the cloud gaming paradigm is theindispensable network connectivity. Indeed, an overhead is incurred to establish andmaintain the network connections between the cloud and players terminals duringthe gaming session. This may be a reason that has kept customers away from cloudgaming. However, this worry is unlikely to impact the decisions of end users whenit comes to multiplayer games, since network access is already mandatory for suchgames.2. Temporary Engagement: An important feature of cloud gaming is to enable gameplay without download and installation. This nature of click-and-play becomes moreattractive in a multiplayer scenario where people in proximity are engaged to playthe same game temporarily. For instance, several friends in a party might decide toplay some video games together but they could not find a game that is installed in alltheir smartphones. In this case, the benefit of click-and-play cloud gaming becomesself-evident.3. Gaming Fairness: How to achieve fairness between multiplayer is a crucial issuein designing online games. As the players are competing with each other in thesame game scene, the system should respond to their actions immediately. Playersof a conventional online game may suffer from unfairness, especially when the QoS(e.g., latency, packet loss rate) of their network connections varies. With cloudgaming, players gaming instances are hosted in the cloud. Hence, the messageexchanges between game instances occur inside the cloud, which makes it easier to142Chapter 5. Conclusions and Future Workmaintain a guaranteed QoS. The cloud gaming system may be able to adapt itselfto a terminal’s network to provide better fairness. For example, previous researchproposed to adjust rendering parameters to reduce video quality for those playerswith poor network access. By reducing the video quality, players with less capabledevices or experiencing poor network conditions can be treated fairly in multiplayergames.Research challenges include: i) Video Sharing: Video sharing cooperative cloudgaming reduces bandwidth consumption with cooperative encoding. However, it alsobrings several challenges and research issues. First, introducing reference-based encodingbrings additional overhead to the system, such as increased workload in the videoencoder servers. A common assumption in cloud computing paradigm is that all gameengines and video encoder server are extremely powerful to perform the encoding, due toscalable computing resources. However, the cost of cloud resources cannot be neglected inpractice. Hence, optimization inside the cloud should be considered. Second, decodingvideo frames from predicted images require additional cloudlet support, or using an adhoc networking model that enables terminals to decode the videos cooperatively. Energyconsumption of the mobile terminals to perform the tasks of cooperative video decodingand ad hoc network communications can be a critical issue. Furthermore, systemperformance in the presence of device mobility could also be an important issue. ii)Cooperative Component Sharing: Component sharing cooperative cloud gamingshould be built upon the concept of component-based gaming architecture. The mostcommonly seen challenge for such an architecture is the decomposition complexity, or, tobe more specific, the decomposition level (e.g., data level, task level, function level). Thedecomposition level defines the frequency that components interact with each other, andthus the rate of data exchange between components. It is actually the determining factor143Chapter 5. Conclusions and Future Workin the ad-hoc cloudlet based gaming architecture. Since components could be remotelyexecuted, a high data exchange rate (high decomposition level) between remotecomponents could be highly detrimental to both the system performance andcommunication cost. As the decomposition level varies with game genre, how to find theappropriate level of decomposition remains the biggest challenge. Furthermore, thebeacon messages and the memory used to acquire and store the neighbors gamingstatuses are overheads that require further modeling and analysis. Moreover, efficient anddecentralized service discovery, device discovery, and membership managementmechanisms should be carefully designed to ensure the scalability of the system.5.2.2 Novel Gaming Paradigm Convergence in CloudCloud computing provides additional opportunities for novel games paradigms, such asvirtual reality (VR) games, augmented-reality games and context-aware games.1. Virtual Reality Cloud Gaming: VR games have been talked about for years,but we have yet to see many of them become availble to the market. A number ofleading companies, such as Oculus, Valve and HTC, are on their way to produce high-quality equipment to facilitate VR games. If realized, the industry then needs to startbuilding content for this new and potentially “game changing” platform as quicklyas possible. However, the real-time rendering of omnipresent 3D scenes requires verystrong graphical computation power, which might limit the application of VR games.A potential solution involves the cloud, as it provides rich resource up in the clusters,e.g., NVIDIA GRID, etc. The high volume of memories and computational powermake the infinite virtual world for the players become possible.2. Augmented-Reality Cloud Gaming: Project Glass is a research anddevelopment program by Google to develop an augmented reality head-mounted144Chapter 5. Conclusions and Future Workdisplay [90]. In contrast to traditional mobile devices, Google Glasses provide ahands-free display of information on the lenses, integrating the virtual display tothe reality in one’s vision. In addition, the device enables people to interact withthe Internet via natural language voice command. Therefore, it is a perfect solutionfor augmented-reality cloud games, which can be launched while people arewalking. A typical augmented-reality cloud gaming can be demonstrated by thefollowing examples. The camera on the glasses continuously captures the player’svision in real-time, and the device transmits the video to the cloud via a wirelessnetwork. In the cloud-end, the video analyzer processes the video images withsophisticated artificial intelligence technologies, such as pattern recognition. Thegame logic in the cloud then creates gaming contents and delivers them to the gameplayers. These virtual gaming contents, such as coins and bombs, can be displayedin the real scenarios through the lenses. Therefore, the system provides the playersa gaming world with mixed virtual and real items. During the gaming session, theplayers should move their bodies or their vision angles to interact with those virtualitems, in order to achieve the designed gaming goals. This type of games can beused in daily exercise and for health-care purposes. However, how to guarantee thesafety of players during the gaming session remains a critical issue for gamedesigners.3. Context-Aware Cloud Gaming: An example of context-aware cloud gaming isgaming onboard a vehicle. People nowadays prefer to entertain themselves withgames when they are trying to pass time onboard a bus or subway train. The mobilityof a vehicle provides a new gaming experience for players. In this gaming scenario, thevehicular game reports Global Positioning System (GPS) information to the cloudvia a wireless network, so that the cloud is able to deliver corresponding gaming145Chapter 5. Conclusions and Future Workcontents to the mobile devices. For example, when the player is in the urban area,the environment of the game is set to be in the crowd and is busy; when the playeris in the suburb area, virtual wild animals might appear in the game and attackthe avatar. Furthermore, the game also collects the mobility information with itsequipped accelerators and the cloud utilizes these sensed data to facilitate variousgaming contents. For example, when the vehicle is accelerating, the avatar in thegame will enter a speed-up mode, such that the player has less response time todeal with the challenges in the game. In addition, with the assistance of the cloud,the game is able to search for peer players, e.g., those in the same vehicle, thusintroducing more interactive gaming scenarios such as encountered challenges.146Bibliography[1] P. Ross, “Cloud computing’s killer app: Gaming,” IEEE Spectrum, vol. 46, no. 3, pp.14–14, 2009.[2] K. Yang, S. Ou, and H.-H. Chen, “On effective offloading services forresource-constrained mobile devices running heavier mobile internet applications,”Communications Magazine, IEEE, vol. 46, no. 1, pp. 56–63, 2008.[3] S. Wang and S. Dey, “Modeling and characterizing user experience in a cloud serverbased mobile gaming approach,” in Global Telecommunications Conference, 2009.GLOBECOM 2009. IEEE, Nov.-Dec. 2009, pp. 1 –7.[4] M. Chen, “Amvsc: A framework of adaptive mobile video streaming in the cloud,” inGlobal Communications Conference (GLOBECOM), 2012 IEEE, 2012, pp. 2042–2047.[5] S. Wang and S. Dey, “Rendering adaptation to address communication andcomputation constraints in cloud mobile gaming,” in 2010 IEEE GlobalTelecommunications Conference (GLOBECOM 2010), USA, 2010, pp. 1–6.[6] K. Chen, Y. Chang, P. Tseng, C. Huang, and C. Lei, “Measuring the latency ofcloud gaming systems,” in Proceedings of the 19th ACM international conference onMultimedia, ser. MM ’11. New York, NY, USA: ACM, 2011, pp. 1269–1272.[7] J. Vanhatupa, “Browser games: The new frontier of social gaming,” in Recent Trendsin Wireless and Mobile Networks, ser. Communications in Computer and InformationScience, vol. 84. Springer Berlin Heidelberg, 2010, pp. 349–355.[8] W. Cai, M. Chen, and V. Leung, “Toward gaming as a service,” IEEE InternetComputing, pp. 12–18, May 2014.[9] D. Mishra, M. E. Zarki, A. Erbad, C.-h. Hsu, N. Venkatasubramanian, and M. ElZarki, “Clouds + Games: A Multifaceted Approach,” Internet Computing, IEEE,vol. 18, no. 3, pp. 20–27, May 2014.[10] L. Riungu-kalliosaari, J. Kasurinen, and K. Smolander, “Cloud Services andCloud Gaming in Game Development,” IADIS International Conference Game andEntertainment Technologies 2013 (GET 2013), no. 1, 2013.[11] A. Ojala and P. Tyrvainen, “Developing cloud business models: A case study on cloudgaming,” Software, IEEE, vol. 28, no. 4, pp. 42 –47, July-Aug. 2011.147Bibliography[12] C. Moreno, N. Tizon, and M. Preda, “Mobile cloud convergence in gaas: A businessmodel proposition,” in System Science (HICSS), 2012 45th Hawaii InternationalConference on, Jan. 2012, pp. 1344 –1352.[13] S. Dey, “Cloud mobile media: Opportunities, challenges, and directions,” in 2012International Conference on Computing, Networking and Communications, ICNC’12,2012, pp. 929–933.[14] O. Soliman, A. Rezgui, H. Soliman, and N. Manea, “Mobile Cloud Gaming: Issuesand Challenges,” in 10th International Conference, MobiWIS 2013, Paphos, Cyprus,August 26-29, 2013. Proceedings, ser. Lecture Notes in Computer Science, F. Daniel,G. Papadopoulos, and P. Thiran, Eds. Springer Berlin Heidelberg, 2013, vol. 8093,pp. 121–128.[15] Z. Wu, “Gaming in the cloud : one of the future entertainment,” InteractiveMultimedia Conference 2014, 2014.[16] K.-t. Chen, C.-y. Huang, C.-h. Hsu, and G. Integration, “Cloud Gaming Onward:Research Opportunities and Outlook,” Proceeding of The 2014 IEEE InternationalConference on Multimedia and Expo (ICME2014), no. Proceeding of The 2014 IEEEInternational Conference on Multimedia and Expo (ICME2014), 2014.[17] S.-P. CHUAH, C. YUEN, and N.-M. CHEUNG, “Cloud Gaming: A Green Solutionto Massive Multiplayer Online Games,” IEEE Wireless Communications, no. August,pp. 78–87, 2014.[18] E. Depasquale, A. Zammit, M. Camilleri, S. Zammit, A. Muscat, P. Mallia, andS. Scerri, “An analytical method of assessment of RemoteFX as a cloud gamingplatform,” in Mediterranean Electrotechnical Conference (MELECON), 2014 17thIEEE, Apr. 2014, pp. 127–133.[19] K. I. Kim, S. Y. Bae, D. C. Lee, C. S. Cho, H. J. Lee, and K. C. Lee, “Cloud-Basedgaming service platform supporting multiple devices,” ETRI Journal, vol. 35, pp.960–968, 2013.[20] C. Huang, K. Chen, D. Chen, H. Hsu, and C. Hsu, “GamingAnywhere: The FirstOpen Source Cloud Gaming System,” ACM Trans. Multimedia Comput. Commun.Appl., vol. 10, no. 1s, pp. 10:1—-10:25, Jan. 2014.[21] S. Shi, C. Hsu, K. Nahrstedt, and R. Campbell, “Using graphics rendering contextsto enhance the real-time video coding for mobile cloud gaming,” in Proceedings of the19th ACM international conference on Multimedia, ser. MM ’11. New York, NY,USA: ACM, 2011, pp. 103–112.148Bibliography[22] X. Nan, X. Guo, Y. Lu, Y. He, L. Guan, S. Li, and B. Guo, “A novel cloudgaming framework using joint video and graphics streaming,” in Multimedia and Expo(ICME), 2014 IEEE International Conference on, July 2014, pp. 1–6.[23] K. Lee, D. Chu, E. Cuervo, A. Wolman, and J. Flinn, “Demo: DeLorean: UsingSpeculation to Enable Low-latency Continuous Interaction for Mobile Cloud Gaming,”in Proceedings of the 12th Annual International Conference on Mobile Systems,Applications, and Services, ser. MobiSys ’14. New York, NY, USA: ACM, 2014,p. 347.[24] M. Claypool, “Motion and scene complexity for streaming video games,” inProceedings of the 4th International Conference on Foundations of Digital Games,ser. FDG ’09. New York, NY, USA: ACM, 2009, pp. 34–41.[25] M. Claypool, D. Finkel, A. Grant, and M. Solano, “Thin to win? network performanceanalysis of the onlive thin client game system,” in Network and Systems Support forGames (NetGames), 2012 11th Annual Workshop on, 2012, pp. 1–6.[26] K.-t. Chen, Y.-c. Chang, H.-j. Hsu, and D.-y. Chen, “On the Quality of Service ofCloud Gaming Systems,” IEEE Transactions on Multimedia, vol. 16, no. 2, pp. 480–495, Feb. 2014.[27] M. Manzano, J. Hernandez, M. Uruena, and E. Calle, “An empirical study of cloudgaming,” in Network and Systems Support for Games (NetGames), 2012 11th AnnualWorkshop on, 2012, pp. 1–2.[28] M. Manzano, M. Uruen˜a, M. Suzˇnjevic´, E. Calle, J. A. Herna´ndez, and M. Matijasevic,“Dissecting the protocol and network traffic of the OnLive cloud gaming platform,”Multimedia Systems, vol. 20, no. 5, pp. 451–470, 2014.[29] R. Shea, J. Liu, E. Ngai, and Y. Cui, “Cloud gaming: architecture and performance,”Network, IEEE, vol. 27, no. 4, pp. –, 2013.[30] R. Shea and J. Liu, “On GPU Pass-Through Performance for Cloud Gaming:Experiments and Analysis,” in Proceedings of Annual Workshop on Network andSystems Support for Games, ser. NetGames ’13. Piscataway, NJ, USA: IEEE Press,Dec. 2013, pp. 6:1—-6:6.[31] H.-j. Hong, C.-r. Lee, K.-t. Chen, C.-y. Huang, and C.-h. Hsu, “GPU Consolidationfor Cloud Games : Are We There Yet ?” Network and Systems Support for Games(NetGames), 2014 13th Annual Workshop on, 2014.[32] M. Suznjevic, J. Beyer, L. Skorin-kapov, S. Moller, N. Sorsa, T. U. Berlin, and S. Juni,“Towards understanding the relationship between game type and network traffic forcloud gaming,” in Multimedia and Expo Workshops (ICME), 2014 IEEE InternationalConference on, July 2014, pp. 1–6.149Bibliography[33] U. Lampe, Q. Wu, S. Dargutev, R. Hans, A. Miede, R. Steinmetz, and U. L. B,“Assessing Latency in Cloud Gaming,” Cloud Computing and Services Science SE -4, vol. 1, pp. 52–68, 2014.[34] Z. Xue, D. Wu, J. He, X. Hei, and Y. Liu, “Playing High-End Video Games in theCloud: A Measurement Study,” Circuits and Systems for Video Technology, IEEETransactions on, vol. 25, no. 12, pp. 2013–2025, Dec. 2015.[35] Y. Chang, P. Tseng, K. Chen, and C. Lei, “Understanding the performance ofthin-client gaming,” in Communications Quality and Reliability (CQR), 2011 IEEEInternational Workshop Technical Committee on, 2011, pp. 1–6.[36] M. Jarschel, D. Schlosser, S. Scheuring, and T. Hossfeld, “An evaluation of qoe incloud gaming based on subjective tests,” in 2011 Fifth International Conference onInnovative Mobile and Internet Services in Ubiquitous Computing (IMIS), June-July2011, pp. 330 –335.[37] M. Jarschel, D. Schlosser, S. Scheuring, and T. Hoßfeld, “Gaming in the clouds: Qoeand the users’ perspective,” Mathematical and Computer Modelling, vol. 57, no. 11,pp. 2883–2894, 2013.[38] S. Mo¨ller, D. Pommer, J. Beyer, J. Rake-revelant, T. I. Laboratories, and D. T. Ag,“Factors Influencing Gaming QoE : Lessons Learned from the Evaluation of CloudGaming Services.”[39] I. Slivar, M. Suznjevic, L. Skorin-kapov, and M. Matijasevic, “Empirical QoE Studyof In-Home Streaming of Online Games,” Network and Systems Support for Games(NetGames), 2014 13th Annual Workshop on, 2014.[40] Y. Lee, K. Chen, H. Su, and C. Lei, “Are all games equally cloud-gaming-friendly?an electromyographic approach,” in Proceedings of IEEE/ACM NetGames 2012, Oct.2012.[41] P. Quax, A. Beznosyk, W. Vanmontfort, R. Marx, and W. Lamotte, “An evaluation ofthe impact of game genre on user experience in cloud gaming,” in Games InnovationConference (IGIC), 2013 IEEE International, Sep. 2013, pp. 216–221.[42] M. Claypool and D. Finkel, “The Effects of Latency on Player Performance in cloud-based games,” Network and Systems Support for Games (NetGames), 2014 13thAnnual Workshop on, 2014.[43] K. Raaen, “Can gamers detect cloud delay ?” Network and Systems Support forGames (NetGames), 2014 13th Annual Workshop on, vol. 200, pp. 7–9, 2014.150Bibliography[44] C.-y. Huang, C.-h. Hsu, D.-Y. Chen, and K.-T. Chen, “Quantifying User Satisfactionin Mobile Cloud Games,” in Proceedings of Workshop on Mobile Video Delivery, ser.MoViD’14. New York, NY, USA: ACM, 2013, pp. 4:1—-4:6.[45] S. Wang and S. Dey, “Cloud mobile gaming: modeling and measuring user experiencein mobile wireless networks,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 16,no. 1, pp. 10–21, July 2012.[46] Y. Liu, S. Wang, and S. Dey, “Modeling, characterizing, and enhancing userexperience in Cloud Mobile Rendering,” 2012 International Conference on Computing,Networking and Communications (ICNC), pp. 739–745, Jan. 2012.[47] L. Xu, X. Guo, Y. Lu, S. Li, O. C. Au, and L. Fang, “A low latency cloud gamingsystem using edge preserved image homography,” in Multimedia and Expo (ICME),2014 IEEE International Conference on, July 2014, pp. 1–6.[48] L. Lin, X. Liao, G. Tan, H. Jin, X. Yang, W. Zhang, and B. Li, “LiveRender: ACloud Gaming System Based on Compressed Graphics Streaming,” in Proceedings ofthe ACM International Conference on Multimedia, ser. MM ’14. New York, NY,USA: ACM, 2014, pp. 347–356.[49] D. Meilander, F. Glinka, S. Gorlatch, L. Lin, W. Zhang, and X. Liao, “Bringing mobileonline games to clouds,” in Computer Communications Workshops (INFOCOMWKSHPS), 2014 IEEE Conference on, April 2014, pp. 340–345.[50] S. Jarvinen, J.-P. Laulajainen, T. Sutinen, and S. Sallinen, “Qos-aware real-timevideo encoding how to improve the user experience of a gaming-on-demand service,”in Consumer Communications and Networking Conference, 2006. CCNC 2006. 3rdIEEE, vol. 2, Jan. 2006, pp. 994 – 997.[51] J.-P. Laulajainen, T. Sutinen, and S. Jarvinen, “Experiments with qos-aware gaming-on-demand service,” in Advanced Information Networking and Applications, 2006.AINA 2006. 20th International Conference on, vol. 1, April 2006, pp. 805 –810.[52] S. Wang and S. Dey, “Addressing response time and video quality in remoteserver based internet mobile gaming,” in Wireless Communications and NetworkingConference (WCNC), 2010 IEEE, 2010, pp. 1–6.[53] Y. Lu, Y. Liu, and S. Dey, “Enhancing Cloud Mobile 3D display gaming userexperience by asymmetric graphics rendering,” in Computing, Networking andCommunications (ICNC), 2014 International Conference on, Feb. 2014, pp. 368–374.[54] L. He, G. Liu, and C. Yuchen, “Buffer status and content aware scheduling scheme forcloud gaming based on video streaming,” in Multimedia and Expo Workshops (ICME),2014 IEEE International Conference on, Jul. 2014, pp. 1–6.151Bibliography[55] A. Bujari, M. Massaro, and C. E. Palazzi, “Vegas Over Access Point: Making Roomfor Thin Client Game Systems in a Wireless Home,” Circuits and Systems for VideoTechnology, IEEE Transactions on, vol. 25, no. 12, pp. 2002–2012, Dec. 2015.[56] J. Wu, C. Yuen, N. Cheung, J. Chen, and C. W. Chen, “Enabling Adaptive High-Frame-Rate Video Streaming in Mobile Cloud Gaming Applications,” Circuits andSystems for Video Technology, IEEE Transactions on, vol. 25, no. 12, pp. 1988–2001,Dec. 2015.[57] M. Hemmati, A. Javadtalab, A. A. Nazari Shirehjini, S. Shirmohammadi, and T. Arici,“Game as video: Bit rate reduction through adaptive object encoding,” in Proceedingof the 23rd ACM Workshop on Network and Operating Systems Support for DigitalAudio and Video, ser. NOSSDAV ’13. New York, NY, USA: ACM, 2013, pp. 7–12.[58] G. Cheung, N.-M. Cheung, and A. Ortega, “Optimized frame structure usingdistributed source coding for interactive multiview streaming,” in IEEE InternationalConference on Image Processing, Cairo, Egypt, Nov. 2009.[59] G. Huerta-Canepa and D. Lee, “A virtual cloud computing provider for mobiledevices,” in Proceedings of the 1st ACM Workshop on Mobile Cloud Computing &#38;Services: Social Networks and Beyond, ser. MCS ’10. New York, NY, USA: ACM,2010, pp. 6:1–6:5.[60] M. Black and W. Edgar, “Exploring mobile devices as grid resources: Using anx86 virtual machine to run boinc on an iphone,” in Grid Computing, 2009 10thIEEE/ACM International Conference on, Oct. 2009, pp. 9 –16.[61] E. E. Marinelli, “Hyrax : Cloud computing on mobile devices using mapreduce,”Science, vol. 0389, no. September, 2009.[62] P. Sharma, S.-J. Lee, J. Brassil, and K. Shin, “Aggregating bandwidth for multihomedmobile collaborative communities,” in IEEE Transactions on Mobile Computing, vol.6, no.3, Mar. 2007, pp. 280–296.[63] R. Bhatia, L. E. Li, H. Luo, and R. Ramjee, “ICAM: Integrated cellular and ad hocmulticast,” in IEEE Transactions on Mobile Computing, vol. 5, no. 8, Aug. 2006, pp.1004–1015.[64] X. Liu, G. Cheung, and C.-N. Chuah, “Structured network coding and cooperativewireless ad-hoc peer-to-peer repair for WWAN video broadcast,” in IEEETransactions on Multimedia, vol. 11, no.4, 2009.[65] M. Levoy and P. Hanrahan, “Light field rendering,” in ACM SIGGRAPH, NewOrleans, LA, Aug. 1996.152Bibliography[66] P. Merkle, A. Smolic, K. Muller, and T. Wiegand, “Efficient prediction structures formultiview video coding,” in IEEE Transactions on Circuits and Systems for VideoTechnology, vol. 17, no.11, Nov. 2007, pp. 1461–1473.[67] W. Cai, G. Cheung, T. Kwon, and S.-J. Lee, “Optimized frame structure forinteractive light field streaming with cooperative cache,” in IEEE International Conf.on Multimedia and Expo, Barcelona, Spain, July 2011.[68] G. Cheung, A. Ortega, and N.-M. Cheung, “Generation of redundant coding structurefor interactive multiview streaming,” in Seventeenth International Packet VideoWorkshop, Seattle, WA, May 2009.[69] N.-M. Cheung, A. Ortega, and G. Cheung, “Distributed source coding techniques forinteractive multiview video streaming,” in 27th Picture Coding Symposium, Chicago,IL, May 2009.[70] J. Lee, I. Shin, and H. Park, “Adaptive intra-frame assignment and bit-rate estimationfor variable gop length in h.264,” Circuits and Systems for Video Technology, IEEETransactions on, vol. 16, no. 10, pp. 1271 –1279, Oct. 2006.[71] W. Gao and G. Cao, “On exploiting transient contact patterns for data forwardingin delay tolerant networks,” in Proceedings of the The 18th IEEE InternationalConference on Network Protocols, ser. ICNP ’10. Washington, DC, USA: IEEEComputer Society, 2010, pp. 193–202.[72] S. Ioannidis, A. Chaintreau, and L. Massoulie, “Optimal and scalable distribution ofcontent updates over a mobile social network,” in INFOCOM 2009, IEEE, April 2009,pp. 1422–1430.[73] X. Wang, M. Chen, Z. Han, D. Wu, and T. Kwon, “Toss: Traffic offloading by socialnetwork service-based opportunistic sharing in mobile social networks,” in INFOCOM,2014 Proceedings IEEE, April 2014, pp. 2346–2354.[74] K.-T. Chen, P. Huang, and C.-L. Lei, “How sensitive are online gamers to networkquality?” Commun. ACM, vol. 49, no. 11, pp. 34–38, Nov 2006.[75] M. P. Karscig, Principles of Economics, 2nd ed. Harcourt., Inc., 2001.[76] W. Cai, V. Leung, and L. Hu, “A cloudlet-assisted multiplayer cloud gaming system,”Mobile Networks and Applications, vol. 19, no. 2, pp. 144–152, 2014.[77] D. S. Modha, R. Ananthanarayanan, S. K. Esser, A. Ndirango, A. J. Sherbondy, andR. Singh, “Cognitive computing,” Commun. ACM, vol. 54, no. 8, pp. 62–71, Aug.2011.153Bibliography[78] I. Giurgiu, O. Riva, D. Juric, I. Krivulev, and G. Alonso, “Calling thecloud: enabling mobile phones as interfaces to cloud applications,” in Proceedingsof the ACM/IFIP/USENIX 10th international conference on Middleware, ser.Middleware’09, Berlin, Heidelberg, 2009, pp. 83–102.[79] B. Chun and P. Maniatis, “Dynamically partitioning applications between weakdevices and clouds,” in Proceedings of the 1st ACM Workshop on Mobile CloudComputing & Services: Social Networks and Beyond, ser. MCS ’10, New York, NY,USA, 2010, pp. 7:1–7:5.[80] B. Chun, S. Ihm, P. Maniatis, M. Naik, and A. Patti, “Clonecloud: elastic executionbetween mobile device and cloud,” in Proceedings of the sixth conference on Computersystems, ser. EuroSys ’11, New York, NY, USA, 2011, pp. 301–314.[81] E. Cuervo, A. Balasubramanian, D.-k. Cho, A. Wolman, S. Saroiu, R. Chandra, andP. Bahl, “Maui: making smartphones last longer with code offload,” in Proceedingsof the 8th international conference on Mobile systems, applications, and services, ser.MobiSys ’10. New York, NY, USA: ACM, 2010, pp. 49–62.[82] W. Cai and V. Leung, “Decomposed cloud games: Design principles and challenges,”Proceeding of The 2014 IEEE International Conference on Multimedia and Expo(ICME2014), July 2014.[83] M. Mitchell, An Introduction to Genetic Algorithms, 1998. MIT Press, 1998.[84] R. Poli and W. B. Langdon, “Schema theory for genetic programming with One-Pointcrossover and point mutation,” Evolutionary Computation, vol. 6, no. 3, pp. 231–252,1998.[85] K. A. D. Jong and W. M. Spears, “A formal analysis of the role of multi-point crossoverin genetic algorithms,” Annals of Mathematics and Artificial Intelligence, vol. 5, no. 1,pp. 1–26, Mar. 1992.[86] P. Langley, J. Laird, and S. Rogers, “Cognitive architectures: Research issues andchallenges,” Cognitive Systems Research, vol. 10, no. 2, pp. 141 – 160, 2009.[87] M. O’docherty, Object-Oriented Analysis & Design. John Wiley & Sons, 2005.[88] W. Cai, X. Wang, M. Chen, and Y. Zhang, “Mmoprg traffic measurement, modelingand generator over wifi and wimax,” in 2010 IEEE Global TelecommunicationsConference (GLOBECOM 2010), Dec. 2010, pp. 1–5.[89] D. B. Lange and O. Mitsuru, Programming and Deploying Java Mobile Agents Aglets,1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1998.[90] D. Goldman, “Google unveils ’project glass’ virtual-reality glasses,” in Money, Apr.2012.154Appendix AProof of Theorem 2.6In the n× n solution matrix M , we define: i) Two-node loop: ∃ i, j ∈ {1, 2, ..., n} and i 6=j, s.t. Mij ·Mji = 1, ii) Three-node loop: ∃ i, j, k ∈ {1, 2, ..., n} and i 6= j, j 6= k, k 6=i, s.t. Mij ·Mjk ·Mki = 1, iii) Similarly for higher order loops. Denote Q = M2, such that,qij =n∑h=1Mih ·Mhj (A.1)Note that, since Mij ∈ {0, 1},Mkij = Mij for k = 1, 2, ..., n, then we derive:qii =n∑h=1Mih ·Mhi = M2ii +n∑h=1h6=iMih ·Mhi= Mii +n∑h=1h6=iMih ·Mhi(A.2)tr(Q) =n∑i=1qii =n∑i=1(Mii +n∑h=1h6=iMih ·Mhi)=n∑i=1Mii +n∑i=1(n∑h=1h6=iMih ·Mhi)= tr(M) +n∑i=1(n∑h=1h6=iMih ·Mhi)(A.3)Since Mij ∈ {0, 1}, if there is no two-node loop, then,155Appendix A. Proof of Theorem 2.6Mij ·Mji = 0,∀i, j ∈ {1, 2, ..., n} and i 6= j (A.4)Thus,n∑i=1(n∑h=1h6=iMih ·Mhi) = 0 (A.5)therefore,tr(Q) = tr(M2) = tr(M) (A.6)Now, let X = M3 = Q ·M , if there is no two-node loop, we derive:xii =n∑h=1qih ·Mhi = Mii · qii +n∑h=1h6=iqih ·Mhi= M3ii +n∑h=1h6=iqih ·Mhi = Mii +n∑h=1h6=iqih ·Mhi= Mii +n∑h=1h6=i(n∑v=1v 6=i,hMiv ·Mvh ·Mhi)(A.7)156Appendix A. Proof of Theorem 2.6Thus,tr(X) =n∑i=1xii =n∑i=1(Mii +n∑h=1h6=in∑v=1v 6=i,hMiv ·Mvh ·Mhi)=n∑i=1Mii +n∑i=1n∑h=1h6=in∑v=1v 6=i,hMiv ·Mvh ·Mhi= tr(M) +n∑i=1n∑h=1h6=in∑v=1v 6=i,hMiv ·Mvh ·Mhi(A.8)Since Mij ∈ {0, 1}, if there is no three-node loop,∀i, v, h ∈ {1, 2, ..., n}, i 6= v, v 6= h, h 6= iMiv ·Mvh ·Mhi = 0 (A.9)thus,n∑i=1n∑h=1h6=in∑v=1v 6=i,hMiv ·Mvh ·Mhi = 0 (A.10)Therefore,tr(X) = tr(M3) = tr(M) (A.11)Using the same approach for higher order loops, we conclude that, to guarantee loop-free solution, the following equation shall be satisfied:∀p ∈ {1, 2, ..., n}, tr(Mp) = tr(M) (A.12)157


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items