The Peer-to-Peer Model

The Elements of Network Communication

Network communication is often characterized by five attributes: topology, bandwidth, latency, reliability, and protocol. I'll consider each one briefly.

Topology

Topology is the interconnection shape of machines linked over a network. Popular shapes are the ring, star, and all-to-all, illustrated by Figure 29-1.

Figure 29-1. Some network topologies

Choosing the best topology for an application is a complicated matter depending on many network characteristics, such as bandwidth, latency, and the particular communication patterns inherent in the system.

The star topology, present in client/server applications, is the most popular; the all-to-all topology appears (in modified forms) in peer-to-peer systems.

Bandwidth

Bandwidth is the rate at which the network can deliver data from a sender to the destination host. Modems can typically deliver anywhere from 14,400 to 56,000 bits per second (14.4 to 56 Kbps), Ethernet can attain 10 to 100 Mbps (million bits per second), with newer technologies offering 1 Gbps (gigabits per second). Fiber-optic cable exhibits speeds of up to 10 Gbps.

Dial-up usage is declining rapidly in the United States, but 49.31% of users still connect with modems, according to July 2004 figures from Nielsen/NetRatings (http://www.nielsen-netratings.com/). Specifically, 40.49% use 56-Kbps modems, 6.22% have 28/33.3 Kbps, and 2.60% are stuck with 14.4-Kbps modems. Also, 66.2% of people used modems the previous year, in March 2003.

An estimated 150 million broadband lines were in place worldwide by the end of 2004, including all kinds of mass-market broadband services, such as DSL, cable modems, and fiber optic. Usage is growing even faster than the uptake of mobile phones (http://www.internetworldstats.com/articles/art030.htm).

Research by Bolt Lab from January 2005 indicates that 70% of the Gen-Y group (15-22-year-olds) in the United States use broadband to access the Internet (http://biz.yahoo.com/prnews/050114/nyf005_1.html). Of those teens, 50% use a cable modem, 44% use DSL, and 6% a T1/T3 line.

Nevertheless, 56 Kbps is probably a realistic bandwidth estimate for most users, at least for 2005.

Bandwidth restricts the number of players in a game: too many participants will swamp the network with data traffic. However, the nature of the extra load depends on topology. For example, a message sent around a ring will have to travel through many links, occupying bandwidth for a longer amount of time. A message traveling through a star topology only requires two links to go from any sender to any receiver, and a message in an all-to-all topology goes directly to its destination.

A knowledge of the available bandwidth allows us to estimate upper limits for the amount of data that can be transferred per each frame rendered in a game and to suggest a likely maximum for the number of users.

A 56-Kbps modem means 7,000 bytes can be transferred per second. I'll assume that the game updates at 30 frames per second (FPS), and each player sends and receives data from all the other players during each frame update. The total amount of data that can be transferred to each frame is 7,000/30 233 bytes per frame. This is about 117 bytes for output, 117 bytes for input.

If there are n players, then each player will send (n - 1) output messages and receive (n - 1) input messages at each frame update. As n increases, the 117 bytes limit will be quickly reached.

I can estimate the maximum number of users by starting with a lower bound for the amount of data that must be transferred during each frame update. For instance, if the lower bound is 20 bytes and there's 117 bytes available for output, then a maximum of about six messages can be sent out (117/20), which means seven players in the game.

These kinds of ballpark figures explain why games programmers try hard to avoid broadcast models linked to frame rate and why transmitted data is kept as small as possible. Some techniques for reducing data transmission in multiplayer games are discussed in Chapter 32, when I develop a networked version of the Tour3D application.

A network protocol solution is to move from a broadcast model to multicasting. Multicasting is a form of subscription-based message distribution: a player sends a single message to a multicast group, where it's automatically distributed to all the other players currently subscribed to that group. The saving is in the number of messages sent out: one instead of n - 1.

A similar saving can be made in a star topology: a player sends a single message to the server, which then sends copies to the other players. This is a software solution, dependent on the server's implementation, which allows for further server-side optimizations of the communication protocols.

Latency

Latency is the amount of time required to transfer data from one place to another (typically from one player's machine to another). In a Massively Multiplayer Online Role-Playing Game (MMORPG), latency exhibits itself as the delays when two players are interacting (e.g., shooting at each other); the goal is to reduce latency as much as possible.

Most latency can be accounted for by the modems involved in the network: typically each one adds 30-40 ms to the transfer time. A client/server system may involve four modems between the sending of a message and its reception by another user: the sender's modem, the modem inbound to the server, the modem outbound from the server, and the receiver's modem result in a total latency of perhaps 160 ms.

Another major contributor, especially over the Internet, are routers, which may easily add hundreds of milliseconds. This is due to their caching of data before forwarding and delays while a router decides where to send a message. Routers may drop data when overloaded, which can introduce penalties in the 400-500 ms range for protocols (like TCP), which detect lost data and resend it.

Another issue is the speed of light because games would certainly benefit if it were faster. A message sent from the East Coast to the West Coast of the United States will take about 20 ms to get there. In general, about 8 ms are added to the travel time for each time zone that a message passes through.

Designers often incorporate tolerances of 250 ms into the communication models used in games. A key observation is that most games don't require complete synchronization between all the players all the time. Synchronization is usually important only for small groups of players (e.g., those in close proximity inside the game world) and then only at certain moments.

This relaxing of the synchronization requirement opens the door to various approaches based on temporarily "guessing" information about other players. For instance, the game running on the user's machine estimates other players' current positions and velocities and corrects them when the correct data arrive over the network.

Another implementation strategy is to decouple general game play from the networking side of the application. A separate thread (or process) waits for incoming data, so the rest of the application can continue unaffected.

Latency is essentially a WAN or Internet issue; applications running over a LAN rarely need to consider latency, which may total less than 10 ms.

Reliability

Increased network reliability may increase latency time. For example, the possibility that a message could be lost while traveling over the network led to the development of the TCP protocol, which deals with data loss by resending. The disadvantage is that the actual arrival time of a message can increase, affecting latency.

A desire to measure reliability has led to more complex checking of data based on cyclic redundancy checks (CRCs), which add further overheads.

An alternative approach is to live with a certain degree of unreliability, reducing overheads as a consequence. Many forms of Internet-based multimedia, such as streaming audio and video, take this view because losing small amounts of data only means a momentary loss in sound or picture quality. The rapid transmission of the data is a more valued attribute.

Protocol

A protocol is a notation for specifying the communication patterns between the components of a networked application. Different protocols support different capabilities, with the choice of protocol depending on many factors, such as the type of data being transmitted, the number of destinations, and the required reliability. Most gaming application uses multiple protocols: one for data, another for control, and perhaps others specialized for particular types of data such as audio or video.

Different protocols exist for different levels of communication, which are defined in the ISO OSI model (see Figure 29-2).

A protocol suite is a collection of related protocols for different layers of the OSI model. The most popular is TCP/IP, originally developed by DARPA in the early 1980s. Its wide popularity stems from being implemented on everything from PCs to supercomputers, not being vendor-specific, and its suitability for all kinds of networks, from LANs up to the Internet.

Figure 29-2. The ISO OSI model

This isn't a book about data communications, so I'll only consider TCP/IP within a simplified version of the OSI model, limited to four layers. Communication between two networked systems can be viewed (see Figure 29-3).

Figure 29-3. Communication between two systems

Figure 29-3 shows that application-level protocols, which include FTP, HTTP (the web protocol), and SMTP (the email protocol), are implemented on top of lower-level protocols (TCP or UDP).

At a particular layer, the data appears to cross directly to the equivalent layer on the other system. In fact, data is passed down through the layers, across the physical network, and back up through the layers of the other system. As each layer is descended, the user's data is wrapped inside more header (and footer) information. The headers (and footers) are removed as the data rises through the layers on the other system.

The data link layer corresponds to the OSI physical and data layers. Frames are delivered between two directly connected machines.

The network layer delivers datagrams between any two machines on the Internet, which may be separated by intervening gateways/routers. Each datagram is routed independently, which means that two datagrams sent from the same source may travel along different paths and may arrive in a different order from the way they were sent. Since a gateway/router has limited memory, it may discard datagrams if too many arrive at once. A node or link in the network may fail, losing packets. For these reasons, the IP protocol makes no guarantees that a datagram will arrive at its destination.

A datagram has size constraints, which often force a single piece of user data to be divided into multiple datagrams. The data arriving at the receiver may, therefore, have missing pieces and parts in the wrong order.

A datagram is sent to an IP address, which represents a machine's address as a 32-bit integer. Programs usually employ IP addresses in dotted-decimal form (e.g., 172.30.0.5) or as a dotted-name (e.g., fivedots.coe.psu.ac.th). translation of dotted-name form to an IP address is carried out using a combination of local machine configuration information and network naming services such as the Domain Name System (DNS).

The IP protocol is currently in transition from Version 4 to Version 6 (IPv6), which supports 128-bit addresses, a simpler header, multicasting, authentication, and security elements. Java supports IPv4 and IPv6 through its InetAddress class.

The transport layer delivers datagrams between transport endpoints (machine ports) for any two machines on the Internet. An application's location is specified by the IP address of its host, and the number of the port where it is "listening." A port number is a 16-bit integer.

The TCP/IP transport layer protocols are UDP and TCP.

UDP is a connectionless transport service: a user message is split into datagrams and each datagram is sent along an available path to its destination. There is no (expensive) long-term, dedicated link created between the two systems. UDP inherits the drawbacks of the IP protocol: datagrams may arrive in any order, and a datagram has no guarantee of arriving. UDP is often compared to the postal service.

TCP is a connection-oriented transport service. From the user's point of view, a long-term, dedicated link is set up between the sender and receiver, and two-way stream-based communication then becomes possible. For this reason, TCP is often compared to the telephone service.

However, the dedicated link is implemented on top of IP, so packets of information are still being sent with the chance of reordering and loss. Consequently, TCP employs sophisticated internal error-checking to ensure that its component TCP datagrams arrive in the order they were sent and that none will be lost. This overhead may be too severe for gaming applications that value low latency.

UDP and TCP use a socket data structure to represent an endpoint in the communication. For UDP, the socket is something like a mailbox; for TCP socket it is more like a telephone.

Java supports both TCP and UDP. A programmer uses the Socket class for creating a sender's TCP socket and the ServerSocket class for the recipient. Java offers the DatagramSocket for both sides of UDP communication and a DatagramPacket class for creating UDP packets.