`
`Services "Express
`37 CFR 1.10 om the date indicated above and is addressed to:
`Assistant Commissioner for Patents , Washington, D.C. 20231
`
`
`
`SenmaA.Mlemact
`
`PATENT
`Attorney Docket No. 16326-701
`
`SERVER-GROUP MESSAGING SYSTEM
`FOR INTERACTIVE APPLICATIONS
`
`Inventors: Daniel Joseph Samuel
`Marc Peter Kwiatkowski
`Jeffrey Jackiel Rothschild
`
`FIELD OF THE INVENTION
`
`Thepresentinvention relates to computer network systems, and
`particularly to server group messaging systems and methods for reducing
`message rate andlatency.
`
`Backgroundofthe Invention
`There are a wide rangeofinteractive applications implemented on
`computer systems today. All are characterized by dynamic response to the
`user. The user providesinput to the computer and the application responds
`quickly. One popular exampleofinteractive applications on personal
`computers (PCs)are games. In this case, rapid response to the user may mean
`redrawing the screen with a new picture in between 30ms and 100ms.
`Interactive applications such as games control the speed of their interaction
`with the user through an internal time base. The application uses this time base
`to derive rates at which the user input is sampled, the screen is redrawn and
`sound is played.
`
`
`=>a wenHal
`— iyaquethiedes
`haathBRat+HddHdl
`
`if
`
`i
`
`
`
`alt
`ye
`
`10
`
`15
`
`
`
`6
`
`a
`
`-2-
`
`As computers have become more powerful and common, it has become
`important to connect them together in networks. A network is comprised of
`nodes and links. The nodes are connected in such a waythat there exists a path
`from each nodeoverthe links and through the other nodesto each ofthe other
`
`nodesin the network. Each node may be connected to the network with one
`
`or more links. Nodesare further categorized into hosts, gateways and routers.
`Hosts are computer systems that are connected to the network by one link,
`They communicate with the other nodes on the network by sending messages
`and receiving messages. Gateways are computer systems connected to the
`network by morethan onelink. They not only communicate with the other
`
`nodesas do hosts, but they also forward messages on one oftheir network
`
`links to other nodes on their other network links. This processing of
`forwarding messagesis called routing. In addition to sending and receiving
`messagesandtheir routing functions, gateways may perform otherfunctions in
`a network. Routers are nodes that are connected to the network by more than
`one link and whosesole function is the forwarding of messages on one network
`
`link to the other network links to whichit is connected. A network consisting
`
`of many networklinks can be thought of as a network of sub-networks with
`
`gateways and/or routers connecting the sub-networkstogether into whatis
`
`10
`
`15
`
`ray
`
`atesfSeweya
`
`
`
`
`20
`
`called an internet. Today the widely known example of a world wideinternetis
`
`the so called “Internet” which in 1995 has over 10 million computers connected
`
`full time world-wide.
`
`With so many computers on a single world-wide network, it is desirable to
`
`create interactive networked applications that bring together many people in a
`shared, networked,interactive application. Unfortunately, creating such
`
`25
`
`
`
`9
`
`5
`
`-3-
`
`shared, networked,interactive applications runsinto the limitations of the
`existing network technology.
`|
`As an example, consider a game designed to be deployed over a network
`which is to be played by multiple players simultaneously. The game could be
`implemented in software on a PC connected to a network.Arateset byits
`internal time base, it would sample the inputs of the local user, receive
`messages from the network from the PCsof the other players and send
`- Messages out to the PCsofthe other players. A typical rate will be ten time2
`per second for a time period of 100ms. The messages sent between the PCs
`would contain information that was needed to keep the gameconsistent
`betweenall of the PCs. In a gamethat createdtheillusion of a spatial
`environment where each player could move, the packets could contain
`information about the new positions ofthe players as they moved. Today there
`are many commercial example%f PC gamesthat can be played between
`multiple players on Local Area Networks (LANs)or by twoplayers overdial-
`up phonelines using modems. The network messages sent by such games
`contain a wide variety of information specific to the game. This can include
`position and velocity information oftheobjects in the game along with special
`actions taken by a player that effect the other players in the game.
`The case of a two player game played over a modem is particularly simple.
`Ifthe message rate is 10 messages per second, each PC sends 10 messages per
`secondto the other PC and receives 10 messages per second. The delay
`introduced by the modemsand phoneline is small and will not be noticed in
`
` 10
`
`15
`
`20
`
`25
`
`most games. Unfortunately, the case of two playersis uninteresting for
`networkedinteractive applications. With the same game played with 8 players
`on a LAN,the messagerate increases. Each PC must send 7 messages, one to
`
`
`
`5
`
`NOttt
`hesage
`eath
`gettyityAdhaes
`
`:
`foeA
`wfDis
`theal
`
`sy
`
`a
`
`Se
`
`© k
`
`—
`
`4.
`
`each of the other 7 players every time period and will receive 7 messages from
`the other players in the same time period. If the messaging time periodis
`100ms, the total message rate will be 70 messages sent per second and 70
`messages received per second. As can be seen the messagerate increases
`linearly with the numberofplayers in the game. The messagerates and data
`rates supportedby popular LANsare high enough to support a large numberof
`players at reasonable messagesizes. Unfortunately, LANsare only deployed in
`commercial applications and cannot be considered for deploying a networked
`interactive application to consumerusers.
`
`10
`
`The wide area networks available today to consumerusersall must be
`
`accessed through dial-up phonelines using modems. While modem speeds
`
`have increased rapidly, they have now reached a bit rate of 28.8 Kbits/sec
`
`whichis close to the limit set by the signal-to-noise ratio of conventional phone
`
`lines. Further speed increases are possible with ISDN,but this technology is
`not ready for mass market use. Other new wide area networkingtechnologies
`are being discussed that would provide much higher bandwidth, but none are
`
`close to commercial operation. Therefore, in deploying a networked,
`
`interactive application to consumers, it is necessary to do so in a waythat
`
`operates with existing networking and communicationsinfrastructures.
`In the exampleofthe 8 player networked game, consider a wide area
`network implementation where the PCs of each ofthe players is connected to
`the network with a 28.8 Kbit/sec modem. Assumethat the network used in
`
`this example is the Internet sothat all of the network protocols and routing
`
`the De ses CP/IP72. ii its
`behavioris well defined and understood.
`AsosdeleCeebred Clo
`pro
`messages between the PCsin the game, the,
`phonelines can be advantageously used to compress the TCP/IP headers.
`
`15
`
`20
`
`25
`
`=
`
`
`
`
`
`-5-
`
`Even so, a typical message will be approximately 25 bytes in size. Sent
`through the modem, this is 250 bits. The messagesare sent 10 times per
`second to each of the other PCs in the gameand received 10 times per second
`from the other PCs. This is 35.0 Kbits/sec which exceeds the capabilities of the
`modem by 20%. Ifthe messages are reduced to 20 bytes, just 8 players can be
`supported, but this approach clearly cannot support networked interactive
`applications with large numbers of participants, There are other problems
`beyondjust the bandwidth ofthe network connection. Thereis the loading on
`each PC caused by the high packet rates and there is the latency introduced by
`
`10
`
`the time needed to sendall of the outbound packets. Each packetsent or
`
`received by a PC will require some amountof processing time. As the packet
`
`rate increases with the numberofplayers in the game,less and less of the
`
`processorwill be available for running the gamesoftwareitself. Latency is
`important in an interactive application because it defines the responsiveness of
`the system. Whena player provides a new input on their system, it is desirable
`
`15
`
`for that input to immediately affect the gameonall of the other players
`systems. This is particularly important in any.game where the game outcome
`depends on players shooting at targets that aretoved by the actions ofthe
`other players. Latency in this case will be the time from when a player acts to
`
`20
`
`movea target to the time that the target has moved on the screens of the other
`
`players in the game. A majorportion ofthis latency will come from the time
`
`needed to send the messagesto the other seven players in the game. In this
`
`example the time to send the messagesto the other 7 players will be
`
`approximately 50 ms. While thefirst player of the seven will receive the
`
`25
`
`message quickly, it will not be until 50 ms have passed that the last player of
`
`the seven will have received the message..
`
`
`
`S
`
`®
`
`-6-
`
`Internet Protocol Multicasting
`
`As mentioned before, the Internet is a widely known example of a wide
`
`area network. The Internet is based on a protocol appropriately called the
`
`Internet Protocol (IP). In the OSI reference model for layers of network
`
`5
`
`protocols, IP correspondsto a layer 3 or Networklayer protocol. It provides
`
`services for transmission and routing of packets between two nodesin an
`
`internet. The addressing model provides a 32 bit address for all nodes in the
`
`network andall packets carry source and destination addresses. IP also defines
`
`the routing of packets between networklinks in an inter-network. Gateways
`
`10
`
`and routers maintain tables that are used to lookup routing information based
`
`15
`
`20
`
`on the destination addresses of the packets they receive. The routing
`
`informationtells the gateway/router whether the destination of the packetis
`
`directly reachable on a local network link connected to the gateway/routerorif
`
`not, the address of another gateway/router on one ofthe local network links to
`which the packet should be forwarded. Ontop ofIP are the layer 4 transport
`
`protocols TCP and UDP. UDPprovides datagram delivery services to
`
`- applications that does-not guarantee reliable or in-order delivery of the
`
`datagrams. TCP is a connection oriented service to applications that does
`
`providereliable delivery of a data stream. It handles division of the stream into
`packets and ensuresreliable, in-order delivery. See the Internet Society RFCs:
`
`RFC-791 “Internet Protocol”, RFC-793 “Transmission Control Protocol” and
`
`RFC-1180 “A TCP/IP Tutorial”. IP, TCP and UDPareunicast protocols:
`
`packets, streams or datagramsare transmitted from a source to a single
`
`destination.
`
`25
`
`As an example, consider Figures 1 and 2. Figure 1 shows a conventional
`
`unicast network with hosts 1, 2, 3 and 4 and networklinks 11, 12, 13, 14,
`
`
`MyBPtaggersddl
`
`
`te
`
`PH
`
`
`
`@
`
`8 |
`
`-7-
`
`15,16,17, 18 and 19 and routers 5, 6, 7, 8, 9 and 10. In this example, each host
`wants to send a data payload to each ofthe other hosts. Host 1 has network
`_ address A, host 2 has network address C, host 3 has network address B and
`host 4 has network address D. Existing network protocols are typically based
`on packet formats that contain a source address, destination address and a
`payload. This is representative of commonly used wide area network protocols
`such as IP. There are other componentsin an actual IP packet, but for sake of
`this example, only these items will be considered. Figure 2 shows the example
`packetsthat are sent by the hosts to one another using a conventional unicast
`network protocol such as IP. Host 1 send packets 20, to host 3, packet 21 to
`host 2 and packet 22 to host 4. Host 1 wants to send the same data P1 to each
`
` 10
`
`ofthe otherthree hosts, therefore the payload in all three packets is the same.
`Packet 20 travels over network links 11, 12, 15 and 18 and through routers 5,
`6, and 8 to reach host 3. Inasimilar fashion host 3 sends packets 23 to host 1,
`packet24 to host 2 and packet 25 to host 4. Host 2 and host 4 send packets
`15
`26, 27, 28 and 29, 30, 31 respectively to the other three hosts. All ofthese
`packets are carried by the unicast network individually from the source host to
`the destination host. So in this example each host must send three packets and
`receive three packets in order for each host to send its payload to the other
`three hosts.
`|
`
`20
`
`As can be seen, each host must send a packet to every other hostthatit
`wishes to communicate with in an interactive application. Further, it receives a
`packet from every other host that wishes to communicate with it. In an
`interactive application, this will happen at a regular and high rate. All of the
`hosts that wish to communicate with one anotherwill need to send packets to
`each other eight to ten times per second. With four hosts communicating with
`
`25
`
`b
`
`
`
`-8-
`
`one anotheras in this example, each host will send three messages and receive
`three messageseightto ten times per second. As the numberofhosts in the
`application that need to communicate with one another grows, the message
`rate will reach a rate that cannot be supported by conventional dial-up lines.
`This makes unicast transport protocols unsuitable for delivering interactive
`applications for multiple participants since their use will result in the problem of
`high packet rates that grow with the numberofparticipants.
`
`Work has been doneto attempt to extend the IP protocol to support
`multicasting. See RFC-1112 “Host Extensions for IP Multicasting.”. This
`document describesa set ofextensions to the IP protocol that enable IP |
`multicasting. IP multicasting supports the transmission of a IP datagram to a
`host group by addressing the datagram to a single destination address.
`
`Multicast addresses are a subset ofthe IP address space andidentified by class
`
`D IP addresses- these are IP addresses with “1110” in the high order4 bits.
`The host group contains zero or more IP hosts and the IP multicasting protocol
`transmits a multicast datagram to all members ofthe group to whichit is
`addressed. Hosts may join and leave groups dynamically and the routing of
`
`multicast datagramsis supported by multicast routers and gateways. It is
`
` 10
`
`15
`
`20
`
`proper to describe this general approach to multicast messaging as “distributed
`
`multicast messaging”. It is a distributed technique because the job of message
`
`delivery and duplication is distributed throughout the networktoail of the
`
`multicast routers. For distributed multicast messaging to work in a wide area
`
`network, all of the routers handling datagramsfor multicast hosts must support
`
`25
`
`the routing of multicast datagrams. Such multicast routers must be aware of
`
`the multicast group membership ofall of the hosts locally connected to the
`
`
`
`-9.
`
`routerin order to deliver multicast datagramsto local hosts. Multicast routers
`mustalso be able to forward multicast packets to routers on their local network
`links. Multicast routers mustalso decide to which if any local routers they
`must forward multicast datagrams. When a multicast datagram is received, by
`a multicast router, its group address is comparedto a list for each local
`multicast router ofgroup addresses. Whenthereis a match, the datagram is
`then forwarded to that local multicast router. Therefore, the multicast routers
`in the network must maintain an accurate and upto datelist ofgroup addresses
`for which they are to forward datagrams to. Theselists are updated when
`hostsjoin or leave multicast groups. Hosts do this by sending messages using
`Internet Group ManagementProtocol (IGMP)to their immediately-
`neighboring multicast routers. A further attribute of distributed multicast
`messaging is that the routers must propagate the group membership
`information for a particular group throughout the network to all of the other
`routersthat will be forwardingtraffic for that group. RFC-1112 does not
`describe howthis is to be done. Manydifferent approaches have been defined
`for solving this problem that will be mentionedlater in descriptions of related
`prior art. Despite their differences, all of these approaches are methods for
`propagation of multicast routing information between the multicast routers and
`techniques for routing the multicast datagramsin an inter-network supporting
`distributed multicast messaging.
`
`The distributed multicast messaging approach has a numberof undesirable
`side effects. The process of propagation of group membership information to
`all of the relevant routers is not instantaneous.
`In a large complex network it
`can even take quite a period of time depending on the numberofrouters that
`mustreceive that updated group membership information and how many
`
`
`
`10
`
`15
`
`20
`
`25
`
`\O
`
`
`
`@
`
`©@
`
`-10-
`
`routers the information for the group membership update must past through.
`This process can easily take many seconds and even minutes depending on the
`specifics of the algorithm that is used. RFC-1112 mentions this problem and
`someofthe side effects that must be handled by an implementation of a
`practical routing algorithm for multicast messaging. One problem results when
`groups are dynamically created and destroyed. Since there is no central
`authority in the network for assigning group addresses,it is easily possible in a
`distributed network for there to be duplication of group address assignment.
`This will result in incorrect datagram delivery, where hosts will receive
`|
`unwanted datagrams from the duplicate group. This requires a method at each
`hostto filter out the unwanted datagrams. Another set of problems result from
`the time delay from when a group is created, destroyed or its membership
`changed to whenall of the routers needed to route the datagrams to the
`memberhosts have been informed of these changes. Imagine the case where
`Host N joins an existing group by sending a join messageto its local router.
`The group already contains Host M whichis a numberofrouter hops away
`from Host N in the network. Shortly after Host N has sentit join message,
`Host M sends a datagram to the group,but the local router ofHost M has not
`yet been informed of the change in group membership and as a result the
`datagram is not forwarded to oneofthe particular network links connected to
`the local router of Host M that is the only path in the network from that router
`that ultimately will reach Host N. Theresult is that Host N will receive no
`datagramsaddressedto the group from Host M until the local router of M has
`its group membership information updated. Other related problemscan also
`occur. Whena hostleaves a group, messages addressed to the groupwill
`continue for sometimeto be routed to that host upto the local router of that
`
`iNeatesACYRk
`auaapyytsElen
`iah
`
`sogure
`
`e
`
`cHal
`
`
`10
`
`15
`
`20
`
`25
`
`\
`
`
`
`Diasee
`
`:
`
`tt
`WnJ
`eye
`shan
`de
`
`aadTm)haHallTIAL
`
`weragee neatdl
`
`-ll-
`
`host. The local router will know at least not to route the datagram onto the
`
`local networkof that host. This can still result in a great deal of unnecessary
`
`datagrams being carried in a large network when there are many active
`
`message groupswith rapidly changing memberships.
`
`5
`
`Finally, distributed multicast messaging does not sufficiently reduce the
`message rate between the hosts. With distributed multicast messaging, each
`host need only send one message addressed to the message groupin order to
`
`send a messagetoall of other hosts in the group. This is an improvement over
`
`conventional unicast messagingwhere one message would need to be sent to
`
`10.
`
`each of the other hosts in a group. However, distributed multicast messaging
`
`does nothing to reduce the received messagerate at each of the hosts when
`
`multiple hosts in a group are sending messages to the group closely spaced in
`time. Let us return to the example of a group often hosts sending messages
`seven times per-second to the group. With conventional unicast messaging,
`
`15
`
`each host will need to send 9 messages to the other hosts, seven times per-
`
`second and will receive 9 messages, seven times per-second. With distributed
`
`multicast messaging, each host will need to send only one messageto the group
`
`containingall of the hosts seven times per-second, but will still receive 9
`messages, seven times per-second.It is desirable to further reduce the number
`
`of received messages.
`An example ofdistributed multicasting is shown in Figures 3 and 4. Figure
`3 shows a network with multicast routers 39, 40, 41, 42, 43 and 44 and hosts
`35, 36, 37, 38 and networklinks 45, 46, 47, 48, 49, 50, 51, 52 and 53. The
`four hosts have unicast network addresses A, B, C, D and are also all members
`of a message group with address E. In advance the message group was created
`and eachofthe hosts joined the message group so that each of the multicast
`
`20
`
`25
`
`VO
`
`
`
`6
`
`@
`
`-12-
`
`routers is aware of the message group and has the proper routing information.
`
`A networkprotocol such IP with multicast extensions is assumed to be used in
`this example. Host 35 sends packet 54 with source address A and destination
`multicast address E to the entire message group.
`In the same mannerhost 37
`sends packet 55 to the group, host 36 sends packet 56 to. the group and host 38
`sends packet 57 to the group. Asthe packets are handled by the multicast
`routers they are replicated as necessary in order to deliver them to all the
`members ofthe group. Let us consider how a packets sent by host 35 is
`ultimately delivered to the other hosts. Packet 54 is carried over network link
`45 to multicast router 39. The router determines from its routing tables that
`the multicast packet should be sent onto network links 46 and 47 and
`duplicates the packet and sends to both ofthese network links. The packet is
`received by multicast routers 40 and 43. Multicast router 43 sends the packet
`onto network link 50 and router 40 sendsits onto links 48 and 49. The packet
`is then received at multicast routers 44, 42 and 41. Router 41 sends the packet
`over network link 51 whereit is received by host 36. Router 42 sends the
`packet over networklink 52 to host 37 and router 44 sends the packet over
`link53 to host 38. A similar process is followed for each ofthe other packets
`sent by the hosts to the multicast group E. The final packets received by each
`host are shown in Figure 4.
`While distributed multicasting does reduce the numberof messagesthat
`need to besentby the hostsin a networked interactive application, it has no
`effect on the number of messagesthat they receive. It has the further
`disadvantages of poor behavior when group membershipis rapidly changing
`and requires a special networkinfrastructure of multicast routers. It also has
`no support for message aggregation and cannot do so since message delivery is
`
`ayHsaedlUARalathyit
`whfheoeBebas
`
`
`ad
`Ai
`
`10
`
`20
`
`25
`
`\S
`
`
`
`
`
`Faint
`
`#
`
`awe
`ae
`
`-13-
`
`distributed. Distributed multicasting also has no support for messagesthat
`
`define logical operations between message groups and unicast host addresses.
`
`All of these problems can be understood whenplaced in context of the
`
`design goals for distributed multicast messaging. Distributed multicast
`
`5
`
`messaging was not designed for interactive applications where groups are
`
`rapidly created, changed and destroyed. Instead it was optimized for
`
`applications where the groups are created, changed and destroyed over
`relatively long time spans perhaps measured in many minutesor even hours.
`An example would be a video conference whereall the participants agreed to
`
`connect the conferenceat a particular time for a conference that might last for
`an hour. Another would be the transmission ofan audio or video program
`from one host to manyreceiving hosts, perhaps measured in the thousands or
`
`even millions. The multicast group would exist for the duration of the
`
`audio/video program. Host members would join and leave dynamically, but in
`this application it would be acceptable forthere to be a significanttime lag
`from joining or leaving before the connection was established or broken.
`While IP and multicast extensions to IP are based on the routing of packets,
`another form of wide area networking technology called Asynchronous
`Transfer Mode (ATM) is based on switching fixed sized cells through switches.
`Unlike IP which supports both datagram and connection oriented services,
`ATM is fundamentally connection oriented. An ATM network consists of
`ATM switchesinterconnected by point-to-point links. The host systems are
`connected to the leaves of the network. Before any communication can occur
`
`between the hosts through the network, a virtual circuit must be setup across
`the network. Two forms of communication can be supported by an ATM
`network. Bi-directional point-to-point between two hosts and point-to-
`
`10
`
`15
`
`20
`
`25
`
`\
`
`
`
`-14-
`
`multipoint in one direction from one host to multiple hosts. ATM, however,
`does notdirectly support any form of multicasting. There are a number of
`proposals for layering multicasting on top of ATM. Oneapproachis called a
`multicast server, shown in Figure 8. Host systems 112, 113,114, 115 setup
`point-to-point connections 106, 107,108 and 109 to a multicast server 105.
`
`ATM cells are sent by the hosts to the multicast server via these links. The
`multicast server sets up a point-to-multipoint connection 111 to the hosts
`whichcollectively constitute a message group. Cells sent to the server which
`
`are addressed to the group are forwardedto the point-to-multipoint link 111.
`
`The ATM network 110 is responsible for the transport and switching for
`
`maintaining all of the connections between the hosts and the server. The cells
`
`carried by the point-to-multipoint connection are duplicated when necessary by
`the ATM switchesat the branching points in the network tree between and
`
`forwarded down the branching networklinks. Therefore, the networkis
`
`responsible for the replication of the cells and their payloads, not the server.
`This method has the same problems as distributed multicasting when used for
`
`an interactive application. Each hoststill receives individual cells from each of
`the otherhosts, so there is no aggregation ofthe payloads ofthe cells targeted
`at a single host. There is no support for addressing cells to hosts based on
`
` 10
`
`15
`
`20
`
`logical operations on the sets of members of host groups.
`
`Related Prior Art
`
`There are a numberofexisting patents and European patent applications
`that are related to the area of the invention. These can be organized into two
`
`separate categories: multicast routing/distribution and source to destination
`
`25
`
`multicast streams.
`
`
`
`
`
`
`
`-15-
`
`Multicast routing and distribution
`These patents are US 4,740,954 by Cottonet al, US 4,864,559 by Perlman,
`
`US 5,361,256 by Doeringeret al, US 5,079,767 by Perlman and US 5,309,433
`by Cidon et al. Collectively these patents cover various algorithms for the
`
`routing and distribution of the datagramsin distributed multicast networks.
`
`Nonedeal with the problems described previously for this class of multicast
`routing and message distribution such as poor behaviors when the message
`groups changerapidly.
`In all of these patents, messages are transmitted from a
`
`10
`
`host via a distributed network of routers to a plurality of destination hosts
`
`which are membersof a group. Since these patents deal only with variants of
`
`distributed multicasting they provide no means to reduce the received message
`
`rate, no method to aggregate messages and provide no methodin the messages
`
`to perform logical operation on message groups.
`
`15
`
`Source to destination multicast streams
`
`These are PCTs and a European patent application. They are EP 0 637 149
`
`A2 by Perlman et al, PCT/US94/11282 by Danneels et al and
`
`PCT/US94/11278 by Sivakumar et al. These three patent applications deal
`
`with the transmission of data streams from a source to a group ofdestinations.
`
`20
`
`In none ofthese patent applications, is a method described for transmitting data
`
`In all of these applications, the data ©
`between multiple members of a group.
`transmission is from a source to a plurality of designations. Since these patent
`applications deal only with point-to-multipoint messaging, they can provide no
`
`means to reduce the received message rate, no method to aggregate messages
`
`25
`
`and provide no methodin the messagesto perform logical operation on
`
`message groups.
`
`\K%
`
`
`
`$015
`
`aeaieHedee
`
`WwW
`
`Yeetas
`
`hy
`atcHMad
`g815,feaEach
`
`
`#
`
`-16-
`
`SUMMARYOF THE INVENTION
`The presentinventionrelates to facilitating efficient communications
`between multiple host computers over a conventional wide area
`communications network to implementan interactive application such as a
`computer game between multiple players.
`In such an application, the hosts will
`be dynamically sending to each other informationthat the other hosts need in
`order to keep the interactive application operating consistently on each ofthe
`hosts. The invention is comprised of a group messaging server connected to
`the network that maintains a set of message groups used by the hosts to
`communicate information between themselves. The invention further
`comprises a server-group messaging protocol used bythe hosts and the server.
`Theserver-group messaging protocolis layered on top of the Transport Level
`Protocol (TLP) of the network andis called the Upper Level Protocol (or
`ULP). In the OSI reference model the ULP can be thought of as a session
`layer protocol built on top ofa transport or applicationslayer protocol. The
`ULP protocol uses a server-group address spacethat is separate from the
`address space ofthe TLP. Hosts send messagesto addresses inthe ULP
`address space to a group messaging server using the underlying unicast
`transport protocol of the network. The ULP address space is segmented into
`unicast addresses, implicit group messaging addresses andlogical group
`messaging addresses. The implicit and logical group messaging addresses are
`collectively called group messaging addresses.
`Host systems must first establish connections to a group messaging server
`before sending messages to any ULP addresses. The process of establishing
`this connection is done by sending TLP messagesto the server. The server
`establishes the connectionby assigning a unicast ULP addressto the host and
`
`5
`
`10
`
`15
`
`20
`
`25
`
`\r
`
`
`
`Hohasfeyce
`oShal
`
`BA
`
`
`
`-17-
`
`returning this address in an acknowledgment messageto the host. Once
`
`connected, hosts can inquire about existing message groups, join existing
`message groups, create new message groups, leave message groupsthey have
`joined and send messages to ULP addresses known bythe server. Each
`
`message groupis assigned either an implicit or logical ULP address depending
`
`onits type.
`Figure 5 shows an example of a wide area network with a group messaging
`server ("GMS"). Hosts 58 has TLP address A and ULP address H,host 59 has
`
`TLP address C and ULP address J, host 60 has TLP address B and ULP
`
`10
`
`address I and host 61 has TLP address D and ULP address K. The networkis
`
`a conventional unicast network of networklinks 69, 70, 71, 72, 73, 74, 75, 76,
`
`and 77 and unicast routers 63, 64, 65, 66, 67, and 68. The group messaging
`server 62 receives messages from the hosts addressed to amessage group and
`send/the contentsofthe messages to the members ofthe message group.
`Figure 6 shows an example of datagrams sent from the hosts to a message
`groupthat they are membersof. As before, a TLP such as IP (where the
`message header contain the source and destination TLP addresses) is assumed
`to be used here. Host 58 sends message 80 which contains the TLP source
`
`address A ofthe host and the destination TLP address S for the GMS 62. The
`
`destination ULP address G is an implicit ULP address handled by the GMS and -
`the payload P1 contains both the data to be sent and the source ULP address H
`of the host.
`It is assumed that prior to sending their ULP messagesto the |
`GMS,that each host as already established a connection to the GMSand
`joined the message group G. Host 60 sends message 81 with payload P2
`containing data and source ULP address I. Hosts 59 sends message 82 with
`payload P3 containing data and source ULP address J. Host 61 sends message
`
`15
`
`20
`
`25
`
`\O
`
`
`
`8
`
`@
`
`-18-
`
`83 with payload P4 containing data and source ULP address K. The GMS
`receives all of these messages and sees that each messageis addressed to
`implicit message group G withmembers H,I, J, and K. The GMScan either
`process the message with or without aggregating their payloads. Figure 6
`shows the case wherethere is no aggregation and Figure 7 showsthe case with
`
`aggregation.
`Without aggregation, the GMSgenerates the outbound messages84,85,
`86, 87, 88, 89, 90, 91, 92, 93, 94, and 95 whichit sends to the hosts. The
`datagrams have TLP headers with the source and