United States Patent [19J
`Gleeson et al.
`
`[54] SYSTEM FOR EFFICIENT MULTICAST
`DISTRIBUTION IN A VIRTUAL LOCAL
`AREA NETWORK ENVIRONMENT
`
`[75]
`
`Inventors: Bryan J. Gleeson, Cupertino; Percy P.
`Khabardar; Norman W. Finn, both of
`San Jose, all of Calif.
`
`[73] Assignee: Cisco Technology, Inc., San Jose, Calif.
`
`[ *] Notice:
`
`This patent issued on a continued pros(cid:173)
`ecution application filed under 37 CFR
`1.53( d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`[21] Appl. No.: 08/882,632
`
`[22] Filed:
`
`Jun. 25, 1997
`
`Int. Cl.6
`..................................................... H04L 12/46
`[51]
`[52] U.S. Cl. ........................... 370/390; 370/401; 370/432
`[58] Field of Search ..................................... 370/390, 397,
`370/449, 389, 469, 432, 395, 400, 401,
`409, 270
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,864,559
`4,922,486
`5,304,992
`5,305,311
`5,361,256
`5,394,402
`5,511,168
`5,612,959
`5,633,869
`5,684,800
`5,740,171
`
`9/1989 Perlman .................................. 370/390
`5/1990 Lidinsky et al. .......................... 370/60
`4/1994 Herashima .............................. 370/390
`4/1994 Lyles ....................................... 370/390
`11/1994 Doeringer et al. ...................... 370/390
`2/1995 Ross ........................................ 370/402
`4/1996 Perlman et al.
`........................ 370/409
`3/1997 Takase et al. ........................... 370/390
`5/1997 Burnett et al. .......................... 370/396
`11/1997 Dobbins et al. ........................ 370/401
`4/1998 Mazzoca et al.
`....................... 370/401
`
`I 1111111111111111 11111 lllll lllll 111111111111111 1111111111 111111111111111111
`US005959989A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,959,989
`*Sep.28,1999
`
`5,742,604
`5,752,003
`5,764,636
`
`4/1998 Edsall et al. ............................ 370/401
`5/1998 Hart ........................................ 395/500
`6/1998 Edsall ...................................... 370/401
`
`OTHER PUBLICATIONS
`
`Lucent Technolgies Inc.'s Initial Disclosure of Prior Art
`Under Civil Local Rule 16-7, Case No. C98-20826 JW
`(PVT) ENE (Nov. 18, 1998).
`M. Seaman and D. Delaney, Single or Multiple Filtering
`Databases (May 8, 1997).
`IEEE, "Draft Standard for Virtual Bridged Local Area
`Networks", pp. 1-10 and 70-72 (May 1997).
`S. Deering and D. Cheriton, Multicast Routing in Datagram
`Internetworks and Extended LANs, vol. 8, "ACM Transac(cid:173)
`tions on Computer Systems", pp. 85-110 (May 1990).
`S. Deering et al., An Architecture for Wide---SArea Multi(cid:173)
`casting, Proceedings of SIGCOMM '94 Conf., ACM, pp.
`126-135 (Oct. 1994).
`
`Primary Examiner-Chau Nguyen
`Assistant Examiner--K. Vanderpuye
`Attorney, Agent, or Firm-Cesari and McKenna, LLP
`
`[57]
`
`ABSTRACT
`
`A mechanism for efficiently distributing multicast messages
`having group destination addresses to subscribing entities in
`a computer network. The network includes a plurality of
`virtual local area network (VLAN) designations among
`those entities and a multicast network device (MND) con(cid:173)
`figured to generate at least one unique multicast (MYLAN)
`identifier (ID) for each group destination address. Each
`MYLAN ID encompasses all VLAN designations of the
`subscribing entities, except for the VLAN designation asso(cid:173)
`ciated with the entity sourcing the message. Each MYLAN
`ID is propagated to intermediate devices of the network and
`attached to subsequent multicast messages to enable efficient
`distribution of those messages over the network.
`
`29 Claims, 8 Drawing Sheets
`
`I MULTICASTVLAN
`TAG SOURCE
`i
`MULTICAST CONTROLLER
`
`:
`
`310
`
`f300
`
`(306
`
`SUBSCRIBING VLAN
`GROUP
`DESTINATION DESIGNATIONS. PHYSICAL
`ADDRESS
`INTERFACE NUMBER
`
`SUBSCRIBING ENTITIES
`(WITHOUT VLAN DESIGNATIONS),
`PHYSICAL INTERFACE NUMBER
`
`NEWSFROM27
`
`----------
`
`----------
`
`RED, 1
`BLUE, 1
`GREEN, 1
`----
`----
`----
`----
`----
`
`2
`
`312~
`
`MULTICAST VLAN
`IDENTIFIER
`BLUE-GREEN
`
`RED-BLUE
`
`-------
`
`-------
`
`CORRESPONDING
`VLAN DESIGNATIONS
`BLUE
`GREEN
`RED
`BLUE
`-------
`-------
`-------
`-------
`-------
`
`306
`
`! (305 ! (305 t ( 305
`
`I
`
`VLAN
`VLAN
`VLAN
`LOGICAL LOGICAL LOGICAL
`INT.
`INT.
`INT.
`(RED)
`(BLUE)
`(GREEN)
`
`t.
`I TRUNK/PORT
`
`.J
`:I
`
`PHYSICAL \NTERFACE
`
`\. 302
`
`r
`TRUNK/PORT I
`1 \. 304
`
`PHY. INT.
`2
`
`(TO/FROM) (TO/FROM)
`TRUNK
`LAN
`231
`236
`
`Ex.1025
`VERIZON / Page 1 of 21
`
`

`

`\0
`00
`\0
`....
`\0
`Ul
`\0
`....
`Ul
`
`CIO
`
`'"""' 0 ....,
`~ ....
`'JJ. =-~
`
`\0
`\0
`'"""'
`\0
`~CIO
`N
`~ '?
`'JJ.
`
`= ......
`~
`......
`~
`~
`•
`r:JJ.
`d •
`
`6 ()'110' 1lo'c:J ? ?9?
`
`22 23
`
`\ 111
`
`(PRIOR ART)
`
`FIG. 1A
`
`20
`
`.., Y -112
`
`(cid:127).
`
`132
`
`, ~ I I I
`
`I
`
`-
`
`)
`
`In '--1H:
`
`.l. u C
`
`1 os-.l.
`
`C S? ----,___ 125
`
`104..,
`
`c113
`
`0,Y 6 6
`
`y
`
`121
`
`S5
`
`O,Y
`
`131
`
`R,B,G
`
`("'\ (')
`25
`
`0
`
`sfi
`
`y
`
`/
`
`122
`
`O,Y
`
`10,v
`
`"
`
`125
`
`ci124
`
`r::-{123
`
`(100
`
`L101
`B I I I
`
`~1]6/
`R
`
`102-'
`
`107-' 1161)1 CjJ r II~
`
`1 81""'\.
`
`108
`
`21
`
`117
`116
`
`128
`
`R,B
`125
`
`103-' ~ ~·
`
`Ex.1025
`VERIZON / Page 2 of 21
`
`

`

`U.S. Patent
`US. Patent
`
`Sep.28,1999
`Sep. 28, 1999
`
`Sheet 2 of 8
`Sheet 2 0f 8
`
`5,959,989
`5,959,989
`
`(X)
`mmw
`LO ..-
`
`E
`
`0 z
`w
`
`a
`
`0 z
`w
`
`,r-----~
`
`,,. r----..-- ,....
`
`(.0
`LO
`..-
`_,/
`
`9.:v2
`
`v
`LO
`..-
`_./
`
`
`
` Nmr-FZMFZOOw0<mmw§A<mvmmmmoo<2n:mmmmom<
`
`
`
`I-z w
`I-z
`0
`0
`w
`CJ
`<(
`(J)
`
`(J) w
`~
`
`-<(
`
`MOmDOm
`
`w~
`(.) (J)
`er: (J)
`:::::>w
`0 er:
`CJ) 0
`0
`<(
`
`C\I
`LO
`..-
`_,/
`
`Z<(
`00
`I- ;;;-
`<( (J) Zw
`I- er:
`(J)o
`Wo
`0 <(
`
`ZOF<Zmeo
`
`wm
`
`..-
`F
`LO
`..-
`_./
`
`I-er:
`<(
`I-
`(J)
`
`
`
`0
`LO
`..-
`
` om?
`
`
`
`0
`om.‘
`LO ..-
`
`mp.GE
`
`E3:95»
`
`I-z w
`I-z
`0
`(.)
`w
`CJ
`<(
`(J)
`
`59200$58:mumDOm
`
`
`
`-<(
`29mmmmoo<
`
`w~
`(.) (J)
`er: (J)
`:::::>w
`0 er:
`(J) 0
`0
`<(
`
`(J) w
`~
`
`Z<..>
`
`0“GE
`
`E?most:
`
`0 co
`..-
`_./
`
`Z<(
`0 C)
`I- ;;;-
`<( (J) Zw
`I- er:
`(J) 0 Wo
`
`29mmmmoo<
`
`292253
`
`C) <(
`
`I-er:
`<(
`I-
`(J)
`
`z
`0
`z I-
`<( <(
`_J z
`>(!)
`(J) w
`
`ZO_._.<zmu_mmo
`
`C)
`
`EX.1025
`
`VERIZON / Page 3 of 21
`
`Ex.1025
`VERIZON / Page 3 of 21
`
`
`

`

`\0
`00
`\0
`....
`\0
`Ul
`\0
`....
`Ul
`
`212
`
`~ ~
`0 ....,
`~ ....
`'JJ. =-
`
`CIO
`
`~
`
`36
`223
`
`V
`
`\0
`\0
`'"""'
`\0
`~CIO
`N
`'?
`~
`'JJ.
`
`= ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`~
`
`34
`
`y
`Moy
`
`0
`Moy
`
`218
`
`213
`
`214-
`
`FIG. 2A
`
`32
`
`31
`
`221
`
`-
`
`209~
`
`IMsG
`
`218
`
`222
`218
`
`®
`
`35
`
`Moy
`O,Y
`
`m
`
`232
`
`4
`
`MsG,Moy
`O,B,G
`
`33
`
`/
`
`MsG,Moy
`
`O,B,G
`
`~
`
`2
`
`1
`
`,... I
`
`208
`
`___ '\.
`"-
`MsG,Moy -/-R,G,B
`
`MsG
`
`230
`231
`
`MsG,MoY~BG
`R,G,B
`
`I
`
`30
`
`I -' '"' '
`
`207 ...,
`
`1
`
`MsG,Moy
`
`~J
`
`MsG,Moy
`O,Y,B,G
`
`234
`
`220 219~J ~ O,Y,B,G
`
`R,G,O
`
`206..., 218 'r 141 13 t;:;J-219
`
`,.226
`
`28
`
`__.c-228
`
`~Ub
`
`(
`
`,-200
`
`• l~ -~ ~®
`
`G,MsG
`
`I~ ••
`
`29
`
`204-'
`
`R
`
`Ex.1025
`VERIZON / Page 4 of 21
`
`

`

`\0
`00
`\0
`....
`\0
`Ul
`\0
`....
`Ul
`
`CIO
`
`0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`,i;;..
`
`\0
`\0
`'"""'
`\0
`~CIO
`N
`~ '?
`'JJ.
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`
`2, d •
`
`FIG. 2C
`
`FIG. 2B
`
`----, ----
`----, ----
`--------
`----, ----
`--------
`--------
`--------
`----, ----
`----' ----
`----, ----
`RED, 5
`
`,
`,
`,
`
`,
`
`-------------
`
`-------------
`
`ORANGE, 4
`ORANGE, 3
`GREEN, 3
`BLUE, 3
`RED, 3
`
`GREEN, 2
`
`NEWSFROM27
`
`PORT NUMBER
`
`VLAN,
`
`SUBSCRIBING
`
`ADDRESS
`
`DESTINATION
`
`GROUP
`
`2,
`
`29
`
`30
`
`--
`
`28
`
`-
`
`27
`
`RED
`
`5 (INTERNAL)
`
`ORANGE-YELLOW
`
`ORANGE
`
`4 (INTERNAL)
`
`ORANGE-YELLOW
`
`BLUE-GREEN
`
`YELLOW
`ORANGE
`GREEN
`BLUE
`RED
`
`3 (EXTERNAL)
`
`BLUE-GREEN
`
`GREEN
`
`2 (INTERNAL)
`
`RED
`
`1 (INTERNAL)
`
`ADDRESSES
`
`MAC
`
`ENTITY
`
`DESIGNATION
`
`VLAN
`
`NUMBER
`
`PORT
`
`Ex.1025
`VERIZON / Page 5 of 21
`
`

`

`\0
`00
`\0
`....
`\0
`Ul
`\0
`....
`Ul
`
`CIO
`
`0 ....,
`Ul
`~ ....
`'JJ. =(cid:173)~
`
`\0
`\0
`'"""'
`\0
`~CIO
`N
`~ '?
`'JJ.
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`(TO/FROM) (TO/FROM)
`t ~ 304
`
`236
`LAN
`
`2
`
`231
`
`TRUNK
`
`'
`
`PHY. INT.
`
`TRUNK/PORT
`
`t
`
`~ 302
`
`1
`
`PHYSICAL INTERFACE
`
`TRUNK/PORT
`
`,-f
`
`½
`
`(GREEN)
`
`INT.
`
`(BLUE)
`
`INT.
`
`(RED)
`INT.
`
`LOGICAL LOGICAL LOGICAL
`
`VLAN
`
`VLAN
`
`VLAN
`
`t (305
`
`( 305
`
`''
`
`(305
`
`l
`
`306
`
`-------
`-------
`-------
`-------
`-------
`BLUE
`RED
`
`GREEN
`BLUE
`
`VLAN DESIGNATIONS
`
`CORRESPONDING
`
`-------
`
`-------
`
`RED-BLUE
`
`BLUE-GREEN
`IDENTIFIER
`
`MULTICAST VLAN
`
`312--
`
`FIG. 3
`
`2
`
`GREEN, 1
`BLUE, 1
`RED, 1
`
`----
`----
`----
`----
`----
`
`----------
`
`----------
`
`NEWSFROM27
`
`PHYSICAL INTERFACE NUMBER
`(WITHOUT VLAN DESIGNATIONS),
`
`INTERFACE NUMBER
`
`ADDRESS
`
`DESTINATION DESIGNATIONS, PHYSICAL
`
`SUBSCRIBING ENTITIES
`
`SUBSCRIBING VLAN
`
`GROUP
`
`(308
`
`MULTICAST CONTROLLER
`
`~
`
`TAG SOURCE
`
`t
`
`MULTICAST VLAN
`
`Ex.1025
`VERIZON / Page 6 of 21
`
`

`

`\0
`\0
`'"""'
`\0
`~CIO
`N
`~ '?
`'JJ.
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`~
`
`\0
`00
`\0
`....
`\0
`Ul
`\0
`....
`Ul
`
`~
`
`CIO
`
`0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`O'I
`
`~
`
`~
`
`DATA
`
`DATA
`
`418
`
`~
`
`DATA
`
`(418
`
`FIG. 4A
`
`FIG. 4D
`
`ADDRESS
`SOURCE
`
`424
`
`FIG. 4C
`
`DESTINATION
`
`ADDRESS
`
`START
`
`~ MULTICAST
`
`VLAN
`
`ADDRESS
`SOURCE
`
`DESTINATION
`
`ADDRESS
`
`START
`
`VLAN
`
`~
`
`416
`
`4
`
`FIG. 48
`
`ADDRESS
`SOURCE
`
`416
`
`~ DESTINATION
`
`ADDRESS
`
`START
`
`414
`
`MESSAGE
`
`410
`
`IP SOURCE I IP DESTINATION
`
`r408
`
`406
`
`ADDRESS
`
`ADDRESS
`
`IP HEADER
`
`404
`
`~
`
`Ex.1025
`VERIZON / Page 7 of 21
`
`

`

`U.S. Patent
`US. Patent
`
`Sep.28,1999
`Sep.28, 1999
`
`Sheet 7 of 8
`Sheet 7 0f 8
`
`5,959,989
`5,959,989
`
`9
`
`VN
`
`,-...
`{3.92
`LO
`
`L0
`
`.
`
`en
`m
`
`0-
`
`
`
`'0
`
`I
`
`C5‘
`IL
`
`0
`
`0 O
`
`v
`:5
`
`0
`C\J
`LO
`
`.0
`
`,_
`,--
`C\J
`O
`LO
`
`NL
`
`EX.1025
`
`VERIZON / Page 8 of 21
`
`~I
`
`co
`,--
`LO
`
`C\J
`C\J
`LO
`
`Ex.1025
`VERIZON / Page 8 of 21
`
`

`

`U.S. Patent
`US. Patent
`
`Sep.28,1999
`Sep. 28, 1999
`
`Sheet 8 of 8
`Sheet 8 0f 8
`
`5,959,989
`5,959,989
`
`Fm<0.._..._3_>_
`
`Zz
`~o
`> I-
`_J <(
`<( z
`z (!) --(!) Cl)
`-w
`a: 0
`0
`
`w
`(.) Cl)
`a: Cl)
`=>w
`0 a:
`(/)O
`...J 0
`<( <(
`z (.)
`(!) <(
`a: ~
`0
`
`Z<.._>._<Z_G_m0mOmDOm4<Z_0_m0
`
`
`
`
`ZO_._.<Z_._.mmomDOmw
`
`C\J
`C\J
`(.0
`\.__
`
`0
`C\J
`(.0
`\.__
`
`(.0
`,...
`(.0
`\.__
`
`V ,...
`<.O
`\.__
`
`,...
`C\J
`<.O
`\.__
`
`0 mJ
`
`
`
`
`
`ZO_._.<Z.O_mmowmmmoo<O<_>_
`
`z
`0
`-Cl)
`I- Cl)
`<( w
`z a:
`I- Cl
`(/)0
`~ <(
`a.. (.)
`::::, <(
`0~
`a:
`(!)
`
`wwwmoo<0.32
`
`a:
`I-
`Cl) w
`<( z u:::
`Z<._>
`O~-
`I-
`-
`I- >Z
`_J w
`0
`::::,
`~ -
`
`mmEszQ
`
`<0
`m.GE
`•
`(!J
`ti:
`
`EX.1025
`
`VERIZON / Page 9 of 21
`
`Ex.1025
`VERIZON / Page 9 of 21
`
`

`

`5,959,989
`
`1
`SYSTEM FOR EFFICIENT MULTICAST
`DISTRIBUTION IN A VIRTUAL LOCAL
`AREA NETWORK ENVIRONMENT
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to the distribution
`of messages in a computer network environment and, more
`specifically, to the efficient distribution of multicast mes(cid:173)
`sages.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`VLAN designations with messages transmitted from any of
`the ports to which the VLAN designation has been assigned.
`The VLAN designation for each internal port is stored in a
`memory portion of the switch such that every time a
`5 message is received by the switch on an internal port the
`VLAN designation of that port is associated with the mes(cid:173)
`sage. Association is accomplished by a flow processing
`element which looks up the VLAN designation in a memory
`based on the internal port where the message originated.
`In many cases, it may be desirable to interconnect a
`plurality of these switches in order to extend the VLAN
`associations of ports in the network. Ross, in fact, states that
`an objective of his VLAN arrangement is to allow all ports
`and entities of the network having the same VLAN desig-
`15 nation to interchange messages by associating a VLAN
`designation with each message. Thus, those entities having
`the same VLAN designation function as if they are all part
`of the same LAN. Message exchanges between parts of the
`network having different VLAN designations are specifi-
`20 cally prevented in order to preserve the boundaries of each
`VLAN segment.
`FIG. lA illustrates a conventional computer network 100
`comprising a plurality of LANs 101-115. The LANs
`101-115, moreover, are interconnected by a plurality of
`switches 117-122. More specifically, each LAN 101-115 is
`preferably coupled to a specific internal port 116 of switches
`117-122. The network 100 may also include a plurality of
`routers 123, 124, such that a router (e.g., router 123) is
`associated with a given segment of the network 100 (e.g.,
`30 LANs 101-108). Switches 117-122 and routers 123,124 are
`typically interconnected by trunk lines 128-133, which may
`be point-to-point links. Trunk lines 128-133 are typically
`coupled to specific external ports 125 of switches 117-122
`and routers 123, 124.
`Utilizing the system disclosed in the '402 Patent, various
`LANs may be grouped together to form VLANs. As shown
`in FIG. lA, each VLAN may be identified by a color code,
`e.g., "R" for red, "B" for blue, "G" for green, "Y" for yellow
`and "O" for orange. More specifically, switches 117-122
`associate each internal port 116 with at least one VLAN
`color tag. For example, switches 117 and 119 may each
`associate their ports coupled to LANs 102, 103 and 107 with
`the "red" VLAN designation, thereby grouping these LANs
`together. Since all entities located on a given LAN (e.g.,
`LAN 102) utilize the same shared port 116 of the corre(cid:173)
`sponding switch 117, moreover, each of these entities is also
`associated with the VLAN designation(s) assigned to that
`port ( e.g., red).
`Each external port 125 of switches 117-122 is similarly
`associated with one or more VLAN designation(s). The
`VLAN designations associated with external ports 125 cor(cid:173)
`respond to the VLANs that are reachable through that
`external port 125. For example, switch 117 may associate its
`55 one external port 125 with the red VLAN designation,
`among others, to reflect that one or more LANs (e.g., LAN
`107) associated with the red VLAN designation is "behind"
`that port.
`To identify the various VLAN designations defined
`throughout the network 100, switches 117-122 and routers
`123, 124 typically participate in a VLAN configuration
`protocol. In accordance with the protocol, each switch
`117-122 periodically transmits information regarding the
`VLAN designation(s) assigned to its internal ports 116.
`Upon receipt, the other switches 117-122 typically utilize
`this information to assign VLAN designations to their
`external ports 125.
`
`25
`
`35
`
`Many organizations, including businesses, governments
`and educational institutions, utilize computer networks in
`order to share and exchange information. A computer net(cid:173)
`work typically comprises a plurality of entities intercon(cid:173)
`nected by means of a communications media. An entity may
`consist of any device, such as a computer, that "sources"
`(i.e., transmits) or "sinks" (i.e., receives) data frames over
`the communications media. A common type of computer
`network is a local area network ("LAN") which typically
`refers to a privately owned network within a single building
`or campus. LANs typically employ a data communication
`protocol (LAN standard), such as Ethernet, FDDI or token
`ring, that defines the functions performed by data link and
`physical layers of a communications architecture (i.e., a
`protocol stack).
`In many instances, several LANs may be interconnected
`by point-to-point links, microwave transceivers, satellite
`hook-ups, etc. to form a wide area network ("WAN") or
`subnet that may span an entire country or continent. One or
`more network devices are often used to couple LANs
`together and allow the corresponding entities to exchange
`information. For example, a network switch may be utilized
`to provide a "switching" function for transferring
`information, such as data packets, among entities of a
`computer network. Typically, the switch is a computer and
`includes a plurality of ports that couple the switch to the
`other entities. The switching function includes receiving
`data at a source port from an entity and transferring that data 40
`to at least one destination port for receipt by another entity.
`Another network device is referred to as a router. A router
`is often used to interconnect LANs executing different LAN
`standards and/or to provide higher functionality than the
`switches, such as efficient message routing. To perform these 45
`tasks, a router, which is also often a computer, typically
`examines the destination address and source address of all
`packets passing through the router. Routers typically operate
`at the network layer of the protocol stack, such as the
`Transmission Control Protocol/Internet Protocol ("TCP/IP") 50
`reference model. If the LAN standards associated with the
`source entity and the destination entity are dissimilar ( e.g.,
`Ethernet and Token Ring), the router may alter the format of
`the packet so that it is in conformance with the standard
`corresponding to the destination entity.
`An arrangement that is capable of associating any port of
`a switch with any particular segregated network group is
`disclosed in U.S. Pat. No. 5,394,402, issued on Feb. 28,
`1995 to Floyd E. Ross (the "'402 Patent"). According to the
`'402 Patent, any number of physical ports of a particular 60
`switch may be associated with any number of groups within
`the switch by using a virtual local area network (VLAN)
`arrangement that virtually associates the port with a particu-
`lar VLAN designation. Specifically, Ross discloses a switch
`or hub for a segmented virtual local area network with 65
`shared media access that associates VLAN designations
`with at least one internal port and further associates those
`
`Ex.1025
`VERIZON / Page 10 of 21
`
`

`

`5,959,989
`
`3
`As set forth in the '402 Patent, any entity associated with
`the red VLAN designation may exchange messages with any
`other similarly designated entity, even though the two enti(cid:173)
`ties may be physically remote from each other and associ(cid:173)
`ated with switches that are coupled to other VLANs. For
`example, assume that entity 17 which is coupled to a "red"
`internal port 116 at switch 117 wishes to send a message
`(i.e., a unicast message) to entity 18 coupled to a "red" port
`at switch 119. As shown in FIG. lB, entity 17 generates a
`message 150, which typically includes a start flag 151, a
`destination address 152 ( corresponding to entity 18), a
`source address 154 ( corresponding to entity 17), information
`156 comprising the message and an end of message flag 158.
`Entity 17 then drives message 150 on the corresponding
`LAN 103.
`Switch 117 receives the message on an internal port 116
`associated with the red VLAN and, as shown in FIG. lC,
`attaches a red VLAN designation field 160 to the message
`150. Although the VLAN designation 160 is shown
`appended to the message 150, those skilled in the art will
`understand that it may be attached at any point within the
`message. Switch 117 also examines the destination address
`( entity 18) and determines that network entity 18 is not
`coupled to an internal port 116 of switch 117, but that its one
`external port 125 is associated with the red VLAN
`designation, among others. Accordingly, switch 117 drives
`message 150 with VLAN designation 160 onto port 125.
`Switch 117 may additionally encapsulate message 150 for
`transmission over trunk 128.
`Message 150 is next received at switch 118. Since the 30
`only port on switch 118 associated with the red VLAN
`designation ( other than the port on which the message
`arrived) is its second external port 125 ( corresponding to
`trunk 129), the message 150 is switched to that port for
`transmission to switch 119. Upon receiving the message, 35
`switch 119 examines the VLAN designation 160 and desti(cid:173)
`nation address 152 and determines that it corresponds to
`entity 18 which resides on LAN 107. Switch 119 further
`determines that "red" VLAN designation of the message 150
`matches the designation associated with the internal port 116 40
`coupled to LAN 107. Accordingly, switch 119 strips off the
`VLAN designation field 160 and drives message 150 onto
`internal port 116 coupled to LAN 107.
`To improve the flexibility of network 100, it is desirable
`to support the transmission of message to a predefined group 45
`of entities, including entities of diverse VLAN designations.
`Such a message is known as a group multicast message. For
`example, a group of entities (e.g., entities 18-25) may wish
`to receive certain types of messages originating from entity
`17. These entities typically register with one or more mul- 50
`ticast routers ( e.g., router 123) which controls the transmis(cid:173)
`sion of messages across VLAN boundaries. Router 123 may
`employ a security mechanism to prevent entities having a
`particular VLAN designation from subscribing to multicast
`messages to which they not entitled.
`Registration may be accomplished via the Internet Group
`Management Protocol (IGMP) which defines operations that
`may be used by entities to join a group (e.g., JoinGroup). To
`limit the amount of traffic, only one entity per LAN typically
`transmits such a request. Other interested entities will rely 60
`on the first subscription request to cause the message to be
`delivered to the LAN, thereby making it available to all
`interested entities. The switches may perform additional
`filtering such that router 123 receives only one subscription
`request per VLAN. In response, router 123 creates a sub- 65
`scription list (not shown) associating each group multicast
`address with the list of VLANs on which at least one
`
`4
`subscribing entity resides. Thereafter, entity 17 utilizes this
`group destination address to send multicast messages to the
`subscribing entities.
`Switches 117-122 may also monitor the IGMP messaging
`5 between entities and multicast router 123 to learn which
`ports 116, 125 lead either to a router or to at least one entity
`subscribing to a particular group multicast address. As
`discussed above, however, switches 117-122 may not
`exchange messages between segments of the network 110
`associated with different VLAN designations (e.g., between
`entities associated with the red and blue VLANs). To support
`cross-VLAN traffic, switches 117-122 deliver all multicast
`messages to the multicast router 123.
`Entity 17 generates a multicast message by entering the
`15 predefined group multicast address in the destination address
`field 152 (FIG. lB). The multicast message is then driven on
`LAN 103 and received by switch 117. As with unicast
`messages, switch 117 attaches the corresponding VLAN
`designation 160 associated with the port 116 on which the
`20 message was received. Switch 117 also determines that the
`message is a group multicast message and (assuming the
`switch participates in IGMP) accesses its subscription list to
`determine which internal and external ports 116, 125 are
`associated with this address. Since only LAN 103 and trunk
`25 128 are associated with this group multicast address and the
`message was received from LAN 103, switch 117 drives the
`message onto trunk 128 via external port 125 where it is
`received by switch 118.
`Switch 118 examines the destination address of the mes(cid:173)
`sage and its own subscription list which indicates that LAN
`106 and trunks 128 and 129 are associated with this group
`multicast address. The "red" VLAN designation of the
`message, however, does not match the "blue" VLAN des(cid:173)
`ignation associated with the internal port 116 coupled to
`LAN 106 and thus switch 118 is precluded from forwarding
`the message onto this internal port 116. Furthermore, since
`the message was received on trunk 128, switch 118 simply
`drives the message onto its external port 125 coupled to
`trunk 129.
`Switch 119 receives the message, examines the VLAN
`designation and destination address and determines that
`LAN 107 and trunks 129 ( on which the message was
`received), 130 and 131 are associated with this group
`multicast address. Here, the red VLAN designation of the
`message matches the VLAN designations associated with
`port 116 coupled to LAN 107 and with port 125 coupled to
`trunk 130, but not with port 125 coupled to trunk 131.
`Accordingly, switch 119 strips off the VLAN designation
`field 160 and forwards the message onto internal port 116 for
`transmission over LAN 107. Switch 119 also drives the
`message with the VLAN designation field 160 on its external
`port 125 coupled to trunk 130 for receipt by multicast router
`123.
`Multicast router 123 examines the message and deter(cid:173)
`mines that it is a "red" multicast message from entity 17.
`Router 123 accesses its subscription list and determines this
`group multicast address is associated with the red, blue,
`green, yellow and orange VLANs. Since the VLAN desig(cid:173)
`nation of the message matches one of the associated VLANs
`(i.e., red), router 123 presumes that message has already
`been delivered to the subscribers on that VLAN (e.g., entity
`19). That is, switches 117-122, as described above, are able
`to deliver multicast messages in which the VLAN designa(cid:173)
`tion of the message matches the VLAN designation of the
`subscribing entities. Thus, multicast router 123 need not
`forward multicast messages to the same VLAN designation
`
`10
`
`55
`
`Ex.1025
`VERIZON / Page 11 of 21
`
`

`

`5,959,989
`
`5
`
`5
`as the sourcing entity. Because switches 117-122 were
`precluded from forwarding the multicast message across
`non-matching VLANs, router 123 proceeds to forward the
`message to those VLANs (i.e., the blue, green, orange and
`yellow VLANs).
`To deliver multicast messages to subscribers of diverse
`VLAN designations, router 123 must create a separate
`message for each of the remaining VLAN designations. That
`is, router 123 creates four identical copies of the message,
`each with a different VLAN designation attached thereto 10
`(i.e., blue, green, yellow and orange). Each copy is then sent
`out on the network 100 by router 123.
`As these messages are received by the switches 118-122,
`they are directed to internal ports associated with the cor(cid:173)
`responding blue, green, yellow or orange VLAN designa(cid:173)
`tions to which a subscribing entity is coupled. That is, the 15
`first copy having the blue VLAN designation is received and
`sent out by switch 118 on the "blue" port 116 coupled to
`LAN 106 (for receipt by entities 19 and 20). The second
`copy is forwarded by switch 119 on its "green" port 116
`coupled to LAN 108 for receipt by entity 21. Similarly, the 20
`third copy of the message is delivered to entities 22 and 23
`associated with the yellow VLAN at switch 120 and the
`fourth copy to entities 24 and 25 associated with the orange
`VLAN at switches 120 and 122. In this manner, the message
`is transmitted to all LANs on which at least one subscribing 25
`entity resides.
`Although the prior art arrangement as described above is
`capable of delivering multicast messages to entities of
`diverse VLAN designations, it nonetheless has certain dis(cid:173)
`advantages. First, the arrangement requires that the same 30
`message be copied multiple times by the multicast router;
`one copy for each VLAN associated with the message, In
`addition, each copy must be placed on the trunk line(s)
`linking the multicast router to the computer network.
`Depending on the number of VLAN designations associated 35
`with a given group multicast address, this may severely
`compromise the throughput on this trunk line. Multicast
`messaging may thus subject the network to substantial
`performance penalties, limiting the benefits of having estab(cid:173)
`lished virtual local area networks.
`SUMMARY OF THE INVENTION
`It is an object of the present invention to provide an
`efficient mechanism for distributing multicast messages.
`It is a further object of the present invention to provide an
`efficient mechanism for distributing multicast messages in a
`virtual local area network environment.
`It is a further object of the present invention to reduce the
`number of messages that must be sent to accomplish mul(cid:173)
`ticasting.
`The invention relates to a mechanism for efficiently
`distributing multicast messages to subscribing entities via
`group multicast addresses in a computer network having a
`plurality of virtual local area network (VLAN) designations
`among those entities. The mechanism comprises a multicast
`network device (MND) configured to generate a multicast
`VLAN (MYLAN) identifier (ID) for each unique combina(cid:173)
`tion of VLANs to which any multicast group address is to be
`directed. The MYLAN ID preferably encompasses all
`VLAN designations of the entities subscribing to a multicast
`message stream, except for the VLAN designation of the
`entity or entities sourcing the multicast messages, The
`MYLAN ID, along with its corresponding VLAN
`designations, is then propagated to intermediate devices of
`the network and attached to subsequent multicast messages
`to enable efficient distribution of those messages over the
`network.
`
`6
`In the illustrative embodiment, the MND coordinates
`distribution of multicast messages by storing associations of
`VLAN designations and group multicast addresses. Asso(cid:173)
`ciations are entered when the MND receives a subscription
`request across a VLAN on which at least one subscribing
`entity resides and deleted when the MND receives corre(cid:173)
`sponding cancellation requests. An entity preferably com(cid:173)
`prises a host computer that sends and/or receives informa-
`tion over the network. Thereafter, the MND examines the
`VLAN designations associated with each group multicast
`address and accesses a multicast VLAN tag source to
`establish at least one MYLAN ID for use in distributing
`messages to those associated VLANs. The MYLAN ID with
`its corresponding VLAN designations is then propagated to
`the intermediate devices via advertisement messages over
`the network. An intermediate device preferably comprises a
`switch for forwarding information, including the multicast
`messages, to the entities.
`In response to the advertisements, the intermediate
`devices modify their VLAN association tables in order to
`associate the MYLAN ID with its corresponding VLAN
`designations for subsequent multicast message handling.
`That is, each intermediate device updates its VLAN asso(cid:173)
`ciation table to add the MYLAN ID as if it were another
`VLAN designation to any ports (internal or external) that are
`associated with any of the VLAN designations correspond(cid:173)
`ing to that MYLAN ID. The intermediate devices may also
`maintain subscription information by monitoring subscrip(cid:173)
`tion and cancellation request exchanges between the MND
`and the entities. Accordingly, the intermediate devices may
`also know which ports, internal and external, are to receive
`a particular multicast message stream.
`Thereafter, upon receipt of a multicast message, the
`intermediate device adjacent to the entity sourcing the
`message attaches the VLAN designation associated with the
`port on which the message was received. Thereafter, the
`switches deliver the multicast message to the MND and all
`subscriber-ports sharing the same VLAN designation as the
`sourcing entity. Upon receipt, the MND creates a new
`message replacing the VLAN designation with the MYLAN
`40 ID corresponding to the remaining VLAN designations
`associated with the group multicast address. The MND then
`forwards this multicast message to the appropriate interme(cid:173)
`diate devices, each of which references its VLAN associa(cid:173)
`tion table to deliver the message to the remaining subscriber-
`45 ports.
`Specifically, each particular intermediate device identifies
`the ports that are to receive the multicast message and
`determines whether those ports are associated with the
`MYLAN ID attached to the message. As noted, all
`50 subscriber-ports (except those sharing the same VLAN
`designation as the message sender) have been associated
`with the MYLAN ID as a result of the prior advertisements.
`A message having an MYLAN ID and group multicast
`address that correspond to an internal port ( e.g., a port
`55 coupled to a LAN containing subscribing entities), is for(cid:173)
`warded directly to that port by the intermediate device after
`removing the MYLAN ID. A message having an MYLAN
`ID and group destination address that correspond to an
`external port is forwarded to that external port with the
`60 MYLAN ID still in place. If the MYLAN ID does not
`correspond to a port that nonetheless subscribes to the
`message (e.g., because the port shares the same VLAN
`designation as the sourcing entity and thus already received
`the message), the intermediate device does not forward the
`65 message to that port.
`In an alternate embodiment of t