UNITED STATES DEPARTMENT OF COMMERCE
`United States Patent and Trademark Office
`
`June 29, 2015
`
`THIS IS TO CERTIFY THAT ANNEXED IS A TRUE COPY FROM THE
`RECORDS OF THIS OFFICE OF THE FILE WRAPPER AND CONTENTS
`OF:
`
`APPLICATION NUMBER: 091629,577
`FILING DATE: July 31, 2000
`PATENT NUMBER: 6,732,147
`ISSUE DATE: May 04, 2004
`
`By Authority of the
`Under Secretary of Commerce for Intellectual Property
`~ !ld Director of the United States Patent and Trademark Office
`
`M. TARVER
`Certifying Officer
`PART (3) OF (6) PART(S)
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 649 of 1657
`
`

`
`United States Patent [19J
`Chen et al.
`
`I IIIII
`
`~11111111111111111~ 111111111 ~1111111111111111111111
`US005946316A
`5,946,316
`(11] Patent Number:
`[45] Date of Patent:
`Aug. 31, 1999
`
`[54] DYNAMIC DISTRIBUTED MUil'ICAST
`ROUTING PROI'OCOL
`
`(75]
`
`Inventors: XJaoqhmg Chen, Eatontown; Vijay
`Pochampalli Kumal", Freehold, both of
`NJ.; Caullgi Srlnivasa Ragbavendra,
`Pullman, Wash.; Ramanathan
`Venkateswaran, Holmdel, NJ.
`
`[73] Assignee: Lucent Teclmologles, Inc., Murray
`Hill, NJ.
`
`(21] Appl. No.: 08/785,625
`
`[22] Filed:
`
`Jan. 17, 1997
`
`6
`Int. Cl.
`······················-···························· H04L 12/56
`[51]
`(52] U.S. Cl ............................ 370/408; 370/256; 370/432
`(58] Field of Sean:b ..................................... 370/256, 390,
`370/400, 408, 432, 395; 340/825.02
`
`[56]
`
`References Cited
`
`U.S. PA:I'ENT DOCUMENTS
`
`5,351,146 9/1994 Chan et al .••••••..•••.....•••..•.•••.•• 370/408
`5,541,927 7/1996 Kristol et aL ....••....••.•••.•........• 370/408
`5,671,222 9/1997 Chen et al .............................. 370/388
`
`Primary Examiner-Alpus H. Hsu
`Assistant Exam.iner--Ricky Q. Ngo
`Arromey, Agent, or Finn-Frederick B. Luludis; Daniel J.
`Piotrowski
`
`[57]
`
`ABSTRACT
`
`The distribution of multicast information in a communica(cid:173)
`tions network formed from a plurality of communications
`nodes, e.g., ATM switches, is enhanced by providing an
`efficient mechanism for routing a request to join a multicast
`connection to an originator of the multicast and an efficient
`mechanism for then connecting the requester to the multicast
`connection.
`
`5,291,477
`
`3/1994 Liew ....................................... 370/408
`
`12 Claims, 11 Drawing Sheets
`
`401
`
`REQUEST
`(IDx. CNTRx, RCx)
`
`IF CNTRx > CNTRo, SET
`CNlRa = CNlRx + 1
`
`IF NEXT NODE
`AVAILABLE IN on.
`YES
`
`YES
`
`SAVE INFORMAnON X IN
`MESSAGE TABL£ FORWARD
`REQUEST ON All UNKS
`OF lHE SPT, EXCEPT lHE
`INCOMING UNK.
`
`SAVE INFORMAnON IN
`MESSAGE TABlE.
`FORWARD THE JOIN-REQ
`TO THE NEXT NODE.
`
`SEND A
`RETRY BACK
`
`1 SEND A
`REPLY BACK
`MTH COST = -1.
`
`IDLE STATE
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 650 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31,1999
`
`Sheet 1 of 11
`
`5,946,316
`
`FIG. 1
`
`100
`
`105
`
`----~ MUlllMEDIA
`OOT
`
`150
`
`110
`
`175
`
`WORK
`STA110N
`
`170
`
`115
`
`130
`
`135
`
`FIG. 2
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 651 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31, 1999
`
`Sheet 2 of 11
`
`5,946,316
`
`FIG. 3
`
`302
`
`JOIN-ACK
`
`FIG. 4
`
`401
`
`REQUEST
`(lOx. CN1Rx, RCx)
`
`IF CN1Rx > CNlRo, SET
`CN1Ra = CN1Rx + 1
`
`IF NEXT NOD£
`AVAILABLE IN DTL
`YES
`
`YES
`
`SAVE INFORMATION X IN
`MESSAGE TABlE FORWARD
`REQUEST ON All UNKS
`OF lHE SPT, EXCEPT IDE
`INCOMING UNK.
`
`SAVEINFORUATION IN
`MESSAGE: TABLE
`FORWARD lHE JOIN-REO
`TO lHE NEXT NODE.
`
`t SEND A
`REPLY BACK
`WllH COST = -1.
`
`IDLE STAlE
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 652 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31,1999
`
`Sheet 3 of 11
`
`5,946,316
`
`FIG. 5A
`
`MESSAGE TABLE HAS AN
`ENlRY {IDy,CNlRy,RCy)
`WAIT STAlE
`
`REQUEST
`(IDx, CNlRx,RCx)
`
`501
`
`IF CN1Rx > CN1Ro, SET
`CN1Ra = CNlRx + 1
`
`r-------.....;.;YE~S IF MAG(y) < MAG{x)
`NO
`SEND A RElRY
`BACK TOWARDS X
`
`SEND A REPLY BACK
`'MlH COST = - 1.
`
`SAVE INFORMAnON X IN
`MESSAGE TABLE. FORWARD
`REQUEST ON ALL UNKS
`Of THE SPT, EXCEPT
`THE INCOMING UNK.
`
`RETRY STAlE
`
`WAIT STAlE
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 653 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31, 1999
`
`Sheet 4 ofll
`
`5,946,316
`
`FIG. 5B
`MESSAGE TABLE HAS AN ENTRY.
`(IOy,CNTRy,RCy}
`WAIT STATE
`
`REPLY
`{llly,CNTRy,RCy)
`
`502
`
`IF SENDER ACTIVE, SAVE
`(COST+UNK_COST.)
`
`WAIT STATE
`
`DETERMINE NEAREST NOOE
`BASED ON BEST COST.
`
`NO
`
`FORWARD REPLY FROM
`NEAREST NODE TOWARDS
`lOy.. AFTER UPDATING COST.
`
`IF NO ACTIVE NODE
`YES
`
`aiAR Y ENTRY IN
`MESSAGE TABLE
`
`IF SAVE CNTR > 0
`NO
`
`IDLE STATE
`
`RETRY STATE
`
`COMPUTE PA 1H
`TO NEAREST NODE
`
`SENIJ JOIN-REQ
`TOWARDS NEAREST
`NODE.
`
`lENT. STATE
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 654 of 1657
`
`

`
`FIG. 6
`
`MESSAGE TABLE HAS AN ENTRY
`(IDy,CNTRy,RCy)
`r WAIT STAlE"
`
`RETRY
`(IDy,CNTRy,RCy)
`601
`
`IF lOy == NODE A
`NO
`
`YES
`
`JOIN-REQ
`
`61
`
`CLEAR Y ENTRY IN MESSAGE
`TABLE. FORWARD lHE RETRY
`TOWARDS Y
`
`CLEAR Y ENTRY IN MESSAGE
`TABLE. SA 'It CNTR = CNTRy
`RESCHEDULE REQUEST nMER
`
`YES
`
`IDLE STAlE
`
`RETRY STAlE
`
`SEND A RETRY BACK
`
`~_WAIT STAlE)
`
`··-
`
`IF NEXT NODE
`AVAILABLE IN Dll
`YES
`CLEAR Y ENTRY IN MESSAGE
`TABLE. FORWARD THE RETRY
`TOWARDS Y
`
`SA'It INFORMATION IN
`MESSAGE TABLE. FORWARD
`THE JOIN-REQ TO THE
`NEXT NODE.
`
`lENT. STAlE_.~
`
`d • C/). •
`f
`
`~ q;
`~
`" .....
`~
`'..:I
`
`ga
`ii
`s:.
`::::
`
`tn
`
`Ul
`
`'I> lf:
`~
`~
`~
`~
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 655 of 1657
`
`

`
`FIG. 7
`
`'
`
`IF CNTRx > CNTRa,
`SET CNTRa = CNTRx + 1
`
`SEND A RETRY BACK I
`
`(TENT. STATE)
`
`MESSAGE TABLE HAS AN ENTRY
`(lOy, CNTRy, RCy)
`(TENT. STATE)
`
`REQUEST
`(IDyx,CNTRx,RCx)
`
`7~1
`
`RETRY
`(IDy, CNTRy, RCy}
`
`'-"' 702
`
`JOIN-ACK
`(lOy, CNTRy, RCv}
`
`-,
`
`703
`
`CLEAR Y ENTRY IN MESSAGE
`TABLE. FORWARD THE JOIN-ACK
`TOWARDS Y
`
`s
`
`IF lOy == NODE A )HQ..
`
`(ACTIVE STATE
`
`ClEAR Y ENTRY IN MESSAGE
`TABLE. SAVE CNTR = CNTRy
`RESCHEDULE REQUEST TIMER
`
`CLEAR Y ENTRY IN MESSAGE
`TABLE. FORWARD THE RETRY
`TOWARDS Y
`
`(RETRY STATE)
`
`(
`
`IF SAVE CNTR > 0 ;NO
`YES
`
`(RETRY STATE)
`
`IDLE STATE
`
`(:l
`•
`00
`•
`
`~ i
`t
`
`~
`"' ~
`~
`
`loQ
`
`ga a
`<::1'1 = ~ =
`
`U1
`
`..... 'f.
`
`~
`~
`1-1-
`~
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 656 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31, 1999
`
`Sheet 7 of 11
`
`5,946,316
`
`FIG. 8
`
`{10
`
`801
`
`JOIN-REQ
`
`802
`
`803
`
`IF CNTRx > CNTRa,
`SET CNlRa = CNlRx t 1
`
`SEND A JOIN-ACK BACK
`
`IF ~OUP MEMBER
`NO
`
`ACTIVE STAlE
`
`IS LEAF OF
`MULTICAST TREE
`_ ___,_ __ YES
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 657 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31, 1999
`
`Sheet 8 of 11
`
`5,946,316
`
`FIG. 9
`
`902
`
`JOIN-REO
`
`RETRY STAlE
`REQUEST
`(lOx, CNTRx, RCx)
`901--
`
`IF CNTRx > CNTRa,
`SET CNTRa = CNTRx + 1
`
`IF MSG(y) < MSG(x)
`NO
`
`...,.....;.;N~O
`
`IF NEXT NODE
`AVAILABL£ IN Dll
`YES
`
`SAVE INFORMAnON IN
`MESSAGE TABLE. FOWARD
`THE JOIN..,.REQ TO lHE
`NEXT NODE.
`
`lENT. STAlE
`
`SEND A REPLY
`BACK WITH
`COST= -1.
`
`SAVE INFORUAnON X IN
`MESSAGE TABLE. FOWARD
`REWEST ON All UNKS
`OF lHE SPT, EXCEPT
`lHE INCOMING UNK
`
`<lEAR Y ENTRY IN
`MESSAGE TABLE.
`
`WAIT STATE
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 658 of 1657
`
`

`
`U.S. Patent
`FIG. 10
`
`Aug. 31,1999
`
`Sheet 9 of 11
`
`5,946,316
`
`FIG. 11
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 659 of 1657
`
`

`
`U.S. Patent
`Aug. 31, 1999
`FIG. 12
`
`Sheet 10 of 11
`
`5,946,316
`
`' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '
`
`FIG. 13
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 660 of 1657
`
`

`
`U.S. Patent
`
`Aug. 31, 1999
`
`Sheet 11 of 11
`
`5,946,316
`
`FIG.
`
`14
`
`FIG.
`
`15
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 661 of 1657
`
`

`
`5,946,316
`
`1
`DYNAMIC DISTRIBUTED MULTICAST
`ROUTING PROTOCOL
`
`F1ELD OF TilE INVENTION
`
`The invention relates to data networks and more particu(cid:173)
`larly relates to a multicast protocol for locating, joining and
`leaving a multicast gronp that is receiving particular infor(cid:173)
`mation.
`
`BACKGROUND OF TilE INVENTION
`
`2
`find message identifying the multicast group to the selected
`nodes in accordance with the routing tree. In response to
`receipt of a message identifying the nearest node connected
`to the multicast group, the requesting node then simply
`5 sends a join message to the identified node to join the
`multicast group.
`These and other aspects of the claimed invention are
`disclosed in the ensuring detailed description, accompany(cid:173)
`ing drawings and claims.
`
`10
`
`BRIEF DESCRIPTION OF TilE DRAWINGS
`
`Presently, a user associated with a multimedia terminal,
`e.g., a conventional workstation or PC, may enter a request
`via the terminal to participate in a particular event, e.g., a
`lecture, audio/video conference, televised speech, etc., that
`is being provided by a node, e.g., a packet switch, in a digital
`network. The event is typically associated with some type of
`identifier, i.e., group identifier (e.g., 800 number or confer(cid:173)
`ence bridging number in conventional telephone networks)
`so that a user who wants to participate in the event may 20
`identify the event in a request that tbe user submits to his/her
`terminal. The user's terminal then forwards the request to an
`associated serving node within the digital network. A group
`identifier may represent a collection of users who are
`interested in particular information associated with the 25
`evenl (Note that group identifier is different from an iden(cid:173)
`tifier that is used to identify a particular user.) JYpically, the
`membership associated with a group identifier may be
`dynamic such that a member may join and leave the group
`at any time. Also, there is no restriction on the physical 30
`location of multicast group members who may or may not be
`at the same physical location. The network maintains infor(cid:173)
`mation relating to tbe group and typically does this by
`conslructing a network directory which is used to track the
`connectivity of active members. That is, a serving node 35
`submits the group identifier to the network directory. The
`directory, in tnrn, retnms the address of the nearest node
`which it can join. The serving node then sends a request to
`join the multicast group to the identified node. A node that
`joins or leaves a multicast group must notify the directory so 40
`that it can update the membership information.
`Unfortunately, membership may change so frequently that
`management of sucb a directory may become costly and
`inefficient.
`The network may also maintain such membership by 45
`constructing a multicast server in the network. Data that is
`sent by a user is then first delivered to the server, which, in
`tnrns, delivers the information to all other members in the
`multicast group. Although this approach appears to be
`simple to implement it, nevertheless, may lead to a single so
`point of failure in the event that the server fails. Moreover,
`this approach does not use the network resources efficiently,
`since user data bas to be sent to the server.
`
`In the drawing:
`F1G. 1 shows a communications network in which the
`1s principles of the invention may be practiced;
`F1G. 2 illustrates a routing tree rooted at a particular one
`of the nodes of FIG. 1;
`F1G. 3 shows a state diagram illustrating the operation of
`a node in accordance with the principles of the invention;
`F1GS. 4-9 are respective expanded versions of the opera(cid:173)
`tions states shown in F1G. 3, and
`FIGS. 10-15 illustrate the operation of the principles of
`the invention in an illustrative hierarchical network.
`
`DETAILED DESCRIPTION
`
`Our inventive protocol supports what we call a
`"Participant-Initiated Join", in which a node initiates a
`request to join a multicast group and, in doing so, determines
`the network path that is to be used to join the multicast. The
`protocol bas two phases. We call the first phase the "Find"
`phase, since it is the requesting node that determines the
`identity of the nodes that are already on the multicast tree.
`We call tbe second phase the "Join" phase, since the request(cid:173)
`ing node attempts to join the nearest node that is already on
`the multicast tree.ln the Find phase, a node that wants to join
`the multicast group originates a REQUEST message and
`sends it to all of its neighbors on the shortest path tree rooted
`at the requesting node. A neighbor that receives the message
`then forwards it downstream to its neighbors along the links
`of the shortest path tree rooted at tbe originating node. This
`process continues until the REQUEST message reaches
`either a node that is already on the multicast tree or a leaf
`node of the shortest path tree rooted at the originating node
`(i.e., the node that has the sought-after multicast
`information.) Each node that is already on the multicast tree
`replies to the request, with the cost parameter set to D. The
`leaf nodes that are not on the multicast tree reply to the
`request with the cost parameter set to -1. On receiving all of
`the replies to the message, a node determines the nearest
`node and forwards the REPLY message from the nearest
`node upstream towards the originator of the REQUEST.
`Before doing so, tbe node updates the cost function to reflect
`the cost from this node to the nearest node. The originator
`ss receives all tbe replies and determines the nearest node. This
`ends the Find phase. ln the Join phase, the requesting node
`determines the path to the nearest node and sends a JOIN(cid:173)
`REO message. The determined path is inserted in the
`message so that an intermediate node does not have to make
`the same determination. The nearest node (having the
`sought-after information) replies with aJOIN-ACK.message
`and all the nodes in the patb become a branch of the
`multicast tree.
`An illustrative example of the foregoing is shown in F1G.
`1, in which sought-after multicast information is assumed to
`be a multimedia event 150, e.g., a televised lectore. Multi(cid:173)
`media signals characterizing the multimedia event are sup-
`
`SUMMARY OF TilE INVENTION
`The foregoing is addressed and the relevant art is
`advanced by providing an efficient and sealeable mechanism
`for a data network to maintain multicast group information
`in a dislnbuted fashion in which any node in the network
`may automatically locate, join and leave a multicast group. 60
`The mechanism is distributed so that a single node bas to
`maintain complete information about the other participants
`of the multicast group. ln particular, in accordance with an
`illustrative embodiment of the invention, a network node
`enters a request to join a multicast group, by constructing at 65
`least one routing tree formed from selected paths to each of
`a number of other nodes identified in the tree and sending a
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 662 of 1657
`
`

`
`5,946,316
`
`4
`3
`plied to node lOS, which may operate as a conventional
`nodes 110 and 120, which are in the path of the multicast,
`start receiving the multicast information then they note in
`video server for the purpose of supplying the video signal in
`their respective intemal memories that they also have such
`the form of digital signals to a user who has entered a request
`to receive a copy of such signals via network 100 formed
`information.
`from data nodes lOS, 110, 115, 120, 125, 130 and 135. In an s Assume at this point that a user associated with node 130
`also wishes to receive the multicast and enters a request for
`illustrative embodiment of the invention, each of the nodes
`may be, for example, a conventional AJ'M switch. Assume
`that information. Similarly, node 130 constructs a least-cost
`path tree and launches its own find message in accordance
`that a user associated with workstation 170 in a conventional
`manner enters a request via a keyboard (not shown) to view
`with the tree (not shown). When the message reaches node
`the event on monitor 175, in which the request includes an 10 120, it responds with a reply message to node 130 indicating
`identifier associated with the multimedia event. The request,
`that it has the information. As discussed above, node 130
`however, does not contain the identity (e.g., address) of the
`aecumulates the reply messages and then detemlines from
`source of the multicast information. Workstation 170, in
`those message which of the nodes having the sought-after
`information is closest to node 130. In the present illustrative
`response to receipt of the request, converts the request into
`a form expected by associated network node 125, also 15 example, the closest node fur the desired purpose would be
`shown as tbe E node. As an aspect of the invention, network
`node 120. Accordingly, then node 130 may join the multicast
`100 does not include a directory identifying the information
`by sending a Join message to node 120, rather than to node
`that is respectively supplied by the netwolk 100 nodes.
`lOS. Thus, when node 120 receives a packet of such infor-
`mation from node no, it sends a copy to node 125 and a
`Accordingly, to locate the node that has the multicast
`information, node 125 will poll each of the other network 20 copy to node 130.
`If at this point, the user at workstation 170 enters a request
`100 nodes. Before doing so, however, node 125 constructs
`to terminate receipt of the multicast, then node 125 forms a
`a tree formed from selected paths to each of the other node&,
`in which the selection is based on predetemlined parameter,
`"Leave" message and sends the message to node 120 in
`for example, cost, number of hops, etc. In an illustrative
`accordance with the constructed path tree rooted at node
`embodiment of the invention, cost is characterized by a 25 125. When node 120 receives the message, it stores the
`weight value. Such weight values are shown in parentheses
`message in local memory and temlinates the supplying of
`the multicast information to node 125 but will continue
`in FIG. 1 and are used, as mentioned, to identify a least cost
`path/route. For example, if node 120 (D) needs to send a
`supplying that information as it is received to node 130. If
`message to node 105 (A), then node 120 will likely send the
`prior to the end of the televised event, node 130 launches a
`message via· node ·110 (B) since the sum of the weights 30 "Leave" message, then node 120, in response to that mea-
`associated with the links in that path is less than the sum of
`sage and in response to having no other receiver fur the
`the weights associated with the links in the via node 115 (C)
`multicast, sends a message to node 110 to temlinate the
`supplying of the multicast to node 120. Similarly, node no
`path, i.e., (5)+(1)<(6)+(3).
`sends a similar message to node 105 if it has no other
`Thus, in accordance with known techniques, node 125, in
`the ":lind"phase, constructs a path tree and uses that tree to 35 receiver for the multicast information.
`A situation could arise in which a node receives, at about
`control the routing of a message to locate a node that has the
`requested multicast information, i.e., the televised event
`the same time (concurrently), Find messages from a plural-
`150. An example of such a tree is illustrated in FIG. 2. Node
`ity of node&, e.g., two nodes. To handle this situation and
`120 thus sends a "Find" message to node 135 (G) and to
`preserve the correctness of the distributed protocol, a node,
`node 120(D) in accord with the tree. The "Find" message 40 e.g., node 125, appends a time stamp to a Find message. In
`this way, if a node, e.g., node D, receives concurrently
`include&, inter alia, the address of the message originator,
`identifier associated with the songht-after information, a
`"Find" message from nodes 125 and 130, then it processes
`request for the identity of the node that has the sought-after
`the Find message bearing the earliest time stamp and retorns
`information. The message may also include information
`a Reply message to the node, e.g., node 130, that launched
`characterizing the constructed path tree. Accordingly, then, 45 the Find message bearing the latest time stamp. Then, when
`the least cost multicast path is established from node 105 to
`upon receipt of the message, node 135 retorns a Reply
`message with the cost parameter set to -1. Although node
`node 120, then node 130 launches a .Find message after
`120 does not have the sought-after information, it does not
`waiting a random (or a predetermined) period of time and
`discard the message since the path tree indicates that the
`then proceeds as discussed above.
`message should be individually routed to nodes no, 115 and so
`In an illustrative embodiment of the invention, the prin-
`130, as shown in FIG. 2. Similarly, ~hen tbe message
`ciples of the invention are embodied in a state machine
`reaches node no, the node does not discard the message
`which is implemented in each network node for each mul-
`(even though it does not have the sought-after information),
`ticast group.An illustrative example of such a state machine
`but forwards it to node lOS (A). Since, it is assumed that
`is illustrated in FIG. 3 and is CODlpOSCd of five major states,
`node lOS has the sought after information, then it responds 55 namely IDLE 301, WAIT 302, TENTATIVE 303, ACilVE
`to the received message by returning to node 125 a reply
`304 and RETRY 305. Before discnssing FIG. 3, it would be
`best to review the different message(s) that may be sent by
`message containing the identity (address) of node 105 and
`with the cost parameter set to 0.
`a node attempting to join a multicast and the message(s) that
`are sent by the other nodes in the network in response to a
`Upon receipt of the latter message, node 125 enters the
`"Join" phase, as discussed above. In this phase, node 125 60 request to join a multicast session. Briefly, a node that wants
`constructs the shortest path to node lOS and sends a Join
`to join a multicast tree/session sends a REQUEST message,
`in the manner discussed above. The header of the request
`message containing the node 125 address with a request to
`message contains, inter alia, the identity of the multicast
`join the multicast of the identified event.
`Referring to FIG. 2, it is seen that such path would be via
`information, sender lD, and time-stamp. (It may also contain
`nodes no and 120, rather than via nodes ns and 120. Node 65 a retry count.) A request message can only be originated by
`lOS returns a Join-ACK and then starts supplying the
`a node that is in the IDLE state. A node sends a REPLY
`message in response to receipt of a REQUEST message. A
`televised event to node 125 via the determined path. When
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 663 of 1657
`
`

`
`5,946,316
`
`10
`
`5
`REPLY message includes the header information of the
`REQUEST message and an associated cost parameter which
`identifies the cost of the shortest path from the current node
`to the nearest node that is already on the tree. The cost is
`updated as the REPLY moves from one node to another 5
`node. The cost is set to -1 if there is no ACTIVE node on
`that particular path. A node sends a REI'RY message if it
`determines that another request is already being processed.
`as discussed above. The request with the earlier time-stamp
`is allowed to continue while a RE1RY message is sent to the
`originator of the request having the later time stamp, as
`mentioned above. A node sends a JOIN-REQ message when
`it wants to join the multicast session/tree. The path to the
`nearest node is encoded within this message. An ACTIVE
`node sends a JOIN-ACK message in response to receiving
`a JOIN-REQ message. The receipt of this message indicates 15
`that a node is on the multicast tree. A node sends a LEAVE
`to an ACTIVE neighbor node when it wants to leave the
`multicast session/tree.
`Thming then to FIG. 3, Briefly, in the IDLE state a node
`has no information pertaining to the multicast informatinn 20
`(or tree). A node enters the WAIT state after it has sent/
`forwarded a REQUEST message and is waiting for a
`response. A node enters the TENTATIVE state after it has
`sent/forwarded a JOIN-REQ message towards the nearest
`node that is already on the multicast tree. In this state, the 25
`node is waiting fur a JOIN-ACK message. A node enters the
`ACTIVE state when it joins a multieast session (i.e., it is on
`the multicast tree. A node reaches this state when it receives
`a JOIN-ACK message from a node that is already on the
`tree. A node in the ACTIVE state may also maintain the 30
`tree-based informatinn regarding all the links that are inci(cid:173)
`dent on it and belong to the tree. However, the node does not
`maintain any state information about new requests to join
`the tree. A node reaches the RE'IRY state when it is the
`originator of a REQUFST to join a multieast tree and 35
`receives a RE'IRY message via one of the links of the tree.
`In this state, a node does not have to maintain any state
`information relating to other requests. Also, the node waits
`for a random period of time before re-sending the original
`REQUFST. It may also track the number of REQUEST 40
`messages that it sends.
`An expanded version of the IDLE state is shown in FIG.
`4. As mentioned above a node initiates a REQUEST mes-
`sage when it is in the IDLE state.
`A node in this state only can initiate a REQUEST mes(cid:173)
`sage. A REQUEST message is identified using the
`tuple<SenderiD,time-stamp,retry-count>, where senderiD is
`the ID of the node that is the originator of the message,
`time-stamp is the value of a counter at the senderiD and 50
`retry-count is the number of attempts the node has made to
`join the tree. The retry-count is initially 0. The initial
`REQUEST message is forwarded on all the links via the
`shortest-path tree rooted at the originating node. The node
`then enters the WAIT state. The following actions are taken
`when the node receives either a REQUEST message (action
`path 401) or JOIN REQ message (action path 402). For
`example, assume that a REQUEST message is received from
`node B, and therefore contains the tuple<I.Dn,CNTRn,
`RCs"'· Then the receiving node takes the following actions: 60
`If the message is not on the shortest path, then send a
`REPLY with cost~l towards the originator. Else,
`update the time stamp (local counter).
`Save the state information of the message.
`Forward the REQUEST message. Change State= WAIT. 65
`If no available link, send REPLY with cost~-1. State=
`IDLE.
`
`45
`
`55
`
`6
`If a JOIN-REQ message is received from node B, then the
`receiving node proceeds as follows:
`Forward JOIN-REQ message to next node. Change State=
`TEND\TIVE.
`If current node is the final destination noted in the
`message, then return a RETRY message to the originator.
`(Note that this conditinn may arise if the node changes its
`state from ACTIVE to IDLE during the time between the
`sending of the REQUEST message andJOIN-REQ message
`to node B.)
`An expanded version of the WAIT state is shown in FIGS.
`SA, 5B and 6. For FIGS. SA and B, assume that a node
`received a REQUEST message containing the tuple <IDA,
`CNTRA,RCA>from node A.
`If the node also receives a REQUEST message from node
`B, <IDB,CNTRB,RC_a>. Then the node takes the followiDg
`actions (path 501 ):
`Update the local time stamp counter.
`If the message had not been received via the shortest path,
`then send a REPLY to B, setting cost to -1.
`If the message is received via the shortest path and A
`precedes B in time, then send a REI'RY message to B.
`If the message is received via the shortest path and B
`precedes A in time, then send a RE'IRY message to A
`Clear state information pertaining to A. Save informa(cid:173)
`tion pertaining to B and forward REQUEST message.
`If the node receives a REPLY message via one of its links,
`then the node takes the following actions (path 502):
`Ignore the REPLY message if it does not contain state
`informatinn.
`If not the last reply, then store the cost information and
`wait fur other reply messages.
`If tbe last REPLY, then determine best message by mini(cid:173)
`mizing the (cost field of message+link: cost). Then
`forward the best message towards the originator of the
`REQUFST after updating cost.
`Change state•IDLE.
`If originator of REQUEST message, then compute the
`shortest path to the nearest node. Send JOIN-REQ
`message towards that node via the shortest path.
`Change stat~ T'EN':IiU1VE.
`If the node receives a REI'RY message via one of its links,
`then the node takes the following actions (path 601, FIG. 6):
`Ignore the RE'IRY message if it does not contain state
`information.
`Clear the state information and forward the REI'RY
`message towards the originator of REQUEST.
`ChaDge state•IDLE.
`If originator of REQUFST, then change stat~RE'IRY.
`Increment retry count.
`Wait for a random period of time, then resend the
`REQUEST message with the updated retry count value.
`(Note: The same counter value (CNTR) will be used to
`ensure fairness.)
`If the node receives a JOIN-REQ message from a node,
`e.g., node B, then the node proceeds as follows (path 602,
`FIG. 6):
`Change state=TENTJUIVE.
`If next node information is available, then forward the
`JOIN-REQ message to the next node and send a
`RE'IRY message to node A.
`If no next node, then send a RE'IRY message towards the
`originator of the JOIN-REQ message.
`An expanded version of the TEND\TIVE state of FIG. 3,
`is shown in FIG. 7, in which a node enters the TENTJUIVE
`
`IPR2016-00726 - ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1002, Vol. 3, p. 664 of 1657
`
`

`
`5,946,316
`
`7
`8
`State after it receives a JOIN-REQ message originated by
`Change state-WAIT. (A is now waiting for B)
`another node, e.g., node A. If at that time, the node receives
`If. on the other hand, a JOIN-REQ message is received
`from node B, then the node takes the following actions (path
`a REQUEST message from node B containing the
`902):
`tuple<ID8 ,CNTR8 , RC8 >, then the receiving node proceeds
`Change state~TENTA:IlVE. Forward JOIN-REQ mes(cid:173)
`in the following manner (path 701):
`sage to next node on the path.
`If a REQUEST message is not received via the shortest
`Save A's information and wait. (A cannot resend
`path, then return a REPLY with cost ~-1 to the origi(cid:173)
`REQUEST message until B has joined multicast
`nator. Else,
`group).
`Update local counter value.
`If Retry timer has expired, then increment Retry count and
`Send RETRY message towards the originator of the 10
`send REQUEST message containing the following
`message.
`tuple; <IDA,CNTRA,RCA>·
`If, on the other hand, the node receives a RETRY
`The old value of CNTRA is used to ensure fairness.
`Message, then the node takes the following actions (path
`The foregoing may be readily implemented in a netwmk
`702):
`15 formed from a plurality of so-called Peer groups, in which
`If RETRY matchesJOIN-REQ, forward RETRY message
`a peer group is a group of network nodes forming a smaller
`back towards node A.
`network. In particular, a large network formed from a large
`number of nodes may be logically restructured to improve
`Change slate=IDLE.
`Ignore if RETRY message does not match JOIN-REQ.
`the efficiency of the number. Such restructuring entails
`If the node otherwise receives a JOIN-ACK Message, 20 forming nodes into groups each operating as a smaller
`network, in which connection management functions are
`then the node takes the following actions (path 703):
`logically extended to each level of the netwolk hierarchy.
`Change State-ACTIVE.
`The state information is maintained at each physical node. In
`Forward Join-Ack to node A.
`aear all state information.
`addition, each group is represented as a logical node at a
`Update multicast tree information to include the link over 25 higher level of the network hierarchy by a peer group leader
`(POL). The POL maintains separate slate information for
`which the JOIN-REQ was received.
`An expanded version of the ACTIVE slate of FIG. 3, is
`that logical node at that hierarchical leveL The logical nodes
`shown in FIG. 8, in which a node is already on the multicast
`perform the same state transitions as the physical nodes at
`the lowest level of the netwolk hierarchy. In that sense, our
`tree. In that case, the node only responds to new requests and 30 inventive protocol may be applied to such a netwmk with the
`join requests. Other messages may be ignored.
`following modifications (extensions).
`If a node in the active slate receives a REQUEST message
`Find Phas