(12) United States Patent
`Borgione
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,586,895 B2
`Sep. 8, 2009
`
`US007586895B2
`
`(54) PERFORMING EXTENDED LOOKUPS ON
`MAC-BASED TABLES INCLUDINGLEVEL3
`MULTICAST GROUP DESTINATION
`ADDRESSES
`
`(*) Notice:
`
`(75) Inventor: Gaetano Borgione, San Jose, CA (US)
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 562 days.
`(21) Appl. No.: 11/096.738
`(22) Filed:
`Apr. 1, 2005
`
`(65)
`
`Prior Publication Data
`US 2006/022196.0 A1
`Oct. 5, 2006
`
`(51) Int. Cl.
`(2006.01)
`H04L 2/56
`(2006.01)
`H04L 2/28
`(2006.01)
`H04.3/16
`(2006.01)
`H043/24
`(52) U.S. Cl. ....................... 370/349; 370/389; 370/392;
`370/471; 370/474
`(58) Field of Classification Search ................. 370/349,
`370/389, 471, 474
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`1/2000 Varghese et al. ............ 370,392
`6,011,795 A *
`1/2000 Turner et al. ................ 370,392
`6,018,524. A
`6,526,055 B1* 2/2003 Perlman et al. ............. 370,392
`6,563,823 B1* 5/2003 Przygienda et al. ......... 370,392
`6,697.363 B1
`2/2004 Carr ........................... 370,389
`6,697.380 B1* 2/2004 Egbert et al. ................ 370/469
`
`- - - - - - 707/6
`
`6,876,655 B1 * 4/2005 Afek et al. .................. 370,392
`5/2006 Singh et al. .......
`7,039,018 B2*
`... 370,255
`7,054,993 B1*
`... 711.108
`5/2006 Srinivasan et al.
`7,089,240 B2 * 8/2006 Basso et al. ....
`... 370,392
`7,116,663 B2 * 10/2006 Liao ..............
`... 370,392
`7,260,096 B2 * 8/2007 Basso et al. .......
`... 370,389
`2003/0235191 A1* 12/2003 Heggarty et al. ..
`2004/0013113 A1
`1/2004 Singh et al. ................. 370,389
`OTHER PUBLICATIONS
`S. Deering et al., “Host Extensions for IP Multicasting”. Aug. 1989,
`IETF Standard (RFC 1112), Internet Engineering Task Force.*
`S. Bhattacharyya et al., “An Overview of Source-Specific Multicast
`(SSM)”, Jul. 2003, IETF Standard (RFC 3569), Internet Engineering
`Task Force.
`
`
`
`(Continued)
`Primary Examiner Kwang BYao
`Assistant Examiner—Adam Duda
`(74) Attorney, Agent, or Firm—Campbell Stephenson LLP
`
`ABSTRACT
`(57)
`A method, system, and computer program product are pre
`sented to optimize OSI Level 2 switch forwarding of frames
`comprising IP addresses, 802.1 QinC VLAN identifiers,
`multi-protocol label switching labels, and any other usable
`information meaningful to derive an L2 forwarding result on
`frames. In one embodiment, a 16-bit key is included as a
`prefix to a 48-bit OSI Level 2 address entry, thereby allowing
`the inclusion of a 32-bit OSI Level 3 address in the lookup
`table (e.g., a complete IP version 4 address). Implementations
`of Such a solution are presented to resolve address aliasing
`issues experienced with multicast group destination
`addresses, including single source multicast. Solutions to
`optimizing forwarding of frames in an IEEE 802.1 QinC
`environment are also presented. A result of these implemen
`tations can be reduction of the amount of unnecessary net
`work traffic generated by a network Switch incorporating
`such an OSI Level 2 address lookup table.
`
`16 Claims, 12 Drawing Sheets
`
`O
`
`8
`
`16
`
`-1 500
`
`48
`
`fig Bit 510
`
`Key 520
`
`3 GDA
`530
`
`Ex.1017
`VERIZON / Page 1 of 22
`
`

`

`US 7,586.895 B2
`Page 2
`
`OTHER PUBLICATIONS
`The Cable Guy, “Overview of IP Multicast”, Feb. 2002, Microsoft
`TechNET, pp. 1-5.*
`Firewall.cx et al., “Introduction to Multicast”, Apr. 21, 2003,
`Firewall.cx, all pages.*
`International Search Report as mailed from the PCT on Dec. 7, 2006,
`for counterpart WO Application (PCT/US06/01 1607; Filed Mar. 29,
`2006), 5 pages.
`
`S. Deering, Network Working Group, RFC 1112, “Host Extensions
`for IP Multicasting.” IETF Standard, Internet Engineering Task
`Force, Aug. 1989, pp. 1-17.
`S. Bhattacharyya, Network Working Group, RFC 3569, "An Over
`view of Source-Specific Multicast (SSM).” IETF Standard, Internet
`Engineering Task Force, Jul. 2003, pp. 1-14.
`* cited by examiner
`
`Ex.1017
`VERIZON / Page 2 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 1 of 12
`
`US 7,586.895 B2
`
`
`
`
`
`
`
`
`
`120(3,1)
`
`
`
`
`
`
`
`110(2)
`
`110(3)
`
`110(1)
`
`
`
`
`
`110(N)
`
`110(5)
`
`
`
`120(4,1)
`
`110(4)
`
`120(4,2)
`
`Figure 1
`
`Ex.1017
`VERIZON / Page 3 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 2 of 12
`
`US 7,586.895 B2
`
`210
`
`-- Index
`
`220 ——
`
`MAC (L2) Address
`SMAC(120(1,1))
`SMAC(120(2,1))
`SMAC(120(22))
`SMAC(120(3,1))
`SMAC(120(N.1)
`Figure 2
`
`230 --
`
`Port
`110(1)
`110(2)
`110(2)
`110(3)
`110(N)
`
`410 --
`
`Index
`1
`2
`
`420 — —
`
`MAC (L2) Address
`SMAC(120(1,1))
`SMAC(120(2,1))
`
`430 -
`
`Port
`110(1)
`110(2)
`
`P
`P+1
`P-2
`
`SMAC(120(N,1))
`01:00:5e:7f:00:01
`01:00:5e:XX:XXXX
`
`110(N)
`110(1), 110(3)
`110(1),..., 110(N)
`
`440
`
`450
`
`465
`
`460
`
`Figure 4
`
`470
`
`Ex.1017
`VERIZON / Page 4 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 3 of 12
`
`US 7,586.895 B2
`
`—128 bits—
`ff02:O:C::705f:OOO1 -"
`—32 bits—
`33:33.70:5f:00:01-1"
`-
`48 bits
`
`Figure 3
`
`Key 520
`
`Ex.1017
`VERIZON / Page 5 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 4 of 12
`
`US 7,586.895 B2
`
`600 (-) 610
`
`650
`
`Figure 6
`
`Ex.1017
`VERIZON / Page 6 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 5 of 12
`
`US 7,586.895 B2
`
`740
`
`750
`
`710
`
`Index
`
`2
`
`P
`P-1
`P-2
`PQ
`P+Q+1
`P+Q+1
`
`720
`
`MAC (L2) Address
`SMAC(120(1,1))
`SMAC(120(2,1))
`
`SMAC(120(N, 1))
`KEY1 GROUP(1)
`KEY1|GROUP(2)
`KEY1|GROUP(Q)
`KEY2(1)SOURCE(1,1)
`KEY2(1)SOURCE(1,2)
`
`760
`
`P+Q+R
`P+Q+R+1
`
`KEY2(1)SOURCE(1,R)
`KEY2(2)SOURCE(2,1)
`
`Figure 7
`
`Port
`110(1)
`1 10(2)
`
`110(N)
`List(1)
`List(2)
`List(Q)
`SList(1,1)
`SList(1,2)
`
`SList(1,R)
`SList(2,1)
`
`910
`
`920
`
`925
`
`Index
`1
`935
`P+1
`940
`950 ( P-M-1
`955 ( P-Mo-1
`
`MAC (L2) Address Bridge Domain
`SMAC(120(1,1))
`PE VLAN
`KEY1GROUP(1)
`PE VLAN
`KEY2CE VLAN
`KEY3CE VLAN
`
`PE VLAN
`
`Port
`110(1)
`List(1)
`List(2)
`List(3)
`
`Figure 9
`
`Ex.1017
`VERIZON / Page 7 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 6 of 12
`
`US 7,586.895 B2
`
`CE VLAN(2,1)
`842
`
`CE VLAN(2.2)
`844
`
`CE VLAN(1,2)
`824
`
`CE VLAN(1,1)
`822
`
`
`
`CE VLAN (1,3)
`826
`
`C
`820
`
`CE VLAN(1,4)
`828
`
`PE VLAN.(2)
`
`PE VLAN(1)
`860
`
`CE VLAN(1,1)
`832
`
`CE VLAN(1,1)
`834
`
`C1
`830
`
`850
`
`CE. VLAN(2,1)
`852.
`
`CE. VLAN(2.2)
`854
`
`CE VAN(1.2)
`836
`
`Figure 8
`
`Ex.1017
`VERIZON / Page 8 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 7 of 12
`
`US 7,586.895 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Receive Multicast
`Administration Message
`
`Read IP Multicast Group
`Destination Address
`(IP GDA)
`
`Form L2 GRP Address using
`a Key and IP GDA
`
`1005
`
`010
`
`105
`
`SL2 GRP in Table?
`
`Read P Multicast Source
`Address
`
`Perform Administration
`Operation Specified in Admin
`Message on 2 GRP Table
`Entry
`
`Add 2 GRP to New Entry in
`Table and Perform
`Administration Operation
`
`Form L2 SRC from 2GRP
`index and P Multicast
`Source Address
`
`ls Message an SSM
`Admin Message?
`
`is 2 SRC in Table?
`
`Add 2 SRC to New Entry in
`Table and Perform
`Administration Operation
`
`
`
`Perform Administration
`Operation Specified in Admin
`Message on L2 SRC Table
`Entry
`
`Figure 10
`
`Ex.1017
`VERIZON / Page 9 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 8 of 12
`
`US 7,586.895 B2
`
`Receive Muticast Frame
`
`Read L3 Group Destination
`Address
`(L3 GDA)
`
`Fom L2 GRP using
`Key and L3 GDA
`
`1105
`
`1110
`
`1115
`
`1125
`
`
`
`
`
`1120
`
`Drop or Broadcast Frame
`
`No
`
`is 2 GRP in Table?
`
`Figure 11
`
`
`
`
`
`
`
`Yes
`
`Read 3 Source. Address
`from Frame (if Any)
`
`Form L2 SRC using 2GRP
`Index and L3 Source
`Address
`
`1130
`
`1140
`
`1150
`
`ls 2 SRC in Table?
`
`Yes
`
`Replicate Frame as Needed
`and Send to Ports
`Designated in L2 SRC Table
`Entry
`
`1160
`
`
`
`1155
`
`Drop or Replicate Frame as
`Needed and Send to Ports
`Designated in 2GRP table
`Entry
`
`Ex.1017
`VERIZON / Page 10 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 9 of 12
`
`US 7,586.895 B2
`
`1205
`
`1210
`
`1215
`
`1220
`
`1225
`
`Receive Multicast Frame
`
`Read L3 Group Destination
`Address (L3 GDA) from
`Frame
`
`Derive or Read PE. VLAN
`Designation for Frame
`
`Read CE WAN Designation
`from Frame
`
`Form L2 GRP from Key1 and
`PGDA
`
`ls
`L2 GRP + PE VLAN
`in Table?
`
`Figure 1 2
`
`Form 2 CVAN. Address
`from L2 GRP + PE. VLAN
`Entry index and CE VLAN
`Designation
`
`1240
`
`No
`
`|
`
`
`
`
`
`ls 2 CVLAN in Table?
`
`Drop or Broadcast Frame
`
`1235
`
`1245
`
`1255
`
`Drop or Replicate Frame as
`Needed and Transmit to
`Ports Designated in L2 GRP
`Entry
`
`
`
`Replicate Frame as Needed
`and Transmit to Ports
`Designated in l2 CVLAN
`Entry
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ex.1017
`VERIZON / Page 11 of 22
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 10 of 12
`
`US 7,586.895 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Receive Unicast CinC Frate
`
`Read estination MAC
`(DMAC) from Frame
`
`Read or Derive PE VLAN
`Designation for Frame
`
`Read CE VLAN Designation
`from Frame
`
`1305
`
`1310
`
`1315
`
`1320
`
`
`
`
`
`
`
`is
`DMAC +PE VLAN
`in Table?
`
`Send Frame to Port
`Designated in Table
`
`1335
`
`
`
`1350
`
`
`
`
`
`
`
`Figure 1 3
`
`Form Qino Flood Address
`from KEY3+ CE VLAN
`Designation
`
`1340
`
`1345
`
`
`
`ls Qino Flood+
`PE VLAN in Table?
`
`Drop or Broadcast on
`PE VLAN
`
`
`
`Replicate Frame as Needed
`and Transmit to Ports
`Designated in Qino Flood
`Entry
`
`Ex.1017
`VERIZON / Page 12 of 22
`
`

`

`fig33m
`
`3am:$829:
`
`
`
`
`
`
`
`
`
`83.25{9225:380o\_roams.829688821@250
`
`U.S. Patent
`
`90028,
`
`n
`
`nf
`
`m
`
`Eggw
`
`S0?:92EU95in30.308:...
`
`%as?w,x.9.Ho”awx53323‘2:9".
`7965.20
`
`m«ES83adgm:5fig38m:8.23
`
`$3.aa'3:
`
`0I
`
`.388an:44IS;I8:mfi/.2m58inBE28ng882:885&5
`
`
`
`
`mINN:llmmm:lgm:lug:ma$3$3
`
`
`
`
`
`«Moomtmio_u=<$1$1momtmfi092on5:280Emogoxtomfitow56mg5&5
`
`EX.1017
`
`VERIZON / Page 13 of 22
`
`Ex.1017
`VERIZON / Page 13 of 22
`
`
`
`

`

`U.S. Patent
`
`Sep. 8, 2009
`
`Sheet 12 of 12
`
`US 7,586.895 B2
`
`0091 º
`
`Keluw
`069||
`
`
`
`G?, aun61-I
`
`
`
`
`
`
`
`
`
`Ex.1017
`VERIZON / Page 14 of 22
`
`

`

`US 7,586,895 B2
`
`1.
`PERFORMING EXTENDED LOOKUPS ON
`MAC-BASED TABLES INCLUDINGLEVEL3
`MULTICAST GROUP DESTINATION
`ADDRESSES
`
`FIELD OF THE INVENTION
`
`The field of this invention relates to information networks.
`Specifically, a method, system, and apparatus are presented to
`provide a representation of a 32-bit address in an OSI Level 2
`switch address table; thus, allowing for the inclusion of a full
`IPv4 Multicast Address in the OSI Level 2 switch address
`table, thereby eliminating address aliasing.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`2
`administrator or can be dynamically determined within the
`environment that the network node resides. In version four of
`the internet protocol (IPv4), L3 addresses are 32 bits in
`length, while in internet protocol version 6 (IPv6), L3
`addresses are 128 bits in length. When transmitted over a
`network, an OSI Level 3 packet will be encapsulated within
`an OSI Level 2 frame, therefore such frames can contain both
`L2 and L3 Source and destination addresses.
`FIG. 2 illustrates a L2 address table showing the node-port
`associations of switch 100. Each entry in the table has an
`associated index 210. The number of entries in the table can
`be equal to the number of nodes connected to switch 100 (e.g.,
`P). Each entry in the table contains a MAC address 220 that
`corresponds to a source MAC address found in frames trans
`mitted by each node (e.g., SMAC (120(1,1)) is the source
`MAC address for node 120(1,1)). Each L2 address table entry
`also includes a port 230 corresponding to the node, wherein
`the association is made by switch 100 when it receives a frame
`from the network node. Information linking a node address
`with a particular port is related to the hardware of the node
`(e.g., a network interface) and is typically static in a L2
`address table, unless a node is physically moved from one
`port to another port on the switch.
`An L2 address table cannot automatically be populated
`with multicast destinations as done with node-port designa
`tions. This is because a multicast GDA cannot be a source
`MAC address. Portions of L3 multicast GDAs are included in
`an L2 address table through the use of software protocols such
`as the internet group management protocol (IGMP). When a
`network node wishes to Subscribe to a multicast transmission,
`a special IGMP protocol frame is transmitted as a multicast
`“join” request. An IGMP-enabled switch will have a "snoop
`ing software running on the Switch to read Such a frame and
`build a corresponding entry for the L2 address table. Such an
`entry can relate a form of the multicast GDA (an L3 address)
`with ports that are connected to Subscribing nodes.
`An IGMP frame contains an L3 GDA along with other
`information pertinent to the operation requested in the IGMP
`frame. Such an L3 address requires manipulation to be
`included in an L2 address table.
`FIG. 3 illustrates a manipulation of IPv4 and IPv6 multi
`cast group destination addresses into a form acceptable for
`inclusion into entries of an L2 address table. An IPv4 GDA is
`32 bits in length and falls in the range of addresses 224.0.0.0-
`239.255.255.255. Such an IP address is illustrated at 310 in
`FIG. 3. As stated above, an L2 address is limited to 48 bits,
`which is split into two 24bit segments. The first three octets
`(the first 24bits) of an L2 MAC multicast address are set to
`01:00:5E (325). To create an L2 MAC multicast address for
`the L2 address table corresponding to an L3 GDA, the last 23
`bits of the L3 GDA are inserted into the last 23 bits of the
`MAC address 320. Since a portion of the 32 bit IPv4 address
`is being inserted into the 23 bit area of the MAC address, nine
`bits of information are lost from the IPv4 address. Five of the
`nine bits are significant, since the first four bits of any IPv4
`multicast address are always 1110. Such loss of information
`is referred to as address aliasing, since more than one L3 GDA
`can be represented by a single L2 MAC multicast address.
`(For example, an IPv4 GDA 239.255.0.1 will share an L2
`MAC multicast address with other IPv4 GDAs such as
`238.255.0.1 and 239.127.0.1.) The address aliasing problem
`is magnified with IPv6 GDAs as illustrated in 330 and 340. An
`IPv6 address 330 is 128 bits in length, and therefore 80
`significant bits are lost in the transition from an L3 IPv6 GDA
`to a L2 MAC address.
`Address aliasing of multicast addresses can result in an
`increase in network traffic due to frames being sent to a first IP
`
`25
`
`30
`
`35
`
`40
`
`Today's network links carry vast amounts of information.
`High bandwidth applications supported by these network
`links include, for example, streaming video, streaming audio,
`and large aggregations of voice traffic. In the future, network
`bandwidth demands will increase. Certain applications. Such
`as streaming audio and streaming video, can generate a large
`amount of network traffic due to sending such a transmission
`to multiple subscribers. In order to help decrease network
`traffic load due to Such applications, multicast extensions to
`network protocols have been developed.
`Multicast protocols enable multicast transmission (i.e.,
`one-to-many connections) by replicating a multicast network
`frame close to the destination of that frame, obviating the
`need for multiple unicast connections for the same purpose,
`saving network bandwidth and improving throughput. Upon
`receiving a multicast frame, a network node can examine a
`multicast group destination address (GDA) of the frame and
`determine whether subscribers to the multicast frame are
`connected to the network node. The network node can then
`duplicate the multicast frame as needed and transmit the
`multicast frame to any connected Subscribing nodes.
`FIG. 1 is a simplified block diagram of a network switch
`100. The switch provides ports 110(1)-(N), wherein a net
`work frame arriving at any port can be directed to any other
`port connected to the Switch as determined by an examination
`of the frame's destination address. Connected to each port are
`network nodes 120(1,1)-(NM). In a typical network environ
`ment, each node 120(1,1)-(NM) has a unique media access
`control (MAC) address. Switch 100 can learn the MAC
`45
`addresses of network nodes 120(1,1)-(NM) as those nodes
`transmit frames to each other via the switch. Each frame
`transmitted by a network node contains a source MAC
`address that switch 100 can read and associate with a port
`110(1)-(N). Such node-port information is stored in an
`address table. Such a table has been called an L2 Address
`table (referring to Level 2 of the Open System Interconnec
`tion networking framework for implementing protocols,
`which is also called the data link layer) or a MAC Address
`table.
`Within the OSI network model a network node, or utilities
`on a network node, can have a different representation of its
`network address at each level of the model. Switch 100 can
`operate at Level 2 (L2) (i.e., the data link layer of the OSI
`model). These L2, or MAC addresses, of a network node are
`unique to each network interface on a network and are typi
`cally hardware encoded in the network interface. MAC
`addresses are 48 bits in lengths, containing a 24 bit vendor
`code followed by a 24bit hardware address. A network node
`can also have an OSI Level 3 address, which can include
`addresses such as internet protocol (IP) addresses. IP
`addresses are software encoded and can be supplied by an
`
`50
`
`55
`
`60
`
`65
`
`Ex.1017
`VERIZON / Page 15 of 22
`
`

`

`US 7,586,895 B2
`
`3
`multicast group also being sent to other IP multicast groups
`that share the same low order 23 bits in the L3 multicast
`addresses. Further, overhead at receiving nodes can be
`increased due to unsubscribing nodes having to drop frames.
`Both the increase in traffic and the dropping of frames results
`in a waste of network bandwidth resources. It is therefore
`desirable to construct multicast entries in an L2 address table
`in such a way that the loss of L3 GDA information is elimi
`nated or reduced, thereby allowing more extensive lookups
`for multicast frames.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`4
`thereby eliminating address aliasing of IPv4 multicast GDAs.
`Using Such an L2 address table will also optimize forwarding
`issues that arise in source specific multicast (SSM) and
`802.1Q-in-Q (QinCR) scenarios, through the use of chained
`address lookups. Such an increased address space in a L2
`address table can also serve to reduce address aliasing that
`occurs with IPv6 L3 multicast GDAs.
`Address aliasing and an increase in transmission of multi
`cast frames due to address aliasing is caused by the necessity
`of truncating a 32 bit IPv4 multicast GDA into a 23 bit space
`in an L2 address table entry. If a full 32 bit IPv4 multicast
`GDA (IPv4 GDA) can be included in that L2 address table
`entry, then no address aliasing will occur, nor will there bean
`increase in network multicast traffic due to Such network
`aliasing.
`The least significant bit of the first octet of a multicast MAC
`address is the so-called I/Gbit (individual/group bit). An I/G
`bit set to a 1 indicates that the address is a multicast or
`broadcast address. An I/G bit set to a 0 indicates that the
`address is a unicast address. A broadcast destination address
`is distinguished from a multicast destination address if all
`destination MAC address bits are set to 1 (e.g., the destination
`MAC address is ffff:ffff:ffff). Thus, the only part of a MAC
`address that is needed in order to identify it as a multicast
`address is an I/Gbit being set to a one. As stated above, when
`a multicast address is included in a L2 address table entry, the
`first 24 bits contain octets 01:00:5e. Since this is a fixed
`pattern, it can be compressed using some sort of key that
`retains the I/G bit set to 1; thereby avoiding any interference
`with L2 unicast addresses stored in the L2 address table.
`FIG. 4 illustrates an L2 address table including traditional
`MAC multicast destination addresses. As with FIG. 2 the
`table contains an initial set of Pentries, each containing index
`410, address 420 and port 430. The first set of unicast
`addresses 440 is received into the table as discussed above. A
`set of multicast destination addresses 450 is illustrated as
`additional entries (P+1) and (P+2). As illustrated, a generic
`MAC multicast destination address 460 includes: the initial
`octets 01:00:5e, followed by a subsequent set of three octets
`into which bits from the IPv4 GDA are inserted. Each multi
`cast entry is associated with a group of one or more ports
`linked to subscribing network nodes 470.
`FIG. 5 illustrates a format of a modified L2 address table
`entry for a multicast group address (L2 GRP) in accord with
`one embodiment of the present invention. As stated above, the
`L2 GRP table entry must include an I/G bit equal to one,
`where the I/G bit is the least significant bit of the first octet of
`the address entry. Entry 500 includes such an I/Gbit 510, but
`incorporates it within a 16 bit key 520, rather than in 32 bits
`containing octets 01:00:5e. By limiting the key to a total of 16
`bits, 32bits are made available for the inclusion of an L3 GDA
`S30.
`Use of a 16 bit key 520 rather than octets 01:00:5e is not
`disruptive to the utilization of an L2 address table. The mul
`ticast L2 GRP entries of the L2 address table will not be
`referenced unless looking up an IPv4 multicast address. Fur
`ther, since L2 GRP addresses are dynamic and entered by
`Software, changes to the hardware need not be made to
`accommodate the L2 GRP entries in an L2 address table.
`In the event that a multicast frame (I/Gbit=1) containing a
`destination MAC address that includes a match to key 520
`arrives at a network device utilizing the above L2 address
`table, incorrect forwarding to multicast Subscriber ports can
`result. A Solution can be either to broadcast the incoming
`frame to all nodes on the corresponding broadcast domain
`(e.g., a VLAN) or to drop the frame, depending upon the
`specific implementation. Such a decision can be made prior to
`
`The present invention may be better understood, and its
`numerous objects, features and advantages made apparent to
`those skilled in the art by referencing the accompanying
`drawings.
`FIG. 1 illustrates a simplified block diagram of a network
`switch.
`FIG. 2 illustrates a L2 address table showing the node-port
`associations of a switch such as that illustrated in FIG. 1.
`FIG. 3 illustrates a manipulation of IPv4 and IPv6
`addresses into a form acceptable for inclusion into entries of
`an L2 address table.
`FIG. 4 illustrates an L2 address table including traditional
`MAC multicast destination addresses.
`FIG. 5 illustrates a format of a modified L2 address table
`entry for a multicast group address in accord with one
`embodiment of the present invention.
`FIG. 6 is a simplified block diagram illustrating the concept
`of source specific multicasting (SSM) as addressed by one
`embodiment of the present invention.
`FIG. 7 illustrates an example of an L2 address table incor
`porating entries modified in accord with one embodiment of
`the present invention for use in resolving Source specific
`multicast.
`FIG. 8 is a simplified block diagram illustrating the use of
`provider VLANs to transport customer VLANs.
`FIG. 9 illustrates an L2 address table incorporating ele
`ments to allow QinC address resolution in accord with one
`embodiment of the present invention.
`FIG. 10 is a simplified flow diagram illustrating steps that
`can be taken to populate an L2 address table with 32-bit L3
`GDA fields in accord with one embodiment of the present
`invention.
`FIG. 11 is a simplified flow diagram illustrating a L2
`address table lookup for multicast, including SSM, frames in
`accord with one embodiment of the present invention.
`FIG. 12 is a simplified flow diagram illustrating a method
`for table lookup to resolve multicast addressing in a QinC
`environment in accord with one embodiment of the present
`invention.
`FIG. 13 is a simplified flow diagram illustrating a method
`for table lookup to resolve unicast addressing in a QinC
`environment in accord with one embodiment of the present
`invention.
`FIG. 14 depicts a block diagram of a computer system
`Suitable for implementing the present invention.
`FIG. 15 is a block diagram depicting a network architecture
`Suitable for implementing the present invention.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`DETAILED DESCRIPTION
`
`The present invention provides for the availability of at
`least 32 bits of addressing information in multicast entries of
`an L2 address table. This will permit the inclusion of a full
`IPv4 multicast GDA in the entries of the L2 address table,
`
`65
`
`Ex.1017
`VERIZON / Page 16 of 22
`
`

`

`5
`any L2 address table lookup. For example, a chosen key can
`have a hex value of 0x0101. If a non-IP multicast frame
`arrives with a destination MAC address of 0.101.e022.2222,
`such a MAC address can collide with an L2 GRP correspond
`ing to IPv4 GDA 224.34.34.34 and would be wrongly for
`warded to ports subscribing to that L2 GRP if an L2 address
`table lookup was performed.
`Applications for the above-described modified L2 address
`table entries go beyond solving the address aliasing problem
`present with IPv4 GDAs. Chaining of such 32 bit address
`table lookups can be performed to address issues presented by
`SSM and QinC applications. Further, the additional address
`space in the L2 address table reduces address aliasing issues
`presented by the longer addresses found in IPv6 multicast
`lookups and also allows the usage of different types of look
`ups (e.g., multi-protocol label switching (MPLS)).
`Source Specific Multicast
`FIG. 6 is a simplified block diagram illustrating the concept
`of source specific multicasting (SSM) as addressed by one
`embodiment of the present invention. Network 600 contains
`two multicast groups 610 and 650. Due to reasons such as
`geography or a desire to distribute server/network load over
`network 600 there are multiple multicast transmission
`sources for each group 610 and 650. A multicast subscriber
`node can specify not only a desire to join a particular group
`but also can Subscribe to the source of the transmission. As an
`example, group 610 is divided into three subgroups 610(1),
`610(2), and 610(3). Each subgroup is served by a source 620,
`630, and 640, respectively. Similarly, a second group of mul
`30
`ticast subscribers (e.g. subscribers to a different multicast
`transmission) is divided into two subgroups 650(1) and 650
`(2), which have as their sources 660 and 670, respectively.
`IGMPv3 provides the ability for a subscriber node to
`specify not only the multicast group the node wishes to join
`but also the source of the multicast. It can be seen, however,
`that if an L2 address table lookup was limited to only the
`group (as described above) then the source distinction would
`be lost. Further, if a group or source address was limited to
`only 23 bits, then there is a multiple address aliasing problem.
`Merely modifying L2 address table entries to include 32 bit
`address fields doesn’t solve this issue either since both group
`and source addresses are 32 bit IPv4 fields. A 64 bit set of
`addresses is too big for even the modified L2 address
`described above to containina single entry. Chaining lookups
`in a modified L2 address table can resolve this problem.
`FIG. 7 illustrates an example of an L2 address table incor
`porating entries modified in accord with one embodiment of
`the present invention for use in resolving Source specific
`multicast. As with FIGS. 2 and 4, the illustrated table includes
`entries including an address 720 and a set of designated ports
`corresponding to that address 730. Each table entry has an
`associated index 710. The set of entries 740 correspond to the
`unicast destination addresses 1 to P, as described in FIG. 2.
`The set of entries 750 beginning at index (P+1) and continu
`ing to index (P+Q) contain L2 GRP addresses with a first key
`(KEY1) and a 32 bit GDA (GROUP(1)-GROUP(Q)). L2
`GRP can be of a format as illustrated in FIG. S. Entries 750
`can also include a listing of each port corresponding to nodes
`that subscribe to L2 GRP (List(1)-List(Q)). As discussed
`above, KEY1 is a 16 bit field including an I/G bit equal to one.
`FIG. 7 includes another set of entries 760 that allow for
`specification of multicast source. For these entries a 32 bit
`source address (SOURCE (1,1)-SOURCE (Q.R) is associ
`ated with a second key (KEY2), together called L2 SRC.
`KEY2 corresponds to the index (e.g., index 710 of FIG. 7) of
`the group entry with which the source is associated. For
`
`50
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`US 7,586,895 B2
`
`10
`
`15
`
`25
`
`6
`example, referring to FIG. 6, a lookup of group 610 can result
`in a determination of a first index related to group 610's entry.
`One can then use that first index as a key that is associated
`with a 32bit address of one of source 620, 630, or 640, which
`is used in a lookup of an entry 760 to determine a list of
`Subscriber destination ports (e.g., SList(1)). In this manner,
`group destination address ports and Source destination ports
`can be presented and resolved in an L2 address table.
`For reasons similar to those presented in the previous sec
`tion, this modification of an L2 address table to allow for
`chained lookups to resolve SSM destination ports will not
`interfere with traditional L2 address table lookups. Entries
`corresponding to multicast sources will not be reached in a
`lookup without an appropriate key, and Such a key will not be
`had unless acquired through the initial group destination
`address lookup. Further, since a multicast frame contains both
`the L3 GDA as well as designation of L3 source address, no
`new information need be provided by the multicast frame.
`QinC
`QinC network protocols enable service providers to use a
`single virtual LAN (VLAN) to securely transport most or all
`of a single customer's VLANs across the service providers
`metropolitan area network (MAN) or wide-area network
`(WAN) backbone. The software that permits this adds an
`extra IEEE 802.1Q tag to customers’ traffic in a switch at the
`edge of the service provider's network. This tag assigns a
`unique customer VLAN ID number (PE VLAN) to each
`customer to keep each customer's traffic segregated and pri
`vate in the provider's network. All of a customer's VLANs
`(CE. VLAN) are combined at the edge switch for transport
`into the provider network. This allows for routing customer
`VLANs (or bridge domains) across a provider VLAN.
`FIG. 8 is a simplified block diagram illustrating the use of
`provider VLANs to transport customer VLANs. Provider net
`work 810 (a MAN or a WAN) provides network transport for
`two customers C1 and C2. Customer C1 transmits traffic
`between two sites on network 810, site 820 and site 830.
`Likewise, customer C2 transmits traffic between sites 840 and
`850. Local area networks for customers C1 and C2 are
`divided into local VLANs as a mechanism for localizing
`network traffic. At site 820, customer C1 supports CE VLAN
`(1,1) (822,826) and CE VLAN(1,2) (824.828). Customer C1
`supports at site 830: CE VLAN(1,1) (832.834) and CE V
`LAN(1,2) (836). Customer C2 supports CE VLAN(2.1)
`(842) and CE VLAN(2.2) (844) at site 840 and CE VLAN
`(2.1) (852) and CE VLAN(2.2) (854) at site 850. Through
`the use of QinC encoding, VLAN traffic at site 820, for
`example, can be transported across PE VLAN 860 to site 830
`and C2's traffic can be similarly transmitted across PE V
`LAN 870.
`A problem with the QinC method arises with both unicast
`and multicast addressing. The introduction of a PE VLAN
`identifier on the provider network will impede regular usage
`of initial CE VLAN information to optimize forwarding of
`L2 traffic among different remote sites for a specific cus
`tomer. Regular Switches are not capable of inspecting and
`using both PE VLAN and CE VLAN information to derive
`forwarding actions on customer frames.
`FIG. 9 illustrates an L2 address table incorporating ele
`ments to allow QinC address resolution in accord with one
`embodiment of the present invention. FIG. 9 illustrates an L2
`address table of a format similar to that shown in FIG. 7. The
`L2 address table contains a MAC address (920) that can be a
`source MAC address for network nodes connected to ports for
`unicast address resolution, and, for multicast, L2 GRP entries
`with a 16 bit key and a 32 bit L3 GDA. The L2 address table
`
`Ex.1017
`VERIZON / Page 17 of 22
`
`

`

`US 7,586,895 B2
`
`10
`
`15
`
`7
`further includes a listing of subscriber po