United States Patent
`Cheriton et al.
`
`19
`
`54 METHOD FOR TRAFFIC MANAGEMENT,
`TRAFFIC PRIORITIZATION, ACCESS
`CONTROL, AND PACKET FORWARDING IN
`A DATAGRAM COMPUTER NETWORK
`
`75 Inventors: David R. Cheriton; Andreas V.
`Bechtolsheim, both of Palo Alto, Calif.
`73 Assignee: Cisco Systems, Inc., San Jose, Calif.
`
`*
`
`Notice:
`
`This patent issued on a continued pros
`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. No.: 08/581,134
`22 Filed:
`Dec. 29, 1995
`(51) Int. Cl. ............................................... H04L 12/56
`52 U.S. 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
`
`Re. 33,900 4/1992 Howson.
`4,131,767 12/1978 Weinstein.
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`O 384758 2/1990 European Pat. Off..
`O 384758 A2 8/1990 European Pat. Off..
`O 431 751A1 11/1990 European Pat. Off..
`O 567 217 A2 10/1993 European Pat. Off..
`WO93/07569 4/1993 WIPO.
`WO93/07692 4/1993 WIPO.
`WO94/O1828 1/1994 WIPO.
`WO95/20850 8/1995 WIPO.
`WO95/20850 8/1995 WIPO.
`
`US006091725A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,091,725
`*Jul.18, 2000
`
`OTHER PUBLICATIONS
`William Stallings, Data and Computer Communications, PP:
`329-333, Prentice Hall, Upper Saddle River, New Jersey
`O7458.
`Allen, M., “Novell IPX Over Various WAN Media (IPXW
`AN).” Network Working Group, RFC 1551, Dec. 1993, pp.
`1-22.
`
`(List continued on next page.)
`Primary Examiner Min Jung
`Attorney, Agent, or Firm-Oblon, Spivak, McClelland,
`Maier & Neustadt, P.C.
`57
`ABSTRACT
`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 applications.
`
`6 Claims, 6 Drawing Sheets
`
`FACKETARRIES
`
`CHEDSA
`WIRTUALPANEX IN
`IRJALPAHACHF
`
`(ALD
`W3TALPATH
`ECR
`FOUND 3
`
`
`
`S
`
`ERRC STAGRM
`ECTROLLER CPJ
`
`CONROLLERC)
`PROCESSES DATARA
`INSEF3E
`
`CPUFORARDS
`DAGRANPACKT
`STUP PRT
`SEY) PACE
`
`CESTOLER CPU
`WRES NEWRUAL
`PATH RECORD
`REPRESLEAST
`ECENTLY SEDFTRY
`FNEESS3
`
`PREESS DATASRA
`INSWITCHARE
`
`FORRETOOTRUT
`PORT SENCPACKET
`
`PDATE SAISES
`FELDS
`
`NOAC Ex. 1057 Page 1
`
`

`

`6,091,725
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`7/1979 Parikh et al..
`4,161,719
`4,316.284 2/1982 Howson.
`4,397,020 8/1983 Howson.
`4,419,728 12/1983 Larson.
`4,424,565
`1/1984 Larson.
`4,437,087 3/1984 Petr.
`4,438,511
`3/1984 Baran.
`4,439,763 3/1984 Limb.
`4,445,213 4/1984 Baugh et al..
`4,446,555 5/1984 Devault et al..
`4,456.957 6/1984 Schieltz.
`4,464,658 8/1984 Thelen.
`4,499,576 2/1985 Fraser.
`4,506,358 3/1985 Montgomery .
`4,507,760 3/1985 Fraser.
`4,532,626
`7/1985 Flores et al..
`4,644,532 2/1987 George et al..
`4,646.287 2/1987 Larson et al..
`4,677,423
`6/1987 Benvenuto et al..
`4,679,189 7/1987 Olson et al. .............................. 370/60
`4,679,227 7/1987 Hughes-Hartogs.
`4,723.267 2/1988 Jones et al..
`4,731,816 3/1988 Hughes-Hartogs.
`4,750,136 6/1988 Arpin et al..
`4,757.495
`7/1988 Decker et al..
`4,763,191
`8/1988 Gordon et al..
`4,769,810 9/1988 Eckberg, Jr. et al..
`4,769,811
`9/1988 Eckberg, Jr. et al..
`4,771,425 9/1988 Baran et al..
`4,819,228 4/1989 Baran et al..
`4,827.411
`5/1989 Arrowood et al..
`4,833,706 5/1989 Hughes-Hartogs.
`4,835,737 5/1989 Herrig et al..
`4,879,551 11/1989 Georgiou et al..
`4,893,306
`1/1990 Chao et al..
`4,903.261
`2/1990 Baran et al..
`4,922,486 5/1990 Lidinsky et al. .
`4,933,937 6/1990 Konishi.
`4,960,310 10/1990 Cushing.
`4,962,497 10/1990 Ferenc et al..
`4,962,532 10/1990 Kasirai et al..
`4,965,772 10/1990 Daniel et al..
`4,970,678 11/1990 Sladowski et al..
`4,979,118 12/1990 Kheradpir ............................... 364/436
`4,980,897 12/1990 Decker et al..
`4,991,169 2/1991 Davis et al..
`5,003.595 3/1991 Collins et al..
`5,014,265 5/1991 Hahne et al..
`5,020,058 5/1991 Holden et al..
`5,033,076
`7/1991 Jones et al..
`5,054,034 10/1991 Hughes-Hartogs.
`5,059,925 10/1991 Weisbloom.
`5,072,449 12/1991 Enns et al..
`5,088,032 2/1992 Bosack.
`5,095,480 3/1992 Fenner ................................... 370/94.1
`5,115,431
`5/1992 Williams et al..
`5,128,945
`7/1992 Enns et al..
`5,136,580 8/1992 Videlock et al..
`5,166.930 11/1992 Braffet al..
`5,199,049 3/1993 Wilson.
`5,206,886 4/1993 Bingham.
`5,208.811
`5/1993 Kashio et al..
`5,212,686 5/1993 Joy et al. .
`5,224,099 6/1993 Corbalis et al..
`5,226,120 7/1993 Brown et al..
`5,228,062 7/1993 Bingham.
`5,229.994 7/1993 Balzano et al..
`5,237,564 8/1993 Lespagnol et al..
`5,241,682 8/1993 Bryant et al..
`5,243,342 9/1993 Kattemalalavadi et al. .
`
`5.243,596 9/1993 Port et al..
`5,245,614 9/1993 Gutman et al. ......................... 370/477
`5,247,516 9/1993 Bernstein et al..
`5.249,178 9/1993 Kurano et al..
`5,253,251 10/1993 Aramaki.
`5.255.291 10/1993 Holden et al..
`5,260,933 11/1993 Rouse.
`5,260,978 11/1993 Fleischer et al..
`5,268,592 12/1993 Bellamy et al..
`5,268,900 12/1993 Hluchy et al..
`5,271,004 12/1993 Proctor et al..
`5,274,631 12/1993 Bhardwaj.
`5,274,635 12/1993 Rahman et al..
`5,274,643 12/1993 Fisk.
`5,280,470
`1/1994 Buhrke et al..
`5,280,480
`1/1994 Pitt et al..
`5,280,500
`1/1994 Mazzola et al..
`5,283,783 2/1994 Nguyen et al..
`5,287,103 2/1994 Kasprzyk et al. .
`5,287,453 2/1994 Roberts ................................... 395/200
`5,291,482 3/1994 McHarg et al. .
`5,305,311
`4/1994 Lyles.
`5,307.343 4/1994 Bostica et al..
`5,309.437 5/1994 Perlman et al. ..................... 370/85.13
`5,311,509 5/1994 Heddes et al..
`5,313,454 5/1994 Bustini et al..
`5,313,582 5/1994 Hendel et al..
`5,317.562 5/1994 Nardin et al..
`5,319,644 6/1994 Liang.
`5,327,421
`7/1994 Hiller et al..
`5,331,637 7/1994 Francis et al..
`5,335,224 8/1994 Cole et al. .............................. 370/235
`5,345,445 9/1994 Hiller et al..
`5,345,446 9/1994 Hiller et al..
`5,359,592 10/1994 Corbalis et al..
`5,361,250 11/1994 Nguyen et al..
`5,361,256 11/1994 Doeringer et al..
`5,361,259 11/1994 Hunt et al..
`5,365,524 11/1994 Hiller et al..
`5,367,517 11/1994 Cidon et al..
`5,371,852 12/1994 Attanasio et al..
`5,386,567
`1/1995 Lien et al..
`5,390,170 2/1995 Sawant et al..
`5,390,175
`2/1995 Hiller et al..
`5,394,394 2/1995 Crowther et al..
`5,394.402 2/1995 Ross.
`5,400,325 3/1995 Chatwani et al..
`5,408,469 4/1995 Opher et al..
`5,416,842 5/1995 Aziz.
`5,422,880 6/1995 Heitkamp et al..
`5,422,882 6/1995 Hiller et al..
`5,423,002 6/1995 Hart.
`5,426,636 6/1995 Hiller et al..
`5,426,637 6/1995 Derby et al. ............................ 370/401
`5,428,607 6/1995 Hiller et al..
`5,430,715 7/1995 Corbalis et al..
`5,430,729 7/1995 Rahnema.
`5,432,784 7/1995 OZVeren .................................. 370/235
`5,442.457 8/1995 Najafi.
`5,442,630 8/1995 Gagliardi et al. .
`5,452.297 9/1995 Hiller et al..
`5,473,599 12/1995 Li et al..
`5,473,607 12/1995 Hausman et al..
`5,477.541 12/1995 White et al..
`5,485,455
`1/1996 Dobbins et al..
`5,490,140 2/1996 Abensour et al..
`5,490,258 2/1996 Fenner .................................... 395/401
`5,491,687 2/1996 Christensen et al..
`5,491,804 2/1996 Heath et al..
`5,497,368 3/1996 Reijnierse et al..
`5,499,238 3/1996 Shon ....................................... 370/399
`5,504,747 4/1996 Sweasey.
`
`
`
`NOAC Ex. 1057 Page 2
`
`

`

`6,091,725
`Page 3
`
`5,509,006 4/1996 Wilford et al..
`5,517,494 5/1996 Green.
`5,519,704 5/1996 Farinacci et al..
`5,519,858 5/1996 Walton et al. .......................... 395/600
`5,526,489 6/1996 Nilakantan et al..
`5,530.963
`6/1996 Moore et al..
`5.535,195
`7/1996 Lee.
`5,539,734 7/1996 Burwell et al..
`5,541,911
`7/1996 Nilakantan et al..
`5,546,370 8/1996 Ishikawa.
`5,555,244 9/1996 Gupta et al..
`5,561,669 10/1996 Lenney et al..
`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 2/1997 Komine et al..
`5,608,726 3/1997 Virgile.
`5,617,417
`4/1997 Sathe et al. .
`5,617,421
`4/1997 Chin et 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 7/1997 Belove et al..
`5,659,684 8/1997 Giovannoni et al..
`5,666,353 9/1997 Klausmeier et al..
`5,673,265 9/1997 Gupta et al..
`5,678,006 10/1997 Valizadeh et al..
`5,680,116 10/1997 Hashimoto et al..
`5,684,797 11/1997 Aznar et al. ............................ 370/390
`5,689,506 11/1997 Chiussi et al. .......................... 370/388
`5,694,390 12/1997 Yamato et al..
`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.
`5,892,924 4/1999 Lyon et al. ......................... 395/200.75
`5,903.559 5/1999 Acharya et al..
`OTHER PUBLICATIONS
`Becker, D., “3c589.c: A3c589 Etherlink3 ethernet driver for
`linux,” beckerGCESDIS.gsfc.nasa.gov, May 3, 1994, pp.
`1-13.
`
`Chowdhury, et al., “Alternative Bandwidth Allocation Algo
`rithms for Packet Video in ATM Networks,” INFOCOM
`1992, pp. 1061-1068.
`Doeringer, W., “Routing on Longest-Matching 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. 1-19.
`Simpson, W., “The Point-to-Point Protocol (PPP).” Net
`work Working Group, RFC 1548, Dec. 1993, pp. 1–53.
`Tsuchiya, P.F., “A Search Algorithm for Table Entries with
`Non-Contiguous 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. “Rate-Controlled Static-Priority 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 no Nov. 1992, pp. 409–411.
`Esaki, et al., “Datagram Delivery in an ATM-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, No. 1, Feb. 1996,
`pp. 86-97.
`
`NOAC Ex. 1057 Page 3
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 1 of 6
`
`6,091,725
`
`- - - - - - -
`NETWORKSWITCHING DEVICES
`
`- - - - - - -
`116
`
`105
`
`106
`
`107
`
`105
`
`108 it
`
`104
`
`127
`SERVER
`COMPUTERS
`
`- - - - - - - - - - - - - - - - - - - - - - -
`110- 111-U 112
`113
`114
`115
`-- - - - - - -
`
`\
`
`CLENT COMPUTERS
`- - - - - - - - - - - - - - - - - - - - - - - -
`
`NOAC Ex. 1057 Page 4
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 2 of 6
`
`6,091,725
`
`ARN piction TTTTTTTTTTTTTTTTTTTT
`DESTINATION |
`SOURCE
`TYPE
`DATA FIELD
`CRC
`ADDRESS
`ADDRESS
`FIELD
`(VARIABLE SIZE)
`FIELD
`
`20
`L - - - - - -
`
`2O2
`
`2O3
`
`J
`
`A MC.2
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`VIRTUAL PATH RECORD 500
`TAG
`FORWARDING
`FIELD
`FIELD
`
`STATSICS
`FIELD
`
`:
`
`
`
`STATE
`FIELD
`
`|
`|
`-- - - - -10
`TAG FIELD.
`DESTINATION |
`ADDRESS
`
`a
`
`---
`
`SOURCE
`ADDRESS
`
`3.11
`
`312
`
`---
`
`340
`
`is -
`INPUT
`PORT
`
`514
`
`TYPE
`FIELD
`
`513
`
`FORWARDING FIELD:
`OUTPUT
`PRIORITY
`PORT
`
`MULTI
`REAL | STORE
`TIME
`FORWARD | CAST
`
`SNOOP BUFFER
`MODE
`SIZE
`
`521
`
`522
`
`525
`
`524.
`
`525
`
`526
`
`327
`
`STATE FIELD:
`HEAD
`POINTER
`
`TAL
`POINTER
`
`INK
`POINTER
`
`351
`
`532
`
`555
`
`STATISTICS FIELD:
`NO OF PACKETS NO OF BYTES
`RECEIVED
`RECEIVED
`
`341
`
`342
`
`AAC. 3
`
`NOAC Ex. 1057 Page 5
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 3 of 6
`
`6,091,725
`
`
`
`VIRTUAL
`PATH
`INDEX
`650
`
`VIRTUAL PATH CACHE
`
`415
`
`HIT/MISS
`SIGNAL
`
`655
`
`VIRTUAL PATH
`RECORD BUS
`
`655
`
`SWITCH HARDWARE
`
`409
`
`OUTPUT
`PORTS
`
`INPUT
`PORTS
`
`
`
`
`
`
`
`
`
`BUFFER
`MEMORY
`
`410
`
`411
`
`CPU INTERFACE 412
`
`MEMORY
`
`415
`
`414
`
`A / C. 47
`
`NOAC Ex. 1057 Page 6
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 4 of 6
`
`6,091,725
`
`
`
`
`
`
`
`
`
`PACKET ARRIVES
`
`CHECK DATAGRAM
`VIRTUAL PATH INDEX IN
`VIRTUAL PATH CACHE
`
`YES
`
`
`
`VALID
`VIRTUAL PATH
`RECORD
`FOUND 2
`
`M0
`
`FORWARD DATAGRAM
`TO CONTROLLER CPU
`
`CONTROLLER CPU
`PROCESSES DATAGRAM
`IN SOFTWARE
`
`CPU FORWARDS
`DATAGRAM PACKET TO
`SWITCH OUTPUT PORT
`SEND PACKET
`
`
`
`CONTROLLER CPU
`WRITES NEW VIRTUAL
`PATH RECORD
`REPLACES LEAST
`RECENTLY USED ENTRY
`IF NECESSARY
`
`PROCESS DATAGRAM
`INSWITCH HARDWARE
`
`FORWARD TO OUTPUT
`PORT SEND PACKET
`
`UPDATE STATISTICS
`FIELDS
`
`AAC. 6
`
`NOAC Ex. 1057 Page 7
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 5 of 6
`
`6,091,725
`
`VIRTUAL PATH INDEX (630)
`VIRTUAL PATH
`CACHE INDEX
`(652)
`
`HASH
`FUNCTION
`
`HIT/MISS
`655
`
`VIRTUAL PATH
`RECORD DATABUS
`
`48 BTS
`
`
`
`48 BTS
`
`VIRTUAL PATH
`INDEX 650
`
`NOAC Ex. 1057 Page 8
`
`

`

`U.S. Patent
`
`Jul.18, 2000
`
`Sheet 6 of 6
`
`6,091,725
`
`
`
`OUTPUT PORT 80
`
`TRANSMT LIST 804
`
`A MO. 6
`
`NOAC Ex. 1057 Page 9
`
`

`

`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
`SOCWC.
`
`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,
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,091,725
`
`2
`which complicates the behavior of network nodes that need
`to create virtual circuits to communicate.
`Datagram Packet Switching
`In the datagram approach, each datagram packet is a
`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.
`Datagram packet Switching has the advantage that it
`avoids the overhead and cost of Setting up 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 traffic 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
`
`NOAC Ex. 1057 Page 10
`
`

`

`3
`to as Carrier Sense Multiple Access with Collision Detection
`(CSMA/CD), see U.S. 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, N.Y. 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.
`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
`CC.
`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.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,091,725
`
`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.
`Traffic 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 traffic 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
`network congestion problem, Since it does not take the
`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 flows, 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
`
`NOAC Ex. 1057 Page 11
`
`

`

`6,091,725
`
`5
`
`15
`
`35
`
`25
`
`S
`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
`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
`40
`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
`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
`Other features and advantages of the present invention
`will become more apparent to those skilled in the art from
`the following detailed description in conjunction with the
`appended drawings in which:
`FIG. 1 is a block diagram of a computer communication
`System;
`FIG. 2 is a block diagram of the Ethernet datagram packet
`format,
`FIG. 3 illustrates the Virtual Path Record data structure;
`FIG. 4 is a block diagram of the network Switching
`device;
`FIG. 5 is a flow diagram of the network switching device
`operation;
`FIG. 6 is a block diagram of the virtual path cache;
`FIG. 7 is a block diagram of the virtual path hash function;
`and
`FIG.