throbber
CERTIFICATE OF MAILING BY "EXPRESS MAIL"
`
`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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket