7 Countermeasures for Time-Cheat Detection in Multiplayer Online Games 169 be accomplished based on estimations of network latencies and by exploiting the information contained within transmitted messages [17, 18] The scheme is called Algorithm for Cheating Detection by Cheating (AC/DC) [16, 17] To briefly outline the idea behind the scheme, AC/DC consists on the exploitation of a counterattack to be performed against a suspected node, in order to verify if such a peer can be recognized as a cheater More specifically, at a given time only one peer is enabled to perform the counterattack We call such peer the leader peer pl Of course, mechanisms should be enabled to make sure that eventually a node chosen as a leader is not a cheater Hence, such role should be passed among peers, as discussed more in detail in the following Once the leader pl wants to control a suspected node, pl increases the transmission latency of events generated at pl for pi pl starts the counterattack by continuously computing a measure of the average latency from pi to pl Such meai sure is obtained by taking into account values of •il ek for events coming from pi , i i ıil ek D WT rec ek C driftil l i WT i c ek : (8) i i i In (8), W T rec ek represents the time of reception of ek at pl , WT i c ek is the l i (possibly cheated) wallclock time at which (pi claims that) ek has been generated, i and driftli is the drift between physical clocks of the two peers Such values •il ek can be averaged (or manipulated through a low-pass filter to smooth the variable behaviour of latencies [20, 22, 25, 28]) so as to have a value of the latency from the suspected node to the leader The counterattack that pl exploits against pi consists in the delay of the transmission of each novel event e l generated by pl towards pi Such transmission is i delayed for an amount of time œ Concurrently, new latency values •il ek are collected at pl , for a given time interval These measurements are averaged to obtain a novel estimation of the average latency from pi to pl The new measure •il is compared with the old value •il to understand if a statistically significant difference among the two values exists In particular, when •il is significantly larger than •il , then the hypothesis that the two measured values are equal must be rejected and hence pl suspects pi as a cheater Conversely, the value of œ is progressively increased and the cheating counterattack mentioned above is iteratively repeated until an upper bound value equal to  for •il + œ is exceeded, where  UB C TlW s/ C maxfgapil ; pj …l g: (9) If such upper bound  is reached while a significant difference between •il and •il has not been noticed, then pi cannot be considered as a cheater The use of such a bound on the increment of œ is due to several reasons The need to reach UB is due to guarantee that eventually pl is the peer with the higher (cheated) transmission latency to reach pi i.e •li C œ > UB •ji , pj …i;l Moreover, cases may arise where some game events e j , subsequent to e l but 170 S Ferretti pi = peer to control assume δli = δil /*assumption of symmetry*/ λ = init value /*init value > 0*/ while ((δli + λ ≤ Δ) ^ (pi is not suspected)) set additional delaying time = λ observe δil* of received game events if (δil* significantly larger than δil) suspect pi else 10 λ = increase(λ) Fig AC/DC Pseudocode i still within W ek , can be generated by other peers in …i;l With this in view, i the second term TlW s/ accounts for those events e j W ek with simulation ˚ times higher than « l but within a time interval of range s The third term e max gapj l ; pj …il , instead, accounts for those peers pj with gapj l > Put in other words, it may happen that pl and pj generate event s with same simulation times at different real times and pj reaches such simulation times after pl Based on this consideration, the progressive increment of œ, bounded as mentioned above, i is meant to guarantee that eventually no event in W ek / is received by pi later than l e Thus, when the considered peer pi is a cheater, performing a look-ahead cheat, pi will eventually stop to wait for game events generated by pl The algorithm related to the scheme described above is reported in Figure Such algorithm is performed at the leader peer As mentioned in the pseudo-code, the leader must assume that network latencies between itself and the suspected node are symmetric (i.e., •li D •il ) Needless to say, to account for a delay jitter that usually occurs in best-effort networks, a properly tuned number of measurements is needed in order to obtain an accurate value of •il Moreover, the increment of œ, mentioned with a call of a hypothetical function increase() should be implemented using, for instance, a constant increment of œ or some kind of linear growth Of course, the use of a progressive increment of the value of œ allows a smoother and less intrusive counterattack, since the leader could be able to identify a cheater even before reaching the upper bound for œ [16] A point worth of mention is that different methods can be devised to suspect a peer for cheating Probably, a good approach could be to exploit come heuristics based on the combination of diverse factors such that, for instance, i) the degradation of latencies between pl and pi , ii) the observation that other peers in the same geographical area of pi have latencies smaller than pi , iii) a player that always wins and hence, he is very skilled or he is cheating An important assumption is the independence of the generation of game events by a honest peer with those at other peers In other words, even if certain game events, generated by some peer, will certainly influence the semantics of subsequent game events generated by others (by definition of interactivity in MOGs), in general, the pace of event generation at a given player is mainly influenced by Countermeasures for Time-Cheat Detection in Multiplayer Online Games 171 autonomous decisions From a communication point of view, this means that a honest player generates its own events mostly regardless of the amount, rate and latency of the messages he/she receives This assumption is supported by the typical use of techniques such as dead reckoning and/or optimistic synchronization, exploited to hide latencies on notifications and local losses of availability on updated information, which provide players with the possibility of independently advance the game [8, 19] As mentioned, the role of leader should be carefully assigned and managed among peers First of all, only one leader must be present at a time in the P2P system In fact, suppose two peers concurrently elect themselves as leaders, and suppose they decide to control each other In this case, both peers will delay transmission of game events towards the other one Thus, both peers may erroneously suspect each other Moreover, each peer should become leader only for a limited amount of time, then another node should be elected To this, a token-based scheme should be utilized to determine which is the leader at a given time, i.e every time a process receives the token, it becomes the leader A time deadline is set so that each peer is forced to eventually release the token Thus, after such time deadline the leader could randomly select another peer to be the next leader, pass the token to it and reveal itself to all others This way, other peers know that a leader as done its job and that it passed the token to another host However, also in this case, additional mechanisms should be employed in order to guarantee that eventually all peers become leaders, in order to diminish the probability that cheaters collude and, once gained the token, they pass that token only among themselves, thus preventing honest peers to detect cheaters Upon identification of a cheater pi , the leader could pass the token to another, randomly selected peer (not pi , of course), informing it of its pi0 s suspicion Then, the novel peer will in turn control pi Once a majority of peers suspects pi , then such peer can be considered as a cheater This solution enables agreement among honest peers (on cheaters detection) Moreover, such a cooperative approach makes harder for the cheater to detect if some other node is monitoring his behavior Thus, it results more difficult for the cheater to dynamically switch off its cheat as soon as he detects he is being examined Just to provide the reader with an idea of the efficacy of a detection scheme to cope with time cheats in a P2P scenario, we report in Figure the percentage of cheaters identified based on the use of AC/DC In particular, results were based on a simulation performed to mimic a P2P fully connected gaming architecture built over a best effort, reliable network Based on the literature [3, 13, 16, 19], transmission latencies were based on a lognormal distribution, whose average network latency was set to 100 msec We varied the value of the delay jitter between 10 and 100 msec, since this parameter may affect the efficacy of our detection schemes Starting with an initial estimation of the average latency to reach the controlled peer, the leader was in charge to assess whether, during the counterattack, the newly measured average delay (from the cheater to the leader) grew significantly It is clear that this initial estimation plays an important role in AC/DC Indeed, during the game evolution, measured latencies from the cheater to the leader are affected by the 172 S Ferretti Look-Ahead Detection with AC/DC 110 Δ ≥ 300 msec Detection (%) 100 Δ = 290 msec Δ = 280 msec Δ = 270 msec 90 Δ = 260 msec 80 Δ = 250 msec 70 Δ = 240 msec 60 50 10 20 30 40 50 60 70 80 90 100 dev std (msec) Fig Look-Ahead Detection Through AC/DC look-ahead cheat Thus, if the cheater alters its initialization protocol (where the first estimation of the average latency is measured), the leader may start the counterattack with a delay measure which is higher than the real one [16] To evaluate the impact of this possible fallacy, we simulated different scenarios with very diverse initial estimations of the average latency from the leader to the peer Here, we report on the adverse case where the leader starts the counterattack with a false estimation of the average latency, equal to 2•li , i.e the round trip time from the leader to the cheater Needless to say, with lower values of the initial estimation, it was easier for our scheme to detect cheaters The value of œ was initialized to 10 msec and let grow till reaching (if needed) the upper bound  Each curve refers to a different choice of  For each scenario, 30 different simulations have been run During each simulation, measurements for different message transmissions were employed to make a statistical test Among the possible choices on the statistical tests to be employed, due to our interest for measuring average delays and due to the need for viable choices, easily executable on different peers, we decided to employ a classic one-sided t-test ’ D 0:05/ For each test, the number of measurements was set to 40 game events As shown in the Figure, while AC/DC detected all cheaters in most of the considered scenarios (all the scenarios when  was set greater than 300 msec), some percentage of false negatives (i.e., cheaters not detected) was obtained when high jitters and relatively low upper bounds were set However, these results suggest that it suffices to augment the upper bound  to detect those cheaters It is important to notice that no false positives were obtained through AC/DC, even with very high values of the delay jitter (e.g., std.dev set equal to 100 msec) In other words, no honest peers were erroneously identified as cheaters Countermeasures for Time-Cheat Detection in Multiplayer Online Games 173 Conclusions and Future Directions Several malicious mechanisms can be devised to take unfair advantages in multiplayer online games, by exploiting the inadequacies of best-effort networks We presented here a discussion on time cheats, i.e those cheats that consist in assigning faked timestamps to game events Prevention and detection schemes for cheating avoidance have been also outlined, together with some countermeasures to cope with the specific look-ahead time cheat The main open question is when it should be wiser to employ a detection, rather than a prevention scheme Certainly, detection schemes should be taken into consideration when the considered multiplayer game is a fast-paced one, since cases exist when game communication protocols, embodying a cheating prevention scheme, fail to provide that level of responsiveness, which is required to ensure compelling gaming experiences to distributed players References Baughman, N.E, Levine, B.N., Cheat-proof Playout for Centralized and Distributed Online Games, in Proc of INFOCOM 2001, Anchorage (USA), IEEE, April 2001, 104-113 Baughman, N E., Liberatore, M., and Levine, B N 2007 Cheat-proof playout for centralized and peer-to-peer gaming IEEE/ACM Trans Netw 15, (Feb 2007), 1-13 Borella, M.S., Source models for network game traffic, Computer Communications, 23(4):403-410, February 2000 Cecin, F.R., Real, R., de Oliveira Jannone, R., Resin Geyer, C.F., Martins, M.G., Victoria Barbosa, J.L., FreeMMG: A Scalable and Cheat-Resistant Distribution Model for Internet Games, in Proc of International Symposium on Distributed Simulation and Real-Time Applications, Budapest (Hungary), IEEE, October 2004, 83-90 Chambers, C., Feng, W., Feng, W., and Saha, D 2005 Mitigating information exposure to cheaters in real-time strategy games In Proceedings of the international Workshop on Network and Operating Systems Support For Digital Audio and Video (Stevenson, Washington, USA, June 13 - 14, 2005) NOSSDAV ’05 ACM, New York, NY, 7-12 Cristian, F., Probabilistic clock synchronization, Distributed Computing, 3(3):146-158, 1989 Cristian, F., Fetzer, C., The Timed Asynchronous Distributed System Model, IEEE Transactions on Parallel and Distributed Systems, 10(6):642-657, 1999 Cronin, E., Filstrup, B., Jamin, S., Kurc, A.R., An efficient synchronization mechanism for mirrored game architectures, Multimedia Tools and Applications, 23(1):7-30, May 2004 Cronin, E., Filstrup, B., Jamin, S., Cheat-proofing dead reckoned multiplayer games, in Proc of 2nd International Conference on Application and Development of Computer Games, January 2003 10 Drummond, R., Babaoglu, O., Low-cost clock synchronization, Distributed Computing, 6(3):193-203, 1993 11 GauthierDickey, C., Zappala, D., Lo, V., and Marr, J 2004 Low latency and cheat-proof event ordering for peer-to-peer games In Proceedings of the 14th international Workshop on Network and Operating Systems Support For Digital Audio and Video (Cork, Ireland, June 16 - 18, 2004) NOSSDAV ’04 ACM, New York, NY, 134-139 12 Gusella, R., Zatti, S., The accuracy of clock synchronization achieved by tempo in Berkeley Unix 4.3BSD, IEEE Transactions of Software Engineering, 15(7):47-53, July 1989 174 S Ferretti 13 Farber, J., Network game traffic modeling, in Proc of the 1st Workshop on Network and system support for games, Braunschweig (Germany), ACM, April 2002, 53–57 14 Ferretti, S., Interactivity Maintenance for Event Synchronization in Massive Multiplayer Online Games, Ph.D Thesis, Tech Rep UBLCS-2005-05, University of Bologna (Italy), March 2005 15 Ferretti, S., A Synchronization Protocol For Supporting Peer-to-Peer Multiplayer Online Games in Overlay Networks, in Proceedings of the 2nd International Conference on Distributed Event-Based Systems (DEBS’08), ACM Press, Rome (Italy), July 2008 16 Ferretti, S., Cheating Detection Through Game Time Modeling: A Better Way to Avoid Time Cheats in P2P MOGs?, Multimedia Tools and Applications, Springer, Volume 37, Number 3, May 2008, 339-363 17 Ferretti, S., Roccetti, M., AC/DC: an Algorithm for Cheating Detection by Cheating, in Proceedings of the ACM International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV 2006), Newport, Rhode Island (USA), ACM Press, May 2006, 136-141 18 Ferretti, S., Roccetti, M., Game Time Modelling for Cheating Detection in P2P MOGs: a Case Study with a Fast Rate Cheat, in Proceedings of the 5th ACM SIGCOMM Workshop on Network & System Support for Games 2006 (NETGAMES 2006), Singapore, ACM Press, October 2006 19 Ferretti, S., Roccetti, M., Palazzi, C.E., An Optimistic Obsolescence-Based Approach To Event Synchronization For Massive Multiplayer Online Games, International Journal of Computers and Applications, ACTA Press, Vol 29, No 1, February 2007, 33-43 20 Fiedler, U., Bernhard Plattner: Using Latency Quantiles to Engineer QoS Guarantees forWeb Services, in Proc of the 11th International Workshop on Quality of Service, (IWQoS 2003), LNCS 2707, Springer, Berkeley, CA, USA, June 2003, 345-362 21 Fujimoto, R., Parallel and Distribution Simulation Systems, John Wiley and Sons, Inc., 1999 22 Gibbon, J.F., Little, T.D.C., The Use of Network Delay Estimation for Multimedia Data Retrieval, IEEE Journal on Selected Areas in Communications, IEEE, 14(7):1376-1387 23 Henderson, T., Bhatti, S., Modeling user behaviour in networked games, in Proc of the 9th ACM International Conference on Multimedia (ACM Multimedia), Ottawa (Canada), October 2001, 212-220 24 Lee, H., Kozlowski, E., Lenker, S., Jamin, S., Synchronization and Cheat-Proofing Protocol for Real-Time Multiplayer Games, in Proc of the International Workshop on Entertainment Computing, Makuari (Japan), May 2002 25 Liang, Y.J., Farber, N., Girod, B., Adaptive Playout Scheduling and Loss Concealment for Voice Communication over IP Networks, IEEE Transactions on Multimedia, IEEE Signal Processing Society Press, 5(4):532- 543, April 2001 26 Mauve, M., Vogel, J., Hilt, V., Effelsberg, W., Local-lag and timewarp: Providing consistency for replicated continuous applications, IEEE Transactions on Multimedia, 6(1):47-57, February 2004 27 Mills, D.L., Internet time synchronization: the Network Time Protocol, IEEE Transactions on Communications, 39(10):1482-1493, October 1991 28 Palazzi, C.E., Ferretti, S., Cacciaguerra, S., Roccetti, M., Interactivity-Loss Avoidance in Event Delivery Synchronization for Mirrored Game Architectures, IEEE Transactions on Multimedia, IEEE Signal Processing Society, Vol 8, No 4, August 2006, 874-879 Chapter Zoning Issues and Area of Interest Management in Massively Multiplayer Online Games Dewan Tanvir Ahmed and Shervin Shirmohammadi Introduction Game is a way of entertainment, a means for excitement, fun and socialization Online games have achieved popularity due to increasing broadband adoption among consumers Relatively cheap bandwidth Internet connections allow large number of players to play together Since the introduction of Network Virtual Environment (NVE) in 1980s for military simulation, many interesting applications have been evolved over the past few decades Massively multiplayer online (role-playing) game, MMOG or MMORPG, is a new genre of online games that has emerged with the introduction of Ultima since 1997 It is a kind of online computer game with the participation of hundreds of thousands of players in a virtual world Nowadays multiplayer online games are very popular An MMOG could have millions of subscribers such as World of Warcraft, or Quest Interesting is that all subscribers not play with each other in the same space at the same time As a consequence, the virtual world is divided into realms or kingdoms which are the clones of the original virtual world, each hosting several thousand registered players Technically, the realms are geographically distributed across the world Thus, players from a particular region play together in the same realm To accommodate millions of subscribers, gaming companies provide many realms across the world as needed Realms are further divided into separate areas, also known as a zone Zones can have different themes and different levels of difficulties holding inexperienced players advancing into the next hard level MMOGs are similar to generic massively multiuser simulations that have existed for decades, most notably combat training simulations used by Departments of Defense (DoD) around the world, and more recently, disaster management applications, emergency planning simulators, etc These have reached their current state because of their significant impact on virtual training in high-risk situations as well as their D.T Ahmed and S Shirmohammadi ( ) School of Information Technology and Engineering University of Ottawa, Ottawa, Ontario, Canada e-mail: dahmed@discover.uottawa.ca B Furht (ed.), Handbook of Multimedia for Digital Entertainment and Arts, DOI 10.1007/978-0-387-89024-1 8, c Springer Science+Business Media, LLC 2009 175 176 D.T Ahmed and S Shirmohammadi ability to interpret the real and the simulated results in extraordinary circumstances such as natural disasters or terrorist attacks Commercial MMOGs use the client-server architecture with a single authentic server designed for to support the game logic The server pool regulates game traffic using the zoning concept and makes its implementation more convenient Practically, the communication structure within a zone is similar to the Internet multicast structure, not client-server, because of the players’ common interest in the game logic IP multicast, which was originally proposed for group communication, can be an ideal solution for this purpose But it is a well-known fact that IP Multicast is not deployable on the wide-scale Internet, even in future with IPv6 [1] Thus, current practices heavily rely on centralized architectures that cause scalability bottlenecks In addition, the models are costly to adopt and install Current designs (research oriented), however, try to incorporate client and server side resources in a peer-to-peer fashion to address its different challenges such as scalability, responsiveness, and persistence [2][3] Challenges and Requirements The development of an MMOG faces many challenges A fundamental requirement of any real-time application tool is the exchange of regular update messages among the participants It is a challenging task while keeping a low data rate without affecting the gaming experience Scalability is another important concern when designed for large-scale simulators or virtual environments and MMOGs, as it is the function of other gaming components related to the system However, the amount of data that needs to be exchanged among participants is bounded by server-side resources and other technical conditions such as network bandwidth, processing power and network latencies Network Bandwidth - The bandwidth is the amount of data that can be transmitted over a network in a fixed time-slot It is set by the underlying hardware that connects to the computers The user’s connection to its Internet Service Provider (ISP) and the ISP’s hardware and software infrastructures also affect available bandwidth Practically MMOG players have non-uniform bandwidth Thus, the amount of data that can be exchanged between two computers is restricted by the bandwidth of the players Processing Power - The processing power expresses the computation capability the amount of computations/instructions executed by a computer in a fixed time-slot For gaming, higher processing power is required for multiple reasons like physics engine, collision detection, graphic rendering, artificial intelligence, and to send and receive network messages for networked games But the processing power of all users is not homogenous Thus, the amount of information that can be exchanged between two computers and the quality of perception also depends on their CPU resources Zoning Issues and Area of Interest Management 177 Network Latency - Latency is the amount of time a message takes to travel over a network from a source to a destination The physical limitation of the underlying hardware like routers and switches, and network congestion make it variant from time-to-time The interaction details of an MMOG player must be sent to all other active participants in time Because of the networking limitations and the traffic conditions, some of these updates can be lost or delayed Thus, latency issue cannot be ignored The updated game states must be forwarded within a time limit so that the responsiveness of game play is maintained Generally, latency acceptance varies from game-to-game and is restricted to a value between 100ms to 1000ms for online games [4] The acceptable latency depends on game perspectives (i.e First-person or Third-person), game genres (i.e racing or role playing game), and the sensitivity of actions MMOG Architecture – An Overview To accommodate a large number of players, the map is logically divided into multiple zones where each zone encompasses the players that are in the same vicinity Each zone has a master (e.g server) that coordinates the interactions of the zone members in a multicast fashion A set of master nodes regulates the operation of the MMOG and provides overlay services in client-server model On the other hand, hybrid model incorporates the participation of the players The system is hybrid as it combines the benefits of both centralized and distributed systems To overcome the functionality limitations of the IP multicast, application layer multicasting (ALM) can be chosen for intra zonal communication [5] MMOG Classification There are many types of massively multiplayer online games Some popular types are given in the Table Communication Architecture The right communication structure is very important for interest management as it regulates message transmission and controls network resource usage Different packet delivery methods can be used for data communication in multiplayer games This includes basic unicast communication which is the most popular choice, but broadcast and multicast communications are sometimes also useful The proper choice of TCP or UDP protocol for standard unicast communication is important for online games UDP is a simple best-effort procedure that offers no reliability and no guaranteed packet ordering On the other hand, it has 178 D.T Ahmed and S Shirmohammadi Table Types of MMOGs and examples Types of MMOG Characteristics MMORPG Massively multiplayer online role playing games MMOFPS Massively multiplayer online first person shooters MMORTS MMOR MMOTG MMOSG MMOMG Massively multiplayer online real-time strategy Massively multiplayer online racing games Massively multiplayer online tycoon games Massively multiplayer online sports games/social game Massively multiplayer online manager games Example EverQuest, Star war galaxies World War II Online World: Battleground Europe, 10SIX (known as Project Visitor) Ballerium, Time of Defiance, Shattered Galaxy Darkwind: War on Wheels, Trackmania, Test Drive Unlimited Starpeace, Industry Player Second Life Hattrick little overhead, making it appropriate for highly interactive games (e.g., first-person shooter, car racing) where fast packet delivery is more important On the other hand, TCP guarantees ordered packet delivery and simplifies programming with additional overhead Most importantly, TCP can work more transparently across firewalls Thus, many commercial MMOGs (e.g., EVE Online, Lineage II, and World of Warcraft) use TCP for their communication Local area networks (LANs) can be restrictively configured to allow broadcast This can make state dissemination much simpler and efficient Unfortunately, MMOGs are not able to take the advantages of broadcast in an Internet setting as it is not typically supported across the router boundaries Another technique is multicast which provides group-based packet delivery A host can subscribe to one or multiple multicast addresses and receive all messages sent to those addresses It is usually much more efficient than multiple unicast operations However, multicasting is not widely available on the global Internet due to technical, business, and practical reasons [1] and is therefore not a practical solution for MMOGs There are two general types of MMOG architectures: client-server and peer-topeer There are also hybrid architectures that are between these two main paradigms In client-server architecture, each client has a single connection with the server (Figure 1a) The server is responsible to relay the game states between clients The main advantage of the client-server architecture is the easy controller which is centralized and autonomous As a solution for resource limitations multiple servers are deployed The architecture also facilitates easy implementation of load balancing, fault tolerance, security, and many other concerns But in client-server architecture, the server is an architectural bottleneck and limits the scalability of the system Still it is the most popular and practiced approach in the gaming industry Commercial NVEs use the client-server architecture which is expensive to deploy and cumbersome to maintain For example, the virtual world of Second Life 184 D.T Ahmed and S Shirmohammadi Dead Reckoning This method tries to predict the movement of players to help a player take an expert guess in terms of where others players will be in the next short while Say a player moves from a point P to another point P Each and every discrete step on the path P P is required for appropriate rendering as well as for collision detection If we consider a frame rate of 30 steps per second, which is typical movie quality, each step corresponds to a unique state that needs to be shared among the interested players in every 1=30th of a second Thus, for a large number of moving objects, the total volume of data being shared is high and creates a huge load on network Dead reckoning (DR) is a procedure of approximating a player’s current position based upon the last known position and velocity, and advancing that position based upon elapsed time In MMOGs, dead reckoning predicts a remote object’s trajectory and locally calculates the next movement to reduce network load Interest Management Algorithms There are several types of interest management algorithms which can be classified into three broad categories: proximity-based, visibility-based, and reachabilitybased which are explained next Proximity Algorithms Proximity-based interest management algorithms are solely based on the Euclidean distance between publishers and subscribers This type of algorithm ignores the presence of obstacles which could occlude parts of the game space Algorithms like Euclidean Distance, Square Tiles, and Hexagonal Tiles are some examples of proximity-based interest management Euclidean Distance Algorithm (Figure 6) is purely based on the Euclidean distance among objects while the other two are the approximations that use partitioning concept In Figure 6, the area of interest is shown with respect to the men at the center of the circle Square Tiles Algorithm is a simple region-based interest management where the virtual world is divided into equal-sized squares Technically, the size of squares is set according to the radius of interest of the players So, at any location, the subscriber is interested in at most nine tiles: the subscriber’s current tile and the eight or less surrounding tiles (Figure 7) Whenever a player performs an action, the action is shared among all players subscribed to the square where the action has taken place Like Square Tiles algorithm, Hexagonal Tiles algorithm partitions the virtual world into equal-sized hexagons If a player’s radius of interest intersects a tile, the player subscribes to objects in the tiles So, at any location, the subscriber is Zoning Issues and Area of Interest Management 185 Fig Euclidean distance algorithm for interest management Fig Square tile algorithm for interest management interested in at most seven tiles: the subscriber’s current tile and the six or less surrounding tiles (Figure 8) For each subscriber the algorithm performs a search from its current tile to find all tiles based on the subscriber’s radius of interest The player subscribes to all publishers contained within those tiles The algorithm could nicely be implemented using a depth-first search, and is perhaps the most commonly-used proximity-based algorithm for virtual environments and games 186 D.T Ahmed and S Shirmohammadi Fig Hexagonal tile algorithm for interest management Comparison of Euclidean Distance and Hexagonal Tile Algorithms Euclidean Distance Algorithm Pros Easy to implement Computationally inexpensive No partitions of the virtual world Cons Less realistic as it does not consider obstacles High complexity Hexagonal Tile Algorithm Pros Easy to implement Computationally inexpensive A good benchmark Zoning Issues and Area of Interest Management 187 Cons Less realistic as it does not consider obstacles High complexity Visibility Algorithms Visibility-based algorithms consider the occlusion created by obstacles in the virtual world Theoretically, the area of interest is only limited to the player’s visibility scope In visibility-based algorithms, if a player is out of sight from another player, they are not in the same interest group even if they are physically close Ray Visibility and Tile Visibility are two examples of this class Ray Visibility computes the exact visibility between two objects; on the other hand, Tile Visibility uses approximation to compute the visibility between static regions In Ray Visibility, the area of interest is uncovered with respect to the players’ visibility scope (Figure 9) To determine an object is visible to a player, it traces a line from the position of the player to the position of the object If the line does not intersect with any obstacle in the world, they are visible to each other Ray Visibility is a precise interest management algorithm as it accurately determines the area of Fig Ray visibility algorithm for interest management 188 D.T Ahmed and S Shirmohammadi interest of a player The main advantage is that it provides the lower bound on the number of messages that need to be exchanged between players Tile Visibility algorithm is based on the visibility between tiles The algorithm pre-computes the visibility relationship between each pair of tiles, and the area of interest is projected after the tile visibility for each tile has been pre-computed A player’s area-of-interest is the set of tiles visible from the tile it currently stays Comparison of Ray and Tile Visibility Approach Ray visibility Pros Accurately determines area of interest Exchange minimum number of messages between two players Efficient approach Cons Harder to implement Computationally expensive Tile visibility Pros Simple as tile visibility relationships are pre-computed More realistic than proximity based Cons Dynamic zone shaping is not possible Requires supporting algorithms to handle obstacles Reachability Algorithms Reachability-based algorithms define area of interest with respect to reachability even though one or more regions are out of sight due to obstacles It is somewhat similar to proximity-based algorithms, but it discards objects that are unreachable Unlike visibility-based algorithms, an object that is not visible (e.g., behind an obstacle) may be in the area of interest if there is a path to reach that object within its radius of interest Tile Distance and Tile Neighbor algorithms fall into this category Tile Distance algorithm uses Euclidean distance between a player and a triangular tile It runs a breadth first search (BFS) algorithm from the current tile to Zoning Issues and Area of Interest Management 189 discover the set of connected tiles that intersect the player’s radius of interest Then it discards tiles that are not reachable within the player’s area-of-interest On the other hand, Tile Neighbor algorithm defines area of interest using tile neighbor relationship The algorithm implements a breadth-first search from the current tile of the player and determines all reachable tiles until it reaches a predefined depth The depth is defined as a number For example, if depth is one, the set of tiles would be all direct neighbors of the current tile Comparison of Tile Distance and Tile Neighbor Algorithms Tile distance Pros It takes some advantages of both proximity-based and visibility-based approaches Smarter than other two approaches Cons Computationally expensive Tile neighbor Pros Inexpensive compared to Tile Distance approach Can be tuned based on applications Cons Less accurate compared to Tile Distance approach Zone Crossing in P2P MMOGs A zone crossing occurs when an avatar crosses a zone boundary, i.e an active node leaves a zone and enters into a neighboring zone This has an impact on the P2P structure as nodes in the overlay tree are displaced Synchronous communication depends on how well the protocol handles zone crossings There are two tasks associated with zone crossing: first, the detection of zone crossing; second, the reconstruction of both departing and entering zone structures Irrespective of an overlay structure, when a node crosses a zone, all dependent nodes lose the continuity of data as shown in Figure 10 This causes low quality of experience from users’ perspective Most of the cases, it is hard to reduce such zone crossing penalties in a P2P gaming environment 190 D.T Ahmed and S Shirmohammadi Fig 10 Problem of zone crossing in P2P MMOGs Fig 11 (a) Hexagonal regions with check-in and check-out radii with dynamic adjustment of zone marks (b) Controlling of frequent zone crossings As it is difficult to predict players’ movements at the boundaries, repeated connections and disconnections may be encountered either among the zone masters (i.e servers) or among the multiple overlay networks VELVET’s area of interest management can be implemented to avoid the problem of a player’s frequent movement around the zone boundary [11] The interest-driven zone crossing with dynamic shared regions between adjacent zones is a nice solution to regulate such ungraceful events Here, each zone has two marks namely check-in and check-out (Figure 11a) The area between the two marks is called the buffer region (a.k.a common area or overlapped area) It can control total number of disconnections and connections between the master and a player by adjusting inner and outer marks To make it even more effective, an interest vector applicable inside the dynamic shared regions can be used [12] It would be more realistic if the algorithm relates buffer size with player’s velocity, i.e the overlapped region will be different for different types of players The interest vector is defined in the weighted form I v W< W ; W ; ::W c > where W i represents the weight of the object of type i; c is P the number of object types and W i D The logic is as follows: first, if a player is completely inside a zone it is the member of that zone, which is obvious But if it overlaps two zones and crosses the check-out mark, only then it applies the Zoning Issues and Area of Interest Management 191 interest vector It determines the interest values for both zones The interest value is determined by the following equation zj I/ D c X wi j Oi i D1 j where O i is the number of objects of the type i in zone I These values depend on the number of players that fall inside the circle (i.e visibility range) of the corresponding regions and weights of interest vector (Figure 11b) So if I > I , the player is considered to be the member of zone 1,even if it physically lies in zone For more overlapped zones (at most 3), it follows the same principle As it is difficult to predict the movement of the player, a safety margin can be considered Hence it increases radius of the circle by epsilon O which is related to the velocity of the player v/ and safety period t/, i.e D v t Thus, by controlling the parameters, the protocol changes the circle and hence regulates zone crossings Different Interest Management Models – Research Perspectives Delaunay network is a good solution to NVEs, which organizes players according to their position within the NVE [3] The maintenance cost of a Delaunay network increases with a large number of players Thus, players may have considerable volume of traffic to deal with To address this issue, it proposes a dynamic clustering algorithm where each peer in the network monitors its cost of maintenance and forms a cluster as soon as the volume of traffic exceeds a given threshold Members of a cluster then expand their coordinates to increase their reciprocal distances In this way, by decreasing the concentration of players, it tries to achieve a lower maintenance cost Scalable multicast-based communication protocol (SCORE) is designed for large-scale virtual environments (LSVE) over the Internet [13] To handle large number of participants, it supports multiple multicast groups and multiple agents It dynamically partitions the virtual world into spatial areas and applies planar point processes to determine proper cell size Thus, it ensures the traffic at the receiver side below a threshold with a given probability Knutsson et al describe P2P support for Massively Multiplayer Games by using Pastry and Scribe, a P2P overlay and its associated simulated multicast [14] The virtual world is divided into fixed-size regions Each region is managed by a coordinator, the root of a multicast tree Players inside a region subscribe to the address of the root node to receive updates from other players, so neighbors are discovered via the coordinator Coordinators maintain links with each other, facilitating player transition to other regions However, this incurs some disadvantages In Knutsson et al., due to discrete AoI, users cannot see across regions If players decide to listen to more regions, as suggested, additional messages beyond an AoI must be exchanged A serious performance penalty can be introduced as the overlay 192 D.T Ahmed and S Shirmohammadi does not consider appropriate area of interest, and messages may need to be relayed by many intermediate nodes The model proposed by Hample et al reuses an architecture capable of exploiting the flexibility and scalability of P2P networks [15] The main drawback of peerto-peer networks for games is the lack of a central authority that regulates access and prevents cheating It introduced a set of controller peers that supervise each other This kind of redundancy can prevent cheating The model is based on existing Pastry, the extensions of Scribe The key issue is unbounded end-to-end delay that certainly is a problem for synchronization Marios et al present an approach to support Massively Multiplayer Online Role-Playing Games (MMORP) using a centralized distributed architecture [16] It considers player’s locality of interest to reduce bandwidth requirements for both game servers and clients But it is simply a multiple server based client/server architecture where performance improvement is flat There is no guarantee for end-to-end delay Moreover, it completely ignores player’s chain effects on node departures in a dynamic P2P environment The complexity of this approach is also high Yamamoto et al present a load balancing mechanism for crowded sub-space [17] It proposes a technique to reduce end-to-end event delivery latency through load balancing the tree by replacing one of the intermediate nodes with the backup node incrementally It gives a technique for efficient and seamless switching of sub-spaces for subscription while a player’s view moves in the game space For each sub-space, a player node called the responsible node is selected The responsible node forwards events to all players in the same sub space But it does not mention on what basis such nodes will be chosen It also ignores nodes’ capability of performing such critical task Here in a sub-space, the events are distributed from one to all nodes This pattern follows the client-server architecture which has the aforementioned scalability problems MOPAR, a peer-to-peer networked game architecture, is a scheme for interest management in NVEs’ [18] It is a combination of both structured and unstructured peer-to-peer system Here, a master node is chosen in each zone and becomes the parent of all other players in the zone named slaves Each master node supports all slaves within its zone Although the architecture is P2P in the sense that the master node is also connected to other master nodes and manages inter-zonal communication, the network architecture within a zone looks like a client-server architecture So, it has the single point of failure problem that client-server architecture always encounters One of the main drawbacks of MOPAR is unexploited slaves’ bandwidth as salves are only connected to the master node not among themselves A Steed et al propose a simple but powerful visibility structure called frontier sets [19] It shows how to construct this set at runtime For a pair of nodes, a frontier identifies two mutually invisible regions containing nodes The benefit of frontier sets is to enable scalability of a system This is possible because, as long as two nodes stay in their respective frontiers, they not need to send update information to each other This is an interesting method in theory However, it would be computationally expensive to implement it in real-time Zoning Issues and Area of Interest Management 193 To give users a sense of realism in Collaborative Virtual Environments (CVE), there is a need for socialization in virtual community The key issues in CVE research include managing consistency and persistency of distributed information and assuring real-time interactivity C.T Fook et al present Collaborative Interaction Management (CIM) and Task-Oriented Interaction Management (TIM) methods to resolve extensibility issues in CVE [20] When multiple interactions occurred at the same time, these approaches can govern and control the message flow Here Scene Interaction Manager (SIM) monitors the network characteristics to prevent network saturation and long network delay ATLAS focuses two broad concepts to support users to collaborate in heterogeneous environments It goes for self-tune-ability rather than for re-configurability where a system automatically configures itself based on current environment Other concept is the personalized information filtering Based on human heuristics, application semantics, user preferences and current system status, it filters events to increase the scalability without degrading interactive performance of the users [21] To support a large number of concurrent participants, Z Liang proposed a mobile agent-based architecture for Large-scale Collaborative Virtual Environment (LCVE) [22] The software system consists of mobile agents which are responsible for different tasks related to LCVE Conclusions and Future Directions A Distributed Virtual Environment (DVE) is a simulated world that allows people to collaborate in real-time over a network Possible applications for DVE systems are multiplayer online games, collaborative engineering and military training In general, a DVE system consists of several servers where each server performs the message relaying task in real-time to let the clients to collaborate In MMOG, the area of interest management is a way of determining relevant information related to an avatar in the virtual space The massively multiuser online game is large and generates plenty of information caused by various events But, all information is not important to every player Thus, forwarding relevant information to each player is an effective way to approach message distribution Dynamic area of interest management for online games is a new direction of research that characterizes the interaction space in real-time and eliminates/reduces inter-AoI communications To prevent frequent change of AoI, artificial intelligence techniques can be integrated The commercialization of MMOG over hybrid P2P architecture is another area that needs to be explored and examined 194 D.T Ahmed and S Shirmohammadi References A El-Sayed, V Roca, and L Mathy, “A survey of proposals for an alternative group communication service,” IEEE Network Magazine special Issue on Multicasting: An Enabling Technology, vol 17, no 1, pp 47–54, 2003 S.-Y Hu, S.-C Chang, and J.-R Jiang, “Voronoi state management for peer-to-peer massively multiplayer online games,” in IEEE Consumer Communications and Networking Conference, 2008, p 1134–1138 M Varvello, E Biersack, and C Diot, “Dynamic clustering in delaunay-based p2p networked virtual environments,” in ACM SIGCOMM workshop on Network and system support for games, 2007, pp 105–110 M Claypool and K Claypool, “Latency and player actions in online games,” Entertainment networking SPECIAL ISSUE: Entertainment networking, pp 40–45, 2006 M Hosseini, D T Ahmed, S Shirmohammadi, and N D Georganas, “A Survey of Application-Layer Multicast Protocols,” IEEE Communications Surveys & Tutorials, vol 9, no 3, pp 58–74, 2007 I Kazem, D T Ahmed, and S Shirmohammadi, “A visibility-driven approach to managing interest in distributed simulations with load balancing,” in IEEE Symposium on Distributed Simulation and Real-Time Applications (DS-RT), 2007, pp 31–38 T Iimura, H Hazeyama, and Y Kadobayashi, “Zoned federation of game servers: a peer-topeer approach to scalable multi-player online games,” in NetGames ’04: Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, 2004, pp 116–120 B De Vleeschauwer et al., “Dynamic microcell assignment for massively multiplayer online gaming,” in ACM SIGCOMM workshop on Network and system support for games (NetGames), 2005, pp 1–7 F Lu, S Parkin, and G Morgan, “Load balancing for massively multiplayer online games,” in ACM SIGCOMM workshop on Network and system support for games (NetGames), 2006, p 10 J Smed, T Kaukoranta, and H Hakonen, “Aspects of networking in multiplayer computer games,” in International Conference on Application and Development of Computer Games in the 21st Century, 2001, pp 74–81 11 J C d Oliveira and N D Georganas, “VELVET: an adaptive hybrid architecture for very large virtual environments,” Presence: Teleoperators and Virtual Environments, vol 12, no 6, pp 555–580, 2003 12 D T Ahmed, S Shirmohammadi, and J Oliveira, “Improving gaming experience in zonal MMOGs,” in MULTIMEDIA ’07: Proceedings of the 15th international conference on Multimedia, 2007, pp 581–584 13 E L´ ty, T Turletti, and F Baccelli, “SCORE: a scalable communication protocol for largee scale virtual environments,” IEEE/ACM Transactions on Networking (TON), vol 12, no 2, pp 247–260, 2004 14 B Knutsson, H Lu, W Xu, and B Hopkins, “Peer-to-Peer Support for Massively Multiplayer Games,” in IEEE Conference on Computer Communications (INFOCOM), 2004 15 T Hampel, T Bopp, and R Hinn, “A peer-to-peer architecture for massive multiplayer online games,” in NetGames ’06: Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, 2006, p 48 16 M Assiotis and V Tzanov, “A distributed architecture for MMORPG,” in ACM SIGCOMM workshop on Network and system support for games (NetGames), 2006, p 17 S Yamamoto, Y Murata, K Yasumoto, and M Ito, “A distributed event delivery method with load balancing for MMORPG,” in NetGames ’05: Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, 2005, pp 1–8 18 A P Yu and S T Vuong, “MOPAR: a mobile peer-to-peer overlay architecture for interest management of massively multiplayer online games,” in international workshop on Network and operating systems support for digital audio and video (NOSSDAV)), 2005, pp 99–104 19 A Steed and C Angus, “Supporting Scalable Peer to Peer Virtual Environments Using Fron- Zoning Issues and Area of Interest Management 195 tier Sets,” in VR ’05: Proceedings of the 2005 IEEE Conference 2005 on Virtual Reality, 2005, pp 27–34 20 C T Fook, L Qingping, and Z Liang, “A Novel Approach for Addressing Extensibility Issue in Collaborative Virtual Environment,” in CW ’03: Proceedings of the 2003 International Conference on Cyberworlds, 2003, p 78 21 D Lee, M Lim, S Han, and K Lee, “ATLAS: A Scalable Network Framework for Distributed Virtual Environments,” Presence: Teleoperators and Virtual Environments, vol 16, no 2, pp 125–156, 2007 22 Z Liang, L Qingping, and C T Fook, “Mobile Agent-Based Architecture for Large-Scale CVE,” in CW ’03: Proceedings of the 2003 International Conference on Cyberworlds, 2003, p 69 Chapter Cross-Modal Approach for Karaoke Artifacts Correction Wei-Qi Yan and Mohan S Kankanhalli Introduction A multimedia environment ….t / usually consists of a multiplicity of correlated data streams …i t / with n 2/: ….t / D f…i t / ; i D 0; 1; 2; ; nI t 0; C1/g (1) The correlations R among them can be expressed as: RD ˚ W …p t / …q t / ; Ä p; q Ä n « (2) Karaoke (“missing orchestra” in Japanese) is an example of such a multimedia environment This Japanese entertainment form features a live singer with prerecorded accompaniment The user sings into a microphone while the stored music is played simultaneously Karaoke is tremendously popular in eastern Asia as an avenue for recreation and entertainment Some of the distinctive characteristics of karaoke are: – It encourages artistry in which users try to emulate the original singer in terms of timbre and expression; – The dynamic highlighting of the song caption along with the music provides synchronization cues to the user; – Its appeal lies in the immediate feedback of the experience to the user; – It is a vicarious means of experiencing concert singing; – Users usually have a portfolio of songs to sing and they tend to improve the quality of rendition with practice W.-Q Yan Department of Computer Science, Queen’s University of Belfast, Belfast, UK e-mail: w.yan@qub.ac.uk M.S Kankanhalli ( ) Department of Computer Science, National University of Singapore, Singapore e-mail: mohan@comp.nus.edu.sg B Furht (ed.), Handbook of Multimedia for Digital Entertainment and Arts, DOI 10.1007/978-0-387-89024-1 9, c Springer Science+Business Media, LLC 2009 197 198 W.-Q Yan and M.S Kankanhalli The karaoke system is usually based on a CD player The CD multimedia data includes one video stream and one audio stream which is the musical accompaniment The system has two audio channels by which the live singing and the accompaniment channels are mixed and played through the speakers The original rendering of the singing is usually available on the CD Given that most users are not professionally trained singers, their rendition often includes some artifacts related to pitch, tempo and tune There are several reasons for the cause of artifacts [17]: – Amateurs sometimes cannot sing a song in the proper key and they jump from one scale to another freely In high key singing, exhaustion often leads to artifacts – Some karaoke users are not able to maintain a regular beat, which can vary from being very fast to being too slow – The timbre of the singing may be very different from that of the original singer This is because a singer needs to be trained so as to properly exercise the vocal cords in order to produce a rich timbre Moreover, accents can also affect the quality of the rendition – There can be noise artifacts due to sensitive pickups and feedback A huffing sound is produced by a sensitive microphone which amplifies the breathing sounds A piercing screech can sometimes be heard due to amplifier feedback especially when the speakers are close to the microphone Such artifacts, which are annoying to the karaoke users and watchers, occur frequently as shown in Fig and Fig Our goal of karaoke artifacts handling is to remove or mitigate the effects of the artifacts in the karaoke audio The key idea is to use the original singer’s rendition as a guide to correct the artifacts Actually, even after the correction, the singing will not sound like that of the professional singer The main reason is that we are basically doing timing correction The actual sound quality is determined by the timbre, voice quality, training, emotion, mood etc which is not affected by our processing Thus, this leaves enough leeway for individuality and creativity in the improvised rendition Given that there is correlation and redundancy among audio and video streams, we exploit the cross-modal information in order to perform artifact removal We will thus judiciously employ all of the available information in order to perform the correction Fig A professional singer’s waveform with music accompaniment Cross-Modal Approach for Karaoke Artifacts Correction 199 Fig Two amateur singers’ waveforms without music accompaniment Fig Flowchart for the cross-modal karaoke correction In this chapter, we combine adaptive sampling in conjunction with video analogies (VA) to correct the audio stream in the karaoke environment Ä D fÄ.t / W Ä.t / D U t / ; K.t // ; t ts ; te /g where ts and te are start time and end time respectively, U.t / is the user multimedia data We employ multiple streams from the karaoke data K.t / D KV t / ; KM t / ; KS t//, where KV t /, KM t / and KS t / are the video, musical accompaniment and original singer’s rendition respectively along with the user multimedia data U t / D UA t / ; UV t // where UV t / is the user video captured with a camera and UA t / is the user’s rendition of the song We analyze the audio and video streaming features ‰.Ä/ D f‰.U t / ; K.t //g D f‰.U t // ; ‰.K.t //g D f‰U t / ; ‰K t /g, to produce the corrected singing, namely output U t /, which is made as close as possible to the original singer’s rendition Note that ‰ represents any kind of feature processing Figure summarizes the research problem tackled in this chapter In a Karaoke system, the input is video stream KV t/, music stream KM t / and user audio stream UA t / After multiple stream segmentation, the tune, tempo and loudness of audio stream are adjusted aligning to the audiovisual information extracted from the original performance The corrected audio stream is mixed with the music stream together as the output ... Kankanhalli ( ) Department of Computer Science, National University of Singapore, Singapore e-mail: mohan@comp.nus.edu.sg B Furht (ed.), Handbook of Multimedia for Digital Entertainment and Arts, DOI 10.1007/978-0-387-89024-1... used to determine useful information for a specific player and block all other information For example, the area of interest of an avatar in an MMOG is the set of avatars and non-playing components... Ahmed and S Shirmohammadi ( ) School of Information Technology and Engineering University of Ottawa, Ottawa, Ontario, Canada e-mail: dahmed@discover.uottawa.ca B Furht (ed.), Handbook of Multimedia