Ulllted States Patent
`
`[19]
`
`[11] Patent Number:
`
`6,081,522
`
`Hendel et al.
`
`[45] Date of Patent:
`
`Jun. 27, 2000
`
`US006081522A
`
`[54]
`
`[75]
`
`SYSTEM AND METHOD FOR A
`MULTLLAYER NETWORK ELEMENT
`
`Inventors: Ariel Hendel, Cupertino; Leo A.
`Hejza; Shree Murthy, both of
`Sunnyvale, all of Calif.
`
`[73] Assignee: Sun Microsystems, Inc., Mountain
`View, Calif.
`
`[21] Appl. No.: 08/885,559
`
`[22]
`
`Filed:
`
`Jun. 30, 1997
`
`Int. Cl.7 ........................... .. H04L 12/28; H04L 12/56
`[51]
`
`[52] U.S. Cl.
`............. ..
`. 370/389; 370/412; 370/428
`[58] Field of Search ................................... .. 370/389, 392,
`370/400, 401, 402, 432, 469, 412, 413-419,
`428,429; 340/825.52; 395/200.1, 200.2
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`9/1985 DeB1ule1‘ ............................... .. 364/200
`4,539,637
`4,627,052 12/1986 Hoare et al.
`.. 370/88
`4,641,302
`2/1987 Miller ...................................... .. 370/60
`4,652,874
`3/1987 Loyer ............................... .. 340/825.05
`4,737,953
`4/1988 Koch et al.
`.... .. 370/94
`.
`4,807,111
`2/1989 Cohen et al.
`364/200
`4,811,337
`3/1989 Hart
`............ ..
`.. 370/85
`4,850,042
`7/1989 Petronio et al.
`...................... .. 455/606
`4,899,333
`2/1990 Roediger ............................... .. 370/427
`4,922,503
`5/1990 Leone
`. 370/85.13
`4,933,938
`6/1990 Sl1eel1y .... ..
`. 370/85.13
`4,935,869
`6/1990 Yamamoto
`364/200
`5,130,977
`7/1992 May et al.
`.. 370/60
`5,150,358
`9/1992 Punj et al.
`370/468
`5,159,685
`10/1992 Kung ....... ..
`395/575
`5,163,046
`11/1992 Hahne et al.
`.. 370/79
`5,210,746
`5/1993 Maher et al.
`.. 370/79
`5,220,562
`6/1993 Takada et al.
`370/401
`5,231,633
`7/1993 Hluchyj et al.
`370/94.1
`5,251,205
`10/1993 Callon et al.
`........................... .. 370/60
`
`.
`.
`
`5,278,830
`5,291,482
`5,293,379
`
`1/1994 Kudo .................................... .. 370/94.1
`. 370/413
`3/1994 McHarg et al.
`
`...................................... .. 370/474
`3/1994 Carr
`
`(List continued on next page.)
`OTHER PUBLICATIONS
`
`“Load Balancing for Multiple Interfaces for Transmission
`Control Protocol/Internet Protocol for VM/MVS”,
`IBM
`Technical Disclosure Bulletin, 38(9): 7-9 (Sep., 1995).
`T. Nishizono et al., “Analysis on a Multilink Packet Trans-
`mission System”, Electron. Commun. JPN 1, Commun.,
`(USA), 68(9): 98-104 (Sep., 1985).
`International Search Report, PCT/US 98/13203.
`The Institute of Electrical & Electronics Engineers, Inc.,
`“International Standard” ISO/IEC 10038, ANSI/IEEE Std.
`802.1D, First edition, 1993-07-08, pp.1-180.
`Microsoft Press, “Microsoft Computer Dictionary Fourth
`Edition”, Microsoft Corporation, 1999, 4 pages.
`
`(List continued on next page.)
`
`Primary Examiner—Ajit Patel
`Attorney, Agent, or Firm—Blakely Sokoloff Taylor &
`Zafman
`
`[57]
`
`ABSTRACT
`
`A multi-layer network element for forwarding received
`packets from an input port to one or more output ports. The
`packet is examined to look for different types of forwarding
`information. An associative memory is searched once for
`each type of information. The results from the two searches
`are combined to forward the packet to the appropriate one or
`more output ports. The packet may be examined for other
`information as well to make the forwarding decisions. In one
`embodiment, the invention examines the packet for layer 2
`information as the first type and layer 3, and perhaps some
`layer 4, information as the second type. The results are
`merged to determine the most appropriate combination of
`layer 2 or layer 3 forwarding decisions for the packet.
`
`29 Claims, 7 Drawing Sheets
`
`
`
`Multilayer
`Network Element I
`
`12
`
`
`
`
`ARISTA 100
`
`1
`
`ARISTA 1004
`
`

`
`................ .. 395/200.17
`7/ 997 Griesmer et al.
`..
`370 392
`7 997 Van Seters et al.
`370/20012
`10/ 997 Aggarwaletal.
`..
`370/401
`11/ 997 Dobbins et al.
`11/ 997 Chiussi et al.
`........................ .. 370/388
`11/ 997 Galand et al.
`....................... .. 371/37.1
`11/ 997 Gardner et al.
`370/401
`1/ 998 Ruff et al.
`....... ..
`395/497.04
`2/ 998 Picazo, Jr. et al.
`.. 395/200.8
`3/ 998 Basso et al.
`370/384
`3/ 998 Headfick 61 91-
`~ 370/418
`Lee ........................................ ..
`3/ 998 Blakeley et al.
`...................... .. 370/392
`3/ 998 Yu ............... ..
`.. 395/500
`4/ 998 Mazzola et al.
`. 370/392
`4/ 998 Wakeman et al.
`3'95/422
`4/ 998 01111110 0101 ~~
`395/20008
`4/ 998 EF153110/1a1~
`370/401
`4/ 998 P1cazo,.Jr., et al.
`.................. .. 370/351
`4/ 998 Taguchret al.
`.................. .. 340/870.01
`5/ 998 Bergantino et al.
`370/398
`5/ 998 Hauseretal.
`................... .. 395/200.79
`5/ 998 Raabet al.
`....................... .. 395/200.58
`5/ 998 D.°1’1’1“”1*‘1"
`595’29008
`5/ 998 11}1F1‘*1~
`3,70/315
`..
`5/ 998 Bittinger et al.
`395/200.33
`5/ 998 160110100111 0101-
`395/308
`5/ 998 110131
`~ 370/235
`5/998 Schnell .................................. .. 370/392
`Fuknda 61. al.
`................... ..
`6/ 998 Christensen et al
`.......... ..
`
`370/401
`
`
`
`..
`
`
`
`..
`
`
`
`5,649,109
`5 651 002
`5:675:741
`5,684,800
`5,689,506
`5,689,518
`5,691,984
`5,706,472
`5,720,032
`5,724,348
`57249358
`
`5,734,651
`5,734,865
`5,740,171
`5,740,175
`597409375
`597429004
`5,742,760
`5,745,048
`5,748,631
`5,748,905
`5,751,967
`597519971
`597549540
`5,754,774
`597549801
`597579771
`5,757,795
`
`5,764,634
`
`6,081,522
`Page 2
`
`370/60
`
`
`
`
`
`N
`
`
`
`U.S. PATENT DOCUMENTS
`395/725
`4/1994 Lee ........
`5,301,333
`340/827
`5/1994 Perlman et al.
`5,309,437
`.......................... .. 370/13
`5/1994 Bustini ct al.
`5,313,454
`8/1994 Cassagnol
`.......................... .. 370/85.13
`5,343,471
`5,353,412 10/1994 Douglas et al.
`395/325
`5355514 11/1994 Hershey et a1_
`________________________ __ 370/17
`5,386,413
`1/1995 McAuley et al.
`....................... .. 370/54
`5,392,432
`2‘/1995 Engelstad et al.
`395/7(1)
`5,394,402
`2/1995 Ross ....... ..
`370/401
`et al
`I 370/60
`........ N
`3/1995 Tumel
`5,402,415
`N 395/725
`4,1995 Kmppweisj Sr.
`5404538
`N 370/390
`4/1995 Aiki et al.
`.
`5,410,540
`395/800
`4/1995 Comaby
`594109722
`5/1995 Perlman ........................... .. 370/85.013
`5,420,862
`6/1995 L111 .......................................... .. 365/49
`5,422,838
`0/1995 Mori .... N
`. 370/60
`5,425,020
`6/1995 Brinon et al.
`N 370/94.1
`5,425,028
`6/1995 Guinean HI
`395/250
`594269736
`74995 Picmj in 6, al.
`N 395/200
`574327907
`9/1995 sugita .... N
`N 370/60.1
`5,450,399
`5,455,820 10/1995 Yamada ................................. .. 370/413
`5,457,681
`10/1995 Gaddis etal.
`........................ .. 370/402
`574597714
`10/1995 Lo et al.
`N 370/13.1
`5,459,717 10/1995 Mullan etal.
`370/351
`5,461,611
`10/1995 D1'ake,J1'. etal.
`. 370/54
`5,401,024 10/1995 Mazzola ..... N
`370/402
`Hausman '
`12/1995 Dankert et a1’
`Huang ........ N
`370/255
`1/1996 Dobbins et al.
`5,485,455
`1/1996 Sweazey .......................... .. 395/200.54
`5,485,578
`2/1996 Baker et al.
`............................ .. 370/60
`5,490,139
`2/1996 Macem et al.
`. 395/200.01
`574907252
`'
`2/1996 Miller et al.
`395/427
`5,490,260
`2/1996 Mullan ......................... .. 370/54
`5,493,564
`3/1990 Perlman et al.
`.
`5,500,800
`................. .. 395/200.15
`4/1996 Dobbins et al.
`5,509,123
`........................ .. 340/402
`5/1996 Murthy et al.
`5,515,376
`5/1996 Miyazaki et al.
`....................... .. 370/16
`5,517,488
`7/1996 Kondoh ......... ..
`370/60.1
`5,535,202
`8/1996 Hardwick et al.
`. 370/60
`5,550,816
`9/1996 Wralker et al.
`. 370/60
`5,553,067
`9/1996 Griesmer et al.
`395/600
`575557405
`9/1996 Calamvokis et al.
`N 370/60.1
`5,557,610
`10/1996 Christensen etal.
`370/434
`5,561,666
`10/1996 Mendelson etal.
`395/550
`5,561,791
`5,563,878 10/1996 Blakeley etal. .
`. 370/60
`55667170 104996 Bakke et al.
`............................ N 370/60
`5,570,365
`10/1996 Yoshida ................................ .. 370/85.6
`5,572,522
`11/1996 Calamvokis etal.
`370/395
`5,574,801
`11/1996 Lorvig et al.
`. 395/200.06
`5,583,981
`12/1996 Pk,/yer
`.... N
`395/326
`
`575927476
`1/1997 Calamvokis at a.
`370/390
`5,594,727
`1/1997 Kolbenson et al.
`370/468
`5,600,641
`2/1997 Duaultetal.
`......................... .. 370/400
`5,602,841
`2/1997 Lebizay etal.
`....................... .. 370/413
`5,606,669
`2/1997 Benin et al.
`'
`. 395/200.15
`....... ..
`3/1997 Murthy ct al.
`3/1997 Dai et al.
`ear1~et~~;i1
`4:/1997 Hiekji .......N '
`4/1997 Crews ct al.
`'
`4/1997
`5/1997
`5‘/1997
`6/1997
`6/1997 Johnson ct al.
`
`
`
`370/414
`N 395/299
`370/381
`364/514
`370/412
`395/500
`....................... .. 395/881
`
`370/401
`. 395/200.17
`-~
`
`574777537
`
`5,610,905
`5,615,340
`
`5619300
`5,619,661
`5,623,489
`5,033,710
`5,633,365
`5,636,371
`5,640,605
`
`3,70/398
`7/ 998 D01
`597819549
`395/20013
`7/ 998 01121010101‘
`597849559
`~~ 395/2008
`7/ 998 8Z°Z°P‘“1°1‘ 0151
`597849573
`8/ 998 Dobbins et al.
`...................... .. 370/400
`5,790,546
`8/ 998 Seaman ............................ .. 395/200.53
`5,790,808
`9/ 998 K100511110
`370/359
`58029047
`9/ 998 Venkataraman ....................... .. 370/395
`5,802,052
`9/ 998 1510100101" """""""""""""""" " 395’200'02
`598029278
`9/ 998 K1100 0101
`370/232
`598129527
`9/ 998 13001313110 ~~~~ ~~
`~~ 395/905
`598159737
`10/ 998 N0g‘““1 91. 01
`' 579/592
`598229319
`10/ 998 11711201305111 0131
`~ 370/395
`598259707
`5,825,772 10/ 998 Doblains et al.
`..
`. 370/396
`5,835,491
`11/ 998 Davis et al.
`.......................... .. 370/386
`5,838,677
`11/ 998 Kozakret al.
`........................ .. 370/389
`58389081
`11/ 998 130110101010
`~ 370/395
`598529007
`12/ 998 011111 ~~~~~~~~~ ~
`~ 370/401
`598509977
`1/ 999 1011801 ‘*1
`~ 370/411
`5,859,849
`1/ 999 Parks ........ ..
`.. 370/395
`598079077
`2/ 999 15010110010 ~
`~ 395/311
`598729783
`2/ 999 0111".-------------------------------------- -- 3,70/395
`5,872,904
`2/ 999 lVIcM1llen et al.
`............... .. 395”/182.02
`5,875,464
`2/999 Knk . . . . . . . . . . .
`.. . ..
`/11/129
`5,878,043
`3/ 999 Casey .................................... .. 370/397
`5,878,232
`3/ 999 Marirnuthu ....................... .. 395/200.79
`598929912
`4/ 999 80711151010 --
`395/200-48
`598989087
`4/ 999 11011004“ 0101
`370/390
`5,931,980
`11/ 998 Vanna et al.
`..
`. 370/395
`
`
`
`
`
`International Search Report, PCT/US98/13206, 6 pages.
`International Search Report, PCT/US98/13362, 5 pages.
`International Search Report, PCT/US98/13203, 7 Pages.
`International Search Report, PCT/US98/13361, 5 pages.
`International Search Report, PCT/US98/13200, 6 pages.
`International Search Report, PCT/US98/13202, 4 pages.
`International Search Report, PCT/US98/13368, 5 pages.
`International Search Report, PCT/US98/13364, 4 pages.
`International Search Report, PCT/US98/13365, 4 pages.
`
`2
`
`

`
`6,081,522
`Page 3
`
`International Search Report, PCT/US98/13177, 4 pages.
`International Search Report, PCT/US98/13199, 5 pages.
`International Search Report, PCT/US98/13015, 5 pages.
`International Search Report, PCT/US98/13380, 4 pages.
`International Search Report, PCT/US98/13016, 4 pages.
`Wang et al., A Novel Message Switch for Highly Parallel
`Systems, IEEE, pp. 150-155, 1989.
`Tobagi, Fast Packet SwitchArchitectures for Broadband
`Integrated Services Digital Networks, Proceedings of the
`IEEE, Vol. 78, Issue 1, pp. 133-167, Jan. 1990.
`Fliesser et al., Design of a Multicast ATM Packet Switch,
`Electrical and Computer Engineering, 1993 Canadian Con-
`ference, pp. 779-783, 1993.
`Chang et al., An Overview of the Pipelined Common Buffer
`Architecture
`(PCBA)
`for Memory Based Packet/Cell
`Switching Systems, Local Computer Networks, 1994, pp.
`288-297, 19th Conference, IEEE.
`Agrawal et al., A Scalable Shared Buffer ATM Switch
`Architecture, VLSI, 1995 5th Great Lakes Symposium,
`IEEE, pp. 256-261, 1994.
`
`Sabaa et al., Implementation of a Window-Based Scheduler
`in an ATM Switch, Electrical and Computer Engineering,
`1995 Canadian Conference, IEEE, pp. 32-35, 1995.
`Naraghi-Pour et al., A Multiple Shared Memory Switch,
`System Theory, 1996 Southeastern Symposium, IEEE, pp.
`50-541996.
`
`Iyengar et al., Switching Prioritized Packets, GLOBECOM
`’89:
`IEEE Global Telecommunications Conference, pp.
`1181-1186, 1989.
`“Foundry Products”, downloaded from Website http://ww-
`w.foundrynet.com/ on Jun. 19, 1997.
`Anthony J. McAuley & Paul Francis, “Fast Routing Table
`Lookup Using CAMs”, IEEE, 1993, pp. 1382-1390.
`“Gigabit Ethernet”, Network Strategy Report, The Burton
`Group, V2, May 8, 1997 40 pages.
`“IP On Speed”, Erica Roberts, Internet-Draft, Data Com-
`munications on the Web, Mar. 1997, 12 pages.
`“Multilayer Topology”, White Paper, Internet-Draft, 13
`pages, downloaded from Website http://VWvwbaynetwork-
`s.com on Apr. 18, 1997.
`
`3
`
`

`
`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 1 of 7
`
`6,081,522
`
`\DV-I
`
`3
`‘-3
`O
`04
`
`X
`
`C
`
`O
`O
`
`2
`
`F I
`
`(5
`
`9|
`
`2/
`
`x
`—«
`
`:3O
`
`
`
`-«Ln
`‘>’~es
`-20
`as
`=3
`22
`
`E \2
`
`4
`
`

`
`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 2 of 7
`
`.60
`E22
`
`mantaK.CoEuE
`E01r
`
`mm
`
`uommoooi
`
`uommouoi
`
`
`finEoEo_mx._o.EoZ
`mmE3322
`
`.CoEu2
`
`E23,
`
`..5
`
`5
`
`

`
`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 3 of 7
`
`6,081,522
`
`Sm
`
`S
`
`BEo8m<
`
`.0053)...
`
`mEEu3._om
`
`.CoEo2
`
`9.
`
`uomwoooi
`
`mm
`
`In
`
`om|u\\.
`
`mm
`
`mfiuaéom
`
`0&3
`
`«onan
`
`tom
`
`Ian
`F...-
`Iqwm
`
`OO0
`
`Iam
`
`m._0_n_
`
`6
`
`
`
`

`
`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 4 of 7
`
`6,081,522
`
`338$.
`
`.CoEo_2
`
`9/
`
`3/
`
`w:::mB._om
`
`F5503
`
`._ommoo8m
`
`mm
`
`wfinaiom
`
`0&3
`
`am
`
`7
`
`
`
`
`
`
`

`
`U.S. Patent
`
`00027:2n.uJ
`
`h
`
`7
`
`6
`
`225,
`
`1Is00,m_n_
`
`5canonmafiazflmuvMucoucoauv
`
`mmufium
`
`M535820onon
`
`S0&3
`
`couo<
`
`3.20
`
`8
`
`nouflnmmmocm
`
`omwoq
`
`8
`
`
`
`

`
`netaPS”U
`
`7:2n.
`
`0
`
`Sheet 6 of 7
`
`6,081,522
`
`00
`
`S
`
`3.30S83
`
`xadun
`
`mcouo<
`
`238m
`
`hmznmom
`
`S83
`
`tS_
`
`mK2m_H
`
`9
`
`wzamom
`
`9
`
`
`

`
`U
`
`aP
`
`S
`
`7fl.0
`
`000’6
`
`2n
`
`1,NGE
`
`gm
`
`ow.u2
`
`31.50%
`
`
`
`um.couacumofl
`
`flnoaom
`
`nfiSm
`
`
`
`temI\KHmomWBxuamozouom
`
`n.8”h
`
`noaom85cmmu
`
`
`
`tom2:F83n8BomWNSn«on xWSN 0E:2031Woo.aom
`
`
`
`10
`
`
`

`
`6,081,522
`
`1
`SYSTEM AND METHOD FOR A
`MULTI-LAYER NETWORK ELEMENT
`
`FIELD OF THE INVENTION
`
`to packet for-
`The present invention relates in general
`warding within a network and, in particular, to a system and
`method for forwarding packets using multi-layer informa-
`tion.
`
`BACKGROUND OF THE INVENTION
`
`Communication between computers has become an
`important aspect of everyday life in both private and busi-
`ness environments. Networks provide a medium for this
`communication and further for communication between
`
`various types of elements connected to the network such as
`servers, personal computers, workstations, memory storage
`systems, or any other component capable of receiving or
`transmitting data to or from the network. The elements
`communicate with each other using defined protocols that
`define the orderly transmission and receipt of information.
`In general, the elements view the network as a cloud to
`which they are attached and for the most part do not need to
`know the details of the network architecture such as how the
`
`network operates or how it is implemented. Ideally, any
`network architecture should support a wide range of appli-
`cations and allow a wide range of underlying technologies.
`The network architecture should also work well for very
`large networks, be efficient for small networks, and adapt to
`changing network conditions.
`Networks can be generally be differentiated based on their
`size. At the lower end, a local area network (LAN) describes
`a network having characteristics including multiple systems
`attached to a shared medium, high total bandwidth,
`low
`delay,
`low error
`rates, broadcast capability,
`limited
`geography, and a limited number of stations, and are gen-
`erally not subject to post, telegraph, and telephone regula-
`tion. At
`the upper end, an enterprise network describes
`connections of wide area networks and LANs connecting
`diverse business units within a geographically diverse busi-
`ness organization.
`To facilitate communication within larger networks, the
`networks are typically partitioned into subnetworks, each
`sharing some common characteristic such as geographical
`location or functional purpose, for example. The partitioning
`serves two main purposes: to break the whole network down
`into manageable parts and to logically (or physically) group
`users of the network. Network addressing schemes may take
`such partitioning into account and thus an address may
`contain information about how the network is partitioned
`and where the address fits into the network hierarchy.
`For descriptive and implementive purposes, a network
`may be described as having multiple layers with end devices
`attached to it, communicating with each other using peer-
`to-peer protocols. The well-known Open Systems Intercon-
`nection (OSI) Reference Model provides a generalized way
`to view a network using seven layers and is a convenient
`reference for mapping the functionality of other models and
`actual implementations. The distinctions between the layers
`in any given model is clear, but the implementation of any
`given model or mapping of layers between different models
`is not. For example, the standard promulgated by the Insti-
`tute of Electrical and Electronics Engineers (IEEE) in its 802
`protocols defines standards for LANs and its definitions
`overlap the bottom two layers of the OSI model.
`In any such model, a given layer communicates either
`with the same layer of a peer end station across the network,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`or with the same layer of a network element within the
`network itself. Alayer implements a set of functions that are
`usually logically related and enable the operation of the
`layer above it.
`The relevant layers for describing this invention include
`OSI Layers 1 through 4. Layer 1, the physical layer, provides
`functions to send and receive unstructured bit patterns over
`a physical link. The physical layer concerns itself with such
`issues as the size and shape of connectors, conversion of bits
`to electrical signals, and bit-level synchronization. More
`than one type of physical layer may exist within a network.
`Two common types of Layer 1 are found within IEEE
`Standard 802.3 and FDDI (Fiber Distributed Data Interface).
`Layer 2, the data link layer, provides support for framing,
`error detecting, accessing the transport media, and address-
`ing between end stations interconnected at or below layer 2.
`The data link layer is typically designed to carry packets of
`information across a single hop, i.e., from one end station to
`another within the same subnet, or LAN.
`Layer 3, the network layer, provides support for such
`functions as end to end addressing, network topological
`information, routing, and packet fragmentation. This layer
`may be configured to send packets along the best “route”
`from its source to its final destination. An additional feature
`
`of this layer is the capability to relay information about
`network congestion to the source or destination if conditions
`warrant.
`
`the transport layer, provides application pro-
`Layer 4,
`grams such as an electronic mail program with a “port
`address” which the application can use to interface with the
`data link layer. Akey difference between the transport layer
`and the lower layers is that an application on a source end
`station can carry out a conversation with a similar applica-
`tion on a destination end station anywhere in the network;
`whereas the lower layers carry on conversations with end
`stations which are its immediate neighbors in the network.
`Layer 4 protocols also support reliable connection oriented
`services, an example Layer 4 protocol providing such ser-
`vices is the Transport Control Protocol (TCP).
`Different building blocks exist for implementing net-
`works that operate at these layers. End stations are the end
`points of a network and can function as sources, destinations
`and network elements or any other intermediate point for
`forwarding data received from a source to a destination.
`At the simplest level are repeaters which are physical
`layer relays which simply forward bits at Layer 1.
`Bridges represent the next level above repeaters and are
`data link layer entities which forward packets within a single
`LAN using look-up tables. They do not modify packets, but
`just forward packets based on a destination. Most bridges are
`learning bridges. In these bridges, if the bridge has previ-
`ously learned a source, it already knows to which port to
`forward the packet. If the bridge has not yet forwarded a
`packet from the destination, the bridge does not know the
`port location of the destination, and forwards the packet to
`all unblocked output ports, excluding the port of arrival.
`Other than acquiring a knowledge of which ports sources are
`transmitting packets to, the bridge has no knowledge of the
`network topology. Many LANs can be implemented using
`bridges only.
`Routers are network layer entities which can forward
`packets between LANs. They have the potential to use the
`best path that exists between sources and destinations based
`on information exchanged with other routers that allow the
`routers to have knowledge of the topology of the network.
`Factors contributing to the “best” path might include cost,
`speed, traffic, and bandwidth, as well as others.
`
`11
`
`11
`
`

`
`6,081,522
`
`3
`Brouters are routers which can also perform as bridges.
`For those layer 3 protocols of which the brouter knows, it
`uses its software to determine how to forward the packet.
`For all other packets, the brouter acts as a bridge.
`Switches are generalized network elements for forward-
`ing packets wherein the composition of the switch and
`whether it implements layer 2 or layer 3 is not relevant.
`Typically, bridges forward packets in a flat network
`without any cooperation by the end stations, because the
`LAN contains no topological hierarchy.
`If a LAN, for
`example, is designed to support layer 3 functionality, then
`routers are used to interconnect and forward packcts within
`the LAN.
`
`Bridges cannot use hierarchical routing addresses because
`they base their forwarding decisions on media access control
`(MAC) addresses which contain no topological significance.
`Typically MAC addresses are assigned to a device at its time
`of manufacture. The number of stations that can be inter-
`
`connected through bridges is limited because traffic
`isolation, bandwidth, fault detecting, and management
`aspects become too difficult or burdensome as the number of
`end stations increases.
`
`Learning bridges self-configure, allowing them to be
`“plug and play” entities requiring virtually no human inter-
`action for setup. Routers, however,
`require intensive
`configuration, and may even require configuration activities
`at the end nodes. For example, when a network utilizes the
`Transmission Control Protocol/Internet Protocol (TCP/IP),
`each end node must manually receive its address and subnet
`mask from an operator, and such information must be input
`to the router.
`
`Generally, as the size and complexity of a network
`increases,
`the network requires more functionality at the
`higher layers. For example, a relatively small LAN can be
`implemented by using Layer 1 elements such as repeaters or
`bridges, while a very large network uses up to and including
`Layer 3 elements such as routers.
`Asingle LAN is typically insufficient to meet the require-
`ments of an organization because of the inherent limitations:
`(1) on the number of end stations that can be attached to a
`physical layer segment; (2) the physical layer segment size;
`and (3) the amount of traffic, which is limited because the
`bandwidth of the segment must be shared among all the
`connected end stations.
`In order
`to overcome these
`constraints, other network building blocks are required.
`As briefly described above, when the number of end
`stations in a network increases, the network may be parti-
`tioned into subnetworks. A typical address in a partitioned
`network includes two parts: a first part indicating the sub-
`network; and a second part indicating an address within the
`subnetwork. These types of addresses convey topological
`information because the first part of the address defines
`geographical or logical portions of the network and the
`second part defines an end station within the subnetwork
`portion. Routing with hierarchial addressing involves two
`steps: first packets are routed to the destination’s subnet-
`work; and second packets are forwarded to the destination
`within the subnetwork.
`
`An end station receives a unique data link address—the
`MAC address—at the time of manufacture, allowing the end
`station to attach to any LAN within a bridged network
`without worrying about duplicate addresses. Data link
`addresses therefore cannot convey any topological informa-
`tion. Bridges, unlike routers, forward packets based on data
`link addresses and thus cannot
`interpret hierarchical
`addresses.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`The current Internet is being forced to deal with increas-
`ing numbers of users and increasing demands of multimedia
`applications. Future networks will be required to support
`even higher bandwidth, larger numbers of users, and trafiic
`classification requirements by the network. Statistical stud-
`ies show that the network domain as well as the number of
`workstations connected to the network will grow at a faster
`rate in future. The trend is also to support multiple traffic
`types with varied characteristics on a same physical link.
`This calls for more network bandwidth and efficient usage of
`resources. To meet the bandwidth requirement, the speed on
`the networks is on the upward trend, reaching to gigabit
`speeds.
`Network designers frequently use one particular combi-
`nation of OSI Layer 2 and Layer 3 because of the success of
`the Internet and the increasing number of products and
`networks using the Internet. Specifically,
`in a typical
`Internet-associated network, designers combine an imple-
`mentation in accordance with the IEEE 802 Standard (which
`overlaps OSI Layer 1 and Layer 2) with the Internet Protocol
`(IP) network layer. This combination is also becoming
`popular within enterprise networks such as intranets.
`Supporting this combination by building networks out of
`layer 2 network elements provides fast packet forwarding
`but has little flexibility in terms of traflic isolation, redundant
`topologies, and end-to-end policies for queuing and admin-
`istration (access control). Building such networks out of
`layer 3 elements alone sacrifices performance and is imprac-
`tical from the hierarchical point of view because of the
`overhead associated with having to parse the layer 3 header
`and modify the packet if necessary. Furthermore, using
`solely layer 3 elements forces an addressing model with one
`end station per subnet, and no layer 2 connectivity between
`the end stations.
`
`Nctworks built out of a combination of layer 2 and layer
`3 devices are used today, but suffer from performance and
`flexibility shortcomings. Specifically, with increasing varia-
`tion in traffic distribution (the role of the “server” has
`multiplied with browser-based applications),
`the need to
`traverse routers at high speed is crucial.
`The choice between bridges and routers typically results
`in significant tradeoffs (in functionality when using bridges,
`and in speed when using routers). Furthermore, the service
`characteristics, such as priority, within a network are gen-
`erally no longer homogeneous, despite whether traffic pat-
`terns involve routers. In these networks, differing trafiic
`types exists and require different service characteristics such
`as bandwidth, delay, and etc.
`the
`To meet
`the traffic requirements of applications,
`bridging devices should operate at line speeds, i.e., they
`operate at or faster than the speed at which packets arrive at
`the device, but they also must be able to forward packets
`across domains/subnetworks. Even through current hybrid
`bridge/router designs are able to achieve correct network
`delivery functions, they are not able to meet today’s increas-
`ing speed requirements.
`What
`is needed is a switch or network element
`
`that
`
`forwards both layer 2 and layer 3 packets quickly and
`efiiciently both within a subnetwork and to other networks.
`Further, a network element is needed that can forward layer
`3 packets at wire-speed, i.e., as fast as packets enter the
`network element. Additionally, a network element is needed
`that allows layer 2 forwarding within a subnetwork to have
`the additional features available in layer 3 routing and to
`provide certain quality of service for applications within the
`subnetwork, such as priority and bandwidth reservation.
`
`12
`
`12
`
`

`
`6,081,522
`
`5
`SUMMARY OF THE INVENTION
`
`The present invention enables the above problems to be
`substantially overcome by providing a system and method
`for a multi-layer network element for forwarding received
`packets to one or more appropriate output ports.
`An embodiment of the present
`invention includes a
`method of forwarding a packet entering from an input port
`to one or more appropriate output ports based on a single
`search of an associative memory for each layer.
`Apacket is received on an input port, and from the packet
`both first and second packet information are determined. An
`associative memory lookup is performed for the first packet
`information which results in two potential forwarding deci-
`sions. If the destination address in the first packet informa-
`tion is known, i.e., a matching entry is found in the asso-
`ciative memory, then the potential output port or ports are
`those associated with the destination address as found in the
`associative memory. If the destination address does not
`match any entry in the associative memory, then all ports
`except the port of arrival are candidates for the potential
`output port or ports.
`An associative memory lookup is also performed for the
`second information. Various actions may be taken as a result
`of the second information,
`including quality of service
`issues. The results of the first search and the second search
`
`are combined to determine which of the potential output port
`or ports as proffered by the two searches is more appropriate
`for this packet. The packet is then forwarded to the appro-
`priate output port or ports.
`The multi-layer network element according to the present
`invention forwards both layer 2 and layer 3 packets quickly
`and efficiently both within a subnetwork and to other net-
`works. The network element recognizes packets at both
`layer 2 and layer 3 and makes forwarding decisions for both.
`In some instances, the multi-layer network element also uses
`information from layer 4.
`The associative memory allows forwarding decisions at
`both layer 2 and layer 3 to be made at the hardware level.
`Having layer 3 forwarding decisions made at the hardware
`level allows layer 3 forwarding at wire-speed, i.e., as fast as
`packets enter the network element. Software normally asso-
`ciated with layer 3 forwarding is used when learning new
`layer 3 flows or routes.
`The invention according to the present invention also
`includes mechanisms for defining default actions for layer 2
`traffic. The default actions may define, among other things,
`QoS so that
`the network element provides QoS when
`forwarding at layer 2. Examples of QoS that can be provided
`include priority and bandwidth reservation.
`Still other embodiments of the present invention will
`become readily apparent to those skilled in the art from the
`following detailed description, which is shown and
`described by way of illustration of the best modes contem-
`plated for carrying out the invention. As will be realized, the
`invention is capable of other and different embodiments and
`several of its details are capable of modification in various
`obvious respects, all without departing from the spirit and
`scope of the present invention. Accordingly, the drawings
`and detailed description are to be regarded as illustrative in
`nature and not as restrictive.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a system incorporating a multi-layer
`network element according to the invention.
`FIG. 2 illustrates the multi-layer networking element of
`FIG. 1.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`FIG. 3 illustrates the switching element of the multi-layer
`network element in more detail.
`
`FIG. 4 illustrates the forwarding logic of the switching
`element in more detail.
`
`FIG. 5 illustrates the class logic of FIG. 4 in more detail.
`FIG. 6 illustrates the process used in determining which
`information dictates a packet’s path through the multi-layer
`network element.
`
`FIG. 7 illustrates the information dependency in deter-
`mining how to forward a packet out of the network element.
`DETAILED DESCRIPTION
`
`FIG. 1 illustrates a system incorporating a multi-layer
`network element according to the present invention. The
`system includes the multi-layer network element, various
`networks, end stations, routers, and bridges. By way of
`example and as broadly embodied and described herein, a
`system 10 incorporating a multi-layer network element 12
`according to the present invention includes networks 14 and
`16, end stations 18, router 24, bridge 26, and local area
`networks (LAN) 28.
`The bridge 26 connects some of the LANs 28 and end
`stations 18 to the network 14 and to each other. The bridge
`26 may be a conventional learning