Transcript Connection
Networks Network Protocols Peer-to-peer Client-Server Configurations Trust Nov 16, Fall 2005 Game Design 1 Topics AI – Flocking & coordinated movement – Planning – Pathfinding and search Networking – Multiplayer/things not covered today Audio Nov 16, Fall 2006 Game Design 2 Other topics Advanced graphics – Animation – Deformation, inverse kinematics – Motion capture – Particle effects – Special lighting Ethics – Cheating, justice Nov 16, Fall 2006 Game Design 3 Other topics Fake terrain Industry Playtesting AIwisdom.com Nov 16, Fall 2006 Game Design 4 Networks Required for multiplayer games 3 Standard technologies – Modems – Ethernet – Internet Nov 16, Fall 2006 Game Design 5 Internet The greatest thing since sliced bread The savior of humanity Will increase freedom and democracy – Around the world – In your neighborhood Nov 16, Fall 2006 Game Design 6 Internet User Protocols TCP UDP – Connection – Reliable – Bytes arrive in order they were sent – Collects small packets and transmits them together – Stream of bytes Nov 16, Fall 2006 Game Design – Connectionless – Unreliable – Arbitrary arrival order 7 TCP Reliable stream of bytes – Implies the need for a “connection” Connection sets up data structures – Hold incoming packets – Hold outgoing packets – Handle retransmits Nov 16, Fall 2006 Game Design 8 TCP Reliability Each packet does Send-ReceiveAcknowledge Sender Send Receiver Receive Acknowledge Sender holds sent packet until ACK is received Sender retransmits if ACK takes too long Nov 16, Fall 2006 Game Design 9 TCP One Send-Receive-Ack takes time Overlay Sends and Acks Maintain a queue in sender and receiver Sender Send 0 Receiver 1 0 2 1 0 3 2 1 3 2 Ack Sender 3 Nov 16, Fall 2006 Game Design 10 TCP Circular Queue -- Sender Sends data and Puts it in send queue Sets timer on this queue item If timer expires, and no ACK, re-send data – Set another, longer timer – Exponentially increasing time When ACK received – If this queue slot is the oldest, • Free the slot for new data If no queue space avail, sender app waits! Nov 16, Fall 2006 Game Design 11 TCP Receive Queue Receiver maintains a queue the same size as the sender’s When a packet arrives, send ACK If the packet is next in sequence – Give it to application Else Keep it in queue – Another, earlier packet is on its way Nov 16, Fall 2006 Game Design 12 TCP If no ACKS arrive for a long enough time – Temporarily gives up – Sends test packets When test packets get through – Starts slow, builds up Nov 16, Fall 2006 Game Design 13 TCP Wrap-up Connection sets up sequencing and queues – Reliable arrival: – Reliable order: Retransmit Sequence numbers TCP bunches up data on 200ms intervals – Minimizes overhead for small chunks of data – This option can be turned off TCP Has an “emergency” channel – OOB Out Of Band Nov 16, Fall 2006 Game Design 14 UDP Connectionless! – No underlying data to maintain Unreliable transmission – If you lose a packet, it’s gone – Network software must handle this Out-of-order arrival – Network software must handle that, too! Fast – When the port gets the data, the app gets it Nov 16, Fall 2006 Game Design 15 UDP Packets will drop! – 1 in 5 over non-local connection Have to do your own re-send Some packets are time sensitive – Care little about the past ship location No header compression – May end up with greater overhead than TCP with PPP Nov 16, Fall 2006 Game Design 16 Game Architectures Peer-to-peer Client/Server – One server per game Floating server – One client is also a server Distributed server – Multiple servers for large world Nov 16, Fall 2006 Game Design 17 Peer-to-Peer Simple version: Lockstep – eg. Doom – Each client transmits to other – Wait for everyone to get data – Proceed to next step Nov 16, Fall 2006 Game Design 18 Peer-to-Peer Advantages Disadvantages – Simple – Nobody has to provide a server • Including the Game’s authors! – Good for turn-based games with low bandwidth – TCP Nov 16, Fall 2006 Game Design – Frame rate is that of • Slowest machine • Worst connection – Hackable – Not good for real-time games 19 Client/Server Server per game – MUDs, Fireteam, NetTrek – Someone must provide server ($$$) • Possibly the game’s authors – Less hackable – Single point of failure – Server must be big & well-connected Nov 16, Fall 2006 Game Design 20 Floating Server Peer-to-peer Server resolves the action One peer is the server – Unreal • One player elects to be the server – X-Wing vs Tie-Fighter: • First player to enter session – Starcraft • Player with the CD Nov 16, Fall 2006 Game Design 21 Multiple Server Many machines coordinate service – Ultima Online, Everquest, AOL Used for large virtual worlds Everquest – One server per game-geographic region – Freeze on handoff affects game play Nov 16, Fall 2006 Game Design 22 What Data to Send? Sending entire world state is usually too much Can send just user actions – Simulation engine does the same thing at each client – Pseudo-random numbers from same seed Nov 16, Fall 2006 Game Design 23 Sending User Actions-Problems Any error in engine – Divergence in worlds – Small error can lead to big divergence X-Wing vs Tie Fighter – Created a resynchronize protocol – Causes jumps • Wrote smoothing algorithm for resynchs Sim City 2000 Network Edition – Send checksums for world state each turn Nov 16, Fall 2006 Game Design 24 Prediction Eg. Unreal Waiting for user inputs is too slow Client does prediction – Motion prediction Server Nov 16, Fall 2006 corrects things if client is wrong Game Design 25 Prediction: Dead Reckoning Eg. SIMNET (US Army Tank Simulator) Each vehicle simulates own tank Sends data every 5 seconds, updating – Position, Speed, Acceleration – Expected path – Prediction violation criteria Receiver simulates own tank – AND simulates local copy of other tanks Nov 16, Fall 2006 Game Design 26 Dead Recokoning Receiver gets latest 5-second update Updates own copy of other tanks Predicts other tanks – Using prediction data – Until new data arrives Each simulator also sends update – When own prediction violates own criteria Assumes Nov 16, Fall 2006 latencies < 500ms Game Design 27 Dead Reckoning Sim A A’s Predicted Path Predict B Sim B B’s Predicted Path Predict A Sim A A’s Predicted Path Predict B Transmit new prediction every 5 seconds Nov 16, Fall 2006 Game Design Sim B B’s Predicted Path Predict A B Exceeds prediction: predict again and transmit 28 Dead Reckoning: Requirements Data structures for other entities Model of entity behavior – Vehicle speed, acceleration range, turn radius – Responsiveness to commands Situation parameters – Following a road – Precomputed path (NPCs) Nov 16, Fall 2006 Game Design 29 Multiple Copies Maintain 2 Data sets Now – Accurate self – Predicted others – “Zero” latency for self Ground Truth – Accurate everybody – Large latency for almost everybody – 200-500ms ago Nov 16, Fall 2006 Game Design 30 Latency Issues When latencies get high – Prediction gets worse and worse Correcting prediction errors may cause visual jumps – Easy to notice! If jumps are large enough – Temporarily interpolate between wrong prediction and the new correction Nov 16, Fall 2006 Game Design 31 Prediction Interpolation Interpolated Response Real Predicted Nov 16, Fall 2006 Game Design 32 Token Ownership Some games may allow distributed ownership – Ballistic simulation – Shooter fires bullet – Intended target receives the simulation Sports - eg. Tennis – Player A hits ball – Player B gets simulation token – B simulates ball path from A’s racket Nov 16, Fall 2006 Game Design 33 Trust “Never trust the client” Data on the user’s hard drive is insecure – Diablo utility to modify character data – Wrote patch to prevent hacking • Throws out your stuff if there’s a time inconsistency – Daylight savings nuked my stuff! Nov 16, Fall 2006 Game Design 34 Trust Network communications are insecure NetTrek communications are encrypted NetTrek also requires “blessed” client – Servers have different policies on requiring a blessed client – Prevents robot players or assistants Nov 16, Fall 2006 Game Design 35 Trust -- Checksums First line of defense: – Checksum of all packets – Include header in checksum! – Stops casual tampering Hash function – Hard to compute source value from result – MD5 Nov 16, Fall 2006 Game Design 36 Checksums Not immune to: – Code disassembly – Packet replay Packet replay attack: – Capture a legal packet, and re-send it more frequently than allowed – Client can restrict send frequency – Server cannot reject high-frequency packets • Internet bunch-ups are source of OK bunch-ups Nov 16, Fall 2006 Game Design 37 Combating Replay Each new packet client sends is different – Add a pseudo-random number to each packet – Not just sequence number! – Client & Server match pseudo-random numbers Random numbers – Seeds must match! – Dropped packets: include sequence number! Nov 16, Fall 2006 Game Design 38 Combating Replay XOR each packet with a pseudo-random bit pattern – Make sure the bit patterns are in sync! – Based on previous synchronized pseudorandom numbers Add junk – Confuse length analysis Nov 16, Fall 2006 Game Design 39 Reverse Engineering Remove symbols Put encryption code in with rest of network stuff Compute magic numbers: – At runtime – In server Encrypt Nov 16, Fall 2006 from the start! Game Design 40 Lists Of Servers Denial of service: – Send a packet to server-server saying “I’m a server” – Fake the IP return address with a random IP# – Server-server adds “new server” to list – Server may run out of memory storing hundreds of thousands of fake servers Nov 16, Fall 2006 Game Design 41 List of Servers Require a dialog – Server-list server responds with • Password • Keepalive interval – Password must be given by attacker at the correct time – Works OK if client is not better connected! Nov 16, Fall 2006 Game Design 42 References CS4455 course at GA Tech by Chris Shaw http://www.cc.gatech.edu/classes/AY2005 /cs4455_fall/ Nov 16, Fall 2006 Game Design 43