UNITED STATES PATENT AND TRADEMARKOFFICE
`DOCUMENTCLASSIFICATION BARCODE SHEET
`
` ATA
`
`
`ooo
`
`CATEGORY:
`
`CLEARED
`
`
`
`ADDRESS
`CONTACT IF FOUND:
`
`

`

`Please type a sign(+) inside this box
`
`> is
`
`o
`
`
`
`
`
`
`meen
`
`2. [Total Pages_60Specification ] applicable, all necessary)
`
`{Total Pages
`
`]
`
`8.
`
`[1] AssignmentPapers (cover sheet & document(s)
`
`9. [ 37 CFR 3.73(b) Statement
`(when thereis an assignee)
`[[] English Translation Document(ifapplicable)
`
`10.
`
`(C] Powerof Attorney
`
`11.
`
`[Information Disclosure
`Statement (IDS)/PTO-1449
`
`[LJ Copies of IDS Citations
`
`PTO/SB/05 (2/98)
`\
`Approvedfor use through 09/30/2000. OMB 0651-0032
`Patent and Trademark Office: U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1995, no persons are required to respondto a collection of information unless it displays a valid OMB control number.
`
`Attorney Docket No.
`1719.0050002
`
`
`.
`~
`n
`
`S “I
`FirstInventor or
`UTILITY PATENT APPLICATION TRANSMITTAL
`Jeffrey J. ROTHSCHILD
`
`
`— uo
`Application Identifier
`
`
`
`<>
`c
`(Onlyfornew nonprovistonal applications under 37 CFR § 1.53(b))
`Title
`Server-Group Messaging Systemfor Interactive
`= un
`Applications
`
`-
`=
`wo
`Express Mail LabelNo]
`“e
`
`
`
`Assistant Commissioner for Patents
`
`
`
`oO
`APPLICATION ELEMENTS
`
`ADDRESS TO:
`Box Patent Application
`See MPEP chapter 600 concerning utility patent application contents
`Washington, DC 20231
`
`
`
`
`
`
`1. £]
`* Fee Transmittal Form (¢.g., PTO/SB/17)
`6. [1 Microfiche Computer Program (Appendix)
`(Submit an original, and a duplicateforfee processing)
`
`
`7. Nucleotide and/or Amino Acid Sequence Submission (if
`
`
`
`
`
`
`(preferred arrangementseiforth below)
`- Descriptivetitle of the Invention
`
`
`a. Ol Computer Readable Copy
`- Cross References to Related Applications
`
`
`~ Backgroundofthe Invention
`- Brief Summary ofthe Invention
`
`
`b. []_ Paper Copy (identical to computer copy)
`- BriefDescription ofthe Drawings (1ffiled)
`
`
`~ Detailed Description
`
`
`
`
`c. []Some ofthe Disclosure Statement verifying identity of above copies
`
`
`
`
`ACCOMPANYINGAPPLICATION PARTS
`
`
`
`
`Drawings (35 U.S.C. 113)—[Total Sheets 11
`3.
`
`
`
`Oath or Declaration
`
`
`a. [] Newly executed (original or copy)
`
`
`
`
`
`
`DELETION OF INVENTOR(S)
`[1] Preliminary Amendment
`12.
`Signed statement attached deleting inventor(s)
`13.
`Return Receipt Postcard (MPEP 503)
`namedin the prior application, see 37 CFR §§
`
`
`1.63(d)(2) and 1.33(b).
`(Should be specifically itemized)
`
`
`14, [] *Small Entity Statement(s)
`(7 Statementfiled in prior
`
`
` 3. Incorporation By Reference (useable ifBox th 1s checked)
`
`
`(PTO/SB/09-12)
`application, Status still proper
`and desired
`Theentire disclosure ofthe prior application, from which a copy of the oath
`
`or declaration is supplied under Box 4b,is considered as being part of the
`
`
`
`disclosure of the accompanying application and is hereby incorporated by
`15
`[] Certified Copy of Priority Document(s)
`reference therein.
`
`
`(ifforeign priority is claimed)
`
`
`16.
`Other:
`37 C.F.R. § 1.136(a)(3) Authorization
`
`O Other
`
`*NOTE FOR ITEMS J & 14. IN ORDER TO BE ENTITLED TO PAY SMALL ENTITY FEES, A
`
`
`SMALL ENTITY STATEMENTIS REQUIRED(37 C.F.R § 1 27), EXCEPTIF ONE FILED IN A
`PRIOR APPLICATION IS RELIED UPON(37 C FR. $3 28)
`
`
` 17.
`If aCONTINUING APPLICATION,check appropriate box, and supply the requisue information below and in a preliminary amendment
`
`
`
`
`& Continuation
`QO Divisional
`OContinuation-in-Part (CIP)
`
`Prior application information: Examiner Zarni Maung
`Group/Art Unit: 2758
`
`]
`
`b. [1] Copy from a prior application (37 CFR 1.63(d)) (or
`continuation/divisional with Box 17 completed)
`[Note Box 5 below]
`
`i.
`
`Ol
`
`4.[]
`
`
`
`
`
`
`
`
`
`ofprior application No: 08/896,797
`
`
`18. CORRESPONDENCE ADDRESS
`
`:
`(] Customer Number
`or Bar Code Label i (InsertCustomerNo.orAttachbarcodelabelhere)!
`
`or Correspondence
`address below
`
`NAME
`
`ADDRESS
`
`
`
`STERNE, KESSLER, GOLDSTEIN & FOX P.L.L.C.
`
`Suite 600, 1100 New York Avenue, N.W.
`
`
`
`
`
`TELEPHONE|(@02)371-3600 (202) 371-2540
`
`
`
`
`
`
`
`
`
`
`signature|gallUUeaeFeyG7
`
`
`
`Burden Hour Statement:
`this form is estimatedfo take 0.2 hours to complete. Time will vary depending uponthe needsof the individual case. Any comments on the amount ofumeyou are required to
`complete this form should be sentto the Chief Information Officer, Patent and Trademark Office, Washington, DC 20231. DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS. SEND
`TO: Assistant Commissioner for Patents, Washington, DC 20231.
`
`
`
`SKGFRev 6/3/98 mac
`
`0050002.sb05
`
`
`
`
`
`

`

`Cc.
`
`STERNE, KESSLER, GOLDSTEIN & FOX P.L.L.
`ATTORNEYS AT LAW
`1100 NEW YORK AVENUE, N.W, SUITE GOO
`WASHINGTON, D C. 20005-3934
`{202) 371-2600
`FACSIMILE (202) 371-2540, (202) 371-6566
`EDWARD W YEE
`ALBERT L FERRO*
`Donato R BANOWIT*
`PeTER A JACKMAN
`MoLLY A MCCALL
`TERESA U MEDLER
`JEFFREY S WEAVER
`KRISTIN K VIDOVICH
`ANDREW S ROBERTS*
`KENDRICK P PATTERSOR*
`
`Eric K STEFFE
`MICHAEL Q LEE
`STEVEN R LUDWIG
`JOHN M COVERT*
`LINDA E ALCORN
`Raz &. FLESHNER
`ROBERT C MILLONIG
`MICHAEL V MESSINGER
`JuoitH U KIM
`TimotHy J SHEA, JR
`
`DonaALD R MCPHAIL
`PaTRICK E GARRETT
`STEPHEN G WHITESIDE
`Jerrrey T HELVEY*
`Heipi L KRAUS
`JEFFREY R KURIN
`RAYMOND MILLIEN
`Patrick D O'BRIEN
`LAWRENCE B BUGAISKY
`Ccrystar D SAYLES*
`
`DONALD J FEATHERSTONE**
`KAREN R MARKOWICZ**
`GRANT E Reep**
`SUZANNE E Ziska**
`BRIAN J Det BuoNo**
`VINCENT L CAPUANO**
`ANDREA J KAMAGE**
`Nancy J DEGEN**
`
`RoBERT H BENSON*
`OF COUNSEL
`
`*BAR OTHER THAN DC
`**REGISTERED PATENT AGENTS
`
`'t
`
`Sa,
`
`ROBERT GREENE STERNE
`EowarbD J KESSLER
`=
`tL Fox
`JORGE A GOLDSTEIN
`Ga
`il
`
`ieae gy DAviD ORNWELL
`
`ea ee ROBERT W ESMOND
`1 Saar 10 TRACY-GENE G DURKIN
`~~ =e MICHELE A CIMBALA
`BND SSE GG MicHAcL B Ray
`*
`RosSERT E SOKOHL
`eee
`WO Saas
`ao =———
`
`|ia
`
`M
`—— OD|
`
`September 28, 1999
`
`WRITER’S DIRECT NUMBER:
`(202) 789-5506
`INTERNET ADDRESS:
`RMILLIEN@SKGF.COM
`
`Box Patent Application
`
`Assistant Commissioner for Patents
`
`SPEymyee
`Outso
`
`PTO Utility Patent Application Transmittal Form (PTO/SB/05);
`
`US. Utility Patent Application entitled:
`
`Server-Group Messaging System for Interactive Applications
`
`and naming as inventors:
`
`Jeffrey J. ROTHSCHILD, Daniel J. SAMUEL and
`Mare P. KWIATKOWSKI
`
`Gyan
`
`| 4
`
`Ki
`
`t$
`Reteltnne
`
`nena
`
`mab Satin
`
`the application consisting of:
`
`Sir: Washington, D.C. 20231
`
`Re:
`
`U.S. Continuation Utility Patent Application under 37 C.F.R. § 1.53(b)
`(Based on Appl. No. 08/896,797; Filed: July 18, 1997)
`Appl. No. To be assigned; Filed: September 28, 1999
`Server-Group Messaging System for Interactive Applications
`For:
`Inventors:
`Jeffrey J. ROTHSCHILD, Daniel J. SAMUEL and
`Mare P. KWIATKOWSKI
`1719.0050002
`
`Our Ref:
`
`The following documents are forwarded herewith for appropriate action by the U.S.
`Patent and Trademark Office:
`
`

`

`oo
`
`=
`
`”
`
`ST@RNE, KeEssLER, GOLDSTEIN & FOX P.L.L.C.
`
`Assistant Commissionerfor Patents
`September 28, 1999
`Page 2
`
`a.
`
`A specification containing:
`
`(i) 55 pages of description prior to the claims;
`(ii) 4 pagesof claims (16 claims);
`(iii)
`aone (1) pageabstract;
`
`
`
`b.
`
`Eleven (11) sheets of drawings: (Figures 1-11);
`
`USPTO Utility Patent Application Transmittal Form PTO/SB/05;
`
`37 C.F.R. § 1.136(a)(3) Authorization to Treat a Reply As Incorporating An
`Extension of Time (in duplicate); and
`
`Two(2) return postcards.
`
`3.
`
`4.
`
`5.
`
`It is respectfully requested that, of the two attached postcards, one be stamped with the
`filing date of these documents and returned to our courier, and the other, prepaid postcard, be
`stamped with the filing date and unofficial application numberand returned as soon as possible.
`
`This application claims priority to U.S. Application No. 08/896,797, filed July 18,
`1997, now allowed, whichis a continuation of U.S. Application No. 08/595,323,filed,
`February 1, 1996, now U.S. Patent No. 5,822,523.
`
`The U.S. Patent and Trademark Office is hereby authorized to charge any fee deficiency,
`or credit any overpayment, to our Deposit Account No. 19-0036. A duplicate copy ofthis letter
`is enclosed.
`
`This patent application is being submitted under 37 C.F.R. § 1.53(b) without
`Declaration and withoutfilingfee.
`
`Respectfully submitted,
`
`STERNE, KESSLER, GOLDSTEIN & FOX P.L.L.C.
`
`(lepnl Wl~
`
`0050002.pto
`
`RaymondMillien
`Attorney for Applicants
`Registration No. 43,806
`
`

`

`CERTIFICATE OF MAILING BY "EXPRESS MAIL"
`“Express Mail” Mailing Label No. TB812048578US.
`
`Date of Depost February1,1996. I hereby certify that
`this paper or fee is being depomted with the United States Postal
`Services "Express Mail Post Office to Addressec" service under
`37 CFR 1.10 on the date indicated above and is addressed to:
`Assistant Commissioner for Patents , Washington, D.C. 20231
`
`Binge2lenge
`
`
`
`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
`
`The present invention relates to computer network systems, and
`
`particularly to server group messaging systems and methods for reducing
`
`messagerate and latency.
`
`Backgroundof the Invention
`
`There are a wide rangeofinteractive applications implemented on
`
`computer systems today. All are characterized by dynamic response to the
`
`user. The user provides input to the computer and the application responds
`quickly. One popular example of interactive applications on personal
`
`10
`
`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 gamescontrol 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
`
`15
`
`soundis played.
`
`

`

`-2-
`
`As computers have become more powerful and common, it has become
`important to connect them together in networks. A network is comprised of
`nodesand links. The nodes are connected in such a waythat there exists a path
`from each nodeoverthe links and through the other nodes to each of the other
`
`nodesin the network. Each node may be connected to the network with one
`
`or morelinks. Nodesare further categorized into hosts, gateways androuters.
`Hosts are computer systems that are connected to the network by onelink.
`They communicate with the other nodes on the network by sending messages
`and receiving messages. Gateways are computer systems connected to the
`network by more than onelink. They not only communicate with the other
`nodes as do hosts, but they also forward messages on oneoftheir network
`links to other nodes ontheir other network links. This processing of
`forwarding messagesis called routing. In addition to sending and receiving
`messages and their routing functions, gateways may perform other functions 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 which it 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-networks together into whatis
`
`called an internet. Today the widely known example of a world wide internetis
`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
`
` 10
`
`15
`
`20
`
`25
`
`

`

`-3-
`
`shared, networked, interactive applications muns into the limitations ofthe
`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. A rate set byits
`internal time base, it would sample theinputs ofthe local user, receive
`messages from the network from the PCsofthe other players and send
`messages out to the PCsofthe other players. A typical rate will be ten time
`per second for a time period of 100ms. The messages sent between the PCs
`would contain information that was needed to keep the gameconsistent
`between all of the PCs. In a gamethat createdtheillusion ofa 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 ofPC gamesthat can be played between
`multiple players on Local Area Networks (LANs)or by twoplayers over dial-
`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 of the objects in the game along with special
`actions taken by a playerthat effect the other players in the game.
`The case of a two player game played over a modemis particularly simple.
`Ifthe message rate is 10 messages per second, each PC sends 10 messages per
`second to the other PC and receives 10 messages per second. The delay
`introduced by the modemsand phoneline is small and will not be noticed in
`
`most games. Unfortunately, the case oftwo 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
`
` 10
`
`15
`
`20
`
`25
`
`

`

`
`
`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
`
`messagesreceived per second. As can be seen the messagerate increases
`
`linearly with the numberofplayers in the game. The message rates and data
`tates supported by popular LANsare high enough to support a large number of
`players at reasonable message sizes. 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 networking technologies
`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 communications infrastructures.
`In the example ofthe 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 so thatall of the network protocols and routing
`behavior is well defined and understood. If the game uses TCP/IP to sendits
`
`messages between the PCsin the game, the PPP protocol over the dial-up
`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 messages are sent 10 times per
`
`second to each of the other PCs in the game and 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 numbersofparticipants. There are other problems
`beyondjust the bandwidth ofthe network connection. There is the loading on
`each PC caused by the high packet rates and thereis the latency introduced by
`
`the time neededto sendall of the outbound packets. Each packet sent or
`
`received by a PC will require some amount ofprocessing time. As the packet
`
`rate increases with the numberofplayers in the game, less andless of the
`processorwill be available for running the game softwareitself. Latency is
`important in an interactive application because it defines the responsiveness of
`the system. Whenaplayer provides a new input ontheir system, it is desirable
`15
`for that input to immediately affect the game onall of the other players
`
` 10
`
`systems. This is particularly important in any game where the game outcome
`
`depends onplayers shooting at targets that are moved by the actions of the
`
`other players. Latencyin this case will be the time from whena playeracts to
`
`movea target to the time that the target has moved on the screens of the other
`players in the game. A major portionofthis 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 ofthe seven will receive the
`message quickly, it will not be until 50 ms have passed thatthe last player of
`
`the seven will have received the message.
`
`20
`
`25
`
`

`

`*-
`
`
`
`
`-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 modelfor layers of network
`protocols, IP correspondsto a layer 3 or Network layer protocol. It provides
`services for transmission and routing ofpackets between two nodes in an
`internet. The addressing modelprovides a 32 bit address for all nodes in the
`network andall packets carry source and destination addresses. IP also defines
`the routing ofpackets between networklinks in an inter-network. Gateways
`and routers maintain tables that are used to lookup routing information based
`on the destination addresses ofthe packets they receive. The routing
`informationtells the gateway/router whether the destination ofthe packetis
`directly reachable on a local network link connected to the gateway/routeror if
`not, the address ofanother gateway/router on oneofthe local network links to
`which the packet should be forwarded. On top 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 ofthe
`datagrams. TCPis a connection oriented service to applications that does
`providereliable delivery of a data stream. It handles division ofthe 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 UDPare unicast protocols:
`packets, streams or datagramsare transmitted from a source to a single
`destination.
`As an example, consider Figures 1 and 2. Figure 1 shows a conventional
`unicast network with hosts 1, 2, 3 and 4 and network links 11, 12, 13, 14,
`
`10
`
`15
`
`20
`
`25
`
`

`

`
`
`
`
`
`
`-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 components in an actual IP packet, but for sake of
`this example, only these items will be considered. Figure 2 shows the example
`packets that 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
`ofthe other three hosts, therefore the payloadin 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. Ina similar 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
`26, 27, 28 and 29, 30, 31 respectively to the other three hosts. All ofthese
`packets are carried by the unicast networkindividually 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.
`As can beseen, 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 ofthe
`hosts that wish to communicate with one another will need to send packets to
`each othereight to ten times per second. With four hosts communicating with
`
`10
`
`15
`
`20
`
`25
`
`

`

`
`
`
`~-8-
`
`one anotheras in this example, each host will send three messages and receive
`three messageseight to ten times per second. As the numberofhostsin the
`application that need to communicate with one another grows, the message
`rate will reach a rate that cannot be supported by conventional dial-uplines.
`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.
`
`10
`
`15
`
`20
`
`25
`
`Work has been doneto attempt to extend the IP protocol to support
`multicasting. See RFC-1112 “Host Extensions for IP Multicasting.”. This
`document describes a set of extensions 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 groupcontains zero or more IP hosts and the IP multicasting protocol
`transmits a multicast datagram to all members ofthe group to whichitis
`addressed. Hosts may join and leave groups dynamically and the routing of
`multicast datagrams is supported by multicast routers and gateways. It is
`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 duplicationis distributed throughoutthe networkto all ofthe
`multicast routers. For distributed multicast messaging to work in a wide area
`network, all ofthe routers handling datagrams for multicast hosts must support
`the routing ofmulticast datagrams. Such multicast routers must be aware of
`the multicast group membership ofall ofthe hosts locally connected to the
`
`

`

`-9-
`
` 10
`
`router in order to deliver multicast datagrams to local hosts. Multicast routers
`mustalso be able to forward multicast packets to routers on their local network
`links. Multicast routers must also decide to whichif any local routers they
`must forward multicast datagrams. When a multicast datagram is received, by
`a multicast router, its group address is compared toalist for each local
`multicast router ofgroup addresses. Whenthere is a match, the datagram is
`then forwarded to that local multicast router. Therefore, the multicast routers
`in the network must maintain an accurate andup to 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 furtherattribute of distributed multicast
`messaging is that the routers must propagate the group membership
`information for a particular group throughoutthe network to all ofthe other
`routers that will be forwarding traffic 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 mentioned later in descriptions ofrelated
`prior art. Despite their differences, all ofthese 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 numberofundesirable
`side effects. The process of propagation of group membership information to
`all of the relevant routers is not instantaneous. In a large complex networkit
`can even take quite a period oftime depending on the numberofrouters that
`must receive that updated group membership information and how many
`
`15
`
`20
`
`25
`
`

`

`-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 ofthe algorithm that is used. RFC-1112 mentions this problem and
`someofthe side effects that must be handled by an implementation ofa
`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,itis easily possible in a
`distributed networkfor there to be duplication ofgroup address assignment.
`This will result in incorrect datagram delivery, where hosts will receive
`unwanted datagramsfrom the duplicate group. This requires a method at each
`host to filter out the unwanted datagrams. Anotherset ofproblems result from
`the time delay from whena groupis created, destroyed orits membership
`changed to whenall ofthe routers needed to route the datagrams to the
`memberhosts have been informed ofthese changes. Imagine the case where
`Host N joins an existing group by sending a join messagetoits 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 sendsa datagram to the group, but the local router ofHost M has not
`yet been informed of the changein group membership and as a result the
`datagram is not forwarded to oneofthe particular network links connected to
`the local router ofHost 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
`datagrams addressedto the group from Host M until the local router ofM has
`its group membership information updated. Other related problemscan also
`25
`occur. Whenahost leaves a group, messages addressed to the group will
`continue for sometimeto berouted to that host up to the local router of that
`
` 10
`
`15
`
`20
`
`

`

`
`
`
`ka
`
`-ll-
`
`host. The local router will know at least not to route the datagram onto the
`
`local network of that host. This can still result in a great deal of unnecessary
`
`datagramsbeingcarried in a large network when there are many active
`message groups with rapidly changing memberships.
`Finally, distributed multicast messaging does notsufficiently reduce the
`message rate betweenthe hosts. With distributed multicast messaging, each
`host need only send one message addressed to the message group in order to
`send a messageto all of other hosts in the group. This is an improvement over
`conventional unicast messaging where one message would need to besent to
`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 ofa group often hosts sending messages
`seven times per-second to the group. With conventional unicast messaging,
`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 message to the group
`containing all 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 exampleofdistributed 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 network links 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 each ofthe hosts joined the message groupso that each ofthe multicast
`
`5
`
`10
`
`15
`
`20
`
`25
`
`

`

`-12-
`
`routers is aware of the message group and has the proper routing information.
`
`A network protocol 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. As the packets are handled by the multicast
`routers they are replicated as necessary in order to deliver them toall the
`members of the group. Let us consider how a packetssent 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 networklinks 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 networklink 50 and router 40 sends its onto links 48 and 49. The packet
`
`is then received at multicast routers 44, 42 and 41. Router 41 sends the packet
`
`over networklink 51 whereit is received by host 36. Router 42 sends the
`packet over network link 52 to host 37 and router 44 sends the packet over
`link 53 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 number of messages that
`need to be sent by the hosts in 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 network infrastructure of multicast routers. It also has
`no support for message aggregation and cannot do so since message delivery is
`
` 10
`
`20
`
`25
`
`

`

`
`
`
`
`-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 when placed in context ofthe
`
`design goals for distributed multicast messaging. Distributed multicast
`
`messaging was not designed for interactive applications where groups are
`
`rapidly created, changed and destroyed. Instead it was optimized for
`
`applications where the groupsare created, changed and destroyed over
`
`relatively long time spans perhaps measured in many minutes or even hours.
`
`An example would be a video conference whereall the participants agreed to
`
`10
`
`connect the conference at a particular time for a conference that mightlast for
`
`an hour. Another would be the transmission of an audio or video program
`
`from one host to many receiving 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
`
`15
`
`this application it would be acceptable for there to be a significant time lag
`
`from joining or leaving before the connection was established or broken.
`
`While IP and multicast extensions to [P are based on the routing of packets,
`
`another form of wide area networking technology called Asynchronous
`
`20
`
`Transfer Mode (ATM) is based on switching fixed sized cells through switches.
`Unlike [P which supports both datagram and connectionoriented services,
`ATM is fundamentally connection oriented. An ATM networkconsists 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
`
`25
`
`the network. Two forms of communication can be supported by an ATM
`
`network. Bi-d