(12) United States Patent
`Muller et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,246,680 B1
`Jun. 12, 2001
`
`US006246680B1
`
`(54)
`
`(75)
`
`HIGHLY INTEGRATED MULTI-LAYER
`SWITCH ELEMENT ARCHITECTURE
`
`Inventors: Shimon Muller, Sunnyvale; Ariel
`Hendel, Cupertino; Howard Frazier,
`Pleasanton, all of CA (US)
`
`(73)
`
`Assignee: Sun Microsystems, Inc., Mountain
`View, CA (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 17 days.
`
`Appl. No.: 08/884,704
`
`Filed:
`
`Jun. 30, 1997
`
`FOREIGN PATENT DOCUMENTS
`
`072535 1
`
`............................. .. G06F/13/36
`7/1996 (EP)
`OTHER PUBLICATIONS
`
`“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.
`
`Primary Examiner—Dang Ton
`Assistant Examiner—Phirin Sam
`
`Int. Cl.7 ................................................... .. H04L 12/56
`
`(74) Attorney, Agent, or Firm—Blakely, Sokoloff, Taylor &
`Zafman
`
`U.S. Cl.
`
`........................... 370/389; 370/395; 370/412
`
`(57)
`
`ABSTRACT
`
`An architecture for a highly integrated network element
`building block is provided. According to one aspect of the
`present invention, a network device building block includes
`a network interface with multiple ports for transmitting and
`receiving packets over a network. The network device
`building block also includes a packet buffer storage which is
`coupled to the network interface. The packet buffer storage
`acts as an elasticity buffer for adapting between incoming
`and outgoing bandwidth requirements. A shared memory
`manager may also be provided dynamically allocate and
`deallocate buffers in the packet buffer storage on behalf of
`the network interface and other clients of the packet buffer
`storage. The network device building block further includes
`a switch fabric which is coupled to the network interface.
`The switch fabric provides forwarding decisions for
`received packets. A given forwarding decision includes a list
`of ports upon which a particular received packet is to be
`forwarded. A central processing unit (CPU) interface is also
`included in the network device building block. The CPU
`interface is coupled to the switch fabric and is configured to
`forward packets received from the CPU based upon for-
`warding decisions provided by the switch fabric.
`
`Field of Search ................................... .. 370/389, 428,
`370/355, 356, 357, 359, 360, 362, 367,
`372, 375, 379, 380, 328, 400, 401, 402,
`465, 468, 418, 434, 395, 386, 396, 398,
`408, 412, 419, 429
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`9/1985 DeBruler ............................ .. 364/200
`12/1986 Hoare et al.
`.. 370/88
`2/1987 Miller
`370/60
`3/1987 Loyer
`340/825.05
`4/1988 Koch et al.
`.... .. 370/94
`2/1989 Cohen et al.
`364/200
`3/1989 Hart
`...............
`370/85
`7/1989 Petronio et al.
`455/606
`2/1990 Roediger
`370/427
`5/1990 Leone
`. 370/85.13
`6/1990 Sheehy
`370/401
`6/1990 Yamamoto .
`364/200
`7/1992 May et al.
`.. 370/60
`.
`9/1992 Punj etal.
`370/468
`10/1992 Kung .................................. .. 395/575
`
`
`
`4,539,637
`4,627,052
`4,641,302
`4,652,874
`4,737,953
`4,807,111
`4,811,337
`4,850,042
`4,899,333
`4,922,503
`4,933,938
`4,935,869
`5,130,977
`5,150,358 *
`5,159,685
`
`(List continued on next page.)
`
`12 Claims, 3 Drawing Sheets
`
`FORWARDING
`AND FILTERING
`DATABASE 140
`
`(21)
`
`(22)
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`T0
`NETWORK
`
`TO ONE OR
`MORE UIHEK
`SWITCH ELEMENTS
`
`ARISTA 1104
`
`
`
`
`"U
`'5‘
`
`CPU INTERFACE
`215
`
`SWITCH FABRIC
`210
`
`SHARED MEMOIKV
`MANAGER
`220
`
`NETWORK
`INTERFACE
`
`205
`
`CASCADINCI
`INTERFACE 225
`
`
`
`..
`
`
`
`
`
`
`1
`
`ARISTA 1104
`
`

`
`US 6,246,680 B1
`Page 2
`
`
`
`.
`-
`
`-
`
`US. PATENT DOCUMENTS
`11/1992 Hahne et al.
`.......................... 370/79
`5,163,046
`5/1993 M61161 61 61-
`-
`- 370/79
`5,210,746
`6/1993 Takada et al.
`..................... .. 370/401
`5,220,562
`7/1993 Hluchyj et al.
`................... .. 370/94.1
`5,231,633
`.
`10/1993 Callon et al.
`370/60
`5,251,205
`1/1994 Kudo ........... ..
`.. 370/94.1
`5,278,830
`3/1994 M6H6rg 6161-
`-- 370/413
`5,291,482
`3/1994 Carr
`..... ..
`370/474
`5,293,379
`4/1994 L66
`395/725
`5,301,333
`4/1994 Lyles .................................... .. 370/60
`5,305,311
`5/1994 Perlman et al .
`.................. .. 340/827
`5,309,437
`5/1994 1311611111 61 61-
`370/13
`5,313,454
`8/1994 Cassanol
`..... ..
`370/401
`5,343,471
`10/1994 Douglas et al.
`.. 395/325
`5,353,412
`11/1994 H6rsh6y 6161-
`- 370/17
`5,365,514
`1/1995 M6Au16y6161-
`- 370/54
`5,386,413
`2/1995 Engelstad et al.
`................. .. 395/700
`5,392,432
`2/1995 Ross ................................... .. 370/402
`5,394,402
`3/1995 Amini6161-
`-- 395/325
`5,396,602
`3/1995 T611161 --------- -«
`370/60
`5,402,415
`4/1995 Kr6ppW61s, 81-
`395/725
`5,404,538
`4/1995 A11<16161-
`-- 370/390
`5,410,540
`4/1995 C0rn61=y -
`395/800
`5,410,722
`5/1995 P6r1m6n -
`370/85-13
`5,420,862
`6/1995 Lin
`365/49
`5,422,838
`6/1995 M611 ~~~~~ --
`370/60
`5,425,026
`6/1995 Britton et al.
`.................... .. 370/94.1
`5,425,028
`6/1995 Guineau, III
`...................... .. 395/250
`5,426,736
`7/1995 P166Z0,1I- 6161-
`-- 395/200
`5,432,907
`9/1995 8118116 ~~~~~ --
`-- 370/601
`5,450,399
`10/1995 Y6m6d6
`370/413
`5,455,820
`10/1995 G6<1<11S 6161-
`-- 370/402
`5,457,681
`10/1995 L0 6161-
`- 370/13-1
`5,459,714
`10/1995 Mullan et al.
`..................... .. 370/351
`5,459,717
`10/1995 Drake et al.
`......................... .. 370/54
`5,461,611
`10/1995 M6ZZ016
`370/402
`5,461,624
`--
`12/1995 116116111611
`370/8513
`5,473,607
`12/1995 Dankert et al.
`370/60
`5,477,537
`1/1996 H6668 ~~~~~~~~~ --
`370/85-13
`5,481,540
`1/1996 Dobbins et al.
`.... .. 370/255
`5,485,455
`1/1996 SW66z6y ,,,, --
`-395/200-54
`5,485,578 *
`2/1996 Baker et al.
`..
`...... .. 370/60
`5,490,139
`2/1996 M66616 6161-
`- 395/200-79
`5,490,252
`2/1996 Miller et al.
`....................... .. 395/427
`5,490,260
`2/1996 Mullan ................................. .. 370/54
`5,493,564
`3/1996 Perlman et al.
`.
`370/85.13
`5,500,860
`4/1996 Dobbins 6161-
`-
`- 395/200-15
`5,509,123
`5/1996 Murthy et al.
`.. 340/402
`5,515,376
`5/1996 Miyazaki et al.
`370/16
`5,517,488
`6/1996 86111611161 61-
`-- 711/121
`5,524,212 *
`7/1996 Kondoh ............................. .. 370/60.1
`5,535,202
`8/1996 Hardwick et al.
`................... .. 370/60
`5,550,816
`9/1996 W611<6r6161-
`- 370/60
`5,553,070
`9/1996 Griesmaer et al.
`.. 395/600
`5,555,405
`9/1996 Calamvokis et al.
`. 370/60.1
`5,557,610
`5,561,666 * 10/1996 Christensen et al.
`.. 370/434
`-
`5,561,791
`10/1996 M6nd61s6n 6161-
`-- 395/550
`5,563,878
`10/1996 Blakeley et al.
`..................... .. 370/60
`5,566,067
`10/1996 Bakke et al.
`......................... .. 370/60
`5,570,365
`10/1996 Y0dhid6 --------- --
`-- 370/85-6
`5,572,522
`11/1996 C616mV01<1S 6161-
`-------------- -- 370/395
`5,583,981
`12/1996 Pleyer ................................ .. 395/326
`5,592,476
`1/1997 Calamvokis et al.
`.. 370/390
`5,594,727 *
`1/1997 Kolbenson et al.
`.. 370/468
`5,600,641
`2/1997 Duault et al.
`.. 370/400
`
`......................... .. 370/402
`4/ 997 Chin et al.
`5,617,421
`4 997 Yamada et al.
`.................... .. 709 214
`5 617 537 *
`4/ 997 Gallagher et a1
`. 370/394
`5:619:497 >x<
`4/997 Hiekali ......... ..
`.. 370/414
`5,619,500
`4/ 997 Crews et al.
`. 395/299
`5.619.661
`4/ 997 Cotton et a1.
`. 370/381
`5.623.489
`5/ 997 Mandal et a1
`. 364/514
`5.633.710
`5/ 997 short ..... ..
`.. 370/412
`5.633.865
`6/997 Yu ......... ..
`395/200.57
`5,636,371
`6/ 997 Johnson et al.
`395/881
`5.640.605
`7/ 997 Griesmer et 61.
`395/200.17
`5,649,109
`7/ 997 Van Seters et al.
`............... N 370/401
`5.651.002
`10/ 997 Aggarwal et al.
`370/200.12
`5.675.741
`11/997 Dobbins etal.
`370/401
`5,684,800
`5.689.506 =x< 11/ 997 C1nnSSieta1_ _
`_ 370/388
`5.689.518
`11/ 997 Ga1and et al.
`.
`371/371
`5,691,984
`11/ 997 Gardner et al.
`370/401
`5,706,472
`1/ 998 Ruff et al.
`..................... .. 395/497.04
`5.720.032
`2/ 998 picazo. Jr. 61 al.
`............. N 395/200.8
`5.724.348 >x<
`3/ 998 Basso et al.
`. . . . . .
`. . . N 370/422
`5,724,358 * 3/998 Headrick et al.
`. 370/418
`5,726,977
`3/ 998 Lee ........ ..
`.. 370/235
`5,734,651
`3/ 998 Blakeley et al.
`. 370/392
`5,734,865
`3/ 998 Yu ................ ..
`.. 395/500
`5,740,171
`4/ 998 Mazzola et al.
`. 370/392
`5,740,175
`4/998 Wakeman etal.
`395/200.45
`5,740,375
`4/ 998 Dunne et al.
`..
`395/200.68
`5,742,604
`4/998 Edsall etal.
`....................... .. 370/401
`5.742.760
`4/ 998 Picazo. Jr. 61 al.
`................ .. 370/351
`5.745.048
`4/ 998 Taguchi 61 a1.
`340/870.01
`5,748,631
`5/ 998 Bergantino et al.
`370/398
`5,748,905
`5/ 998 Hauseretal.
`395/200.79
`5,751,967
`5/ 998 Raab et al.
`.. 395/200.72
`5,751,971
`5/ 998 Dobbins et al.
`395/200.68
`5,754,540
`5/998 Liu etal.
`........................... .. 370/315
`5.754.774
`5/ 998 Bntinger et al.
`.............. N 395/200.33
`5.754.801
`5/ 998 Lambrecht eta1_
`395/308
`5,757,771
`5/ 998 Li etal.
`.... ..
`. 370/235
`5,757,795
`5/ 998 Schnell
`370/392
`.
`5.761.435
`6/ 998 Fnkuda et a1.
`395/200.68
`5,764,634 * 6/998 Christensen etal
`370/401
`5.764.636
`6/ 998 Edsall _________________________________ __ 370/401
`5,781,549
`7/998 Dai
`..................................... .. 370/398
`5.784.573
`7/ 998 szczenanek et a1
`395/200.8
`5,790,546 *
`8/ 998 Dobbins et al.
`................... .. 370/400
`5.790.808
`8/ 998 Seaman ........................... 395/200.53
`5.802.047
`9/ 998 Kinoshna
`370/359
`5.802.052
`9/ 998 Venkataranlan
`370/395
`5,802,278
`9/ 998 Isfeld et al.
`395/200.02
`5.812.527 =x<
`9/ 998 Khne et a1.
`370/232
`5.815.737
`7/ 998 Bnddand
`.. 395/905
`5,822,319
`10/998 Nagami et 61.
`.................... .. 370/392
`5.825.767
`10/ 998 MiZnk6S1neta1_ ________________ N 370/395
`5.831.980 =x< 11/ 998 Vanna et a1.
`..
`. 370/395
`5,835,491 * 11/998 Davis et al.
`. 370/386
`5.838.677
`11/ 998 Kozaki 61,11.
`. 370/389
`5.838.681 =x< 11/ 998 Bononn et al.
`. 370/395
`5.856.977 >x<
`1/ 999 Yang 61,11.
`_
`_ 370/412
`5,859,849 * 1/999 Parks .................................. .. 370/395
`5.867.677 >2
`2/ 999 Tsnkanloto ......................... .. 370/395
`5.872.783
`2/ 999 Chin ............. ..
`.. 370/395
`5,872,904 * 2/999 McMillen etal.
`................. .. 370/217
`5,875,464
`2/ 999 Kirk ................................... .. 711/129
`5.898.687 >x<
`4/ 999 Hannnan et a1.
`................. .. 370/389
`
`
`
`.
`
`.
`
`
`
`..
`
`..
`
`OTHER PUBLICATIONS
`
`<<Mn1ti1ayer Tonobgyw. White Paper. Jn1ernet_Draft. 13
`~
`.
`Fag?’ dlogmllggied from Webs“ hfip‘//baynetworkscom
`0“
`Pr"
`>
`'
`International Search Report, PCT/US98/13203, 7 pages.
`
`
`
`.
`
`..
`
`.
`
`5,602,841
`,606,669
`5,608,726
`5,610,905
`5,615,340 *
`
`.. 5370/413
`2/1997 Lebizay etlal.
`. 39 /200.1
`2/1997 Bertin eta. ..
`3/1997 Virgile ................................. 370/401
`3/1997 Murthy etal. ..................... .. 370/401
`3/1997 Dai et al.
`........................... .. 370/419
`
`2
`
`

`
`US 6,246,680 B1
`Page 3
`
`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.
`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/13016, 4 pages.
`Wang et al., “A Novel Message Switch For Highly Parallel
`Systems”, IEEE, pp. 150-155, 1989.
`Tobagi, Fast Packet Switch / Architectures For Broadband
`Integrated Services Digital Networks, Proceedings of the
`IEEE, vol. 78, Issue 1, pp. 133-167, 1/1990.
`Fliesser et al., “Design Of A Multicast ATM Packet Switch,
`Electrical and Computer Engineering”, 1993 Canadian Con-
`ferencem 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, 19'” Conference IEEE.
`Agarwal et al., “A Scalable Shared Buffer ATM Switch
`Architecture”, VLSI, 1995 5”’ Great Lakes Symposium,
`IEEE, pp. 256-261, 1994.
`
`Sabaa et al., “Implementation Of AWindow-Based Sched-
`uler In An ATM Switch”, Electrical An Computer Engineer-
`ing, 1995 Canadian Conference, IEEE, pp. 32-35, 1995.
`International Search Report, PCT/US98/13361, 5 pages.
`International Search Report, PCT/US98/13200, 6 pages.
`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, Telecommunications Conference, pp. 1181-1186, 1989.
`
`International Search Report, PCT/US98/13206, 8 pages.
`
`International Search Report, PCT/US98/13362, 5 pages.
`
`“Load Balancing for Multiple Interfaces for Transmission
`Control Protocol/Internet Protocol for AM/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).
`
`* cited by examiner
`
`3
`
`

`
`U.S. Patent
`
`n.HJ
`
`1tee
`
`30.1
`
`US 6,246,680 B1
`
`E
`
`8_.
`
`__:._;o
`
`beau:
`
`0O0.
`
`6....\\mm1\R\\II291I
`%.\
`
`§
`
`2_o_§?_=s2:88:oh
`
`_..0_..._
`
`4
`
`
`
`

`
`U.S. Patent
`
`J
`
`02
`
`US 6,246,680 B1
`
`omm
`
`nm:<=m
`
`Eozms
`
`o m
`
`m
`
`
`
`Eozmznezmm
`
`._mo<z<z
`
`N.0_u_
`
`mo<n:_Ez_Mow5.0352Mxokemz
`
`
`
`
`
`v.oEmonaé=o,:.sm
`
`3mmmMmeflwfiflmmmwxammu§_Ez_
`
`
`2ozaémfiw.5mzoSm_N%8<5_Ez_P5
`
`o3mm<m<._.<o
`
`ez_e_<E§_
`
`ozzmsz9,2
`
`5
`
`
`
`
`
`

`
`U.S. Patent
`
`Jun. 12, 2001
`
`Sheet 3 of 3
`
`US 6,246,680 B1
`
`o3$:.E5
`
`cz§_<E_8
`
`ozamsa9,:
`
`ocaé5:»;
`
`y_mEa_
`
`iozmz
`
`
`
`ommEozmz
`
`nB_<=m
`
`own
`
`.::mz.::so:
`
`mace:
`
`omm
`
`
`
`m>_moB_.50:
`
`mace...
`
`Eas
`
`oem
`
`6
`
`
`

`
`US 6,246,680 B1
`
`I
`HIGHLY INTEGRATED MULTI-LAYER
`SWITCH ELEMENT ARCHITECTURE
`
`FIELD OF THE INVENTION
`
`The invention relates generally to the field of computer
`networking devices. More particularly, the invention relates
`to an architecture for a highly integrated network element
`building block.
`
`BACKGROUND OF THE INVENTION
`
`An increasing number of users are requiring increased
`bandwidth from existing networks due to multimedia appli-
`cations for accessing the Internet and World Wide Web, for
`example. Therefore, future networks must be able to support
`a very high bandwidth and a large number of users.
`Furthermore, such networks should be able to support mul-
`tiple traflic types such as data, voice, and video which
`typically require different bandwidths.
`Statistical studies indicate that the network domain, i.e., a
`group of interconnected local area networks (LANs), as well
`as the number of individual end-stations connected to each
`LAN, will grow at ever increasing rates in the future. Thus,
`more network bandwidth and more efficient use of resources
`
`is needed to meet these requirements.
`Building networks using Layer 2 elements such as bridges
`provides fast packet forwarding between LANs; however
`there is no flexibility in traffic isolation,
`redundant
`topologies, and end-to-end policies for queuing and access
`control. While the latter attributes may be met using Layer
`3 elements such as routers, packet forwarding speed is
`sacrificed in return for the greater intelligence and decision
`making capabilities provided by routers.
`Therefore, it is desirable to provide a cost-effective, high
`performance network device building block that is capable
`of performing non-blocking wire-speed multi-layer switch-
`ing on N ports. Generally,
`it would be advantageous to
`provide a network device building block that linearly scales
`its performance with advances in silicon technology.
`Therefore, it is desirable to share common resources, cen-
`tralize common processing, and maximize the utilization of
`hardware resources. More specifically,
`it
`is desirable to
`utilize a dynamic packet memory management scheme to
`facilitate sharing of a common packet memory among all
`input/output ports for packet buffering. Also, it is desirable
`to centralize packet header processing and to provide effi-
`cient access to a centralized database for multiple protocol
`layer based forwarding decisions. Further,
`it would be
`advantageous to provide a central processing unit (CPU)
`interface that requests forwarding decisions of a switch
`fabric for CPU originated packets in a first packet forward-
`ing mode and bypasses the switch fabric header matching by
`transferring the packet directly to one or more specified
`ports in a second packet forwarding mode.
`
`SUMMARY OF THE INVENTION
`
`A method and apparatus for packet forwarding and fil-
`tering is described in the context of an architecture for a
`highly integrated network element building block. Accord-
`ing to one aspect of the present invention, a network device
`building block includes a network interface with multiple
`ports for transmitting and receiving packets over a network.
`The network device building block also includes a packet
`buffer storage which is coupled to the network interface. The
`packet buffer storage acts as an elasticity buffer for adapting
`between incoming and outgoing bandwidth requirements.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`The network device building block further includes a switch
`fabric which is coupled to the network interface. The switch
`fabric provides forwarding decisions for received packets. A
`given forwarding decision includes a list of ports upon
`which a particular received packet is to be forwarded. A
`central processing unit (CPU) interface is also included in
`the network device building block. The CPU interface is
`coupled to the switch fabric and is configured to forward
`packets received from the CPU based upon forwarding
`decisions provided by the switch fabric.
`According to another aspect of the present invention, a
`switch element includes a switch fabric configured to gen-
`erate forwarding decisions for received packets. The switch
`element also includes multiple interfaces for receiving and
`transmitting packets. Each of the interfaces are coupled in
`communication with the switch fabric for requesting and
`receiving forwarding decisions. The interfaces include a
`network interface, a cascading interface, and a central pro-
`cessing unit (CPU) interface. The network interface further
`includes multiple external ports for communication with
`devices on a network. At least two internal links are pro-
`vided by the cascading interface for interconnecting with
`one or more other switch elements in a full-mesh topology.
`The CPU interface allows communication of packets and
`commands between the switch fabric and a CPU. The switch
`element further includes a shared memory manager which is
`coupled to the interfaces for dynamically allocating and
`deallocating buffers in a shared buffer memory on behalf of
`the interfaces. The shared memory manager further tracks
`the status of buffers in the shared buffer memory.
`Other features of the present invention will be apparent
`from the accompanying drawings and from the detailed
`description which follows.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention is illustrated by way of example,
`and not by way of limitation, in the figures of the accom-
`panying drawings and in which like reference numerals refer
`to similar elements and in which:
`
`FIG. 1 illustrates a switch according to one embodiment
`of the present invention.
`FIG. 2 is a simplified block diagram of an exemplary
`switch element that may be utilized in the switch of FIG. 1.
`FIG. 3 is a more detailed block diagram of the switch
`element of FIG. 2.
`
`DETAILED DESCRIPTION
`
`A highly integrated multi-layer switch element architec-
`ture is described.
`In the following description, for the
`purposes of explanation, numerous specific details are set
`forth in order to provide a thorough understanding of the
`present
`invention.
`It will be apparent, however,
`to one
`skilled in the art that the present invention may be practiced
`without some of these specific details. In other instances,
`well-known structures and devices are shown in block
`diagram form.
`The present invention includes various steps, which will
`be described below. While the steps of the present invention
`are preferably performed by the hardware components
`described below, alternatively, the steps may be embodied in
`machine-executable instructions, which may be used to
`cause a general-purpose or special-purpose processor pro-
`grammed with the instructions to perform the steps. Further,
`embodiments of the present invention will be described with
`respect
`to a high speed Ethernet switch. However,
`the
`
`7
`
`

`
`US 6,246,680 B1
`
`3
`method and apparatus described herein are equally appli-
`cable to other types of network devices such as bridges,
`routers, brouters, and other network devices.
`
`AN EXEMPLARY NETWORK ELEMENT
`
`An overview of one embodiment of a network element
`that operates in accordance with the teachings of the present
`invention is illustrated in FIG. 1. The network element is
`used to interconnect a number of nodes and end-stations in
`a variety of different ways. In particular, an application of
`the multi-layer distributed network element (MLDNE)
`would be to route packets according to predefined routing
`protocols over a homogenous data link layer such as the
`IEEE 802.3 standard, also known as Ethernet. Other routing
`protocols can also be used.
`The MLDNE’s distributed architecture can be configured
`to route message traffic in accordance with a number of
`known or future routing algorithms.
`In a preferred
`embodiment, the MLDNE is configured to handle message
`traffic using the Internet suite of protocols, and more spe-
`cifically the Transmission Control Protocol (TCP) and the
`Internet Protocol (IP) over the Ethernet LAN standard and
`medium access control (MAC) data link layer.
`In one embodiment of the MLDNE, a network element is
`configured to implement packet routing functions in a dis-
`tributed manner, i.e., different parts of a function are per-
`formed by different subsystems in the MLDNE, while the
`final result of the functions remains transparent
`to the
`external nodes and end-stations. As will be appreciated from
`the discussion below and the diagram in FIG. 1, the MLDNE
`has a scalable architecture which allows the designer to
`predictably increase the number of external connections by
`adding additional subsystems, thereby allowing greater flex-
`ibility in defining the MLDNE as a stand alone router.
`the
`As illustrated in block diagram form in FIG. 1,
`MLDNE 101 contains a number of subsystems 110 that are
`fully meshed and interconnected using a number of internal
`links 141 to create a larger switch. At least one internal link
`couples any two subsystems. Each subsystem 110 includes
`a switch element 100 coupled to a forwarding and filtering
`database 140, also referred to as a forwarding database. The
`forwarding and filtering database may include a forwarding
`memory 113 and an associated memory 114. The forwarding
`memory (or database) 113 stores an address table used for
`matching with the headers of received packets. The associ-
`ated memory (or database) stores data associated with each
`entry in the forwarding memory that is used to identify
`forwarding attributes for forwarding the packets through the
`MLDNE. A number of external ports (not shown) having
`input and output capability interface the external connec-
`tions 117. In one embodiment, each subsystem supports
`multiple Gigabit Ethernet ports, Fast Ethernet ports and
`Ethernet ports. Internal ports (not shown) also having input
`and output capability in each subsystem couple the internal
`links 141. Using the internal links, the MLDNE can connect
`multiple switching elements together to form a multigigabit
`switch.
`
`The MLDNE 101 further includes a central processing
`system (CPS) 160 that is coupled to the individual sub-
`system 110 through a communication bus 151 such as the
`peripheral components interconnect (PCI). The CPS 160
`includes a central processing unit (CPU) 161 coupled to a
`central memory 163. Central memory 163 includes a copy of
`the entries contained in the individual forwarding memories
`113 of the various subsystems. The CPS has a direct control
`and communication interface to each subsystem 110 and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`provides some centralized communication and control
`between switch elements.
`
`AN EXEMPLARY SWITCH ELEMENT
`
`FIG. 2 is a simplified block diagram illustrating an
`exemplary architecture of the switch element of FIG. 1. The
`switch element 100 depicted includes a central processing
`unit (CPU) interface 215, a switch fabric block 210, a
`network interface 205, a cascading interface 225, and a
`shared memory manager 220.
`Ethernet packets may enter or leave the network switch
`element 100 through any one of the three interfaces 205,
`215, or 225. In brief, the network interface 205 operates in
`accordance with a corresponding Ethernet protocol
`to
`receive Ethernet packets from a network (not shown) and to
`transmit Ethernet packets onto the network via one or more
`external ports (not shown). An optional cascading interface
`225 may include one or more internal links (not shown) for
`interconnecting switching elements to create larger
`switches. For example, each switch element 100 may be
`connected together with other switch elements in a full mesh
`topology to form a multi-layer switch as described above.
`Alternatively, a switch may comprise a single switch ele-
`ment 100 with or without the cascading interface 225.
`The CPU 161 may transmit commands or packets to the
`network switch element 100 via the CPU interface 215. In
`this manner, one or more software processes running on the
`CPU 161 may manage entries in an external forwarding and
`filtering database 140, such as adding new entries and
`invalidating unwanted entries. In alternative embodiments,
`however, the CPU 161 may be provided with direct access
`to the forwarding and filtering database 140. In any event,
`for purposes of packet forwarding, the CPU port of the CPU
`interface 215 resembles a generic input port into the switch
`element 100 and may be treated as if it were simply another
`external network interface port. However, since access to the
`CPU port occurs over a bus such as a peripheral components
`interconnect (PCI) bus, the CPU port does not need any
`media access control (MAC) functionality.
`Returning to the network interface 205, the two main
`tasks of input packet processing and output packet process-
`ing will now briefly be described. Input packet processing
`may be performed by one or more input ports of the network
`interface 205. Input packet processing includes the follow-
`ing: (1) receiving and verifying incoming Ethernet packets,
`(2) modifying packet headers when appropriate, (3) request-
`ing buffer pointers from the shared memory manager 220 for
`storage of incoming packets,
`(4)
`requesting forwarding
`decisions from the switch fabric block 210, (5) transferring
`the incoming packet data to the shared memory manager 220
`for temporary storage in an external shared memory 230,
`and (5) upon receipt of a forwarding decision, forwarding
`the buffer pointer(s) to the output port(s) indicated by the
`forwarding decision. Output packet processing may be per-
`formed by one or more output ports of the network interface
`205. Output processing includes requesting packet data from
`the shared memory manager 220, transmitting packets onto
`the network, and requesting deallocation of buffer(s) after
`packets have been transmitted.
`The network interface 205, the CPU interface 215, and the
`cascading interface 225 are coupled to the shared memory
`manager 220 and the switch fabric block 210. Preferably,
`critical functions such as packet forwarding and packet
`buffering are centralized as shown in FIG. 2. The shared
`memory manager 220 provides an efficient centralized inter-
`face to the external shared memory 230 for buffering of
`
`8
`
`

`
`US 6,246,680 B1
`
`5
`incoming packets. The switch fabric block 210 includes a
`search engine and learning logic for searching and main-
`taining the forwarding and filtering database 140 with the
`assistance of the CPU 161.
`The centralized switch fabric block 210 includes a search
`
`engine that provides access to the forwarding and filtering
`database 140 on behalf of the interfaces 205, 215, and 225.
`Packet header matching, Layer 2 based learning, Layer 2
`and Layer 3 packet forwarding, filtering, and aging are
`exemplary functions that may be performed by the switch
`fabric block 210. Each input port is coupled with the switch
`fabric block 210 to receive forwarding decisions for
`received packets. The forwarding decision indicates the
`outbound port(s) (e.g., external network port or internal
`cascading port) upon which the corresponding packet should
`be transmitted. Additional information may also be included
`in the forwarding decision to support hardware routing such
`as a new MAC destination address (DA) for MAC DA
`replacement. Further, a priority indication may also be
`included in the forwarding decision to facilitate prioritiza-
`tion of packet traffic through the switch element 100.
`In the present embodiment, Ethernet packets are centrally
`buffered and managed by the shared memory manager 220.
`The shared memory manager 220 interfaces with every input
`port and output port and performs dynamic memory alloca-
`tion and deallocation on their behalf, respectively. During
`input packet processing, one or more buffers are allocated in
`the external shared memory 230 and an incoming packet is
`stored by the shared memory manager 220 responsive to
`commands received from the network interface 205, for
`example. Subsequently, during output packet processing, the
`shared memory manager 220 retrieves the packet from the
`external shared memory 230 and deallocates buffers that are
`no longer in use. To assure no buffers are released until all
`output ports have completed transmission of the data stored
`therein,
`the shared memory manager 220 preferably also
`tracks buffer ownership.
`Having described the architecture of the switch element
`100 at a high level, a more detailed view of the individual
`components will now be described with reference to FIG.
`NETWORK AND CASCADING INTERFACES
`
`The switch element of the present invention provides wire
`speed routing and forwarding of Ethernet, Fast Ethernet, and
`Gigabit Ethernet packets among the three interfaces 215,
`205, and 225. According to the present embodiment, each
`port of the network interface 205 and the cascading interface
`225 includes an input packet process (IPP), an output packet
`process (OPP), and a media access controller (MAC).
`The IPPs are coupled in communication with the switch
`fabric 210, the shared memory manager 220, and the OPPs.
`The IPPs request forwarding decisions from the switch
`fabric 210 for received packets and temporarily store the
`packet data in the shared memory 230 until a forwarding
`decision is returned. Upon receipt of a forwarding decision,
`the IPPs forward the corresponding packet to the appropriate
`OPPs, if any.
`According to one embodiment, received packet headers
`are modified by the IPPs as disclosed in U.S. patent appli-
`cation Ser. No. 08/885,000 entitled “Mechanism for Packet
`Field Replacement in a Multi-Layered Switched Network
`Element” filed on Jun. 30, 1997, which is incorporated
`herein by reference.
`The OPPs are coupled in communication with the shared
`memory manager 220. When a packet
`is ready for
`transmission, the OPPs retrieve the packet data from the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`shared memory 230 via the shared memory manager 220
`and transmit the packet data onto the attached network.
`According to one embodiment, dynamic output queuing
`in the OPPs is as disclosed in U.S. patent application Ser.
`No. 08/885,232 entitled “Method and Apparatus for
`Dynamic Queue Sizing” filed on Jun. 30, 1997, which is
`incorporated herein by reference.
`According to another embodiment, packet routing and
`packet field replacement are as disclosed in U.S. patent
`application Ser. No. 08/885,257 entitled “Mechanism for
`Packet Field Replacement in a distributed Multi-Layer Net-
`work Element”filed on Jun. 30, 1997, which is incorporated
`herein by reference.
`
`SWITCH FABRIC
`
`The switch fabric 210 provides centralized access to the
`forwarding and filtering database 140 on behalf of the input
`ports. Highly pipelined logic within the switch fabric 210
`allows it to receive and process packet headers from several
`input ports at once. Advantageously, the centralization and
`pipelining reduce hardware implementation overhead. For
`example, an N stage packet header processing pipeline
`allows N packet headers to be processed from various input
`ports in a single block rather than having to provide N
`individual packet header processing units.
`According to one embodiment, the switch fabric 210 is
`implemented as disclosed in U.S. patent application Ser. No.
`08/885,116 entitled “Search Engine Architectu