United States Patent [19]
`United States Patent [191
`Francis et al.
`Francis et al.
`
`llllllllllllllIlllllllllllllllllllllllllllIllllllllllllllllllllllllllllllll
`US005331637A
`US005331637A
`5,331,637
`[ii] Patent Number:
`Patent Number:
`5,331,637
`[11]
`[45] Date of Patent:
`Jul. 19, 1994
`[45] Date of Patent:
`Jul. 19, 1994
`
`particular
`
`multicast
`
`Primary Examiner—Douglas W. Olms
`Primary Examiner-Douglas W. Olms
`Assistant Examiner—Min Jung
`Assistant Examiner-Min Jung
`Attorney, Agent, or Firm—Leonard C. Suchyta; James
`Attorney, Agent, or Firm-Leonard C. Suchyta; James
`W. Falk
`W. Falk
`[57]
`ABSTRACT
`ABSTRACT
`[57]
`A method for routing multicast packets
`in a network is
`A method for routing multicast packets in a network is
`disclosed. A node slOl wishing
`to
`join
`a
`disclosed. A node $101 wishing to join a particular mul
`ticast group transmits a packet via a sequence of nodes
`ticast group transmits a packet via a sequence of nodes
`(rlOl, rl02,
`rl04, rl07) including a core node rl07 on
`(r101, r102, r104, r107) including a core node r107 on
`the multicast tree corresponding
`to the particular mul­
`the multicast tree corresponding to the particular mul
`ticast group which the node wishes to
`join. The
`packet
`ticast group which the node wishes to join. The packet
`contains a request to
`join the
`particular multicast group
`contains a request to join the particular multicast group
`and the multicast address of the core node rl07 of the
`and the multicast address of the core node r107 of the
`multicast tree corresponding
`to
`the
`particular
`multicast tree corresponding to the particular multicast
`group. The packet is
`received at each node rlOl,
`rl02,
`group. The packet is received at each node r101, r102,
`rl04, rl07 of the sequence of nodes. Each node rlOl,
`r104, r107 of the sequence of nodes. Each node r101,
`rl02, rl04, rl07 which receives the packet writes an
`r102, r104, r107 which receives the packet writes an
`address of the node slOl, rlOl, rl02, rl04 from which
`address of the node $101, r101, r102, r104 from which
`the packet was received in an entry of a multicast for­
`the packet was received in an entry of a multicast for
`warding table maintained thereat which entry is in­
`warding table maintained thereat which entry is in
`dexed by the multicast address of the
`core
`dexed by the multicast address of the core node r107. If
`the node rlOl, rl02, rl04 which
`received
`the packet is
`the node r101, r102, 1104 which received the packet is
`not on the multicast tree of the particular multicast
`not on the multicast tree of the particular multicast
`group, the node rlOl, rl02, rl04 writes an address of the
`group, the node r101, r102, r104 writes an address of the
`next node rl02, rl04, rl07
`the sequence of nodes in
`of
`next node r102, r104, r107 of the sequence of nodes in
`the multicast forwarding table entry indexed by the
`the multicast forwarding table entry indexed by the
`multicast address of the core node rl07. The packet is
`multicast address of the core node r107. The packet is
`then retransmitted to the next node rl02, rl04, rl07 of
`then retransmitted to the next node r102, r104, r107 of
`the sequence of nodes.
`the sequence of nodes.
`
`node
`
`rl07.
`
`[54] MULTICAST ROUTING USING CORE
`[54] MULTICAST ROUTING USING CORE
`BASED TREES
`BASED TREES
`[75] Inventors: Paul T. Francis, Morristown, N.J.;
`[75]
`Inventors: Paul T. Francis, Morristown, N.J.;
`Anthony J. Ballardie, Alstonefield;
`Anthony J. Ballardie, Alstone?eld;
`Jonathan A. Crowcroft, London,
`Jonathan A. Crowcroft, London,
`both of England
`both of England
`[73] Assignee: Bell Communications Research, Inc.,
`[73] Assignee:
`Bell Communications Research, Inc.,
`Livingston, N.J.
`Livingston, NJ.
`[21] Appl. No.: 100,634
`[21]
`App1,No.: 100,634
`[22] Filed:
`Jul. 30,1993
`[22]
`Filed:
`Jul. 30, 1993
`[51] Int.CI.s
`[51]
`H04L 12/44; H04J 3/08
`Int. CL5 ....................... .. H04L 12/44; H04] 3/08
`[52] U.S. a.
`[52]
`370/54; 370/60;
`US. Cl. ...................................... .. 370/54; 370/60;
`370/94.3
`370/943
`[58] Field of Search
`[58]
`370/94.1, 94.3, 60,
`Field of Search ..................... .. 370/94.l, 94.3, 60,
`370/54, 16; 340/827
`370/54, 16; 340/827
`References Cited
`References Cited
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`4,740,954 4/1988 Cotton et al
`.. 370/60
`4,740,954 4/1988 Cotton et al. ....................... .. 370/60
`5,095,480 3/1992 Fenner
`370/94.1
`5,095,480 3/ 1992 Fenner ............ ..
`5,103,444 4/1992 Leung et al
`.. 370/60
`5,103,444 4/1992 Lcung et al. ........................ .. 370/60
`OTHER PUBLICATIONS
`OTHER PUBLICATIONS
`Deering, S., "Multicast Routing in Internetworks and
`Deering, S., “Multicast Routing in Internetworks and
`Extended LANs" ACM Symposium on Communica­
`Extended LANs” ACM Symposium on Communica
`tion Architectures and Protocols, ACM SIGCOMM,
`tion Architectures and Protocols, ACM SIGCOMM,
`pp. 55-64 Aug. 1988.
`pp. 55-64 Aug. 1988.
`Wall, D., "Mechanism for Broadcast and Selective
`Wall, D_, “Mechanism for Broadcast and Selective
`Broadcast," Jun. 1980 (PhD) thesis, Stamford Univer­
`Broadcast,” Jun. 1980 (PhD) thesis, Stamford Univer
`sity.
`my
`
`[56]
`[56]
`
`16 Claims, 8 Drawing Sheets
`16 Claims, 8 Drawing Sheets
`
`5102
`
`MOl
`
`100
`
`200
`
`y rlOB
`
`rl20
`
`| rl05
`
`s?
`
`rl04
`
`slOl
`
`M01
`
`rl02
`
`0102
`
`'/ rl08
`,1
`
`Ii07
`
`rll4
`
`rlQ3
`
`'0105
`
`'/
`Y rllO
`
`rl09
`
`rill
`
`0103
`
`0104
`
`V
`rll?
`
`0105
`
`rli3
`
`rll5
`
`S103
`
`P119
`
`rllB
`
`rllB
`
`rll7
`
`BUNGIE - EXHIBIT 1032
`
`

`

`P a t en t
`US. Patent
`
`J ul y 19, 1994
`July 19, 1994
`
`S h e e t 1 o f 8
`Sheet 1 of 8
`
`5> 3 3 l , 6 3 7
`5,331,637
`
`ral
`
`CO
`
`ic:
`
`
`i
`I
`
`i
`
`c ^
`
`CT l
`
`r \ j j
`
`S f c . ,
`
`
`i
`I
`
`i
`I
`
`o
`
`o
`
`LU
`
`cx
`
`Cjj
`
`cr
`
`&
`
`CD
`
`Q
`
`•*c
`
`CD
`
`cr
`
`[ JC >
`
`x j
`
`ac
`
`PD
`
`I
`I
`I
`I
`
`I
`
`/
`
`I
`
`car
`
`t f /
`c o s
`
`CO
`
`

`

`FIG. 2
`F I G . 2
`(PRIOR ART)
`(PRIOR ART)
`11 r
`i
`12
`CPU
`Li 14
`I/O
`I/O
`I
`13-2
`
`MEM
`
`<
`
`13-1
`
`13-N
`
`FIG. 3
`F I I3 . 3
`(PRIOR ART)
`40
`40
`(PRIOR ART)
`\
`
`I/O
`
`41
`( 41
`
`1
`
`PAYLOAD
`PAYLOAD
`
`U.S. Patent
`US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 2 of 8
`Sheet 2 of 8
`
`5,331,637
`5,331,637
`
`10
`10\
`
`42
`42
`W
`
`\
`
`DEST. ADDR.
`BEST. ADDR.
`
`HEADER
`HEADER
`
`43
`43
`
`50
`so
`
`51
`
`FIG. 4
`FIG . 4
`(PRIOR ART)
`(PRIOR ART)
`NEXT NODE
`NEXT NUDE
`c
`b
`b
`b
`b
`c
`
`INDEX
`INDEX
`v
`"
`x
`y
`v
`z
`u
`
`

`

`U.S. Patent
`US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 3 of 8
`Sheet 3 of 8
`
`5,331,637
`5,331,637
`
`LO
`
`OJ
`
`cn
`c_
`
`m
`
`o
`
`OJ
`
`GO
`C_
`
`•C3
`
`LO
`C_
`
`LO
`
`c>_
`
`ir)„
`:5 as? m 6H1
`cos
`U. -
`
`LO
`
`1
`an c. \//
`!1
`
`C_
`
`C—
`
`LO
`"CD
`
`h
`
`OJ c_
`
`c_
`
`I
`
`tn
`
`

`

`U.S. Patent
`. US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 4 of 8
`Sheet 4 of 8
`
`5,331,637
`5,331,637
`
`m
`c_
`
`CD
`
`CO
`
`CO
`
`to
`c_
`
`m
`
`m
`
`on
`2E
`tn
`
`.
`
`LTV
`
`rvj
`
`en
`
`3%
`
`n
`
`8:.
`
`CO
`
`c_
`
`OJ
`
`to
`
`in
`C-
`
`OJ
`
`3:.
`
`c\j
`tn
`
`we?
`
`(0
`
`CD
`U.
`
`OJ
`C-
`
`82
`
`CO
`
`

`

`U.S. Patent
`US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 5 of s
`Sheet 5 of 8
`
`5,331,637
`5,331,637
`
`FIG. 7
`F I G . 7
`
`/
`101-50
`101-50
`
`101-51
`101 51 _/\
`
`INDEX
`INDEX
`
`rl07
`r107
`
`SUE
`
`NEXT NODES
`NEXT NUUES
`
`slOl.rlOZ
`s101,r102
`
`FIG. 8
`F I G . 8
`
`/
`102-50
`102-50
`
`102-51
`
`INDEX
`INDEX
`
`rl07
`P107
`
`NEXT NODES
`NEXT NUUES
`
`rl01Irl04
`P101,r‘104
`
`

`

`U.S. Patent
`US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 6 of 8
`Sheet 6 of s
`
`5,331,637
`5,331,637
`
`FIG. 9
`F IG. 9
`
`/
`104-50
`104-50
`
`104-51
`10461 _/\
`
`INDEX
`INDEX
`
`rl07
`r107
`
`NEXT NODES
`NEXT NUDES
`
`rlOP.rlO?
`r102,r107
`
`FIG. 10
`F I G . 1O
`
`INDEX
`INDEX
`
`rl07
`r107
`
`NEXT NODES
`NEXT NUDES
`
`rl04
`r104
`
`/I.
`107-50
`107-50
`
`107-51
`
`

`

`U.S. Patent
`US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 7 of s
`Sheet 7 of 8
`
`5,331,637
`5,331,637
`
`FIG. 11
`F I G . 11
`
`/-
`
`103-50
`103-50
`
`103-51
`10351 _/\
`
`INDEX
`INDEX
`
`rl07
`r107
`
`NEXT NODES
`NEXT NDDES
`
`.
`
`dioe.noa
`010M102
`
`sam
`
`FIG. 12
`F I G . 12
`
`INDEX
`INDEX
`
`NEXT NODES
`NEXT NUDES
`
`/
`102-50
`102'50
`
`102-51
`
`rl07
`
`noi.nos.r^
`
`__/\
`
`F I G . 14
`
`FIG. 14
`
`/
`106-50
`105-50
`
`106-51
`
`INDEX
`INDEX
`
`rl06
`P106
`
`NEXT NODES
`NEXT NUDES
`
`dlOl.rlOS
`010M105
`
`

`

`U.S. Patent
`US. Patent
`
`July 19, 1994
`July 19, 1994
`
`Sheet 8 of 8
`Sheet 8 of 8
`
`5,331,637
`5,331,637
`
`LD
`
`OJ
`c_
`
`CO
`
`cn
`
`//
`
`C7^
`
`1,
`
`c_
`
`CO
`c_
`
`CO
`C—
`
`C—
`
`CO
`
`LO
`
`m
`
`OJ cr?
`TD
`
`f o
`
`TD
`
`OJ cr>
`to
`
`cn
`TH
`
`m.“ .mHl
`
`0
`U.
`
`LO
`
`//
`
`OJ
`
`OJ
`
`m
`
`C. I,
`h
`
`OJ
`c_
`
`LD
`
`m O)
`23
`cn
`
`I
`
`SE
`
`cn
`
`

`

`15
`
`30
`
`1
`1
`MULTICAST ROUTING USING CORE BASED
`MULTICAST ROUTING USING CORE BASED
`TREES
`TREES
`
`5,331,637
`5,331,637
`2
`2
`contains communicated data and one or more headers
`contains communicated data and one or more headers
`42 which contain control and/or address information.
`42 which contain control and/or address information.
`A host which initially generates a packet for transmis­
`A host which initially generates a packet for transmis
`sion to another node is called the source node and a host
`sion to another node is called the source node and a host
`RELATED APPLICATIONS
`RELATED APPLICATIONS
`5 which ultimately receives the packet is called a destina­
`which ultimately receives the packet is called a destina
`tion node. Communication may be achieved between a
`The following patent applications are assigned to the
`The following patent applications are assigned to the
`tion node. Communication may be achieved'between a
`single source node and a single destination node using a
`same assignee of the present patent application:
`same assignee of the present patent application:
`single source node and a single destination node using a
`process called unicast routing. In unicast routing, pack­
`1. U.S. patent application Ser. No. 08/069,275 enti­
`process called unicast routing. In unicast routing, pack
`1. US. patent application Ser. No. 08/069,275 enti
`tled "General Internet Method for Routing Pack­
`ets are transferred via a sequence of nodes including the
`tled “General Internet Method for Routing Pack
`ets are transferred via a sequence of nodes including the
`ets in a Communications Network" filed May 28, 10 source node, zero or more intermediary nodes, and the
`10
`ets in a Communications Network” ?led May 28,
`source node, zero or more intermediary nodes, and the
`1993 for Paul Tsuchiya, and
`destination node, in a bucket brigade fashion. For exam­
`1993 for Paul Tsuchiya, and
`destination node, in a bucket brigade fashion. For exam
`2. U.S. patent application Ser. No. 08/033,638 enti­
`ple, a packet may be communicated from the node w to
`2. US. patent application Ser. No. 08/033,638 enti
`ple, a packet may be communicated from the node w to
`tled "Method and System for Shortcut Routing
`the node x by transferring the packet from the node w
`tled “Method and System for Shortcut Routing
`the node x by transferring the packet from the node w
`over Public Data Networks" filed Mar. 16, 1993
`to the node c, to the node d, to the node b, and to the
`over Public Data Networks” ?led Mar. 16, 1993
`to the node 0, to the node d, to the node b, and to the
`for Paul Tsuchiya.
`for Paul Tsuchiya.
`node x. The particular sequence of nodes via which a
`node x. The particular sequence of nodes via which a
`The above listed patent applications contain subject
`The above listed patent applications contain subject
`packet is transmitted is also referred to as a "path". In
`packet is transmitted is also referred to as a “path”. In
`matter related to the subject matter of this patent appli­
`the above example, one path from the source node w to
`matter related to the subject matter of this patent appli
`the above example, one path from the source node w to
`cation and are incorporated herein by reference.
`cation and are incorporated herein by reference.
`the destination node x includes the nodes (w,c,d,b, and
`the destination node it includes the nodes (w,c,d,b, and
`x).
`x).
`FIELD OF THE INVENTION
`FIELD OF THE INVENTION
`20 When a source node transmits a packet to a single
`20
`When a source node transmits a packet to a single
`The present invention relates to transmitting informa­
`The present invention relates to transmitting informa
`destination node, the source node writes the destination
`destination node, the source node writes the destination
`tion organized into packets between nodes of a commu­
`tion organized into packets between nodes of a commu
`address of the packet in a destination address field 43
`address of the packet in a destination address ?eld 43
`nications network. In particular, the present invention
`nications network. In particular, the present invention
`(FIG. 3) of the header 42. Illustratively, each node of
`(FIG. 3) of the header 42. Illustratively, each node of
`relates to multicast routing, or transmitting a single
`relates to multicast routing, or transmitting a single
`the internet 80 is assigned a unique internet address
`the internet 80 is assigned a unique internet address
`packet to each node of a distinct group of one or more 25
`25
`packet to each node of a distinct group of one or more
`which is used for identifying the node for purposes of
`which is used for identifying the node for purposes of
`destination nodes called a multicast group. The present
`destination nodes called a multicast group. The present
`transmitting a packet thereto. The source node then
`transmitting a packet thereto. The source node then
`invention provides a novel, low-overhead method for
`invention provides a novel, low-overhead method for
`retrieves an entry from a forwarding table, such as the
`retrieves an entry from a forwarding table, such as the
`constructing and storing one multi-destination delivery
`constructing and storing one multi-destination delivery
`entry 51 of the table 50 shown in FIG. 4, which entry is
`entry 51 of the table 50 shown in FIG. 4, which entry is
`route for each distinct multicast group of nodes.
`route for each distinct multicast group of nodes.
`indexed by the destination address of the packet. (Illus­
`indexed by the destination address of the packet. (Illus
`BACKGROUND OF THE INVENTION
`tratively, the particular forwarding table 50 shown in
`tratively, the particular forwarding table 50 shown in
`BACKGROUND OF THE INVENTION
`FIG. 4 is stored at the node a.) The forwarding table
`FIG. 4 is stored at the node a.) The forwarding table
`An internet communications network 80 is depicted
`An internet communications network 80 is depicted
`stores a number of entries which entries each contains
`stores a number of entries which entries each contains
`in FIG. 1 including five transit or backbone networks
`in FIG. 1 including ?ve transit or backbone networks
`information for routing a received packet to its ultimate
`information for routing a received packet to its ultimate
`A, B, C, D, and E and three stub networks R, Y, and Z.
`A, B, C, D, and E and three stub networks R, Y, and Z.
`destination. Each indexed entry of the forwarding table
`destination. Each indexed entry of the forwarding table
`A "backbone" network is an intermediary network 35
`A “backbone” network is an intermediary network
`35
`indicates the next node on the path to the destination
`which conveys communicated data from one network
`indicates the next node on the path to the destination
`which conveys communicated data from one network
`node (where the address of the destination node is used
`to another network. A "stub" network is a terminal or
`node (where the address of the destination node is used
`to another network. A “stub” network is a terminal or
`as the index to retrieve the entry). For example, at the
`endpoint network from which communicated data may
`as the index to retrieve the entry). For example, at the
`endpoint network from which communicated data may
`node a, the entry 51 indicates that the next node on the
`only initially originate or ultimately be received. Each
`node a, the entry 51 indicates that the next node on the
`.
`only initially originate or ultimately be received. Each
`network, such as the stub network R, includes one or 40 Pat^ t0 t'le node y is the node b. The source node then
`path to the node y is the node b. The source node then
`network, such as the stub network R, includes one or
`40
`transmits the packet to the next node on the path indi­
`more interconnected subnetworks such as I, J, L and M.
`transmits the packet to the next node on the path indi
`more interconnected subnetworks such as I, J, L and M.
`cated by the retrieved entry. This process is repeated at
`As used herein, the term "subnetwork" refers to a
`cated by the retrieved entry. This process is repeated at
`As used herein, the term “subnetwork” refers to a
`each intermediary node until the packet arrives at the
`collection of one or more nodes, e.g., (d), (a) (b, x, y), (q,
`each intermediary node until the packet arrives at the
`collection of one or more nodes, e.g., (d), (a) (b, x, y), (q,
`destination node.
`v) (r, z), (s, u), (e, f, g), (h, i), (j, k, 1), (m, n), and (o, p),
`destination node.
`v) (I, Z), (8.11), (e, f, g), (h, i), (i, k, 1), (m, n), and (0, P),
`Sometimes a source node has a packet to transmit to
`interconnected by wires and switches for local inter- 45
`interconnected by wires and switches for local inter
`Sometimes a source node has a packet to transmit to
`45
`more than one destination node. For example, the
`nodal communication. Each subnetwork may be a local
`more than one destination node. For example, the
`nodal communication. Each subnetwork may be a local
`packet may contain an electronic mail or E-mail letter
`area network or LAN. Each subnetwork has one or
`packet may contain an electronic mail or E-mail letter
`area network or LAN. Each subnetwork has one or
`to be delivered to each user of a particular mail group
`more interconnected nodes which may be host comput­
`to be delivered to each user of a particular mail group
`more interconnected nodes which may be host comput
`which users are each located at different destination
`ers ("hosts") u, v, w, x, y, z (shown as triangles in FIG.
`which users are each located at different destination
`ers (“hosts”) u, v, w, x, y, 2 (shown as triangles in FIG.
`1) or routers a, b, c, d, e, f, g, h, i, j, k, 1, m, n, o, p, q, r, 50 nodes. Alternatively, the packet may contain voice data
`nodes. Alternatively, the packet may contain voice data
`1) or routers a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r,
`50
`of a speaking teleconference participant at a source
`s (shown as squares in FIG. 1). A host is an endpoint
`of a speaking teleconference participant at a source
`5 (shown as squares in FIG. 1). A host is an endpoint
`node to be simultaneously delivered to a number of
`node from which communicated data may initially orig­
`node from which communicated data may initially orig
`node to be simultaneously delivered to a number of
`listening teleconference participants located at different
`inate or ultimately be received. A router is a node
`listening teleconference participants located at different
`inate or ultimately be received. A router is a node
`which serves solely as an intermediary node between
`destination nodes. Such packets may be transmitted
`destination nodes. Such packets may be transmitted
`which serves solely as an intermediary node between
`two other nodes; the router receives communicated 55 from the source node to each destination node accord-
`two other nodes; the router receives communicated
`from the source node to each destination node accord
`55
`data from one node and retransmits the data to another
`ing to a routing procedure depicted in FIG. 5.
`ing to a routing procedure depicted in FIG. 5.
`data from one node and retransmits the data to another
`node.
`FIG. 5 depicts a portion 75 of an internet. As shown
`node.
`FIG. 5 depicts a portion 75 of an internet. As shown
`FIG. 2 shows a block diagram of a host or router
`in FIG. 5, a packet to be transmitted to a particular
`FIG. 2 shows a block diagram of a host or router
`in FIG. 5, a packet to be transmitted to a particular
`node 10. As shown, the node may include a CPU 11, a
`group of destination nodes dl, d2, d3, d4, d5, and d6 is
`group of destination nodes d1, d2, d3, d4, d5, and d6 is
`node 10. As shown, the node may include a CPU 11, a
`memory 12 and one or more I/O ports 13-1,13-2,..., 60 transmitted from a source si to a first router rl. Illustra-
`transmitted from a source 51 to a ?rst router r1. Illustra
`memory 12 and one or more I/O ports 13-1, 13-2, . . . ,
`13-N connected to a bus 14. Illustratively, each I/O
`lively, the router rl connects the stub containing the
`13-N connected to a bus 14. Illustratively, each I/O
`tively, the router r1 connects the stub containing the
`port 13-1,13-2,..., 13-N is connected by wires, optical
`source node si to the internet 75. The router rl trans­
`source node $1 to the internet 75. The router r1 trans
`port 13-1, 13-2, . . . , 13-N is connected by wires, optical
`fibers, and/or switches to the I/O port of another node.
`mits the packet to the node r2. At the node r2, the
`?bers, and/or switches to the I/O port of another node.
`mits the packet to the node r2. At the node r2, the
`The I/O ports 13-1,13-2,..., 13-N are for transmitting
`packet is transmitted to the destination node d6 via the
`packet is transmitted to the destination node d6 via the
`The I/O ports 13-1, 13-2, . . . , 13-N are for transmitting
`communicated data in the form of a bitstream organized 65 router r3. In addition, the router r2 transmits a copy of
`communicated data in the form of a bitstream organized
`router r3. In addition, the router r2 transmits a copy of
`into one or more packets to another node and for re­
`the packet to the router r4. The router r4 receives the
`into one or more packets to another node and for re
`the packet to the router r4. The router r4 receives the
`ceiving a packet from another node. An exemplary
`copy of the packet and transmits a copy of the received
`ceiving a packet from another node. An exemplary
`copy of the packet and transmits a copy of the received
`packet 40 is shown in FIG. 3 having a payload 41 which
`packet to the destination node dl via the nodes r5 and
`packet 40 is shown in FIG. 3 having a payload 41 which
`packet to the destination node d1 via the nodes r5 and
`
`

`

`5,331,637
`5,331,637
`3
`4
`3
`4
`r6. In addition, the router r4 transmits a copy of the
`One conventional multicast tree construction method
`One conventional multicast tree construction method
`r6. In addition, the router r4 transmits a copy of the
`received packet to the router r7. The router r7, trans-
`is provided in a multicast routing method called Dis-
`is provided in a multicast routing method called Dis
`received packet to the router r7. The router r7, trans
`mits a copy of the received packet to the destination
`tance-Vector
`Multicast
`Routing
`Protocol
`tance-Vector
`Multicast
`Routing
`Protocol
`mits a copy of the received packet to the destination
`node d2 via the router r8. The router r7 transmits a
`("DVMRP"). This multicast tree construction method
`(“DVMRP”). This multicast tree construction method
`node d2 via the router r8. The router r7 transmits a
`copy of the received packet to the destination node d3 5 uses a modified reverse path forwarding algorithm to
`copy of the received packet to the destination node d3
`uses a modi?ed reverse path forwarding algorithm to
`via the routers r9 and rlO. In addition, the router r7
`construct shortest path, sender-based multicast trees. A
`construct shortest path, sender-based multicast trees. A
`via the routers r9 and r10. In addition, the router r7
`transmits a copy of the received packet to the router
`multicast tree is constructed according to DVMRP as
`transmits a copy of the received packet to the router
`multicast tree is constructed according to DVMRP as
`rll. The router rll receives the packet and transmits a
`follows. Initially, a source node transmits the first few
`r11. The router r11 receives the packet and transmits a
`follows. Initially, a source node transmits the ?rst few
`copy of the received packet to the destination node d4 multicast packets without using a multicast tree. In-
`copy of the received packet to the destination node d4
`multicast packets without using a multicast tree. In
`via the router rl2 and a copy of the received packet to 10 stead, the source node transmits the multicast packets in
`stead, the source node transmits the multicast packets in
`via the router r12 and a copy of the received packet to
`the destination node d5 via the router rl3.
`a manner such that a copy of each multicast packet is
`the destination node d5 via the router r13.
`a manner such that a copy of each multicast packet is
`The packet delivery process shown in FIG. 5 is re­
`transmitted via each backbone network. For example,
`transmitted via each backbone network. For example,
`The packet delivery process shown in FIG. 5 is re
`ferred to as multicast routing. In multicast routing, as a
`each router which receives one of the first few multicast
`ferred to as multicast routing. In multicast routing, as a
`each router which receives one of the ?rst few multicast
`packet propagates from router to router, the packet is
`packets transmits a copy of the packet to each other
`packet propagates from router to router, the packet is
`packets transmits a copy of the packet to each other
`selectively replicated at certain routers so that sufficient 15 router attached thereto. Routers which receive these
`selectively replicated at certain routers so that suf?cient
`router attached thereto. Routers which receive these
`copies of the packet are generated and transmitted to
`packets may indicate that they are not on a path to a
`copies of the packet are generated and transmitted to
`packets may indicate that they are not on a path to a
`each destination node of a multicast group. Collec­
`destination node of the multicast group by transmitting
`destination node of the multicast group by transmitting
`each destination node of a multicast group. Collec
`tively, the paths shown in FIG. 5, i.e., the sequences of
`a packet containing a special "prune" message to the
`tively, the paths shown in FIG. 5, i.e., the sequences of
`a packet containing a special “prune” message to the
`nodes which interconnect all of the nodes of a particular
`router from which the multicast packet was received. A
`nodes which interconnect all of the nodes of a particular
`router from which the multicast packet was received. A
`group form a tree called a multicast tree. A path of the 20 particular router may transmit a prune message if:
`group form a tree called a multicast tree. A path of the
`particular router may transmit a prune message if:
`multicast tree between any two nodes, e.g., the path
`(1) the particular router is not directly connected to
`(1) the particular router is not directly connected to
`multicast tree between any two nodes, e.g., the path
`from the node r2 to the node rll including the nodes
`any stub networks containing a node which is a
`from the node r2 to the node r11 including the nodes
`any stub networks containing a node which is a
`(r2, r4, r7, and rll) is referred to as a branch. There is
`member of the multicast group of the packet,
`member of the multicast group of the packet,
`(r2, r4, r7, and r11) is referred to as a branch. There is
`only one branch on the multicast tree between any two
`(IGMP may be utilized to determine that each stub
`only one branch on the multicast tree between any two
`(IGMP may be utilized to determine that each stub
`nodes.
`has no member nodes of the multicast group) and
`25
`nodes.
`has no member nodes of the multicast group) and
`25
`There are several conventional methods for imple­
`(2) the particular router is not an intermediary node
`There are several conventional methods for imple
`(2) the particular router is not an intermediary node
`menting multicast routing, in particular, for construct­
`on a path to a stub network containing a node
`menting multicast routing, in particular, for construct
`on a path to a stub network containing a node
`ing and maintaining multicast trees. See S. Deering,
`which is a member of the multicast group of the
`ing and maintaining multicast trees. See S. Deering,
`which is a member of the multicast group of the
`"Multicast Routing in Internetworks and Extended
`packet. Such is the case if the particular router
`“Multicast Routing in Internetworks and Extended
`packet. Such is the case if the particular router
`LANs," ACM Symposium on Communication Archi- 30
`receives a prune message from each router to
`LANs,” ACM Symposium on Communication Archi
`receives a prune message from each router to
`lectures and Protocols, ACM SIGCOMM, pp. 55-64,
`which the particular router transmitted a multicast
`tectures and Protocols, ACM SIGCOMM, pp. 55—64,
`which the particular router transmitted a multicast
`packet.
`Aug., 1988. Conventionally, multicast tree construction
`packet.
`Aug., 1988. conventionally, multicast tree construction
`is sender based. That is, for each multicast group, one
`For each source node-multicast group pair, each router
`is sender based. That is, for each multicast group, one
`For each source node-multicast group pair, each router
`multicast tree is constructed between each potential
`keeps track of from which routers prune messages have
`multicast tree is constructed between each potential
`keeps track of from which routers prune messages have
`source node, i.e., each node that can potentially trans- 35 been received. When a router subsequently receives
`source node, i.e., each node that can potentially trans
`been received. When a router subsequently receives
`mit multicast packets, and the corresponding destina­
`packets transmitted from the same source node to the
`mit multicast packets, and the corresponding destina
`packets transmitted from the same source node to the
`tion nodes which receive packets from the source node.
`same multicast group, the router retransmits copies of
`tion nodes which receive packets from the source node.
`same multicast group, the router retransmits copies of
`Appropriate routing information for each pair of a mul­
`the packet to only those routers which did not transmit
`Appropriate routing information for each pair of a mul
`the packet to only those routers which did not transmit
`ticast group and a source node is stored at each router
`a prune message in previous multicast communications
`a prune message in previous multicast communications
`ticast group and a source node is stored at each router
`on each multicast tree.
`40 between this source node and multicast group.
`on each multicast tree.
`between this source node and multicast group.
`In multicast tree construction, the Internet Group
`Another conventional multicast tree construction
`In multicast tree construction, the Internet Group
`Another conventional multicast tree construction
`Management Protocol ("IGMP") may be utilized for
`method is provided in a multicast routing method called
`Management Protocol (“IGMP”) may be utilized for
`method is provided in a multicast routing method called
`purposes of determining which host nodes in each sub­
`the Link-State Multicast Routing Protocol. According
`purposes of determining which host nodes in each sub
`the Link-State Multicast Routing Protocol. According
`network desire to join which multicast groups. Accord­
`to this multicast tree construction method, each router
`network desire to join which multicast groups. Accord
`to this multicast tree construction method, each router
`ing to IGMP, a router node is designated as an interro- 45 maintains information regarding each link or each di-
`maintains information regarding each link or each di
`ing to IGMP, a router node is designated as an interro
`45
`gator for a subnetwork. The interrogator transmits a
`rect connection to another node. In addition, for each
`gator for a subnetwork. The interrogator transmits a
`rect connection to another node. In addition, for each
`query packet over the associated subnetwork to each
`link, each router maintains a list of each multicast group
`query packet over the associated subnetwork to each
`link, each router maintains a list of each multicast group
`host. The hosts which receive this query packet respond
`having one or more member nodes on that link, i.e.,
`host. The hosts which receive this query packet respond
`having one or more member nodes on that link, i.e.,
`by indicating of which multicast groups the hosts are
`having one or more mem