US007558273B1
`
`(12) United States Patent
`Grosser, Jr. et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,558,273 B1
`Jul. 7, 2009
`
`(54) METHODS AND SYSTEMS FOR
`ASSOCATING AND TRANSLATING
`VIRTUAL LOCAL AREA NETWORK (VLAN)
`TAGS
`
`(75) Inventors: Donald B. Grosser, Jr., Apex, NC (US);
`Charles E. Hudnall, Jr., Columbus, MS
`(US); Desikan Saravanan, Santa Clara,
`CA (US); Michael Yip, Los Altos, CA
`(US)
`
`(73) Assignee: Extreme Networks, Inc., Santa Clara,
`CA (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1168 days.
`
`(56)
`
`(21) Appl. No.: 10/745,412
`(22) Filed:
`Dec. 23, 2003
`(51) Int. Cl.
`(2006.01)
`H04L 2/28
`(52) U.S. Cl. .................................. 370/395.53; 370/389
`(58) Field of Classification Search ....................... None
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`5,978,378 A * 1 1/1999 Van Seters et al. .......... 370/401
`6,128,666 A 10/2000 Muller et al.
`6,469.987 B1
`10/2002 Rijhsinghani
`6,515,993 B1
`2/2003 Williams et al.
`6,633,567 B1 * 10/2003 Brown ..................... 370,395.3
`6.956.854 B2 * 10, 2005 Ganesh et al. .............. 370,392
`7,133.409 B1 1/2006 Willardson. 370401
`7,385,973 B1* 6/2008 Johnson et al. ............. 370,389
`2003/0152075 A1
`8, 2003 Hawthorne et al. ......... 370,389
`2003/0188031 A1* 10, 2003 Deikman et al. ............ 709/250
`(Continued)
`
`OTHER PUBLICATIONS
`
`“Layer 2 Switching, VLAN tagging, and Compact PCI,
`continued . . . .” CompactPCI Systems, http://www.compactpci-sys
`tems.com/soft corner/archive/jul Aug2002/index.2.shtml, p. 1-2
`1997-2002).
`(
`)
`
`(Continued)
`Primary Examiner Phirin Sam
`(74) Attorney, Agent, or Firm Jenkins, Wilson, Taylor &
`Hunt, PA.
`
`(57)
`
`ABSTRACT
`
`Methods and systems for associating and translating VLAN
`tags are disclosed. In one implementation, multiple different
`member VLAN tags are associated with a translation VLAN
`tag. When a frame addressed to an unknown MAC address
`and containing one of the member VLAN tags is received, the
`frame is flooded to the translation VLAN and to ports asso
`ciated with the source member VLAN other than the origi
`nating port. In the copy sent to the translation VLAN, the
`VLAN tag is replaced with the tag of the translation VLAN,
`for tagged ports. Foruntagged ports, the input VLAN tag may
`simply be stripped from the frames. When a layer 2 frame
`addressed to an unknown MAC address and containing the
`translation VLAN tag is received, the layer 2 frame is flooded
`to each of the member VLANs and to ports of the translation
`VLAN other than the originating port. The VLAN tag in the
`frames forwarded to each of the member VLANs may be
`replaced with the VLAN tag corresponding to each member
`VLAN, for tagged ports. For untagged ports, the input VLAN
`tag may simply be stripped from the frames. MAC address
`learning for frames received from memberVLANs extends to
`the translation VLAN but not to other member VLANs. MAC
`address learning for frames from the translation VLAN
`extends to the member VLANs.
`
`44 Claims, 9 Drawing Sheets
`
`
`
`Ex.1012
`VERIZON / Page 1 of 25
`
`

`

`US 7,558,273 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`2/2004 Oda et al. ................... 370,389
`2004/0032868 A1
`2004/0165595 A1* 8/2004 Holmgren et al. ........ 370/395.3
`2004/0252722 A1* 12/2004 Wybenga et al. ............ 370/474
`2005, OO58118 A1* 3, 2005 Davis et al. .......
`... 370,351
`2006/0143300 A1* 6/2006 See et al. ....
`... TO9,227
`
`
`
`“VLAN Information.” USDavis, http://net21.ucdavis.edu/newvlan.
`htm. p. 1-13, (Oct. 29, 1998).
`"Virtual LANs.” Intel Corporation, p. 1-8, (1997).
`
`* cited by examiner
`
`Ex.1012
`VERIZON / Page 2 of 25
`
`

`

`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 1 of 9
`
`US 7,558,273 B1
`
`m
`
`aa ---
`
`---
`
`f
`S
`
`C
`Se
`
`N H a O
`
`A.
`
`S
`vm
`
`A4
`
`in
`
`O É
`5
`
`A
`
`a n
`
`A.
`
`H
`as on
`
`A.
`
`H
`A.
`
`a
`
`y
`
`O
`
`2
`
`Al
`
`s
`
`s
`
`A
`;
`| ?=a ?h
`A
`
`Wed
`C
`
`Od
`C
`pin
`
`: Is I; A---
`-- A -
`S
`hi? in thi? in ch
`A
`P
`A
`:
`- - - - - - - - - - - -
`
`Ex.1012
`VERIZON / Page 3 of 25
`
`

`

`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 2 of 9
`
`US 7558,273 B1
`
`
`
`
`
`{{OIA?HOI ?NIHOLLAAS
`
`
`
`
`
`VI? ATmGOW O'IOIZ
`
`NOILWOIHISSWTO
`
`{{NIONGH
`
`Z '0IH
`
`0NICTWIWMARIOÀI
`
`{{{IVI.
`
`NOIJ VOJAISSWTO
`
`
`ANI9NH ||
`
`NOLIVOIHISSWTO
`
`§NIÐNH
`
`Ex.1012
`VERIZON / Page 4 of 25
`
`

`

`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 3 of 9
`
`US 7558,273 B1
`
`RECEIVE LAYER2 FRAMEAT A
`PORT OF A SWITCHING DEVICE
`
`PERFORMLOOKUPIN A FORWARDING TABLE
`BASED ON THE DESTINATION ADDRESS AND
`INPUT VLAN TAG OF THE RECEIVED FRAME
`
`PERFORMLOOKUPN AN OUTPUT TAG TABLE
`BASED ON THE ENTRY IN THE FORWARDING
`TABLE THAT MATCHES THE DESTINATION
`ADDRESS AND INPUT VLAN TAG OF THE
`RECEIVED FRAME
`
`IN RESPONSE TO LOCATING AMATCHING
`ENTRY IN THE OUTPUT TAG TABLE, GENERATE
`A COPY OF THE RECEIVED FRAME INCLUDING
`A VLAN TAGTRANSLATED TO THE OUTPUT
`VLAN TAG OF THE MATCHING ENTRY
`
`FORWARD THE FRAME COPY TO THE PORT
`INDICATED IN THE MATCHING ENTRY
`
`
`
`ACCESS OTHERENTRIES, PERFORM
`ADDITIONAL VLAN TRANSLATIONS AND
`FORWARD FRAME TO ADDITIONAL
`DESTINATIONS IN THE OUTPUTTAG TABLE
`UNTIL END-OF-LIST
`
`ST1
`
`ST2
`
`ST3
`
`ST4
`
`STS
`
`ST6
`
`STOP
`
`ST7
`
`FIG. 3
`
`Ex.1012
`VERIZON / Page 5 of 25
`
`

`

`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 4 of 9
`
`US 7558,273 B1
`
`INITIALIZE THE TABLES FOR FORWARDING
`"BROADCAST" DESTINATION FRAMES
`RECEIVED FROM THE TRANSLATION VLAN
`TO TCM
`
`INITIALIZE THE TABLES FOR FORWARDING
`"BROADCAST" DESTINATION FRAMES
`RECEIVED FROM THE TRANSLATION VLAN TO
`ALLPORTS OF THE TRANSLATION AND
`MEMBERVLANS
`
`INITIALIZE THE TABLES FOR FORWARDING
`"BROADCAST" DESTINATION FRAMES
`RECEIVED FROM THE MEMBER VLANS TO THE
`TCMAND ALLPORTS OF THE TRANSLATON
`VLAN AND THE MEMBERVLAN ORIGINATING
`THE RECEIVED FRAME
`
`INTIALIZE THE TABLES FOR FORWARDING
`"UNKNOWN" DESTINATION FRAMES RECEIVED
`FROM THE TRANSLATION VLAN TO ALL PORTS
`OF THE TRANSLATION AND MEMBER VLANS
`
`INITIALIZE THE TABLES FOR FORWARDING
`"UNKNOWN" DESTINATION FRAMES RECEIVED
`FROMMEMBERVLANS TO ALLPORTS OF THE
`TRANSLATION VLAN AND THE SOURCE
`MEMBERVLAN OF THE RECEIVED FRAME
`
`
`
`
`
`
`
`
`
`
`
`
`
`ST1
`
`ST2
`
`ST3
`
`ST4
`
`ST5
`
`STOP
`
`ST6
`
`FIG. 4
`
`Ex.1012
`VERIZON / Page 6 of 25
`
`

`

`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 5 of 9
`
`US 7,558,273 B1
`
`3m
`
`
`
`gmNmmaofimamnvmm
`
`
`
`magmaGZEUHEm<m0HMOA<H<
`
`mmmMn—gU;
`
`Z<H>
`
`ZOHHaJmZdJEL
`
`Mum—Sm:<EOMmDMH<EGEOin
`m0Z<A>
`
`
`
`Z<H>ZOF<AmZ<MH
`
`Em
`
`
`
`mm:MEREgamma
`
`<m.OE
`
`EX.1012
`
`VERIZON / Page 7 of 25
`
`Ex.1012
`VERIZON / Page 7 of 25
`
`
`
`

`

`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 6 of 9
`
`US 7,558,273 B1
`
`O<HZ<~H>mmhD72
`
`ohm
`
`95
`
`
`
`
`
`O<HZ<A>2MngHMOAZOERZGEO
`
`04;SEOWE.ZnNag/Hman?
`
`
`
`mfleOEHZODmafia.
`
`mHm
`
`
`
`
`
`Dad.HDEOmag.OH.>MHZman?
`
`
`
`a:©2~Z~<HZOOmama;
`
`
`
`
`
`972#59232HMOAZOHHSAHGEO
`
`gmamt/50mmmmhmoO<HZ<A>
`
`
`U42mogOmME@3200magi.
`gmmgmommEm0mmmMn—nz
`OEQBMOMNEH.ZNwgQQ<
`
`CgmOgOmEOZHZEPZODmama;
`gumDre/EOEEm0mmmmma
`DZHQMSKVMOmEOhWMHZNmg
`Eli.m0O<HZ4;mmhQ72
`
`
`
`241.5GE<ZHUEO
`
`25m
`
`
`
`GEEBMOmNEH.ZHmmEHZman?
`
`mHm
`
`0523M0maOHPFC/Hm9%
`
`OEMUMDOmma.OZHZH<HZOUmam—<8
`
`
`
`
`052MUMDOMmam.65229200mqmah
`
`
`
`925EOmzmummat.mommmdaa
`
`a:mom0<mQZ<
`
`mbfihZ;Mmmzmz
`
`mOHm
`
`mm.DE
`
`mhm
`
`2034quEQ72EQmEmUm—MEm0mmmEan
`GagZ<A>
`
`EX.1012
`
`VERIZON / Page 8 of 25
`
`Ex.1012
`VERIZON / Page 8 of 25
`
`
`
`

`

`U.S. Patent
`
`US 7558,273 B1
`
`
`
`Z09
`
`OVW
`
`
`
`NOLLWNI ISHOI
`
`009
`
`
`
`
`
`
`
`
`
`
`
`Ex.1012
`VERIZON / Page 9 of 25
`
`

`

`U.S. Patent
`
`US 7,558,273 B1
`
`WOJ.
`
`
`
`L '0IH
`
`
`
`
`
`0 IL
`
`Ex.1012
`VERIZON / Page 10 of 25
`
`

`

`U.S. Patent
`
`, 2009
`Jul. 7
`
`Sheet 9 Of 9
`
`558,273 B1
`US 7,
`
`
`
`
`
`I JRIO? ZI?Od
`
`008Z08
`
`8 "OIH
`
`
`
`I INOM ZJNOI
`
`Z06006
`
`6 "OIH
`
`Ex.1012
`VERIZON / Page 11 of 25
`
`

`

`US 7,558,273 B1
`
`1.
`METHODS AND SYSTEMIS FOR
`ASSOCATING AND TRANSLATING
`VIRTUAL LOCAL AREA NETWORK (VLAN)
`TAGS
`
`TECHNICAL FIELD
`
`The present invention relates to methods and systems for
`layer 2 frame Switching. More particularly, the present inven
`tion relates to methods and systems for associating and trans
`lating VLAN tags in layer 2 frame Switching.
`
`10
`
`BACKGROUND ART
`
`15
`
`25
`
`30
`
`35
`
`Local area networks (LANs) have been used to facilitate
`communications between end users connected to the same
`physical network. Individual LANs may be bridged to allow
`end users to communicate with other end users connected to
`different networks using layer 2 switches. Bridged LANs
`may be furtherinterconnected with other bridged LANs using
`routers to form even larger communications networks. How
`ever, bridging and routing increase the processing load on
`machines that interconnect the various physical networks.
`VLANs have been developed to address various deficien
`cies in bridged and routed networks and to allow LANs to be
`bridged in virtually any desired manner, independently of
`physical topology of the networks. VLANs can contain net
`work traffic to a predefined set of ports in a layer 2 switch, thus
`eliminating the unnecessary use of bandwidth by broadcast
`and multicast frames. For example, layer 2 traffic that arrives
`at a Switch is preferably only flooded onto output ports asso
`ciated with the same VLAN. Without VLANs, layer 2 traffic
`for which no layer 2 forwarding database entry exists is
`flooded onto all output ports. Thus, using VLANs allows
`traffic to be contained within each VLAN for flooding pur
`poses. The VLAN for a received frame is identified by a
`VLAN tag or the assigned VLAN tag for the receiving port. In
`most common VLAN implementations, the VLAN tag is a
`four-byte field between the link layer header and the network
`40
`layer header of a frame. The VLAN tag contains a VLAN
`identifier and an associated user priority field. The term
`VLAN tag, as used herein, is intended to refer to the VLAN
`identifier portion of the VLAN tag, even though it is under
`stood that a VLAN tag may include additional information.
`Using current VLAN implementations, a layer 2 switch is
`not permitted to change the VLAN tag in an incoming frame
`to another VLAN tag in an outgoing frame. As a result, in
`order to interconnect VLANs that use different VLAN tags, it
`is necessary to provide a mechanism for mapping or coordi
`nating VLAN tags used by the different networks. One poten
`tial solution to this problem is to stack VLAN tags in each
`frame. That is, when a frame arrives at a switch from a first
`VLAN and is destined for a second VLAN, the switch may
`add a second VLAN tag to the frame in addition to the first
`55
`VLAN tag. The frame will be switched in the second VLAN
`using the second VLAN tag. When the frame leaves the
`second VLAN, the second VLAN tag is removed.
`One problem with using VLAN tag stacking is that tag
`stacking only provides a mechanism for Switching frames in
`the interconnecting network. When frames leave the intercon
`necting network, the same VLAN tags that were in the frames
`when they entered the interconnecting network must be used.
`In other words, there is no ability to expand the broadcast or
`flooding domain associated with the original VLANs.
`Another problem with tag stacking is that it increases the
`complexity in decoding frames in the interconnecting net
`
`45
`
`50
`
`60
`
`65
`
`2
`work. Accordingly, there exists a need for improved methods
`and systems for associating and translating VLAN tags in
`layer 2 frames.
`
`DISCLOSURE OF THE INVENTION
`
`The present invention includes methods and systems for
`translating VLANs in layer 2 frames, replacing VLANs in
`outgoing frames with the translated VLANs, and associating
`VLANs with other VLANs, thereby expanding the broadcast
`and flooding domains of the VLANs. In one implementation,
`a layer 2 frame addressed to an unknown MAC address is
`received at a switch. The VLAN tag in or associated with the
`layer 2 frame is translated to one or more different VLAN
`tags. If the VLAN tag in the layer 2 switch is of a first type,
`referred to herein as a member VLAN tag, the layer 2 frame
`may be flooded to a VLAN of a second type, referred to herein
`as a translation VLAN, and to the other ports of the source
`VLAN. Flooding preferably does not occur to the originating
`source port. The VLAN tag in the copy of the layer 2 frame
`sent to the translation VLAN may be translated to and
`replaced by a VLAN tag associated with the translation
`VLAN or stripped for untagged ports.
`If the VLAN tag associated with the received layer 2 frame
`is a translation VLAN tag, copies of the layer 2 frame may
`then be created and flooded to memberVLANs and to ports of
`the translation VLAN other than the source port. Each copy of
`the layer 2 frame may include a different VLAN tag than the
`input layer 2 frame. The different VLAN tags in the frame
`copies sent to the member VLANs may be associated with
`each member VLAN. By maintaining associations between
`VLANs and performing the VLAN translations, the layer 2
`Switch expands the broadcast and flooding domains of trans
`lation and member VLANs, while maintaining isolation
`between the traffic of member VLANs.
`As used herein, the term “translation VLAN’ refers to a
`VLAN with which multiple other VLANs are associated by a
`layer 2 switch. The term “member VLAN” refers to one of the
`VLANs that are associated with a translation VLAN. By
`defining translation and member VLANs in a layer 2 switch,
`traffic can be multiplexed and demultiplexed at layer 2. In
`addition, because VLANs are translated, rather than stacked,
`the decoding of layer 2 frames is simplified over tag stacking
`implementations.
`In one implementation, a layer 2 Switch includes a layer 2
`forwarding table and an output tag table. The forwarding table
`includes entries that are indexed by a combination of desti
`nation MAC address and VLAN tag. The result of locating a
`matching entry in the forwarding table is an index to the
`output tag table. The output tag table includes replacement
`VLAN tags for outgoing frames. Multiple entries in the out
`put tag table may be accessed in response to one lookup in the
`forwarding table when multiple copies of a received frame are
`being sent to different VLANs. Because the output tag table
`maintains multiple VLAN associations for a single input
`VLAN, efficient VLAN translations can be achieved.
`Any of the methods and systems described herein can be
`implemented in hardware, software, firmware, or any combi
`nation thereof. Thus, the functional blocks described herein
`may be implemented by a computer program product com
`prising computer executable instructions embodied in a com
`puter readable medium for performing the indicated function.
`Exemplary computer readable media in which the VLAN
`translation methods according to the present invention may
`be embodied include magnetic disks, optical disks, memory
`chips, or any other Suitable device capable of storing instruc
`tions used to control a computer. In addition, a computer
`
`Ex.1012
`VERIZON / Page 12 of 25
`
`

`

`US 7,558,273 B1
`
`3
`program product according to the invention may be embodied
`in an electrical signal downloadable via a computer network.
`Accordingly, it is an object to provide methods and systems
`for translating VLAN tags in received layer 2 frames.
`It is another object of the invention to provide methods and
`systems for associating member VLANs with a translation
`VLAN, while maintaining traffic separation between the
`member VLANs.
`Some of the objects having been stated hereinabove, other
`objects will become evident as the description proceeds when
`taken in connection with the accompanying drawings as best
`described hereinbelow.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`5
`
`10
`
`15
`
`4
`may also include more than one port (not shown) having
`connection to one of VLANs 102, 104,106, 108, or 110.
`VLANs 102, 104, 106, and 108 may include personal
`computers (PCs) 114,116,118, and 120, respectively, having
`unique media access control (MAC) addresses. VLANs 102.
`104, 106, and 108 may also include other end node devices
`(not shown) having unique MAC addresses such as other PCs,
`server computers, printers, mainframe computers, etc. VLAN
`110 can include a router 122 for receiving frames from
`switching device 112 for forwarding the frames to end node
`devices (not shown) of VLAN 110.
`Using conventional layer 2 Switching techniques, frames
`from VLANs 102,104,106, and 108 are limited to transmis
`sion in the associated VLANs because of the prohibition on
`replacing VLAN tags in outgoing frames. The present inven
`tion avoids this problem by maintaining associations between
`translation and member VLANs in switching device 112.
`Switching device 112 translates VLAN tags in received
`frames to the VLAN tags associated with the recipient
`VLANs. As a result, the broadcast and flooding domains of
`member and translation VLANs are expanded over conven
`tional VLAN implementations.
`FIG. 2 illustrates a block diagram of exemplary compo
`nents of switching device 112. Switching device 112 can be
`implemented on any Suitable underlying layer 2 platform,
`such as an Ethernet switch. Ethernet switches including
`underlying hardware platforms suitable for use with embodi
`ments of the present invention include any of the BlackDia
`mondTM AlpineTM, and SummittM Ethernet switches avail
`able from Extreme Networks, Inc., of Santa Clara, Calif.
`In the illustrated example, switching device 112 includes a
`plurality of input/output (I/O) modules 200, 202, 204, 206,
`and 208 associated with ports 2, 3, 4, 5, and 1, respectively.
`I/O modules 200, 202, 204, 206, and 208 may send and
`receive layer 2 frames over network 100 (shown in FIG. 1).
`I/O modules 200, 202, 204, and 206 may be connected to
`member VLANs 102, 104, 106, and 108 (shown in FIG. 1),
`respectively, for sending and receiving layer 2 frames to and
`from these VLANs. I/O module 208 may be connected to
`translation VLAN 110. I/O modules 200, 202, 204, 206, and
`208 may be implemented as printed circuit boards plugged
`into slots in switching device 112. A switch fabric 210 may
`connect I/O modules 200, 202, 204, 206, and 208 to each
`other and to a management switch fabric module (MSM) 212.
`Switch fabric 210 can be any suitable type of switching fabric
`for transferring frames between ports and to and from MSM
`212. In one exemplary embodiment, switch fabric 210
`includes a plurality of gigabit Ethernet connections that can
`be managed by MSM 212.
`Forwarding and Output Tag Tables
`
`Exemplary embodiments of the invention will now be
`explained with reference to the accompanying drawings, of
`which:
`FIG. 1 is a schematic diagram of an exemplary network
`utilizing VLAN association and translation according to an
`embodiment of the invention;
`FIG. 2 is a block diagram of exemplary components of a
`switching device including VLAN translation capabilities
`according to an embodiment of the present invention;
`FIG. 3 is a flow chart illustrating exemplary steps that may
`be performed in forwarding a layer 2 frame to translation and
`member VLANs according to an embodiment of the present
`invention;
`FIG. 4 is a flow chart illustrating exemplary steps that may
`be performed by a table control module in initializing for
`warding and output tag tables with data prior to enabling a
`Switching device to receive layer 2 traffic according to an
`embodiment of the present invention;
`FIGS. 5A and 5B are a flow chart illustrating exemplary
`steps that may be performed by a table control module in
`learning unknown source MAC addresses from received layer
`2 frames according to an embodiment of the present inven
`tion;
`FIG. 6 is a schematic diagram representing the first of four
`layer 2 frames received on a port of a Switching device uti
`lizing VLAN translation and the forwarding of a copy of the
`frame to an output port of the Switching device;
`FIG. 7 is a schematic diagram representing the second of
`the four frames referenced with regard to FIG. 6;
`45
`FIG. 8 is a schematic diagram representing the third of the
`four frames referenced with regard to FIG. 6; and
`FIG. 9 is a schematic diagram representing the second of
`the four frames referenced with regard to FIG. 6.
`
`25
`
`30
`
`35
`
`40
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`50
`
`Methods and systems for associating and translating
`VLAN tags in layer 2 frames can be implemented in any
`Suitable layer 2 Switching device in a network having a plu
`rality of VLANs. FIG. 1 illustrates a schematic diagram of an
`exemplary network, generally designated 100, utilizing
`VLAN association and translation according to an embodi
`ment of the present invention. Referring to FIG. 1, network
`100 may include several member VLANs (designated by
`broken lines 102,104,106, and 108) having connection to one
`another and to a translation VLAN (designated by broken line
`110) via a layer 2 switching device 112. Switching device 112
`may include ports 1-5 having connection to VLANs 110, 102.
`104, 106, and 108, respectively. Switching device 112 may
`forward frames received at one of ports 1-5 to one or more of
`VLANs 110, 102, 104, 106, and 108. Switching device 112
`
`55
`
`60
`
`65
`
`MSM 212 may maintain associations between translation
`and member VLANs and may also maintain forwarding
`tables. In the illustrated example, MSM 212 may include a
`forwarding table 214, an output tag table 216, and a table
`control module (TCM) 218 for performing MAC address
`learning, updating master copies of tables 214 and 216, and
`distributing the copies to the I/O modules. Forwarding table
`214, output tag table 216, and table control module 218 may
`be stored in a memory 220 accessible by a central processing
`unit (CPU) 222.
`Tables 214 and 216 may be distributed to each I/O module
`where these tables are used by classification engines 224 for
`frame classification and VLAN translation. Classification
`engines 224 forward frames and translate VLANs based on
`data in tables 214 and 216. Classification engines 224 may
`
`Ex.1012
`VERIZON / Page 13 of 25
`
`

`

`US 7,558,273 B1
`
`6
`
`5
`forward frames for which learning is required to TCM 218.
`Classification engines 224 may also receive and translate
`untagged and tagged frames.
`Tables 214 and 216 may include information for identify
`ing output ports associated with destination MAC addresses
`and translating VLANs. Table control module 218 may main
`tain tables 214 and 216 and implement a procedure to update
`tables 214 and 216 as new source MAC addresses are learned.
`Further, table control module 218 may initialize tables 214
`and 216 with information for forwarding network frames and
`translating VLAN tags of the forwarded frames prior to
`enabling Switching device 112 to receive frames.
`As stated above, layer 2 frame forwarding and VLAN
`translation may be implemented by classification engines 224
`15
`based on data in tables 214 and 216. FIG. 3 is a flow chart
`illustrating exemplary steps that may be performed by clas
`sification engines 224 in forwarding frames and translating
`VLANs. In step ST1, a layer 2 frame is received at a port of
`switching device 112. Next, at step ST2, classification engine
`224 performs a lookup in forwarding table 214 based on the
`destination MAC address and input VLAN tag of the received
`frame. The input VLAN tag may be extracted from the frame
`for tagged frames or associated with the frame based on the
`input port for untagged frames. Forwarding table 214 may
`include an entry for matching the destination address and
`input VLAN tag of the received frame.
`In one embodiment, forwarding table 214 may include a
`number of entries that each contain a destination MAC
`address and an input VLAN tag or other indicia for matching
`the destination MAC address and input VLAN tag of the
`received frame. The entries of forwarding table 214 may also
`include an output tag table index to be used in indexing output
`tag table 216. Table 1 shown below illustrates exemplary
`entries inforwarding table 214 and a brief description of each
`entry. In Table 1, it is assumed that specific MAC addresses
`have not yet been learned. Accordingly, Table 1 includes
`entries for broadcast and unknown unicast MAC addresses.
`
`TABLE 1-continued
`
`Forwarding Table Before Learning Occurs
`
`Destination MAC
`
`Output Tag
`Input
`VLAN Table (Table 2)
`Tag
`Index
`
`Comments
`
`Broadcast
`
`O3
`
`12
`
`Unknown
`
`O3
`
`13
`
`Broadcast
`
`O4
`
`15
`
`Unknown
`
`O4
`
`16
`
`translation
`
`VLAN an
`VLAN.
`lood broadcast traffic
`o all ports in member
`VLAN and translation
`VLAN and send copy to
`CPU.
`ood unknown unicast
`all ports in member
`LAN and translation
`LAN.
`ood broadcast traffic
`all ports in member
`LAN and translation
`LAN and send copy to
`PU.
`ood unknown unicast
`o all ports in member
`VLAN and translation
`VLAN.
`
`s
`
`In Table 1, each entry contains a unique combination of
`destination MAC address and input VLAN tag. VLAN trans
`lation can be implemented using the data in Table 1 when a
`frame is received by switching device 112. For example,
`when a frame is received at a port of Switching device 112, a
`lookup may be performed in forwarding table 214 based on
`the destination MAC address and input VLAN tag extracted
`from the received frame. Based on the lookup, the output tag
`table index corresponding to the destination MAC address
`and input VLAN tag combination can be retrieved. The output
`tag table index may Subsequently be used to perform a lookup
`in output tag table 216.
`The destination MAC addresses in Table 1 are illustrated in
`text format. The text format includes “Unknown to indicate
`unknown unicast layer 2 traffic and “Broadcast to indicate
`layer 2 broadcast traffic. Broadcast destination traffic refers to
`frames destined for a broadcast MAC address. Unknown
`unicast destination traffic refers to frames that are to be for
`warded to a destination MAC address that is not contained in
`forwarding table 214. It is understood that in the actual imple
`mentation of Table 1, binary values corresponding to actual
`destination MAC addresses would be present in this table.
`Table 1 also contains a Description column Summarizing the
`handling of received network frames having the correspond
`ing destination MAC address and input VLAN tag combina
`tion. It is understood that the information contained in the
`Description column of Table 1 is for illustrative purposes and
`may not be included in forwarding table 214.
`Referring again to FIG. 3, at step ST3, a lookup may be
`performed in output tag table 216 based on the entry in for
`warding table 214 matching the destination address and input
`VLAN tag of the received frame. In one embodiment, output
`tag table 216 includes entries indexed by the results of the
`forwarding table lookups. The entries of output tag table 216
`contain the output port and output VLAN tag for the for
`warded frame. In one embodiment, output tag table 216 may
`include a number of entries that each contain an output tag
`table index, an output port number or other indicia for iden
`tifying a port of the Switching device, an output VLAN tag
`number or other indicia for identifying a VLAN tag, and a
`next output tag table index. Table 2 shown below illustrates
`exemplary entries for an output tag table that contains entries
`
`10
`
`25
`
`30
`
`35
`
`TABLE 1.
`
`Forwarding Table Before Learning Occurs
`
`Destination MAC
`
`Output Tag
`Input
`VLAN Table (Table 2)
`Tag
`Index
`
`Comments
`
`Broadcast
`
`1OOO
`
`O
`
`Unknown
`
`1OOO
`
`Broadcast
`
`101
`
`Unknown
`
`Broadcast
`
`101
`
`102
`
`1
`
`6
`
`7
`
`9
`
`Unknown
`
`102
`
`10
`
`s
`
`Flood broadcast traffic
`o all ports in member
`LANs and translation
`LAN and send copy to
`PU.
`ood unknown unicast
`all ports in member
`LANs and translation
`LAN and send copy to
`PU.
`ood broadcast traffic
`all ports in member
`LAN and translation
`LAN and send copy to
`PU.
`ood unknown unicast
`all ports in member
`LAN and translation
`LAN.
`ood broadcast traffic
`all ports in member
`LAN and translation
`LAN and send copy to
`PU.
`Flood unknown unicast
`o all ports in member
`
`s
`
`s
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Ex.1012
`VERIZON / Page 14 of 25
`
`

`

`US 7,558,273 B1
`
`8
`
`TABLE 2-continued
`
`Output Tag Table
`
`7
`corresponding to the exemplary forwarding table illustrated
`in Table 1 above. In the illustrated example, Table 2 also
`includes a brief description for the entries in the Description
`column. Such descriptions are included for illustrative pur
`poses only and may not be included in an actual implemen
`tation of the output tag table.
`
`TABLE 2
`
`Output Tag Table
`
`Output
`Tag
`Table
`Index
`
`Output
`Port
`
`Output
`VLAN
`Tag
`
`Next Output
`Tag Table
`Index
`
`Description
`
`Strip Tag?
`
`Output
`Tag
`Table
`Index
`
`Output Next Output
`Output VLAN Tag Table
`Port
`Tag
`Index
`
`19
`
`1
`
`1000
`
`End-of-List
`
`Description
`
`Strip Tag?
`
`N
`
`Learned
`entry: Fwd to
`specific port
`of translation
`VLAN
`
`As illustrated in Table 2, each entry in the output tag table
`includes a unique output tag table index. As noted above, the
`output tag table index retrieved by a lookup in forwarding
`table 214 can be matched to an output tag table index in output
`tag table 216. A matching output tag table index in the output
`tag table corresponds to an output port number, an output
`VLAN tag number, and a next output tag index.
`In Table 2, the last column indicates whether a VLAN tag
`should be included or not in the outbound frame. In the
`illustrated example, all of the output ports are assumed to be
`tagged. Thus, the entries are labeled “N' indicating that the
`VLAN tag should not be stripped from the outbound frame. If
`any of the entries in Table 2 were marked “Y”, it would
`indicate that the corresponding output port is untagged. In this
`situation, the input VLAN tag would be stripped from the
`outbound frame and no VLAN tag would be included in the
`outbound frame, even though the input frame may have
`included a VLAN tag.
`In Table 2, the output port information is illustrated in
`numeric and text formats. It is understood that in the actual
`implementation of Table 2, binary values identifying the
`actual output port would be present in this table. The output
`port information in this exemplary output tag table is illus
`trated in numeric format (1-5) and text format (TCM). The
`output port information shown in numeric format corre
`sponds to the ports 1-5 of switching device 112. The output
`VLAN tag information in text format (TCM) corresponds to
`table control module 218.
`Referring again to FIG. 3, at step ST4, in response to
`locating a matching entry in output tag table 216, a copy of the
`received frame is generated. In the frame copy, the VLAN tag
`is translated to the output VLAN tag of the matching entry. If
`the output port is tagged, the output VLAN tag may be
`included in the outgoing frame. If the output port is untagged,
`the VLAN tag may not be included in the outbound frame,
`and the input tag may be stripped from Such frames. At step
`ST5, the frame copy may be forwarded to the port indicated in
`the matching entry. Next, additional entries in the output tag
`table may be accessed based on the next output tag associated
`with each entry until an entry with the next entry set to end of
`list is reached (step ST6). The frame may be forwarded to
`destinations associated with each entry with different VLAN
`tags being inserted in the frame for different destinations.
`Using Such a scheme, multiple VLAN translations can be
`performed for a received frame using a single forwarding
`database lookup. As a result, the time required to perform
`multiple VLAN translations is reduced. The process stops at
`step ST7.
`Initializing the Forwarding and Output Tag Tables
`
`Prior to enabling switching device 112 to receive layer 2
`traffic for Switching, forwarding and output tag tables 214 and
`
`10
`
`15
`
`25
`
`N
`
`N
`
`N
`
`N
`
`30
`
`O
`
`TCM 1OOO
`
`1OOO
`
`101
`
`1
`
`2
`
`3
`
`102
`103
`104
`101
`
`4
`5
`End-of-List
`7
`
`TC M
`
`101
`
`8
`
`1OOO
`
`End-of-List
`
`Fwd to TCM
`for local
`processing
`Fwd to all
`ports of
`translation
`VLAN
`Fwd to all
`ports of all
`member
`VLANS
`
`o TCM
`for local
`processing
`to all
`
`9
`
`TCM
`
`102
`
`102
`
`10
`
`11
`
`to all
`
`N
`
`1OOO
`
`End-of-List
`
`2
`
`TCM
`
`103
`
`13
`
`103
`
`14
`
`Fwd to all
`
`N
`
`1OOO
`
`End-of-List
`
`5
`
`TCM
`
`104
`
`16
`
`104
`
`17
`
`1OOO
`
`End-of-List
`
`101
`
`End-of-List
`
`or local
`processing
`Fwd to all
`ports of
`member
`VLAN
`Fwd to all
`ports of
`translation
`VLAN
`Learned
`entry: Fwd to
`specific port
`of member
`VLAN
`
`N
`
`N
`
`N
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Ex.1012
`VERIZON / Page 15 of 25
`
`

`

`9
`216 are preferably initialized with information for forwarding
`layer 2 frames and translating VLAN tags of the forwarded
`