雷欽隆臺灣大學：電機工程學研究所陳寬達Chen, Kuan-TaKuan-TaChen2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53111近幾年來，因為即時互動應用程式（例如線上遊戲）的流行，如何為這類型應用程式提供好的的服務品質提供已成為重要的研究主題。然後，由於目前的網際網路本身並不提供服務品質保證，再加上這類型應用程式的特性－即時性、互動性以及雙向資料傳輸－這些因素加總起來，使得即時互動應用程式的服務品質提供成為一個十分困難的任務。 要為網路應用程式提供高滿意度的使用經驗的困難之一是，不像系統層面的效能指標，例如頻寬或延遲時間，使用者滿意度是抽象而且不可量測的。要解決這個問題的關鍵是，我們必須能夠客觀並有效率地測量使用者對於網路效能的感覺。 我們在這篇論文裡從各個層面來探討要為即時互動應用程式提供服務品質的問題。因為下述原因，我們把研究焦點放在兩種應用程式，網際網路電話（Voice over IP），以及線上遊戲。首先，它們皆被認為是自從World Wide Web流行之後少見的殺手級應用，而且也是許多網路用戶最常使用的軟體。第二點，更重要的是，大眾使用電腦以及網路的主要動機通常脫離不了人際溝通以及娛樂，而網路電話及線上遊戲正是能夠滿足這兩項需求的代表性應用。 我們的研究可大略分為兩部分。第一部分，我們徹底地分析線上遊戲所產生的網路流量。我們的研究目的是發現及確認潛在的效能問題，為日後開發高效能網路遊戲平台建構更穩固的基礎。第二部分，我們嘗試為網路電話及線上遊戲使用者對於網路品質的「感覺」進行客觀地量測。我們的目標是為即時互動應用程式定義客觀的使用者滿意度指標，做為服務品質提供的最佳化基準。 我們的主要貢獻可分為三點：（一）我們指出目前線上遊戲的潛在效能問題，並且提出各種可能的解決方案；（二）我們提出可從使用某項服務的時間，例如玩線上遊戲的時間或者講電話的時間，來推論使用者對於網路服務品質的感覺。另外我們也為Skype應用程式提出一項基於網路品質的使用者滿意度指標，並且提出驗證方法；（三）我們為目前普遍存在網路遊戲的作弊行為－使用機器人程式來進行遊戲－提出解決之道，我們提出的方法特色在於能夠推廣到其它的遊戲，並且能抵擋來自機器人程式設計者的反制。In recent years, QoS (Quality-of-Service) provisioning for real-time interactive applications, such as online gaming, has been actively discussed because of the popularity of such applications. However, the design of non-QoS-enabled Internet and the requirement of real-timeliness, interactivity, and bi-directionality of the applications together make the goal of QoS provisioning immensely challenging. One of the main obstacles to provide satisfactory user experience for network applications is that, unlike system-level performance metrics, such as bandwidth or latency, user satisfaction is intangible and unmeasurable. The key to this problem is to measure users' opinions about network performance objectively and efficiently. We endeavored in this work to explore the problem of QoS-provisioning for real-time interactive applications in a number of aspects. We aim at two applications, VoIP and online gaming, as our target of study for two reasons. First, they are considered killer applications since the emergence of World Wide Web, and have been part of the primary reasons people use the Internet. The second and more important reason is that, interpersonal interaction and entertainment are usually the goals for the mass to use the computer and Internet, where VoIP and online gaming could be seen representative applications that fulfill those fundamental demands. Our work is classified into two parts. In the first part, we thoroughly analyze the traffic generated from online game playing. We aim to identify potential performance bottlenecks that could be served a basis to develop more efficient network infrastructure for such applications. In the second part, we strive for emph{objectively} measuring the users' perception when using VoIP and gaming applications based on the network conditions the users experience. Our goal is to define a objectively assessable metric for QoS-provisioning of real-time interactive applications through the mapping from system-level performance metrics to user-level satisfaction measures. Our main contributions are three-fold: 1) We pointed out the potential performance problems of online gaming and proposed some possible solutions; 2) We proposed to infer users' awareness of network QoS by the time they spend on a service, e.g., game playing or Internet phone. Also, we proposed and verified a user satisfaction measure for Skype, which is computed based on the network conditions users experience; 3) We proposed a number of strategies to cope with the prevalent but undesirable use of online game bots, where our methods are shown generalizable across different games and robust under counter-attacks from bot developers.Contents List of Figures ix List of Tables xiii 1 Introduction 1 2 Background 6 2.1 Related Research . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Studies of Network Game Traffic . . . . . . . . . . . . . . . . 6 2.1.2 Studies of Network Game Performance . . . . . . . . . . . . . . 7 2.1.3 Assessment of QoS-Sensitivity of Online Gamers . . . . . . . . . 7 2.1.4 Measurement of VoIP User Perception . . . . . . . . . . . . . . 8 2.1.5 Online Game Bot Prevention and Detection . . . . . . . . . . . . 9 2.2 Studied Applications . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 ShenZhou Online . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Ragnarok Online and the Bots . . . . . . . . . . . . . . . . . 12 2.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 Time Censorship and Survival Curve Estimation . . . . . . . . . 14 2.3.2 Logistic RegressionModeling . . . . . . . . . . . . . . . . . . 17 2.3.3 Proportional Hazards Regression Modeling . . . . . . . . . . . 17 3 Trace Collection 19 3.1 ShenZhou Online . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Network Setup . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.2 Identification of Game Sessions . . . . . . . . . . . . . . . . 21 3.1.3 Trace Summary . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.4 Trace Representativeness . . . . . . . . . . . . . . . . . . . 24 3.2 Ragnarok Online . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3 Skype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.1 Network Setup . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.2 Capturing Skype Traffic . . . . . . . . . . . . . . . . . . . . 30 3.3.3 Identification of VoIP Sessions . . . . . . . . . . . . . . . . 30 3.3.4 Measurement of Path Characteristics . . . . . . . . . . . . . . 31 3.3.5 Trace Summary . . . . . . . . . . . . . . . . . . . . . . . . . 32 I System-Level Performance Analysis 35 4 Game Traffic Analysis 38 4.1 Traffic Characteristics of Individual Connections . . . . . . . . 40 4.1.1 Packet Size . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1.2 Packet Load and Bandwidth Usage . . . . . . . . . . . . . . . . 41 4.1.3 Distribution of Packet Interarrival Times . . . . . . . . . . . 42 4.1.4 Temporal Dependence of Packet Interarrivals . . . . . . . . . . 44 4.1.5 Peak Rate and Burstiness . . . . . . . . . . . . . . . . . . . 47 4.2 Aggregate Traffic Characteristics . . . . . . . . . . . . . . . . 52 4.2.1 The Flash Crowd Effect . . . . . . . . . . . . . . . . . . . . 52 4.2.2 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2.3 Burstiness and Self-Similarity . . . . . . . . . . . . . . . . 57 4.3 Session Characteristics . . . . . . . . . . . . . . . . . . . . . 64 4.3.1 Interarrivals . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.2 Duration . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5 Game Performance Analysis 69 5.1 TCP Behavior in Online Games . . . . . . . . . . . . . . . . . . 71 5.1.1 Protocol Overhead . . . . . . . . . . . . . . . . . . . . . . . 71 5.1.2 In-Order Delivery . . . . . . . . . . . . . . . . . . . . . . . 72 5.1.3 Congestion Control . . . . . . . . . . . . . . . . . . . . . . 76 5.1.4 Loss Recovery . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.2 Design Guidelines for Game Transport Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 II User-Level QoS Provisioning 85 6 The Impact of Network QoS on Game Player Departures 87 6.1 General Pattern of Game Player Departures . . . . . . . . . . . . 91 6.2 Day of theWeek Effect . . . . . . . . . . . . . . . . . . . . . . 92 6.3 Sensitivity of Game Playing Time to Network QoS . . . . . . . . . 93 6.4 Sensitivity of Premature Departure to Network QoS . . . . . . . . 95 6.5 Modeling Game Playing Time . . . . . . . . . . . . . . . . . . . 98 6.5.1 Proportional Hazards Check for Categorical Variables . . . . . 99 6.5.2 Functional Form Identification and Adjustment . . . . . . . . 100 6.5.3 Outlier Detection . . . . . . . . . . . . . . . . . . . . . . 104 6.5.4 Assessment of Model Adequacy . . . . . . . . . . . . . . . . . 105 6.5.5 Model Validation and Interpretation . . . . . . . . . . . . . 106 6.6 Modeling Premature Departure Probability . . . . . . . . . . . . 108 6.6.1 Sampling of QoS Factors . . . . . . . . . . . . . . . . . . . 108 6.6.2 Predictability Analysis . . . . . . . . . . . . . . . . . . . 109 6.6.3 Model Fitting . . . . . . . . . . . . . . . . . . . . . . . . 110 6.6.4 Assessment of the Model Adequacy . . . . . . . . . . . . . . . 111 6.6.5 Model Interpretation . . . . . . . . . . . . . . . . . . . . . 112 6.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.7.1 Impact of QoS Factors . . . . . . . . . . . . . . . . . . . . 115 6.7.2 Impact of Transport Protocols . . . . . . . . . . . . . . . . 118 6.7.3 Application of Player Sensitivity to Network QoS . . . . . . . 118 6.7.4 Application of Premature Departure Prediction . . . . . . . . 120 7 Measurement of Skype User Satisfaction 121 7.1 Correlation between Call Duration and Network QoS . . . . . . . 123 7.1.1 Effect of Source Rate . . . . . . . . . . . . . . . . . . . . 123 7.1.2 Effect of Network Conditions . . . . . . . . . . . . . . . . . 125 7.2 Modeling Call Duration . . . . . . . . . . . . . . . . . . . . . 127 7.2.1 Collinearity among Factors . . . . . . . . . . . . . . . . . . 128 7.2.2 Sampling of QoS Factors . . . . . . . . . . . . . . . . . . . 129 7.2.3 Model Fitting . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2.4 Model Interpretation . . . . . . . . . . . . . . . . . . . . . 132 7.2.5 Proposal of User Satisfaction Index . . . . . . . . . . . . . 132 7.3 Validation of User Satisfaction Index . . . . . . . . . . . . . 133 7.3.1 Inferring Conversation Patterns . . . . . . . . . . . . . . . 134 7.3.2 Voice Interactivity Analysis . . . . . . . . . . . . . . . . . 138 7.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.4.1 Impact of QoS Factors . . . . . . . . . . . . . . . . . . . . 143 7.4.2 Comparison between USI and Speech Quality Measures . . . . 144 8 Coping with Online Game Bots 146 8.1 Overview. . . . . . . . . . . . . . . . . . . . . .. . . . . . . 146 8.2 Analysis of Human Player and Bot Traffic . . . . . . . . . . . . 147 8.2.1 Regularity in Client Traffic . . . . . . . . . . . . . . . . . 148 8.2.2 Command Timing . . . . . . . . . . . . . . . . . . . . . . . . 152 8.2.3 Traffic Burstiness . . . . . . . . . . . . . . . . . . . . . . 154 8.2.4 Player Reaction to Network Conditions . . . . . . . . . . . . 159 8.3 Proposed Bot Detection Strategies . . . . . . . . . . . . . . . 161 8.3.1 Command Timing . . . . . . . . . . . . . . . . . . . . . . . . 161 8.3.2 Trend of Traffic Burstiness . . . . . . . . . . . . . . . . . 164 8.3.3 Magnitude of Traffic Burstiness . . . . . . . . . . . . . . . 164 8.3.4 Player Reaction to Network Conditions . . . . . . . . . . . . 165 8.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . 167 8.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 8.5.1 Generality of Proposed Detection Strategies . . . .. . . . . . 169 8.5.2 Robustness against Counter-Attacks . . . . . . . . . . . . . . 169 8.5.3 Server-Side Deployment . . . . . . . . . . . . . . . . . . . . 171 8.5.4 Reactive Identification . . . . . . . . . . . . . .. . . . . . 172 9 Summary 173 9.1 Contributions . . . . . . . . . . . . . . . . . . . .. . . . . . 174 9.1.1 Game Traffic Study . . . . . . . . . . . . . . . . . . . . . . 174 9.1.2 Game Performance Study . . . . . . . . . . . . . . . . . . . . 175 9.1.3 QoS-Sensitivity of Online Gamers . . . . . . . . . . . . . . . 176 9.1.4 User SatisfactionMeasurement . . . . . . . . . . . . . . . . . 177 9.1.5 Game Bot Detection . . . . . . . . . . . . . . . . . . . . . . 177 9.2 Future Research . . . . . . . . . . . . . . . . . . . .. . . . . 178 Bibliography 1792285269 bytesapplication/pdfen-US線上遊戲網路電話服務品質Online GamesVoIPSkypeQoSthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53111/1/ntu-95-D91921008-1.pdf