I 1111111111111111 11111 111111111111111 111111111111111 111111111111111 IIII IIII
`US007965709B2
`
`c12) United States Patent
`Du
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 7,965, 709 B2
`Jun. 21, 2011
`
`(54) BRIDGE FORWARDING METHOD AND
`APPARATUS
`
`(75)
`
`Inventor: Wenhua Du, Guangdong (CN)
`
`(73) Assignee: Huawei Technologies Co., Ltd.,
`Shenzhen (CN)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 476 days.
`
`(21) Appl. No.: 11/583,760
`
`(22) Filed:
`
`Oct. 18, 2006
`
`(65)
`
`Prior Publication Data
`
`US 2007 /0097968 Al
`
`May 3, 2007
`
`(30)
`
`Foreign Application Priority Data
`
`Oct. 19, 2005
`
`(CN) .......................... 2005 1 0112882
`
`(51)
`
`Int. Cl.
`(2006.01)
`H04L 12156
`(52) U.S. Cl. ................... 370/389; 370/392; 370/395.53;
`370/429; 709/243
`( 58) Field of Classification Search .... ...... ........ 3 70/392,
`370/395.53, 389, 390,401,356,429; 707/3,
`707/217, 218; 395/200.15, 200.02
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,511,168 A *
`4/1996 Perlman et al ................ 709/243
`7/2001 Ullumetal.
`6,266,705 Bl
`7,088,714 B2 *
`............... 370/389
`8/2006 Athreya et al.
`7,260,565 B2 *
`1/1
`8/2007 Lee et al.
`7,443,856 B2 *
`10/2008 Lodha et al ................... 370/392
`7,558,273 Bl*
`7/2009 Grosser et al. ........... 370/395.53
`2002/0085551 Al
`7/2002 Tzeng
`
`2003/0053450 Al
`2003/0152075 Al*
`2005/0094634 Al
`2005/0141537 Al*
`2006/0023724 Al*
`2006/0245436 Al *
`
`3/2003 Kubota et al.
`8/2003 Hawthorne et al. ........... 370/389
`5/2005 Santhanakrishnan et al.
`6/2005 Kumar et al.
`................. 370/429
`2/2006 Na et al. ................... 370/395.53
`11/2006 Sajassi ..................... 370/395.53
`
`CN
`CN
`CN
`
`FOREIGN PATENT DOCUMENTS
`1356806 A
`7/2002
`1458771
`11/2003
`1458771 A
`11/2003
`(Continued)
`
`OTHER PUBLICATIONS
`
`Extended Search Report issued in corresponding European Patent
`Application No. 06 25 5388; issued Feb. 6, 2007.
`
`(Continued)
`
`Primary Examiner - Robert W Wilson
`Assistant Examiner - Mohamed Kamara
`(74) Attorney, Agent, or Firm -Brinks Hofer Gilson &
`Liane
`
`ABSTRACT
`(57)
`A bridge forwarding method comprises: receiving a frame
`from an input port, obtaining the input VLAN ID and a
`destination MAC address of the frame; determining an output
`port and an output VLAN ID of the frame, and forwarding the
`frame according to the output port and the output VLAN ID.
`A bridge forwarding apparatus includes at least one output
`port used for receiving a frame from more than one VALN, at
`least one output port used for transmitting the frame to more
`than one VALN and a forwarding unit, the forwarding unit
`obtains the input VLAN ID and the destination MAC address
`in the frame, determines the output port and the output VLAN
`ID of the frame, and outputs the frame to the corresponding
`output port. The method and the apparatus of this invention
`can realize the bridge forwarding of the Ethernet frames
`between multiple VLANs.
`
`23 Claims, 4 Drawing Sheets
`
`Forwarding unit
`
`Input port 1
`
`Input port 2 ~ Input
`analyzing
`module
`
`First
`forwarding
`module
`
`Second
`forwarding
`module
`
`Input port n
`
`Output port 1
`
`Output port 2
`
`Output port n
`
`Ex.1001
`VERIZON / Page 1 of 13
`
`

`

`US 7,965,709 B2
`Page 2
`
`CN
`CN
`EP
`EP
`JP
`
`FOREIGN PATENT DOCUMENTS
`3/2005
`1194508
`12/2008
`100442772 C
`9/1985
`0 155 113 A2
`1206077 A2
`5/2002
`2004-72160
`3/2004
`
`OTHER PUBLICATIONS
`
`Office Action issued in corresponding Chinese Patent Application
`No. 200680012308.1; issued Jul. 14, 2010.
`Office Action issued in corresponding European Patent Application
`No. 06 255 388.8; issued Sep. 8, 2010.
`Written Opinion of the International Searching Authority issued in
`corresponding PCT Application No. PCT/CN2006/002462; mailed
`Feb. 1, 2007.
`
`Office Action issued in corresponding Chinese Patent Application
`No. 2005101128821; issued Nov. 30, 2007.
`
`* cited by examiner
`
`Ex.1001
`VERIZON / Page 2 of 13
`
`

`

`U.S. Patent
`
`Jun. 21, 2011
`
`Sheet 1 of 4
`
`US 7,965,709 B2
`
`101
`
`Receiving the frame from the input port ,
`and obtaining the input VLAN ID of the
`frame
`
`Not it
`
`Un cast
`forw rdin
`
`l05
`
`Obtaining the output
`port
`
`106
`
`Obtaining the MID
`
`Obtaining all output ports
`corresponding to the VSI
`
`Forwarding the frame to the
`output port
`
`Abandoning the frame
`
`y
`
`111
`
`Fig. I
`
`Ex.1001
`VERIZON / Page 3 of 13
`
`

`

`U.S. Patent
`
`Jun. 21, 2011
`
`Sheet 2 of 4
`
`US 7,965,709 B2
`
`201
`
`Receiving the frame from the
`input port
`
`202
`
`Obtaining the input VLAN ID of the frame
`
`203
`
`Searching the mapping table using the doublet {input
`port, input VLAN ID} to detennine the VSI ID
`
`204
`Recording the input port and the input VLAN ID
`corresponding to the SMAC in the MAC address
`forwardin
`table corres ondin
`to the VSI
`205
`
`Searching the MAC address forwarding table using {VSI
`ID, DMAC} or { VSI ID, DMAC, input VLAN ID}
`
`Not
`
`it
`
`213
`
`Determmmg to
`forward the frame
`de
`
`Detennmmg to
`forward the frame
`
`209
`
`Obtaining the MID
`
`215
`
`VLAN ID in the
`frame
`
`Copying the frames
`
`Copying the frames
`
`210
`
`212
`
`Substituting the ouput VLAN ID
`with the VLAN ID in the frame
`
`Forwarding the frame to the
`output port
`
`Abandoning the frame
`
`y
`
`218
`
`Fig.2
`
`Ex.1001
`VERIZON / Page 4 of 13
`
`

`

`U.S. Patent
`
`Jun. 21, 2011
`
`Sheet 3 of 4
`
`US 7,965,709 B2
`
`301
`
`Receiving the frame from the
`input port
`
`302
`
`Obtaining the input inner-layer VLAN ID and outer-layer
`VLAN ID of the frame
`
`303
`
`Searching the mapping tab le using { input port, input
`VLAN ID} to determine the VSI ID
`
`Not it
`
`313
`
`Determmmg to
`forward the frame
`
`Determmmg to
`forward the frame
`w·th br adcast m de
`
`Obtaining the MID
`
`308
`
`310
`
`309
`
`Substituting the ouput
`outer-layer and inner(cid:173)
`layer VLAN ID with
`the input outer-layer
`and inner-layer VLAN
`ID in the frame
`
`Copying the frames
`
`Copying the frames
`
`Forwarding the frame to the
`output port
`
`Abandoning the frame
`
`Fig.3
`
`Ex.1001
`VERIZON / Page 5 of 13
`
`

`

`U.S. Patent
`
`Jun. 21, 2011
`
`Sheet 4 of 4
`
`US 7,965,709 B2
`
`Forwarding unit
`
`Input
`analyzing
`module
`
`First
`forwarding
`module
`
`Second
`forwarding
`module
`
`Input port l
`
`I Input port 2 ~
`
`Input port n
`
`Output port l
`
`Output port 2
`
`Output port n
`
`Fig.4
`
`Ex.1001
`VERIZON / Page 6 of 13
`
`

`

`US 7,965,709 B2
`
`1
`BRIDGE FORWARDING METHOD AND
`APPARATUS
`
`FIELD OF THE TECHNOLOGY
`
`The present invention relates to the network switching
`technical field. More particularly, the present invention
`relates to a bridge forwarding method and a bridge forward(cid:173)
`ing apparatus.
`
`BACKGROUND OF THE INVENTION
`
`2
`Step 111: Abandoning the frames to prevent forwarding
`loops.
`Step 112: Forwarding the frame to the output port.
`The above-mentioned input port and output port corre-
`5 spond to one VSI, and the relationship between the VLAN
`and the VSI is one-to-one relationship.
`Since in one access domain, the relationship between the
`VLAN and the VSI is one-to-one relationship, and the mul(cid:173)
`tiple-to-one relationship between multiple VLANs with one
`10 VSI is not supported, the Ethernet frames can only be for(cid:173)
`warded within one VLAN by means of Layer 2 Ethernet
`bridge forwarding. If the frames need to be forwarded across
`VLAN s, the Layer 3 IP routing must be adopted. In addition,
`the Ethernet frames can only be broadcasted to one VLAN by
`15 means of bridge forwarding, and broadcasting to multiple
`VLANs by means of bridge forwarding is not supported.
`
`There are two approaches for forwarding the frames of the
`Ethernet at present: Layer 2 Ethernet bridge and Layer 3 IP
`route. The Layer 2 Ethernet bridge refers to a method for
`searching the Destination Media Access Control (MAC)
`address forwarding table by using the MAC address to obtain
`the exit information and forwarding the data packets accord(cid:173)
`ing to the exit information. The Layer 3 IP route is a method
`for searching the routing table by using the destination IP to 20
`obtain the exit information and forwarding the data packets
`according to the exit information. The MAC address forward(cid:173)
`ing table is obtained through the self-learning of source MAC
`(SMAC) address or statically configured by software.
`At present, as defined in the Ethernet bridge forwarding 25
`standard, one Virtual Switching Instance (VSI) corresponds
`to one Virtual Local Access Network (VLAN) in one access
`domain. The Layer 2 Ethernet bridge forwarding is forward(cid:173)
`ing the frames within one VLAN, and if the frames need to be
`forwarded between different VLAN s, the forwarding must be 30
`implemented through the Layer 3 IP routing.
`FIG. 1 is a flow chart illustrating the bridge forwarding
`within one VLAN in the prior art. As shown in FIG. 1, the
`MAC address forwarding table is searched by using the des(cid:173)
`tination MAC address and the VLAN Identifier (ID), the exit 35
`information is obtained, and the frames are forwarded accord(cid:173)
`ing to the exit information. The main procedure of bridge
`forwarding includes the following steps:
`Step 101: Receiving the frame from the input port, and
`obtaining the input VLAN ID of the frame.
`Step 102: The self-learning of SMAC address is imple(cid:173)
`mented, i.e., recording the input port corresponding to the
`SMAC address in the MAC address forwarding table corre(cid:173)
`sponding to the VLAN ID.
`Step 103: Searching the MAC address forwarding table 45
`corresponding to the VLAN ID by using the destination MAC
`(DMAC) address obtained from the frame.
`Step 104: If the searching result in the step 103 is the
`unicast forwarding, performing the step 105; if the searching
`result in the step 103 is the multicast forwarding, performing 50
`the step 106; if the searching result is not hit, performing the
`step 108.
`Step 105: Searching the MAC address forwarding table to
`obtain the output port, and then proceeding to the step 110.
`Step 106: Searching the MAC address forwarding table to 55
`obtain the Multicast ID (MID).
`Step 107: Searching the Multicast table by using the MID
`to obtain a set of the output port, and then proceeding to the
`step 110.
`Step 108: Determining to forward the frame with the 60
`broadcast mode.
`Step 109: Obtaining all the output ports corresponding to
`the VLAN in which the input ports locates, and proceeding to
`the step 110.
`Step 110: Determining whether the output port is the same 65
`as the input port, if so, proceeding to the step 111; otherwise,
`proceeding to the step 112.
`
`40
`
`SUMMARY OF THE INVENTION
`
`The embodiments of present invention provide a bridge
`forwarding method and a bridge forwarding apparatus to
`realize cross-VLAN bridge forwarding of frames.
`A bridge forwarding method includes:
`obtaining an input virtual local area network (VLAN) iden(cid:173)
`tifier (ID) and a destination media access control (MAC)
`address of a frame upon receiving the frame from an input
`port;
`determining an output port and an output VLAN ID
`according to the input port, the input VLAN ID and the
`destination MAC address of the frame, and forwarding the
`frame according to the output port and the output VLAN ID.
`According to a preferable embodiment, the method
`includes:
`establishing relationship between one or more combina(cid:173)
`tions of input port and input VLAN ID with one Virtual
`Switching Instance (VSI);
`obtaining an input VLAN ID and a destination MAC
`address of a frame upon receiving the frame from an input
`port;
`determining the VSI corresponding to the combination of
`the input port and the input VLAN ID;
`obtaining the output port and the output VLAN ID corre(cid:173)
`sponding to the destination MAC address through searching a
`MAC address forwarding table corresponding to the VSI.
`According to another preferable embodiment of the
`present invention, the method includes:
`establishing relationship between one or more combina(cid:173)
`tions of input port, inner-layer VLAN ID and outer-layer
`VLAN ID with one VSI;
`obtaining the input inner-layer VLAN ID and the input
`outer-layer VLAN ID of the frame;
`determining the VSI corresponding to the combination of
`the input port, input inner-layer VLAN ID and input outer(cid:173)
`layer VLAN ID;
`obtain the output port, output inner-layer VLAN ID and
`output outer-layer VLAN ID corresponding to the destination
`MAC address through searching the MAC address forward(cid:173)
`ing table corresponding to the VSI.
`A Bridge forwarding apparatus includes:
`at least one input port, for receiving a frame from more than
`oneVLAN;
`a forwarding unit, for obtaining an input VLAN ID and a
`destination MAC address of the frame received from the input
`port, determining an output port and an output VLAN ID
`according to the input port, the input VLAN ID and the
`destination MAC address of the frame, and outputting the
`frame;
`
`Ex.1001
`VERIZON / Page 7 of 13
`
`

`

`3
`at least one output port, for transmitting the frame to more
`than one VLAN.
`wherein, the forwarding unit includes:
`a storing module, for storing relationship between combi(cid:173)
`nations of input port and input VLAN identifier and VS Is, as 5
`well as MAC address forwarding tables corresponding to the
`VS Is, wherein at least one combination ofinput port and input
`VLAN ID corresponds to one VSI;
`an input analyzing module, for obtaining the input VLAN
`ID and the destination MAC address of the frame, and out- 10
`putting the input VLAN ID and the destination MAC address;
`a first forwarding module, for determining the VSI corre(cid:173)
`sponding to the combination of the input port and the input
`VLAN ID according to the relationship between the combi- 15
`nation of the input port and the input VLAN ID and the VSI,
`and obtaining the output port and the output VLAN ID
`through searching the MAC address forwarding table corre(cid:173)
`sponding to the VSI;
`a second forwarding module, for forwarding the massage 20
`according to the output port and the output VLAN ID
`obtained by the first forwarding module.
`As can be seen from the above-mentioned technical
`scheme, the cross-VLANbridge forwarding of frames is real(cid:173)
`ized by establishing the relationship between the {Port,
`VLAN} and the VSI and implementing bridge forwarding of
`frames among different {Port, VLAN}s, and the multiple-to(cid:173)
`one relationship between multiple VLANs with one VSI,
`including one-to-one correspondent relationship is realized.
`The broadcast frames can also be copied for all the {Port,
`VLAN} combinations corresponding to the VSI, and the
`bridge broadcasting to multiple VLANs is supported.
`Further, during the process of frame forwarding, whether
`the input/output port is the same as the input/output VLAN ID
`is determined, so source port filtering can be implemented
`effectively to prevent forwarding loops. In addition, bridge
`forwarding among multi-layer VLAN IDs is supported by the
`present invention.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a flow chart illustrating the bridge forwarding of
`frames in the prior art.
`FIG. 2 is a flow chart illustrating the cross-VLAN bridge
`forwarding according to an embodiment of the present inven(cid:173)
`tion.
`FIG. 3 is a flow chart illustrating the cross-VLAN bridge
`forwarding according to another embodiment of the present
`invention.
`FIG. 4 is a schematic diagram illustrating the bridge for- 50
`warding apparatus according to an embodiment of the present
`invention.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`55
`
`The present invention will be further described in detail
`hereinafter with reference to the accompanying drawings to
`make the technical solution and the advantages of the present
`invention clearer.
`The embodiments of the present invention extend the exist- 60
`ing bridge forwarding method within one VLAN to realize
`the cross-VLAN bridge forwarding of frames. In the solution
`of the present invention, one VSI corresponds to a number of
`doublets {port, VLAN ID}, i.e., one VSI binds a number of
`doublets. Each doublet {port, VLAN ID} is regarded as a
`virtual port, so the bridge forwarding of frames is accom(cid:173)
`plished among the virtual ports.
`
`US 7,965,709 B2
`
`4
`In all the doublets corresponding to the same VSI, the
`relationship may be one port corresponding to one or more
`VLANs, or multiple ports corresponding to one or more
`VLANs. The VLAN may be one or more VLANs from the
`same Ethernet port, one or more VLAN s from different ports
`of the same Ethernet access network, or one or more VLAN s
`from different ports of multiple Ethernet access networks.
`
`Embodiment 1
`
`FIG. 2 is a flow chart illustrating the cross-VLAN bridge
`forwarding. As shown in FIG. 2, in this embodiment, the
`cross-VLAN bridge forwarding method mainly includes the
`steps of:
`Step 201: Receiving the frame from the input port.
`Step 202: Obtaining the input VLAN ID of the frame.
`Specifically, deciding whether the VLAN ID is carried in the
`frame, ifso, obtaining the VLAN ID of the frame; otherwise,
`obtaining the default VLAN ID relevant to the input port, and
`adding the VLAN ID into the frame.
`Step 203: Searching the mapping table by using the doublet
`{ input port, input VLAN ID} to determine the corresponding
`VSI. Here, the VSI is represented by VSI ID, and the search(cid:173)
`ing result is the corresponding VSI ID. For sake of simplify-
`25 ing the description, one doublet { input port, input VLAN ID}
`is defined as one input virtual port.
`The mapping table is established to prescribe the relation(cid:173)
`ship between a set of the multiple virtual ports and one VSI,
`and the format of the items in the mapping table is {port,
`30 VLAN ID, VSI ID}, and the keyword for searching the map(cid:173)
`ping table is {port, VLAN ID}, the searching result is the VSI
`ID corresponding to the virtual port.
`Step 204: The self-learning of SMAC address is imple(cid:173)
`mented, i.e., recording the input port and the input VLAN ID
`35 corresponding to the SMAC address in the MAC address
`forwarding table corresponding to the VSI.
`Step 205: Obtaining the DMAC from the frame, and
`searching the MAC address forwarding table corresponding
`to the VSI with the DMAC address as the keyword, or obtain-
`40 ing the DMAC address and the input VLAN ID from the
`frame, and searching the MAC address forwarding table cor(cid:173)
`responding to the VSI with the DMAC address and the VLAN
`ID as the keywords.
`For the instance of the MAC address forwarding table
`45 being not differentiated according to the VSI, i.e., only one
`MAC address forwarding table is configured, the unified
`MAC address table is searched with the VSI ID and the
`DMAC address as the keywords, or the unified MAC address
`table is searched with the VSI ID, the DMAC address and the
`input VLAN ID as the keywords.
`Step 206: If the searching result in the Step 205 is the
`unicast forwarding, proceeding the step 207; if the searching
`result is the multicast forwarding, proceeding the step 209; if
`the searching result is not hit, proceeding the step 213.
`One flag bit in the item of the MAC address forwarding
`table is used for representing unicast forwarding mode or
`multicast forwarding mode, so whether the frame is for(cid:173)
`warded with unicast or multicast mode can be determined
`according to the value of the flag bit.
`Step 207: Searching the MAC address forwarding table to
`obtain { output port, output VLAN ID}, for sake of simplify(cid:173)
`ing the description, defining the { output port, output VLAN
`ID} as the output virtual port.
`Step 208: Substituting the output VLAN ID for the input
`65 VLAN ID in the frame, and proceeding to the step 217;
`Step 209: Searching the MAC address forwarding table to
`obtain the output MID.
`
`Ex.1001
`VERIZON / Page 8 of 13
`
`

`

`US 7,965,709 B2
`
`5
`Step 210: searching the multicast table with the MID as a
`keyword to obtain a set of the output virtual port, i.e., { output
`port i, output VLAN IDi}, wherein, i= 1 ... n, the i is the serial
`number of the output virtual ports, and the n is the total
`numberof the obtained output virtual ports after searching the 5
`multicast table;
`The multicast table is established through the multicast
`protocol or any other approach in the switch, and the keyword
`for searching the multicast table is the MID. The searching
`result is a set of all the { output port, output VLAN ID} 10
`corresponding to the MID.
`Step 211: Copying the received frame ton copies, wherein
`the n is a positive integer.
`Step 212: Substituting the output VLAN IDi for the input 15
`VLAN ID in the frame, proceeding to the step 217.
`Step 213: If there is nothing can be found from the MAC
`address forwarding table, determining to forward the frame
`with the broadcast mode.
`Step 214: Obtaining all the output virtual ports correspond(cid:173)
`ing to the VSI, i.e., {output port j, output VLAN IDj},
`wherein, j=l ... m, the j is the serial number of the output
`virtual ports, and the m is the total number of the output
`virtual ports in the broadcast mode.
`All the output virtual ports corresponding to the VSI is
`obtained by searching the broadcast table, and the broadcast
`table is also established through the multicast protocol or any
`other approach in the switch. The keyword for searching the
`multicast table is the VSI ID, and the searching result is a set
`of all the { output port, output VLAN ID} corresponding to the
`VSI ID.
`Step 215: Copying the received frame tom copies.
`Step 216: Substituting the output VLAN IDj for the input
`VLAN ID in the frame, proceeding to the Step 217.
`Step 217: Determining whether the output virtual port is 35
`completely the same as the input virtual port, i.e., determining
`whether the output port is the same as the input port and the
`output VLAN ID is the same as the input VLAN ID, if the
`output port is the same as the input port and the output VLAN
`ID is the same as the input VLAN ID, proceeding to the Step
`218; if the output port is the same as the input port while the
`output VLAN ID is not the same as the input VLAN ID, or if
`the output port is not the same as the input port and the output
`VLAN ID is the same as the input VLAN ID, proceeding to
`the Step 219.
`Step 218: Abandoning the frame.
`Step 219: Forwarding the frame to the output port.
`The formal standard of the Virtual Bridge LAN, IEEE
`802.1 Q, prescribes that multiple logical subnet VLAN s can
`be divided in one physical bridge apparatus, and each VLAN 50
`corresponds to one logical forwarding table. In practical
`terms, one MAC address forwarding table is generally
`divided into multiple logical forwarding tables according to
`the VLAN ID. Four bytes are added in the Ethernet frame
`structure, and these four bytes are called generally as the 55
`Virtual Local Access Network Tag (VLAN Tag). In these four
`bytes, 12 bits are used for expressing the VLAN ID.
`The IEEE 802.1 ad standard adds Q-in-Q and VLAN Trans(cid:173)
`lation based on the IEEE 802.1 Q. The Q-in-Q refers to
`adding one more layer ofVLAN Tag for the frame of IEEE 60
`802.1 Qin an Ethernet switch, the previous Tag of the frame is
`known as CE-VLAN, and the new Tag added by the operators
`on the PE is called P-VLAN. Employing two layers of the
`VLAN makes the CE-VLAN used by the users and the
`P-VLAN used by the operators independent to each other. 65
`The VLAN Translation refers to translating one VLAN ID to
`another on a port of a bridge.
`
`6
`In the above-mentioned Step 208, Step 212 and Step 216,
`substituting the output VLAN ID for the VLAN ID in the
`frame. If the Q-in-Q service defined by the IEEE 802.1 ad
`protocol is adopted, the previous VLAN ID is reserved and a
`layer of new output VLAN ID is added, i.e., more 4 bytes are
`added, and 12 bits of the 4 bytes are used for expressing the
`output VLAN ID.
`In this embodiment, the process of the source port restraint
`can be performed after obtaining the output virtual port and
`before substituting the VLAN ID. For example, in the case of
`the unicast forwarding, after obtaining the virtual port in the
`Step 207, determining whether the output virtual port is com(cid:173)
`pletely the same as the input virtual port, if they are com(cid:173)
`pletely same, abandoning the frame and ending the current
`flow; if they are not completely same, substituting the output
`VLAN ID for the VLAN ID in the frame, as said in the Step
`208.
`As said in the Step 204, the MAC address forwarding table
`is established through self-learning, one MAC address for-
`20 warding table can be established in the switch, and the con(cid:173)
`tents learned in connection with the multiple VSis are
`recorded in the MAC address forwarding table. In the MAC
`address forwarding table, different VSI can be differentiated
`by VSI ID. Alternatively, multiple MAC address forwarding
`25 tables can be established, and each MAC address forwarding
`table corresponds to one VSI. When the SMAC address self(cid:173)
`learning is implemented, the input port and the input VLAN
`ID of the frame are recorded in the MAC address forwarding
`table corresponding to the VSI. The format of the items in the
`30 MAC address forwarding table is {VSI ID, MAC address,
`Port, VLAN ID}, the keyword for searching the table is {VSI
`ID, DMAC} or {VSI ID, DMAC, input VLAN ID}, and the
`searching result is corresponding { output port, output VLAN
`ID}.
`In the MAC address forwarding table, the VLAN ID can be
`recorded or searched indirectly through the format of the Tag
`Value or Tag Index. Here, the relationship between the VLAN
`ID and the Tag Value or the Tag Index should be established in
`advance. For instance, transforming the learned VLAN ID to
`40 a Tag Value or a Tag Index according to the pre-established
`relationship, and records the Tag Value or the Tag Index in the
`corresponding item in the MAC address forwarding table.
`When the output virtual port is found after searching the
`MAC address forwarding table with a keyword, and the out-
`45 put VLAN ID found is expressed by the Tag Value or the Tag
`Index, the output VALN ID can be obtained according to the
`pre-established relationship.
`
`Embodiment 2
`
`The Embodiment 1 describes the bridge forwarding of
`frames with only one input VLAN ID. In practical terms,
`however, there is more than one layer of input VLAN ID and
`output VLAN ID, i.e., there are two layers or more than two
`layers of input VLAN ID and output VLAN ID. For example,
`in the applications according to IEEE 802.1 ad standard, two
`layers ofVLAN IDs are carried in the frame. In this kind of
`application environment, there are two layers of input VLAN
`ID, so it possibly needs two layers of output VLAN ID. In this
`embodiment, a number of {input port, input outer-layer
`VLAN, input inner-layer VLAN} correspond to one VSI, i.e.,
`a number of { input port, input outer-layer VLAN, input inner(cid:173)
`layer VLAN} is bound with one VSI.
`The main procedure of bridge forwarding of frames with
`two layers of input VLAN ID and output VLAN ID 1s
`described in detail with reference to FIG. 3.
`Step 301: Receiving the frame from the input port.
`
`Ex.1001
`VERIZON / Page 9 of 13
`
`

`

`US 7,965,709 B2
`
`10
`
`30
`
`7
`Step 302: Determining whether the VLAN ID is carried in
`the frame, if so, obtaining the VLAN ID including the outer(cid:173)
`layer VLAN ID and the inner-layer VLAN ID in the frame;
`otherwise, obtaining the default outer-layer VLAN ID and the
`default inner-layer VLAN ID relevant to the input port, and 5
`adds the default outer-layer VLAN ID and the default inner(cid:173)
`layer VLAN ID in the frame.
`Step 303: Searching the mapping table by using the input
`virtual port, i.e., using a triplet {input port, input VLAN ID}
`to determine the corresponding VSI ID.
`Step 304: The self-learning of SMAC address is imple(cid:173)
`mented. That is, recording the input port, input outer-layer
`VLAN ID and the input inner-layer VLAN ID corresponding
`to the SMAC address in the MAC address forwarding table 15
`corresponding to the VSI.
`Step 305: Obtaining the DMAC address from the frame,
`and searching the MAC address forwarding table correspond(cid:173)
`ing to the VSI with the DMAC address as the keyword, or
`searching the MAC address forwarding table corresponding 20
`to the VSI with the DMAC address, the input inner-layer
`VLAN and the input outer-layer VLAN ID as the keywords.
`For the instance of the MAC address forwarding table
`being not differentiated according to the VSI, i.e., only one
`MAC address forwarding table is configured, the unified 25
`MAC address forwarding table is searched with the VSI ID
`and the DMAC address as the keywords, or the unified MAC
`address forwarding table is searched with the VSI ID, the
`DMAC address, and the input inner-layer VLAN and the
`input outer-layer VLAN ID as the keywords.
`Step 306: If the searching result in the Step 305 is the
`unicast forwarding, proceeding to the Step 307; if the search(cid:173)
`ing result is the multicast forwarding, proceeding to the Step
`309; if the searching result is not hit, proceeding to the Step
`313.
`Step 307: Searching the MAC address forwarding table to
`obtain the output triplet { output port, output outer-layer
`VLAN ID, output inner-layer VLAN ID}.
`Step 308: Substituting the output out-layer VLAN ID for
`the input outer-layer VLAN ID in the frame, proceeding to the 40
`Step 317.
`Step 309: Searching the MAC address forwarding table to
`obtain the output MID.
`Step 310: Searching the multicast table using the MID to
`obtain a set of the output virtual ports, i.e., { output port i, 45
`output outer-layer VLAN IDi, output inner-layer VLAN IDi},
`wherein, i=l ... n, the i is the serial number of the output
`virtual ports, and then is the total number of the output virtual
`ports found by searching the multicast table.
`Step 311: Copying the received frame ton copies.
`Step 312: Substituting the output outer-layer VLAN IDi for
`the input outer-layer VLAN ID in the frame, substituting the
`output inner-layer VLAN IDi for the input inner-layer VLAN
`ID in the frame, and then proceeding to the Step 317.
`Step 313: If there is nothing can be found after searching 55
`the MAC address forwarding table, determining that the
`frame is forwarded with the broadcast mode.
`Step 314: Obtaining all the output virtual ports correspond(cid:173)
`ing to the VSI, i.e., { output port j, output outer-layer VLAN
`IDj, output inner-layerVLAN IDj}, wherein,j=l ... m, thej 60
`is the serial numberofthe output virtual ports, and them is the
`total number of the broadcast output virtual ports.
`Step 315: Copying the received frame tom copies.
`Step 316: Substituting the output outer-layer VLAN IDj for
`the input outer-layer VLAN ID in the frame, substituting the 65
`output inner-layer VLAN IDj for the input inner-layer VLAN
`ID in the frame, and then proceeding to the step 317.
`
`8
`Step 317: Determining whether the output virtual port is
`completely the same as the input virtual port, i.e., determining
`whether the output port, the output outer-layer VLAN ID and
`the output inner-layer VLAN ID are the same as the input
`port, the input outer-layer VLAN ID and the input inner-layer
`VLAN ID respectively; if the output port, the output outer-
`layer VLAN ID and the output inner-layer VLAN ID are the
`same as the input port, the input outer-layer VLAN ID and the
`input inner-layer VLAN ID respectively, proceeding to the
`Step 318; otherwise, proceeding to the Step 319.
`Step 318: Abandoning the frame.
`Step 319: Forwarding the frame to the output port.
`In summary, the present invention combines multiple
`{port, VLAN} s in a set, and binds the set to one VSI, then the
`Ethernet frame is forwarded among the {Port, VLAN}s cor(cid:173)
`responding to the same VSI, thereby realizing the cross(cid:173)
`VLAN bridge forwarding of frames. The main idea of the
`bridge forwarding is: obtaining the VLAN ID in the frame
`upon receiving the frame from the input port; determining the
`VSI corresponding to the {input port, input VLAN ID};
`searching the { output port, output VLAN ID} corresponding
`to the {VSI, DMAC} in the MAC address forwarding table,
`and forwarding the frame according to the { output port, out(cid:173)
`put VLAN ID} found after searching the table. Here, the
`VLAN ID can be one VLAN ID or a combination of two or
`multiple VALN IDs. For instance, a number of {port, outer(cid:173)
`layer VLAN, inner-layer VLAN} and {port, VLAN} are
`bound to one VSI.
`One layer ofVLAN ID or two or more layers ofVLAN ID
`can be obtained from the inputted frame.
`If there is one layer ofVLAN ID, the VS