United States Patent
`Hendel et al.
`
`[19]
`
`[11] Patent Number:
`
`6,081,522
`
`[45] Date of Patent:
`
`Jun. 27, 2000
`
`USOO6081522A
`
`[54]
`
`[75]
`
`SYSTEM AND METHOD FOR A
`MULTI-LAYER NETWORK ELEMENT
`
`Inventors: Ariel I-lendel, Cupertino; Leo A.
`I-Iejza; Shree Murthy, both of
`Sunnyvale, all of Calif.
`
`[73]
`
`Assignee: Sun Microsystems, Inc., Mountain
`View, Calif.
`
`[21]
`
`Appl. No.: 08/885,559
`
`[22]
`
`[51]
`[52]
`[53]
`
`[56]
`
`Filed:
`
`Jun. 30, 1997
`
`Int. Cl.’
`...... H04L 12/28; H04L 12/56
`
`U.S. Cl. ............
`370/389; 370/412; 370/428
`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
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,278,830
`5,291,482
`5,293,379
`
`1/1994 Kudo ...................................... 370/94.1
`3/1994 Mcflarg eta].
`370/413
`3/1994 Carr
`370/474
`
`
`
`(List continued on next page.)
`OTHER PUBLICATIONS
`
`“Load Balancing for Multiple Interfaces for Transmission
`Control Protocol/Intemet Protocol for VM/MVS",
`IBM
`Technical Disclosure Bulletin, 38(9): 7-9 (Sep., 1995).
`T. Nishizono et a1., “Analysis on a Multilink Packet Trans-
`mission System”. Electron. Commun. JPN 1, Commun.,
`(USA), 68(9): 98-104 (Scp., 1985).
`International Search Report, PCT/US 98/13203.
`The Institute of Electrical & Electronics Engineers, Inc.,
`“Intemational Standard” ISO/IEC 10038, ANSI/IEEE Std.
`802.1D, First edition, 1993-07-08, pp.1—180.
`Microsofi Press, “Microsoft Computer Dictionary Fourth
`Edition”, Microsoft Corporation, 1999, 4 pages.
`
`(List continued on next page.)
`
`Primary Examiner—Ajit Patel
`Attorney, Agent, or Fz'mt—B1akely Sokololf 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 difierent 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
`
`364/200
`9/1985 DeBru]er
`4,539,637
`370/88
`4,627,052 12/1986 Hoare et al.
`370/60
`4,641,302
`2/1987 Miller
`.. 340/825.05
`4,652,874
`3/1987 Loyer
`370/94
`4,737,953
`4/1988 Koch etal.
`.. 364/200
`4,307,111
`2/1989 Cohen etal
`4,311,337
`3/1939 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 Sheehy
`370/85.13
`4,935,869
`6/1990 Yamamoto
`364/2(1)
`5,130,907
`7/1992 May el al.
`370/60
`5,150,358
`9/1992 Punj el al
`.. 370/468
`5,159,685 10/1992 Kung ..
`395/575
`5,163,046 11/1992 Hahne elal
`370/79
`5,210,746
`S/1993 Maher etal.
`370/'79
`5,220,562
`6/1993 Takada et al.
`.. 370/401
`5,231,633
`7/1.993 I-lluchyj et al.
`. 370/94.1
`5,251,205
`10/1993 Callon el al.
`............................. 370/60
`
`
`
`..
`
`.
`
`
`
`ARISTA-1007
`
`1
`
`ARISTA-1007
`
`

`
`6,081,522
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`................ .. 395/200.17
`7/1997 Griesmer el al.
`5,649,109
`7/1997 Van Seters et al.
`.................. .. 370/392
`5,651,002
`10/1997 Aggarwaletal.
`............... .. 370/200.12
`5,675,741
`..
`5,684,800 11/1997 Dobbins et al.
`370/401
`
`........................ .. 370/388
`5,689,506
`11,/1997 Chiussi et al.
`5,689,518 11/1997 Galand etal.
`....................... .. 371/37.1
`5,691,984 11,/1997 Gardner et al.
`370/401
`5,706,472
`1/1998 Ruff eta1— ——————— -—
`395/497-04
`5,720,032
`2,/1998 Picazo, Jr. etal.
`.. 395/200.8
`57242348
`3-"1993 BaSS0}=ta1-
`~~~~ -~
`- 370/384
`57724353
`3/1993 Headnck 91 91-
`~ 370/413
`5,726,977
`3/11998 Lee ........................................ .. 370/235
`5,734,651
`3/11998 Blakeley et al.
`........................ 370/392
`37516155
`2511,1333
`-~ 5261582
`444°” ‘*1 --
`1:
`=
`3
`~
`1
`5,740,175
`4/11998 Wakeman et al.
`319-/422
`5,740,375
`4,-11998 Dunne etal.
`.
`395,-200.68
`5>7‘12=‘1114
`411998 P4151111 5131-
`---- --
`3711/4111
`5,742,760
`4711998 P1cazo,1Jr., et al.
`.................... 3170/351
`_,745,048
`4711998
`raguelnetal.
`.................. .. 340,870.01
`5,748,631
`5/11998 Bergantlno et al.
`3170/398
`5,743,905
`511993 11111155151 51-
`59511200-79
`5551957
`5/11993 Ra*1‘1111F1“1--~1-
`395320958
`1371971
`11998 DP
`"1”11‘~
`-9 "2110’53
`~’754>5_40
`51,1993 1-111,“ 11'
`~ ~- - ~ -
`-- ~ -~ 3,711/315
`52754774
`511998 131111115” ‘*1 111-
`395''2°°~53
`5=75‘1=3°1
`5’,1993 1*?‘“1’1"°111 5151’
`595/5113
`5,757,771
`5,-11998 L1 et al.
`. 370/235
`5,757,795
`5/11998 Schnell .................................. .. 3170/392
`5,761,435
`6,1998 Fuknda ctal. ..................... 395,200.68
`;=7g:=f§;11
`31,133:
`33115115115511 51 111-
`5731:1181
`17617516
`71,1668 D?“ """""""
`" 376/366
`1,761,616
`71,1668 F“
`"7,
`15711" 5111-
`39-"2110-13
`53781573
`711998 5Z°z5P“11"'1‘ 51 111-
`-- 395/20118
`5,790,546
`8.111998 Dobbins et al.
`...................... .. 3170/400
`5,790,808
`8.111998 Seaman ............................ .. 395,200.53
`5=892:9‘17
`911998 K1“°51“15
`379/359
`5,802,052
`9/11998 Venkataraman
`3170/395
`5>3112>278
`91,1998 151,°1d°1 51‘
`395/200-02
`53312527
`91,1993 K11“ ‘"1 111-
`372/232
`119111133:
`11j1“°k1‘71,1d1--1~--
`-- 5:6/:35
`1
`31166767 1631668 M*}1§1*1‘11:11:.*"
`‘ 3761365
`_°S 1°11‘
`‘
`/
`>
`*1 _
`531252772
`19119911
`1’‘’1‘1"“-“ 5151-
`- 3711/395
`--
`5,835,491
`11711998 D':1v1s1etal.
`.......................... .. 370/386
`5,838,677 111711998
`Imza_k11etal.
`........................ .. 370/1389
`5353:5151
`1111993 131111111111 5151-
`1 579/595
`5=352-=51”
`12/11993 C1111‘
`~ 3711/401
`533511977
`111999 1911351111‘
`~ 370/411
`51859349
`111999 P111115
`-~ 3711/395
`5:31/’7>‘577
`211999 T5‘{1““"°1° -
`-~ 395/311
`5,872,783
`2.111999 clnn 3170/395
`5,872,904
`2,-11999
`lVl1cM1llen et al.
`............... .. 3951-182.02
`5,875,464
`2,-11999 Kirk
`711/129
`5>373>°‘13
`31,1999 C115‘?
`3,711/397
`5»373=232
`3/11999
`1"1“1'11“.1111111-
`-- 395/1200-79
`'1
`5232191112
`:11",1gg3
`31151.1“ 5151'
`392215119533
`3
`=1’
`‘’“111‘‘111 511-
`/
`~’931’989
`1111993 V5111” 51 111'
`-'
`- 579/595
`
`
`
`
`
`International Search Report, PCT/US98/13206, 6 pages.
`International Search Report, PCT/US98/13362, 5 pages.
`International Search Report,
`7 pageS1
`.
`,.
`’
`1"191"a9.9““1 $991911 $911911’ £g¥1E§g:’,1£g111’ 161 Pages‘
`11 5111111101111
`551°
`511011’
`1
`1,
`7
`Pages"
`Internat1onal Search Report, PCT/US98/113202, 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.
`
`.... -- 395/725
`4/1994 lee
`5,301,333
`340/827
`5/1994 Perlman et al.
`5,309,437
`.......................... .. 370/13
`5/1994 Bustini et al.
`5,313,454
`8/1994 Cassagnol
`..............
`370/85.13
`5,343,471
`5,353,412 10/1994 Douglas et al.
`395/325
`
`........................ .. 370/17
`5,365,514 11/1994 Hershey et al.
`5,386,413
`1/1995 McAu]eyeta1.
`....................... .. 370,/54
`5,392,432
`2/1995 Engelstad et al.
`395/700
`5,394,402
`2/1995 Ross ........................... .. 370/401
`513061602
`311095 411116161611 ................ 11 395/325
`514021415
`3/1995 T111661,
`........11
`3701,60
`5,404,538
`4/1995 Krappweis, Sr.
`395/725
`5,410,540
`4/1995 Aiki el al.
`.
`370/390
`514101722
`4/1995
`395/800
`514201862
`511005
`5701851013
`5,422,838
`6/1995 Lin
`........ 365/49
`5142511126
`6/1095 M611
`1 37011611
`54251028
`611095 1311116661611
`37019411
`514261736
`6/1995 G111111616111111
`395/250
`5,432,907
`7/1995 Picazo, Jr. ct al.
`.. 395/200
`5,450,399
`9/1995 Sugita
`.. 370/601
`5,455,820 10/1995 Yamada ...................... .. 370/413
`5,457,681
`10/1995 Gaddisetal.
`........................ .. 370/402
`5,459,714 10/1995 Loetal.
`......
`.. 370/131
`5,459,717 10/1995 Mullan etal.
`370/351
`514611611
`10/1095 D16116111161611
`1 3701,54
`514611624
`1011095 114622616 .....11
`370/402
`514731607
`1211095 1166666611 1
`370/85113
`5,477,537 12/1995 Dankertetal.
`370/60
`5,481,540
`1/1996 Huang ..........
`370/85.13
`5,485,455
`1/1996 Dobbins et al.
`370/255
`5,485,578
`1/1996 Sweazey ................
`395/200.54
`5,490,139
`2/1996 Baker et al.
`............................ .. 370/60
`514901252
`2/1096 M66616 611111
`1 3051200101
`514001260
`2/1006 1141116161611 1
`305/42.1,
`5,493,564
`2/1996 Mullan
`370/54
`515001860
`31.1996 1,61,1111611 61 11 1
`................. .. 395/200.15
`5,509,123
`4/1996 Dobbins et al.
`.......................... 340/402
`5,515,376
`5/1996 Murthy et al.
`5,517,488
`5/1996 M.iyazak1'eta1. ............... 370/16
`5,535,202
`7/1996 Kondoh ...........
`.. 370/60.1
`5,550,816
`8/1996 Ilardwick et al.
`370/60
`5,553,067
`9/1996 Walker el al.
`. 370/60
`515551405
`011006 6116611161 61 1111
`305/600
`5155711610
`011096 061111176166 61611
`11 57016011
`5,561,666 10/1996 Christensen eta].
`................. .. 370/434
`5,561,791
`10/1996 Mcndclson ct al.
`.................. .. 395/550
`5,563,878 10/1996 Blakeley etal. .
`. 370/60
`5,566,170 10/1996 Bakke et al.
`............................ .. 370/60
`5,570,365
`10/1996 Yoshida ........................... 370/85.6
`51572522 11110106 C616661616161611
`370/3105
`515741661
`11/1996 166,16 6161
`1 3951200106
`515851981
`1211096 146161
`395/326
`5,592,476
`1/1997 Calamvokis er a.
`370/390
`5,594,727
`1/1997 Kolbenson etal.
`370/468
`5,600,641
`2/1997 Duaultetal.
`........................... 370/400
`5,602,841
`2/1997 Lebizay etal.
`......................... 370/413
`5,606,669
`2/1997 Bcrtin ctal. .
`. 395/200.15
`5,698,726
`13/11997 Virgile .........
`370/401
`5,610,905
`3/1997 Multhy et al.
`370/401
`5,515,340
`3/1997 Dai 6t 411-
`- 395/200-17
`5215172421
`4/1997 C111“ 91 111-
`3711/402
`5,619,497
`4/1997 Gallagher et al.
`.................... .. 370/394
`5,619,500
`4/1997 Hiekali ....................... .. 370/414
`5,619,661
`4/1997 Crews et al.
`.
`395/299
`5,623,489
`4/1997 Cotton el al.
`370/381
`516331710
`5/1997 M66061 61 1111
`364/514
`515331355
`5/1997 short
`370/412
`5,636,371
`6/1997 Yu
`395/500
`5,640,605
`6/1997 Johnson et al.
`....................... .. 395/881
`
`
`
`1
`
`
`
`
`
`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 Switcl1Architectures for Broadband
`Integrated Services Digital Networks, Proceedings of the
`IEEE, Vol. 78, Issue 1, pp. 133-167, Jan. 1990.
`Fliesser et a1., Design of a Multieast ATM Packet Switch,
`Electrical and Computer Engineering, 1993 Canadian Con-
`ference, pp. 779-783, 1993.
`Chang et al., An Overview of the Pipelined Common Bulfer
`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,
`Inter11ct—Draft, 13
`pages, downloaded from Website http:,"/wwwbaynetwork-
`s.com on Apr. 18, 1997.
`
`3
`
`

`
`Multilayer
`mCmbEkr0McN
`
`
`
`d.m.5.8:»._E..3.3....$52_=39s:.mB
`
`
`
`
`
`4
`
`

`
`Multilayer
`Network Element
`
`321
`Process or
`
`Processor
`Memory
`
`\
`
`Switching
`Element
`
`
`
`
`
`LJ0Z199118000Z‘LZ'““I'1II31l2d'S'f1
`
`
`
`
`
`zzs‘Is0‘9
`
`5
`
`

`
`Processor
`
`Forwarding
`Logic
`
`Packet
`Memory
`Manager
`
`
`
`
`
`LJ053199118000Z‘LZ'““I'1II31l2d'S'f1
`
`
`
`
`
`zzs‘Is0‘9
`
`6
`
`

`
`
`
`
`
`LJ017199118000Z‘LZ'““I'1II31l2d'S'f1
`
`
`
`
`
`zzs‘Is0‘9
`
`32
`
` Processor
`
`
`
`Forwarding
`
`Forwarding
`Logic
`
`
`Memory
`
`7
`
`

`
`
`
`
`
`LJ0S199118000Z‘LZ'““I'1II31l2d'S'f1
`
`
`
`
`
`eoj‘
`
`Class Logic
`
`
`
`Encapsulation
`Logic
`
`
`
`
`address dependent
`deafult class action
`no class match
`
`
`
`FIG. 5
`
`zzs‘Is0‘9
`
`8
`
`

`
`
`
`
`
`
`
`
`
`LJ09199118000Z‘LZ'““I'1II31l2d'S'f1LJ09199118000Z‘LZ'““I'1II31l2d'S'f1
`
`
`
`
`
`
`
`
`
`
`
`
`
`zzs‘Is0‘9zzs‘Is0‘9
`
`9
`
`

`
`
`
`
`
`LJ0L199118000Z‘LZ'““I'1II31l2d'S'f1
`
`
`
`
`
`zzs‘Is0‘9
`
`200
`
`202
`
` Receive Packet
`
`
`L2 Source Search
`
`Determine
`Class
`
`N) >-- 9
`
`
`
`212
`
`
`
`Destination
`Search
`
`FIG. 7
`
`10
`
`10
`
`

`
`6,081,522
`
`1
`SYSTEM AND METHOD FOR A
`MULTI-LAYER NETWORK ELEMENT
`
`FIELD OF THE INVENTION
`
`The present invention relates in general to packet for-
`warding within a network and, in particular, to a system and
`method for forwarding packets using multi-layer informa-
`tion.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`or with the same layer of a network element within the
`network itself. A layer 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
`
`25
`
`of this layer is the capability to relay information about
`network congestion to the source or destination if conditions
`warrant.
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`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 I.ANs. 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, trallic, and bandwidth, as well as others.
`
`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
`sewers, 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 efiicient 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 dillerent models
`is not. For example, the standard promulgated by the Insti-
`tute of Electrical and Electronics Engineers
`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,
`
`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 packets 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 traific
`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 insuflicient 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
`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
`
`25
`
`30
`
`35
`
`40
`
`45
`
`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 traflic
`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 traflic
`types with varied characteristics on a same physical link.
`This calls for more network bandwidth and ellicient 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 traffic 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.
`
`Networks 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 Lhe “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 trallic pat-
`terns involve routers. In these networks, difiering 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.
`that
`What
`is needed is a switch or network element
`forwards both layer 2 and layer 3 packets quickly and
`efliciently 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
`
`

`
`5
`SUMMARY OF THE INVENTION
`
`6,081,522
`
`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 bridge. The bridge 26
`keeps track of the addresses of the end stations 18 that
`transmit a packet showing up on one of ports 30 to the bridge
`26. The end stations 18 may be any device capable of
`sending or receiving packets of information. Typically, the
`e-nd stations 18 are personal computers, workstations,
`printers, servers, and/or any other device that can be con-
`nected to a network.
`
`The bridge 26 initially does not know on which of its ports
`packet destinations are located, and must flood an incoming
`packet to all ports in order to properly forward the packet.
`Once the bridge 26 receives a packet destined for an address
`it already recognizes, the bridge 26 knows what port the
`destination is on so that it does not have to flood the packet
`on all outgoing ports. Eventually, the bridge 26 has learned
`enough addresses to eliminate the amount of flooding
`needed on the ports of the addresses it has learned. Of
`course, any time an end station 18 changes ports on the
`bridge 26, the bridge 26 must relearn the end station 18’s
`port.
`The bridge 26 typically does not modify the packet,
`contains no information about the topology of the network
`14, and examines few parts of the packet header. The bridge
`26 operates quickly because it makes no modifications to the
`packet and is only concerned with learning sources and
`forwarding to destinations. Typically, bridges 26 use look-up
`tables to search for sources and destinations.
`The router 24 connects the network 14 to the networks 16.
`Only one router 24 is illustrated by way of example, but
`there may be many routers connecting other networks or end
`stations 18. The router 24 provides the communication
`necessary between the network 14 and the networks 16 and
`may be a conventional router. Such routers include layer 3
`functionality for forwarding packets to an appropriate des-
`tination including route calculation, packet fragmentation,
`and congestion control. Routers of this type are described,
`for example, in Intercormectionsz Bridges and Routers by
`Radia Perlman published by Addison-Wesley. The router 24
`must have knowledge of the topology of the network in
`order to determine the best route for packets. The router 24’s
`knowledge of the network is gained through topological
`information passed between multiple such routers 24 con-
`nected to the network 14.
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`45
`
`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
`an