United States Patent
`[19]
`[11] Patent Number:
`6,091,725
`
`Cheriton et a1.
`[45 J Date of Patent:
`*Jul. 18, 2000
`
`USOO6091725A
`
`[54] METHOD FOR TRAFFIC MANAGEMENT,
`TRAFFIC PRIORITIZATION, ACCESS
`CONTROL, AND PACKET FORVVARDING IN
`A DATAGRAM COMPUTER NETWORK
`
`OTHER PUBLICATIONS
`
`.
`.
`.
`.
`.
`William Stalhngs, Data and Computer Communications, PP:
`329—333, Prentice Hall, Upper Saddle River, New Jersey
`07458.
`
`[75]
`
`Inventors: David R. Cheriton; Andreas V.
`Bechtolsheim, both of Palo Alto, Calif.
`
`Allen, M., “Novell IPX Over Various WAN Media (IPXW
`AN)” Network Working Group, RFC 1551, Dec 1993,14).
`1—22.
`
`[73] Assignee: Cisco Systems, Inc., San Jose, Calif.
`
`[*1 Notice:
`
`This patent issued on a continued PFOS-
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent
`term provisions of 35 U.S.C.
`154(a)(2).
`
`[21] APPL N05 08/581,134
`[22]
`Filed:
`Dec. 29, 1995
`
`Int. Cl.7 ..................................................... H04L 12/56
`[51]
`[52] Us. Cl.
`........................... 370/392; 370/397; 370/400
`[58] Field of Search ..................................... 370/230, 231,
`370/235, 236, 237, 395, 392’ 397, 401,
`402, 403, 412, 399, 407, 400
`
`[56]
`
`References Cited
`
`U~S~ PATENT DOCUMENTS
`4/1992 Howson _
`Re. 33 900
`4,131:767 12/1978 Weinstein.
`.
`.
`([415t continued on neXt page.)
`FOREIGN PATENT DOCUMENTS
`
`.
`2/1990 European Pat. Off.
`0 384 758
`8/1990 European Pat Offl ~
`0 384 758 A2
`11/1990 European Pal Offl -
`0 431 751 A1
`0 567 217 A2 10/1993
`European Pat. 01f.
`.
`WO93/07569
`7’1993 WIPO .
`WOO3/07692
`4/1993 WIPO .
`wo94/01828
`1/1994 WIPO .
`WO 95/20850
`8/1995 WIPO .
`WO95/20850
`/1995 WIPO .
`
`PACKET MRWEE
`
`(List continued on next page.)
`Primary Examiner—Min Jung
`Attorney, Agent, or Firm—Oblon, Spivak, McClelland,
`Maier & Neustadt, RC.
`
`ABSTRACT
`[57]
`The invention provides an enhanced datagram packet
`switched computer network. The invention processes net-
`work datagram packets in network devices as separate flows,
`based on the source-destination address pair in the datagram
`packet. As a result, the network can control and manage each
`flow of datagrams in a segregated fashion. The processing
`steps that can be specified for each flow include traffic
`management,
`flow control, packet forwarding, access
`control, and other network management functions. The
`ability to control network traffic on a per flow basis allows
`for the efficient handling of a wide range and a large variety
`of network traffic, as is typical
`in large-scale computer
`networks,
`including Video and multimedia traffic. The
`amount of buffer
`resources and bandwidth resources
`
`assigned to each flow can be individually controlled by
`network management.
`In the dynamic operation of the
`network,
`these resources can be varied based on actual
`network traffic loading and congestion encountered. The
`invention also teaches an enhanced datagram packet
`switched computer network which can selectively control
`flows of datagram packets entering the network and travel-
`ing between network nodes. This new network access con-
`trol method also interoperates with existing media access
`control protocols, such as used in the Ethernet or 802.3 local
`area network. An aspect of the invention is that it does not
`require any changes to existing network protocols or net-
`work apphcamns'
`
`6 Claims, 6 Drawing Sheets
`
`CHER DAMSW
`'y‘lRlUAl PM WDU iN
`WUUAL PAH CALHF
`
`
` WU]
`'[5
`VRTUAL PATH
`?[CO?D
`FOUND 7
`PRMESS DATAGRAM
`
`W SWLH HANJWM
`'W
`
`,
`,
`,
`‘
`
`i
`mam mom
`FORWARD 0 0qu
`10 00010110: 1a
`i
`aura SEND Paw
`comma m
`0 sen/tar
`1 mm; 50 150.3
`PROCESSES Dir/aw
`4i—
`
`
`
`
`
`
`!‘— FEDS
`can roman;
`1
`UA‘ARRAM mm :0
`BMW OUPU PM
`500 PACKE'
`
`LUWULIR EFU
`i ,
`WRMES NEW WWW
`”AM WOW.
`RLPWJH mm
`KEENW JSED WW
`lF NECESSARY
`
`UNIFIED 1002
`
`UNIFIED 1002
`
`

`

`6,091,725
`
`Page 2
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`
`.
`
`.
`
`US. PATENT DOCUMENTS
`.
`71’1979 Pankh et al- -
`491612719
`1’1982 HOWSOH -
`473169284
`81’1983 HOWSOH -
`493977020
`12/1983 Lar50n~
`494199728
`1/1984 Larson .
`4,424,565
`3/1984 Fem
`474379087
`1’1984 Baran ~
`4,438,511
`3/1984 Limb .
`4,439,763
`4/1984 Baugh 91 ii]- -
`4,445,213
`5/1984 Devault et a1.
`4,446,555
`/1984 Schieltz .
`4,456,957
`/1984 Thelen .
`4,464,658
`2/1985 Fraser .
`4,499,576
`3/1985 Montgomery .
`4,506,358
`/1985 Fraser .
`4,507,760
`7/1985 Flores et a1.
`4,532,626
`' /1987 George et a1.
`4,644,532
`.
`2/1987 Larson et a1.
`4,646,287
`.
`6/1987 Benvenuto et a1.
`4,677,423
`7/1987 Olson et a1.
`.............................. 370/60
`4,679,189
`7/1987 Hughes—Hartogs .
`4,679,227
`2/1988 Jones et a1.
`.
`4,723,267
`/1988 Hughes—Hartogs .
`4,731,816
`6/1988 Arpin et a1.
`.
`4,750,136
`7/1988 Decker et a1.
`4,757,495
`.
`/1988 Gordon et a1.
`4,763,191
`9/1988 Eckbel‘g, Jr. et al.
`4,769,810
`9/1988 Eckberg, Jr. et a1.
`4,769,811
`/1988 Baran et a1.
`.
`4,771,425
`4/1989 Baran et a1.
`.
`4,819,228
`.
`5/1989 Arrowood et a1.
`4,827,411
`5/1989 IIughes—Hartogs .
`4,833,706
`5/1989 Herrig et a1.
`.
`4,835,737
`11/1989 Georgiou et al.
`4,879,551
`1/1990 Chao et a1.
`.
`4,893,306
`.
`2/1990 Baran et a1.
`4,903,261
`5/1990 Lidinsky et a1.
`4,922,486
`/1990 Konislli .
`4,933,937
`4,960,310 10/1990 Cushing .
`4,962,497 10/1990 Ferenc et a1.
`4,962,532 10/1990 Kasirai et a1.
`.
`4,965,772 10/1990 Daniel et a1.
`.
`4,970,678
`11/1990 Sladowski et a1.
`4,979,118 12/1990 Kheradpir ............................... 364/436
`4,980,897 12/1990 Decker et a1.
`.
`4,991,169
`2/1991 Davis et a1.
`.
`5,003,595
`3/1991 Collins et a1.
`5,014,265
`5/1991 Hahne et a1.
`5,020,058
`5/1991 Holden et a1.
`5,033,076
`/1991 Jones et a1.
`.
`5,054,034 10/1991 Hughes—Hartogs .
`5,059,925
`10/1991 Weisbloom .
`5,072,449
`12/1991 Enns et a1.
`.
`5,088,032
`2/1992 Bosack .
`5,095,480
`/1992 Fenner
`................................... 370/94.1
`5,115,431
`5/1992 Williams et a1.
`.
`5,128,945
`7/1992 Enns et a1.
`.
`5,136,580
`8/1992 Videlock et a1.
`5,166,930
`11/1992 Braff et a1.
`.
`5,199,049
`3/1993 Wilson .
`5,206,886
`/1993 Bingham .
`5,208,811
`5/1993 Kashio et al.
`5,212,686
`5/1993 Joy et a].
`.
`5,224,099
`6/1993 Corbalis et a1.
`5,226,120
`7/1993 Brown et a1.
`.
`5,228,062
`7/1993 Bingham .
`.
`5,229,994
`/1993 Balzano et a1.
`5,237,564
`8/1993 Lespagnol et a1.
`5,241,682
`8/1993 Bryant et a1.
`.
`5,243,342
`/1993 Kattcmalalavadi ct a1.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`......................... 370/477
`.
`
`.
`9/1993 Port et a1.
`5,243,596
`9/1993 Gutman et a1.
`5,245,614
`9/1993 Bernstein et a1.
`5,247,516
`9/1993 Kurano et a1.
`.
`5,249,178
`10/1993 Aramaki .
`5,253,251
`10/1993 Holden et a1.
`5,255,291
`11/1993 Rouse .
`5,260,933
`11/1993 Fleischer et a1.
`5,260,978
`5,268,592 12/1993 Bellamy et a1.
`5,268,900 12/1993 Hluchyj et a1.
`5,271,004 12/1993 Proctor et a1.
`5,274,631
`12/1993 Bhardwaj .
`5,274,635
`12/1993 Rahman et a1.
`5,274,643
`12/1993 Fisk .
`5,280,470
`1/1994 Buhrke et a1.
`5,280,480
`1/1994 Pitt et al. .
`5,280,500
`1/1994 Mazzola et a1.
`.
`5,283,783
`2/1994 Nguyen et a1.
`.
`5,287,103
`2/1994 Kasprzyk et a1.
`5,287,453
`2/1994 Roberts ................................... 395/200
`5,291,482
`3/1994 McHarg et a1.
`.
`5,305,311
`4/1994 Lyles .
`5,307,343
`4/1994 Bostica et a1.
`5,309,437
`5/1994 Perlman et a1.
`5,311,509
`5/1994 Heddes et a].
`5,313,454
`5/1994 Bustini et a1.
`5,313,582
`5/1994 Hendel et a1.
`5,317,562
`5/1994 Nardin et a1.
`5,319,644
`6/1994 Liang .
`.
`5,327,421
`7/1994 Hiller et a1.
`5,331,637
`7/1994 Francis et a1.
`5,335,224
`8/1994 Cole et a1.
`.
`5,345,445
`9/1994 Hiller et a1.
`.
`5,345,446
`9/1994 Hiller et a1.
`5,359,592 10/1994 Corbalis et a1.
`.
`5,361,250
`11/1994 Nguyen et a1.
`5,361,256
`11/1994 Doeringer et al.
`5,361,259
`11/1994 Hunt et a1.
`.
`5,365,524
`11/1994 Hiller et a1.
`.
`5,367,517
`11/1994 Cidon et a1.
`5,371,852 12/1994 Attanasio et a1.
`5,386,567
`1/1995 Lien et a1.
`.
`5,390,170
`2/1995 Sawant et a1.
`5,390,175
`2/1995 Hiller et a1.
`.
`5,394,394
`2/1995 Crowther et a1.
`5,394,402
`2/1995 Ross .
`5,400,325
`3/1995 Chatwani et a1.
`5,408,469
`4/1995 Opher et a1.
`.
`5,416,842
`5/1995 Aziz .
`5,422,880
`6/1995 Heitkamp et a1.
`5,422,882
`6/1995 Hiller et a1.
`.
`5,423,002
`6/1995 Hart.
`5,426,636
`6/1995 Hiller et a1.
`5,426,637
`6/1995 Derby et a1.
`.
`5,428,607
`6/1995 Hiller et a1.
`5,430,715
`7/1995 Corbalis et a1.
`5,430,729
`7/1995 Rahnema .
`5,432,784
`7/1995 Ozveren .................................. 370/235
`5,442,457
`8/1995 Najafl .
`5,442,630
`8/1995 Gagliardi et a1.
`5,452,297
`9/1995 Hiller et a1.
`.
`5,473,599
`12/1995 Li et a1.
`.
`5,473,607 12/1995 Hausman et a1.
`5,477,541
`12/1995 White et a1.
`.
`.
`5,485,455
`1/1996 Dobbins et a].
`.
`5,490,140
`2/1996 Abensour et a1.
`5,490,258
`2/1996 Fenner
`.................................... 395/401
`5,491,687
`2/1996 Christensen et a1.
`.
`5,491,804
`2/1996 Heath et a1.
`.
`.
`5,497,368
`3/1996 Reijnierse et al.
`5,499,238
`3/1996 Shon ....................................... 370/399
`5,504,747
`4/1996 chascy .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`..................... 370/85.13
`
`.
`
`.
`
`.
`.
`.
`
`..................... 370/235
`
`.
`
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`............................ 370/401
`
`.
`
`.
`
`.
`
`

`

`6,091,725
`
`Page 3
`
`Chowdhury, et al., “Alternative Bandwidth Allocation Algo-
`rithms for Packet Video in ATM Networks,” INFOCOM
`1992, pp. 1061—1068.
`Doeringer, W., “Routing on LongestiMatching Prefixes,”
`IEEE/ACM Transactions in Networking, vol. 4, No. 1, Feb.
`1996, pp. 86—97.
`Esaki, et al., “Datagram Delivery in an ATM—Internet,”
`2334b IEICE Transactions on Communications, Mar. 1994,
`No. 3, Tokyo, Japan.
`IBM Corporation, “Method and Apparatus for the Statistical
`Multiplexing of Voice, Data and Image Signals,” IBM
`Technical Disclosure Bulletin, No. 6, Nov. 1992, pp.
`409—411.
`
`Pei, et al., “Putting Routing Tables in Silicon,” IEEE Net-
`work Magazine, Jan. 1992, pp. 42—50.
`Perkins, D., “Requirements for an Internet Standard Point—
`to—Point Protocol,” Network Working Group, RFC 1547,
`Dec. 1993, pp. 1719.
`Simpson, W., “The Point—to—Point Protocol (PPP),” Net-
`work Working Group, RFC 1548, Dec. 1993, pp. 1753.
`Tsuchiya, RF, “A Search Algorithm for Table Entries with
`NoniContiguous Wildcarding,” Abstract, Bellcore.
`Zhang, et al., “Rate—Controlled Static—Priority Queueing,”
`INFOCOM 1993, pp. 227—236.
`Chowdhury, et al. “Alternative Bandwith Allocation”, 1992,
`IEEE Infocom ’92, pp. 1061—1068.
`Zhang, et al. “RateiControlled StaticiPriority Queueing”,
`1993, IEEE, pp. 227—236.
`IBM, “Method and Apparatus for the Statistical Multiplex-
`ing of Voice, Data, and Image Signals”, Nov., 1992, IBM
`Technical Data Bulletin n6 Nov. 1992, pp. 409—411.
`Esaki, et al., “Datagram Delivery in an AIM—Internet,”
`IEICE Transactions on Communications vol. E77—B, No. 3,
`(1994) Mar., Tokyo, Japan.
`Doeringer, et al., “Routing on Longest—Matching Prefixes,”
`IEEE Transactions on Networking, vol. 4, N0. 1, Feb. 1996,
`pp. 86—97.
`
`.
`
`.
`
`.
`
`/1996 Wilford et al. .
`5,509,006
`5/1996 Green .
`5,517,494
`.
`5/1996 Farinacci et al.
`5,519,704
`5/1996 Walton et al.
`.......................... 395/600
`5,519,858
`/1996 Nilakantan et al.
`.
`5,526,489
`6/1996 Moore et al.
`.
`5,530,963
`/1996 Lee .
`5,535,195
`.
`7/1996 Burwell et al.
`5,539,734
`7/1996 Nilakantan et al.
`5,541,911
`8/1996 Ishikawa .
`5,546,370
`.
`/1996 Gupta et al.
`5,555,244
`10/1996 Lenney et al. .
`5,561,669
`5,583,862 12/1996 Callon .
`5,592,470
`1/1997 Rudrapatna et al.
`5,598,581
`1/1997 Daines et al.
`.
`5,600,798
`2/1997 Chenrukuri et al.
`5,604,868
`/1997 Komine et al.
`.
`5,608,726
`/1997 Virgile.
`5,617,417
`4/1997 Sathe et al. .
`5,617,421
`4/1997 Chin ct al.
`.
`5,630,125
`5/1997 Zellweger ............................... 395/614
`5,632,021
`5/1997 Jennings et al.
`.
`5,634,010
`5/1997 Ciscon et al.
`.
`5,638,359
`6/1997 Peltola et al.
`.
`5,644,718
`/1997 Belove et al.
`.
`5,659,684
`8/1997 Giovannoni et al.
`5,666,353
`9/1997 Klausmeier et al.
`5,673,265
`/1997 Gupta et al.
`.
`5,678,006
`10/1997 Valizadeh et al. .
`5,680,116
`10/1997 Hashimoto et al.
`................ 370/390
`5,684,797
`11/1997 Aznaretal.
`5,689,506
`11/1997 Chiussietal. .......................... 370/388
`5,694,390 12/1997 Yamato etal..
`5,748,186
`5/1998 Raman .................................... 345/302
`5,748,617
`5/1998 McLain, Jr..
`5,802,054
`9/1998 Bellenger .
`5,835,710
`11/1998 Nagami et al.
`5,856,981
`1/1999 Voelker .
`......................... 395/200.75
`5,892,924
`/1999 Lyon et al.
`5,903,559
`5/1999 Acharya et al.
`.
`OTHER PUBLICATIONS
`
`.
`.
`
`.
`
`.
`
`Becker, D., “3c589.c: A3c589 Etherlink3 ethernet driver for
`linux,” becker@CESDIS.gsfc.nasa.g0v, May 3, 1994, pp.
`1—13.
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 1 0f 6
`
`6,091,725
`
`7|
`I
`
`1
`
`T
`E I
`
`II
`
`I
`
`I
`l
`:
`12
`I
`1
`SERVER
`|
`'LCOMPUTERS J'
`___—
`
`I
`1
`|
`:
`I
`
`I I
`
`"___—WEI—onKEwTIcfiINE[III/Tog“— 116
`
`l- ‘92
`I05
`
`106
`
`107
`
`1118 H7
`
`E
`
`M
`
`
`
`___ _ __ ______ __ _ __J
`
`1m
`
`1H
`
`1U
`
`1%
`
`1M
`
`1%
`
`120
`
`121
`
`122
`
`123
`
`124
`
`125
`
`

`

`US. Patent
`
`Jul. 18,2000
`
`Sheet 2 0f6
`
`6,091,725
`
`FD—AITCATNTJIEAEI 200— _______________87““ _, _T
`I
`DESTINATION
`SOURCE
`TYPE
`DATA FIELD
`CRC
`I
`
`
`I
`ADDRESS
`ADDRESS
`EIELO
`(VARIABLE SIZE)
`FIELD
`I
`I
`I
`L
`202
`203
`204
`205
`I
`
`
`
`
`20A
`
`FIG. 2
`
`
`
`T— __________________________ _I
`I VIRTUAL PATH RECORD 300
`I
`I
`TORNARDINC
`I
`,
`FIELD
`I
`|
`|
`I
`I
`I
`“‘~~\
`I_}_____319 _____33320321: _ W330 ______3‘9 _ _I
`I
`TAO FIELD:
`““““
`
`\
`
`STATISTICS
`TIELD
`
`DESTINATION
`ADDRESS
`
`SOURCE
`ADDRESS
`
`TYPE
`TIELD
`
`INPUT
`PORT
`
`311
`
`312
`
`313
`
`314
`
`FORWARDING FIELD:
`
`OUTPUT
`PORT
`
`PRIORITY
`
`
`
`REAL
`TIME
`
`
`
`STORE
`FORWARD
`
`MULTI
`CAST
`
`SNOOP
`MODE
`
`BUFFER
`SIZE
`
`
`
`321
`
`322
`
`323
`
`324
`
`325
`
`326
`
`327
`
`STATE FIELD:
`
`HEAD
`
`TAIL
`
`LINK
`
`POINTER
`
`POINTER
`
`POINTER
`
`331
`
`332
`
`333
`
`STATISTICS FIELD:
`
`NO. OF PACKETS
`
`NO. OF BYTES
`
`RECEIVED
`
`RECEIVED
`
`341
`
`342
`
`FIG. 3
`
`

`

`US. Patent
`
`Jul. 18,2000
`
`Sheet 3 0f6
`
`6,091,725
`
`
`
`WRTUAL PATH CACHE
`
`
`HIT/MISS
`
`WRTUAL PATH
`SIGNAL
`
`
`
`415
`
`RECORD BUS
`
`635
`
`633
`
`SWHCH HARDWARE
`
`WRTUAL
`
`PATH
`
`INDEX
`
`630
`
`INPUT
`
`PORTS
`
`{OS
`
`OUTPUT
`
`PORTS
`
`
`
`
`CPU INTERFACE 412
`
`410
`
`413
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 4 0f 6
`
`6,091,725
`
`PACKET ARRIVES
`
`CHECK DATAGRAM
`
`VIRTUAL PATH CACHE
`
`VIRTUAL PATH INDEX IN
`
`YES
`
`
` VALID
`VIRTUAL PATH
`
`
`
`FOUND ?
`
`”0
`
`RECORD
`
`FORWARD DATAGRAM
`0 C0
`LLER CPU
`
`NTRO
`
`T
`
`PROCESS DATAGRAM
`IN SWITCH HARDWARE
`
`FORWARD TO OUTPUT
`PORT SEND PACKET
`
`UPDATE STATISTICS
`FIELDS
`
`FIG. 5
`
`CONTROLLER CPU
`
`PROCESSES DATACRAM
`IN SOFTWARE
`
`CPU FORWARDS
`
`DATACRAM PACKET TO
`
`SWITCH OUTPUT PORT
`
`SEND PACKET
`IF NECESSARY
`
`CONTROLLER CPU
`
`WRITES NEW VIRTUAL
`PATH RECORD
`
`REPLACES LEAST
`
`RECENTLY USED ENTRY
`
`

`

`US. Patent
`
`Jul. 18,2000
`
`Sheet 5 0f6
`
`6,091,725
`
`VIRTUAL PATH INDEX (630)
`
`WRTUAL PATH
`
`CACHEINDEX
`(632)
`
`HASH
`
`FUNCNON
`LOGIC
`
`C
`
`HH/MBS
`635
`
`VIRTUAL PATH
`
`RECORD DATA BUS
`
`FIG. 6
`
`48 BITS
`DESTINATION ADDRESS
`
`48 BITS
`SOURCE ADDRESS
`
`VIRTUAL PATH
`INDEX 630
`
`
`
`
`
`701
`
`702
`
`FIG. 7
`
`

`

`US. Patent
`
`Jul. 18, 2000
`
`Sheet 6 0f 6
`
`6,091,725
`
`OUTPUT PORT 801
`
`T
`
`
`
`TRANSMTT LIST 804
`
`F1618
`
`

`

`6,091,725
`
`1
`
`METHOD FOR TRAFFIC MANAGEMENT,
`TRAFFIC PRIORITIZATION, ACCESS
`CONTROL, AND PACKET FORWARDING IN
`A DATAGRAM COMPUTER NETWORK
`
`CROSS-REFERENCE TO THE APPENDIX
`CONTAINING SOFTWARE
`
`Appendix A, which is a part of the present disclosure, lists
`the computer programs and related data in one embodiment
`of this invention. This listing of computer programs contains
`material which is subject to copyright protection. The copy-
`right owner has no objection to the facsimile reproduction
`by anyone of the patent document or the present disclosure,
`as it appears in the Patent and Trademark Office patent files
`or records, but otherwise reserves all copyright rights What-
`soever.
`
`10
`
`15
`
`BACKGROUND OF THE INVENTION
`
`1. Field of Invention
`
`The present invention relates to the field of computer
`networks. More particularly, the present invention relates to
`the field of computer networks which are based on datagram
`packet switching.
`2. Background of the Invention
`Computer Networks are used to interconnect computers
`and peripherals to allow them to exchange and share data
`such as files, electronic mail, databases, multimedia/video,
`and other data.
`
`Packet Switching
`Nearly all computer networks use packet switching,
`which divides longer units of data transfer into smaller
`packets which are sent separately over the network. This
`allows each packet
`to be processed independently from
`another packet without having to wait for the entire data
`transfer to be completed. It also enables communications
`between a plurality of computer systems to be intermixed on
`one network. Host interfaces connect the computer systems
`to a network allowing each computer system to act as the
`source and destination of packets on the network.
`A first key issue in packet switched networks is address-
`ing. The addressing in packet switched networks is conven-
`tionally performed by one of two approaches, known as
`virtual circuit packet switching or datagram packet switch-
`ing.
`Virtual Circuit Packet Switching
`In the virtual circuit approach, before any data can be
`transmitted, a virtual circuit must be first established along
`the path from the source to the destination in advance of any
`communication. After the virtual circuit is setup, the source
`can then send packets to the destination. Each packet in the
`virtual circuit approach has a virtual circuit identifier, which
`is used to switch the packet along the path from source to the
`destination.
`
`The virtual circuit approach reduces the size of the
`identification required in each packet header. It also allows
`additional
`information about
`the packet handling to be
`established as part of the virtual circuit setup operation.
`Another claimed benefit is that forwarding and switching of
`virtual circuit packets can be made more efficient because of
`the virtual setup process. However,
`the virtual circuit
`approach incurs the cost of delay to setup the virtual circuit
`before sending any data, and it incurs the cost of maintaining
`the virtual circuit state in each network device along the
`virtual circuit path, even if a virtual circuit is idle. Also, in
`practice the memory space for virtual circuit state in network
`devices has limited the number of circuits that are available,
`
`40
`
`45
`
`60
`
`65
`
`2
`which complicates the behavior of network nodes that need
`to create virtual circuits to communicate.
`Datagram Packet Switching
`is a
`In the datagram approach, each datagram packet
`self-contained unit of data delivery. A typical datagram
`packet includes a globally unique source address, a globally
`unique destination address, a protocol type field, a data field,
`and a cyclic redundancy checksum (“CRC”) to insure data
`integrity.
`Datagrams can be sent without prior arrangement with the
`network, i.e. without setting up a virtual circuit or connec-
`tion. Each network device receiving a datagram packet
`examines the destination address included in the datagram
`packet and makes a local decision whether to accept, ignore,
`or forward this packet.
`Various conventional network devices learn information
`from observing datagram packet traffic in data networks. For
`example, a conventional network switch device that inter-
`connects multiple network segments can “learn” the location
`of network stations connected to its ports by monitoring the
`source address of packets received on its ports. After it has
`associated a station address with a certain port, the network
`switch can then forward datagram packets addressed to that
`station to that port. In this type of device, the datagram
`source address is used to learn the location of a station on the
`
`network, whereas the forwarding decision is made on basis
`of the datagram destination address alone.
`it
`Datagram packet switching has the advantage that
`avoids the overhead and cost of setting 11p virtual circuit
`connection in network devices. However,
`it
`incurs the
`expense of transmitting a larger packet header than required
`for virtual circuit switching, and it
`incurs the cost for
`processing this larger packet header in every network device
`to which it is delivered. Also, there is no virtual circuit setup
`process to establish additional information for datagram
`packet processing. Another disadvantage of datagram packet
`switching is that it is difficult to control packet flow to the
`same degree as with virtual circuits because there is, in the
`conventional case, no state in the network devices associated
`with the trallic flow.
`The datagram packet switching approach has been exten-
`sively used in shared media local area networks. Shared
`media networks provide for a multiplicity of stations directly
`connected to the network, with the shared media providing
`direct access from any transmitter to any receiver. Since the
`receivers need to be able to distinguish packets addressed
`specifically to them, each receiver needs to have a unique
`address. In addition, since the unit of access to the shared
`medium is one packet, each packet needs to contain the
`unique address capable to identify the receiver. As a result,
`all commonly used local area networks are based on data-
`gram packet switching and have no provisions for virtual
`circuit setup.
`Media Access Control Protocol
`The network access mechanism in shared media local area
`network will now be further described. This function, com-
`monly known as the media access control or MAC protocol,
`defines how to arbitrate access among multiple stations that
`desire to use the network. Individual stations connected to
`the network have to adhere to the MAC protocol in order to
`allow proper network operation.
`A number of different media access control protocols
`exist. The MAC protocol,
`in conjunction with the exact
`packet format, is the essence of what defines a local area
`network standard. The following is a brief overview of local
`area network standards that are in wide use today.
`The most widely used local area network is commonly
`known as Ethernet and employs an access protocol referred
`
`

`

`6,091,725
`
`3
`to as Carrier Sense Multiple Access with Collision Detection
`(CSMA/CD). [see US. Pat. No. 4,063,220, issued Dec. 13,
`1977, for a Multipoint Data Communication System with
`Collision Detection, Inventors Metcalfe, Boggs, Thacker,
`and Lampson]. The current definition of the Ethernet
`CSMA/CD protocol is defined in IEEE Standard 802.3,
`published by the Institute of Electrical and Electronics
`Engineers, 345 East 45th Street, New York, NY. 10017. The
`Ethernet standard specifies a data transmission rate of 10 or
`100 Megabits/second.
`Another widely used local area network standard is
`Tokenring, also known as IEEE Std 802.5, transmitting at a
`speed of 4 or 16 Mbits/sec and FDDI or Fiber-Distributed-
`Data-Interface which sends data at a speed of 100 Mbits/sec.
`Both Tokenring and FDDI are based on a circulating token
`granting access to the network, although their respective
`datagram packet formats and other operating aspects are
`unique to each standard.
`What is common to all these media access control mecha-
`nisms is that they do not include provisions for virtual circuit
`setup and have no provisions to specify attributes that relate '
`to virtual circuits, such as traffic management or flow control
`for specific connections. This limits the ability of conven-
`tional
`local area networks to accommodate higher level
`network functions or to support virtual connection oriented
`traffic mechanisms.
`
`10
`
`15
`
`Devices for Interconnecting Local Area Networks
`Another key issue with datagram packet switched net-
`works is how to interconnect individual network segments
`into larger networks. The size and usage of datagram packet
`switched networks has grown much beyond what was envi-
`sioned when these networks were designed. Devices such as
`bridges, switches, and routers, have been used to intercon-
`nect individual LAN segments into larger networks, but each
`have their own set of problems in scaling to higher perfor-
`mance.
`
`Bridges forward datagram packets between network seg-
`ments by learning the location of the devices on the network
`by observing the source address contained in datagram
`packets passing by. Once the bridge has learned which
`network device ia located on which network segment, it can
`then forward datagram packets addressed to that network
`device to the appropriate network segment. One of the
`limitations of bridges is that they do not filter traffic beyond
`the data link level.
`
`Switches are basically multi-port network bridges that can
`forward datagram packets among a multiplicity of network
`ports. Frequently, switches provide additional capabilities
`for assisting with network management, including traffic
`filtering and segmenting networks into virtual LANs. As in
`the case of bridges, switches have to forward broadcasts to
`all ports configured into one virtual LAN. In addition,
`conventional switches cannot provide fair service or priority
`service to individual traffic flows, and they require signifi-
`cant amount of memory to avoid dropping packets in the
`case of network congestion.
`Routers also interconnect several network segments, but
`they operate primarily at the network protocol layer, rather
`than at the datagram packet layer. Routers participate in all
`network protocol functions, which traditionally requires
`general purpose processing. As a result, traditional routers
`are more expensive and have less throughput than switches.
`In addition they are more difficult to administer.
`Finally, virtual circuit packet switched networks, in par-
`ticular ATM, have been proposed to interconnect local area
`network segments. However, it has turned out to be very
`difficult to map existing network protocols that are based on
`datagram packets to the ATM network architecture.
`
`40
`
`45
`
`60
`
`65
`
`4
`In summary, bridges and switches transparently extend
`the domain of networks, and allow for cost-effective and
`high-performance implementations. However, they cannot
`segment a network effectively in terms of traffic manage-
`ment and broadcast traffic. Routers, on the other hand, can
`segment networks very effectively, but are much more
`expensive and are performance bottleneck in high-speed
`networks. ATM has been very difficult to map to current
`network protocols.
`The ideal network device for interconnecting network
`segments would have the high-speed and cost-effectiveness
`of a switch, with the ability of segment and manage network
`traffic similar to a router.
`Traflic Management
`Another key issue in packet switched networks is traffic
`control or traffic management.
`In a packet switched network, each link at every switching
`node in the network represents a queue. As the trafiic arrival
`rate at a link approaches its transmission rate,
`the queue
`length grows dramatically and the data in the queue needs to
`be stored in the attached network nodes. Eventually, a
`network node will run out of packet buffer capacity which
`will cause further packets arriving to be discarded or
`dropped. Dropped packets are eventually retransmitted by
`the source, causing the traffic load to increase further.
`Eventually, the network can reach a state where most of the
`packets in the network are retransmissions.
`Conventionally, two types of traffic control mechanism
`are used in packet switched networks: flow control and
`congestion control. Flow control is concerned with matching
`the transmission rate of a source station to the reception rate
`of a destination station. A typical networks flow control
`mechanism uses a window techniques to limit the number of
`packets a source can transmit which are not yet confirmed as
`having been received by the destination. Conventional flow
`control is an end-to-end mechanism that exists in certain
`
`network protocols, in particular connection oriented network
`protocols such as TCP/IP. However, conventional flow con-
`trol between source and destination does not solve the
`
`take the
`network congestion problem, since it does not
`utilization of buffer resources within the network into
`account. In addition, non-connection oriented network pro-
`tocols do not use window based flow control. Also, continu-
`ous rate traffic sources such as real-time video don’t match
`the nature of destination controlled behavior since the trans-
`
`mission rate is determined by the source.
`Problem Statement
`What is needed is an improved method and apparatus for
`high-speed datagram packet switched networks that can
`support a large number of network stations, a wide range of
`network transmission speeds, a wide variety of source traffic
`behavior including video and multimedia, while maintaining
`compatibility with existing network protocols and applica-
`tions.
`
`SUMMARY OF THE INVENTION
`
`Methods and apparatus for an enhanced datagram packet
`switched computer network are disclosed.
`The invention processes network datagram packets in
`network devices as separate fiows, based on the source-
`destination address pair contained in the datagram packet
`itself. As a result, the network can control and manage each
`flow of datagrams in a segregated fashion. The processing
`steps that can be specified for each flow include traffic
`management,
`flow control, packet forwarding, access
`control, and other network management functions.
`The ability to control network traffic on a per flow basis
`allows for the efficient handling of a wide range and a large
`
`

`

`6,091,725
`
`5
`variety of network traffic, as is typical in large-scale com-
`puter networks, including Video and multimedia type traffic.
`The amount of buffer resources and bandwidth resources
`assigned to each flow can be individually controlled by
`network management.
`In the dynamic operation of the
`network,
`these resources can be varied based on actual
`network traffic loading and congestion encountered.
`The invention also includes an enhanced network access
`control method which can selectively control flows of data-
`gram packets entering the network and traveling between
`network nodes. This new network access control method
`
`interoperates with existing media access control protocols,
`such as used in the Ethernet or 802.3 local area network.
`
`An important aspect of the invention is that it can be
`implemented in network switching devices at very high
`performance and at low cost. High performance is required
`to match the transmission speed of datagram packets on the
`network. Low cost is essential such that it is economical to
`
`5
`
`10
`
`15
`
`’
`
`use the invention widely.
`In the preferred implementation, both high-performance '
`and low cost is achieved by partitioning the task of datagram
`flow processing between dedicated network switch hard-
`ware and dedicated network switch software that executes
`on a high-speed controller CPU.
`The network switch hardware provides a multiplicity of
`network ports, a shared memory buffer for storing datagram
`packets, a Virtual path cache that stores the state and
`processing instructions specific to the active datagram
`packet flows.
`Datagram packets received on an input port are buffered
`in the shared memory buffer. The source-destination address
`pair in the datagram packet header is used to index the
`virtual path cache to find a matching entry. If a matching
`entry is found in the virtual path cache, then the switch
`hardware performs all the packet processing steps indicated
`in the Virtual path record, including traffic management and
`packet routing.
`If no matching entry is found in the Virtual path cache,
`then the datagram packet is forwarded to the controller CPU
`for general purpose processing. The controller CPU
`determines,
`through network management data structures
`and software, how to process further datagram packets with
`this source-destination address in the switch hardware. The
`
`40
`
`controller CPU then loads an appropriate entry into the
`virtual path cache. If all entries in the Virtual path cache are
`in use, then the CPU removes the least recently used entry
`before loading the new entry.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`45
`
`6
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`An enhanced computer network communication system is
`disclosed.
`
`To help understand the invention, the following defini-
`tions are used:
`
`A “datagram packet” is a self-contained unit of packet
`delivery on a packet switched network, which includes a
`destination address field, a source address field, an optional
`type field, and a data field.
`The “destination address” and the “source address” refer
`
`to the physical network device addresses contained in a
`datagram packet, both of which are unique within a network.
`A “flow” is a plurality of datagram packets each packet
`containing an identical source-destination address pair.
`A “Virtual path” is the communication path from a source
`to a destination in a datagram packet switched network.
`In the following description, for purposes of explanation,
`specific numbers, times, signals, and other parameters are
`set forth in order to provide a thorough understanding of the
`present invention. However, it will be apparent to anyone
`skilled in the art that the present invention may be practiced
`without these specific details. In other instances, well known
`circuits and devices are shown in block diagram in order not
`to obscure the present invention unnecessarily.
`The datagram packet switched communication system is
`illustrated in FIG. 1 by way of four network switching
`devices 101, 102, 103, and 104 interconnected with each
`other