(12) United States Patent
`Riddle et al.
`
`1111111111111111111111,111o!IIIIII1111111111111111111110111111
`
`US 6,412,000 B1
`Jun. 25, 2002
`
`(to) Patent No.:
`(45) Date of Patent:
`
`(54)
`
`METHOD FOR AUTOMATICALLY
`CLASSIFYING TRAFFIC IN A PACKET
`COMMUNICATIONS NETWORK
`
`(75)
`
`Inventors: Guy Riddle; Robert L. Packer, both
`of Los Gatos, CA (US)
`
`(73)
`
`Assignee: Packeteer, Inc., Cupertino, CA (US)
`
`5,495,426 A * 2/1996 Waclawsky et al.
`5,838,919 A * 11/1998 Schwaller et al.
`5,870,561 A * 2/1999 Jarvis et al.
`5,903,559 A * 5/1999 Acharya et al.
`5,923,849 A * 7/1999 Venkatraman
`6,028,842 A
`2/2000 Chapman et al.
`6,046,980 A * 4/2000 Packer
`6,137,782 A * 10/2000 Sharon et al.
`6,209,033 B1 * 3/2001 Datta et al.
`
`709/226
`709/224
`709/238
`709/236
`709/224
`370/252
`370/230
`709/238
`709/224
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`* cited by examiner
`
`(21)
`
`Appl. No.: 09/198,090
`
`(22)
`
`Filed:
`
`Nov. 23, 1998
`
`(60)
`
`(51)
`(52)
`
`(58)
`
`Related U.S. Application Data
`Provisional application No. 60/066,864, filed on Nov. 25,
`1997.
`
` GO6F 15/173
`Int. C1.7
` 709/224; 709/223; 709/230;
`U.S. Cl.
`709/238; 709/242; 370/230; 370/235; 370/252;
`370/355; 370/356
` 709/223-226,
`Field of Search
`709/230, 235-236, 238-239, 242, 246;
`370/229-230, 235, 252-253, 355-356,
`401, 466-469
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`Primary Examiner—Zarni Maung
`Assistant Examiner—Bharat Barot
`(74) Attorney, Agent, or Firm—Townsend and Townsend
`and Crew LLP; Kenneth R. Allen
`
`(57)
`
`ABSTRACT
`
`In a packet communication environment, a method is pro-
`vided for automatically classifying packet flows for use in
`allocating bandwidth resources by a rule of assignment of a
`service level. The method comprises applying individual
`instances of traffic classification paradigms to packet net-
`work flows based on selectable information obtained from a
`plurality of layers of a multi-layered communication proto-
`col in order to define a characteristic class, then mapping the
`flow to the defined traffic class. It is useful to note that the
`automatic classification is sufficiently robust to classify a
`complete enumeration of the possible traffic.
`
`5,251,152 A * 10/1993 Notess
`
` 709/224
`
`15 Claims, 7 Drawing Sheets
`
`401
`
`C RETURN
`
`PARSE FLOW
`SPECIFICATION
`FROM A PACKET
`OF THE FLOW
`
`402
`
`COMPARE FLOW
`SPECIFICATION
`WITH EXISTING
`CLASSIFICATION TREE
`
`7- 404
`
`406
`
`NO
`
`TRAFFIC
`MATCHES A
`CLASS?
`
`YES
`
`ENTER INTO A
`SAVED LIST
`CHARACTERISTICS
`OF THE TRAFFIC
`
`y - 408
`
`410
`
`412
`
`SUPPRESS
`DUPLICATES
`
`DETERMINE BYTE
`COUNT FOR TRAFFIC
`AND INCLUDE WITH
`TRAFFIC SPECIFICATION
`IN SAVED LIST
`
`C RETURN )
`
`403
`
`RETRIEVE CLASSIFIED
`TRAFFIC FROM
`SAVED LIST
`
`420
`
`YES
`
`SAVED
`TRAFFIC WELL
`KNOWN?
`
`--422
`
`NO
`
`SAVED
`TRAFFIC A SERVER
`AT UNREGISTERED
`IP PORT?
`
`NO
`
`YES
`
`426
`
`NO
`
`SAVED
`RAFFIC BELONGS
`TO A SERVICE
`GGREGAT
`
`425-,
`
`CREATE NEW
`TRAFFIC CLASS
`FOR SAVED
`TRAFFIC
`
`YES
`
`CREATE TRAFFIC CLASS
`MATCHING ALL
`COMPONENTS OF
`SERVICE AGGREGATE
`
`428
`
`NO
`
`TOO
`MANY CLASSES
`
`--432
`
`YES
`
`(NO MORE AUTO
`
`CLASSIFICATION]
`
`Cloudflare - Exhibit 1039, page 1
`
`Cloudflare - Exhibit 1039, page 1
`
`

`

`Waled *S11
`
`IN)
`cn
`16.4
`O
`O
`16.4
`
`L JO 1 lamIS
`
`iff 000tTe9 Sf1
`
`32
`
`20
`SERVER
`
`40
`
`NETWORK
`
`45
`
`25
`
`CLIENT
`
`NETWORK IF
`
`37
`
`NETWORK IF
`
`37'
`
`000000000
`0 35a-.
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0 0 0 0 0 0 0 0 0
`
`CPU
`
`A
`
`35b
`
`37
`
`0 0 0 0 0 0 0 0 0
`0
`
`0
`0
`0
`0
`O
`0
`O
` 0
`O
`0
`O
`000000000
`
`CPU
`
`
`
`35a'-.
`
`35b'
`
`37'
`
`FIG. -1A
`(PRIOR ART)
`
`Cloudflare - Exhibit 1039, page 2
`
`Cloudflare - Exhibit 1039, page 2
`
`

`

`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 2 of 7
`
`US 6,412,000 B1
`
`.111111111111111M
`
`.y-20
`
`-4
`
`SERVER
`
`5 5
`.____
`
`4 6
`.___
`
`42
`.___.
`
`44
`
`CGI
`
`WEB
`SERVER
`
`OPERATING
`SYSTEM
`
`TCP/IP
`
`/DATA OBJECT
`1
`
`50
`
`,..--•
`
`I
`/ DATA OBJECT
`N
`
`51
`
`QUERY
`FROM USER 0 t „
`
`HTML OUTPUT
`TO USER
`
`45
`
`INTERNET
`
`0
`
`TCP/IP
`
`OPERATING
`SYSTEM
`
`44'
`
`42'
`
`WEB
`BROWSER
`
`46'
`.__
`
`FIG. 18
`(PRIOR ART)
`
`011111111111111111
`
`y -25
`
`CLIENT
`
`Cloudflare - Exhibit 1039, page 3
`
`Cloudflare - Exhibit 1039, page 3
`
`

`

`Waled *S11
`
`L JO £ lamIS
`
`iff 000tTe9 Sf1
`
`---
`
`_/- 71
`SUN
`SPARC
`
`}7- 70
`
`° 111111111111111111
`
`y -62
`
`IBM
`COMPATIBILE
`
`60
`
`75
`
`ROUTER
`
`----1---r
`
`-
`
`ETHERNET
`
`- 63
`
`_
`
`. 72
`
`_
`
`VAX 6000
`
`IBM AS/400
`
`FIG. 1C
`(PRIOR ART)
`
`61
`
`IBM RS/6000
`
`Cloudflare - Exhibit 1039, page 4
`
`Cloudflare - Exhibit 1039, page 4
`
`

`

`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 4 of 7
`
`US 6,412,000 B1
`
`88
`86
`84
`
`82
`80
`
`FTP Telnet HTTP SNMP RPC
`UDP
`TCP
`
`IP and ICMP
`Ethernet, Token Ring, IEEE 802.3. X25, Serial (SLIP)
`ATM, Frame Relay, CSMA/CD, Packet Switching
`
`LEGEND
`88 Session/Application Layer
`86 Transport Layer
`84 Network Layer
`82 Data Link Layer
`80 Physical Layer
`
`FIG. ID
`(PRIOR ART)
`
`201
`
`..1
`
`202
`
`DEPT A
`INSIDE HOST
`SUBNET A
`
`FTP
`OUTSIDE
`PORT 2.0
`
`y -206
`
`WEB
`
`FTP
`
`WEB
`
`208
`
`210
`
`212
`
`DEPT B
`INSIDE HOST
`SUBNET B
`
`DEFAULT
`
`204
`
`205
`
`FIG. 2A
`
`Cloudflare - Exhibit 1039, page 5
`
`Cloudflare - Exhibit 1039, page 5
`
`

`

`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 5 of 7
`
`US 6,412,000 B1
`
`203
`
`DEPT A
`
`f226
`
`DEPT B
`
`DEPT A
`
`228
`
`230
`
`DEPT B
`
`_z- 232
`
`220
`
`224
`
`225
`
`WEB
`
`TCP
`
`DEFAULT
`
`FIG. 2B
`
`y -304
`
`CLASSIFIER
`
`0
`
`-4
`
`0
`
`KNOWLEDGE
`BASE
`
`306
`
`302
`
`308
`
`TRAFFIC a
`
`TRAFFIC b
`
`TRAFFIC c
`
`CLASS A
`
`CLASS B
`
`CLASS C
`
`FIG. 3
`
`Cloudflare - Exhibit 1039, page 6
`
`Cloudflare - Exhibit 1039, page 6
`
`

`

`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 6 of 7
`
`US 6,412,000 B1
`
`401
`
`PARSE FLOW
`SPECIFICATION
`FROM A PACKET
`OF THE FLOW
`
`__
`
`-- 402
`
`COMPARE FLOW
`SPECIFICATION
`WITH EXISTING
`CLASSIFICATION TREE
`
`, j- -- 404
`
`406
`
`NO
`
`TRAFFIC
`MATCHES A
`CLASS?
`
`YES
`
`CRETURN
`
`y-- 408
`
`f410
`
`412
`
`ENTER INTO A
`SAVED LIST
`CHARACTERISTICS
`OF THE TRAFFIC
`
`SUPPRESS
`DUPLICATES
`
`1
`1
`
`DETERM NE BYTE
`COUNT FOR TRAFFIC
`AND INCLUDE WITH
`TRAFFIC SPECIFICATION
`IN SAVED LIST
`
`i
`CRETURN
`
`FIG. 4A
`
`Cloudflare - Exhibit 1039, page 7
`
`Cloudflare - Exhibit 1039, page 7
`
`

`

`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 7 of 7
`
`US 6,412,000 B1
`
`403
`
`RETRIEVE CLASSIFIED
`TRAFFIC FROM
`SAVED LIST
`
`420
`
`YES
`
`SAVED
`TRAFFIC WELL
`KNOWN?
`
`422
`
`NO
`
`SAVED
`TRAFFIC A SERVER
`AT UNREGISTERED
`IP PORT?
`
`423
`
`NO
`
`YES
`
`426
`
`NO
`
`SAVED
`TRAFFIC BELONGS
`TO A SERVICE
`GGREGAT
`
`425
`
`CREATE NEW
`TRAFFIC CLASS
`FOR SAVED
`TRAFFIC
`
`YES
`
`CREATE TRAFFIC CLASS
`MATCHING ALL
`COMPONENTS OF
`SERVICE AGGREGATE
`
`y-428
`
`NO
`
`TOO
`MANY CLASSES
`
`432
`
`YES
`
`(NO MORE AUTO)
`CLASSIFICATION
`
`FIG. 4B
`
`Cloudflare - Exhibit 1039, page 8
`
`Cloudflare - Exhibit 1039, page 8
`
`

`

`1
`METHOD FOR AUTOMATICALLY
`CLASSIFYING TRAFFIC IN A PACKET
`COMMUNICATIONS NETWORK
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This application claims priority from a commonly owned
`U.S. Provisional Patent Application, Ser. No. 60/066,864,
`filed on Nov. 25 1997, in the name of Guy Riddle and Robert
`L. Packer, entitled "Method for Automatically Classifying
`Traffic in a Policy Based Bandwidth Allocation System."
`The following related commonly -owned
`contemporaneously-filed co-pending U.S. Patent Applica-
`tion is hereby incorporated by reference in its entirety for all
`purposes: U.S. patent application Ser. No. 09/198,051, still
`pending, in the name of Guy Riddle, entitled "Method for
`Automatically Determining a Traffic Policy in a Packet
`Communications Network,".
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`Further, this application makes reference to the following
`commonly owned U.S. Patent Application, which are incor-
`porated by reference herein in their entirety for all purposes:
`U.S. Pat. No. 5,802,106, in the name of Robert L. Packer,
`entitled "Method for Rapid Data Rate Detection in a
`Packet Communication Environment Without Data
`Rate Supervision," relates to a technique for automati-
`cally determining the data rate of a TCP connection;
`U.S. patent application Ser. No. 08/977,376, now U.S.
`Pat. No. 6,046,980, in the name of Robert L. Packer,
`entitled "Method for Managing Flow Bandwidth Uti-
`lization at Network, Transport and Application Layers
`in Store and Forward Network," relates to a technique
`for automatically allocating bandwidth based upon data
`rates of TCP connections according to a hierarchical
`classification paradigm; and.
`U.S. patent application Ser. No. 08/742,994, now U.S.
`Pat. No. 6,038,216 in the name of Robert L. Packer,
`entitled "Method for Explicit Data Rate Control in a
`Packet Communication Environment Without a Data
`Rate Supervision," relates to a technique for automati-
`cally scheduling TCP packets for transmission.
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to digital packet
`telecommunications, and particularly to management of
`network bandwidth based on information ascertainable from
`multiple layers of OSI network model. It is particularly
`useful in conjunction with bandwidth allocation mecha-
`nisms employing traffic classification in a digitally-switched
`packet telecommunications environment, as well as in
`monitoriing, security and routing.
`The ubiquitous TCP/IP protocol suite, which implements
`the world-wide data communication network environment
`called the Internet and is also used in private networks
`(Intranets), intentionally omits explicit supervisory function
`over the rate of data transport over the various media which
`comprise the network. While there are certain perceived
`
`US 6,412,000 B1
`
`10
`
`2
`advantages, this characteristic has the consequence of jux-
`taposing very high-speed packet flows and very low-speed
`packet flows in potential conflict for network resources,
`which results in inefficiencies. Certain pathological loading
`5 conditions can result in instability, overloading and data
`transfer stoppage. Therefore, it is desirable to provide some
`mechanism to optimize efficiency of data transfer while
`minimizing the risk of data loss. Early indication of the rate
`of data flow which can or must be supported is imperative.
`In fact, data flow rate capacity information is a key factor for
`use in resource allocation decisions. For example, if a
`particular path is inadequate to accommodate a high rate of
`data flow, an alternative route can be sought out.
`Internet/Intranet technology is based largely on the TCP/
`15 IP protocol suite, where IP, or Internet Protocol, is the
`network layer protocol and TCP, or Transmission Control
`Protocol, is the transport layer protocol. At the network
`level, IP provides a "datagram"delivery service. By contrast,
`TCP builds a transport level service over the datagram
`20 service to provide guaranteed, sequential delivery of a byte
`stream between two IP hosts.
`TCP flow control mechanisms operate exclusively at the
`end stations to limit the rate at which TCP endpoints emit
`data. However, TCP lacks explicit data rate control. The
`25 basic flow control mechanism is a sliding window, super-
`imposed on a range of bytes beyond the last explicitly-
`acknowledged byte. Its sliding operation limits the amount
`of unacknowledged transmissible data that a TCP endpoint
`can emit.
`30 Another flow control mechanism is a congestion window,
`which is a refinement of the sliding window scheme, which
`employs conservative expansion to fully utilize all of the
`allowable window. A component of this mechanism is
`sometimes referred to as "slow start".
`The sliding window flow control mechanism works in
`conjunction with the Retransmit Timeout Mechanism
`(RTO), which is a timeout to prompt a retransmission of
`unacknowledged data. The timeout length is based on a
`running average of the Round Trip Time (RTT) for acknowl-
`40 edgment receipt, i.e. if an acknowledgment is not received
`within (typically) the smoothed RTT+4*mean deviation,
`then packet loss is inferred and the data pending acknowl-
`edgment is retransmitted.
`Data rate flow control mechanisms which are operative
`45 end-to-end without explicit data rate control draw a strong
`inference of congestion from packet loss (inferred, typically,
`by RTO). TCP end systems, for example, will "back-off",
`i.e., inhibit transmission in increasing multiples of the base
`RTT average as a reaction to consecutive packet loss.
`50 Bandwidth Management in TCP/IP Networks
`Conventional bandwidth management in TCP/IP net-
`works is accomplished by a combination of TCP end sys-
`tems and routers which queue packets and discard packets
`when certain congestion thresholds are exceeded. The
`55 discarded, and therefore unacknowledged, packet serves as
`a feedback mechanism to the TCP transmitter. (TCP end
`systems are clients or servers running the TCP transport
`protocol, typically as part of their operating system.) The
`term "bandwidth management" is often used to refer to link
`60 level bandwidth management, e.g. multiple line support for
`Point to Point Protocol (PPP). Link level bandwidth man-
`agement is essentially the process of keeping track of all
`traffic and deciding whether an additional dial line or ISDN
`channel should be opened or an extraneous one closed. The
`65 field of this invention is concerned with network level
`bandwidth management, i.e. policies to assign available
`bandwidth from a single logical link to network flows.
`
`35
`
`Cloudflare - Exhibit 1039, page 9
`
`Cloudflare - Exhibit 1039, page 9
`
`

`

`US 6,412,000 B1
`
`4
`analyzing real traffic in a customer's network and automati-
`cally producing a list of the "found traffic."
`
`SUMMARY OF THE INVENTION
`
`According to the invention, in a packet communication
`environment, a method is provided for automatically clas-
`sifying packet flows for use in allocating bandwidth
`resources and the like by a rule of assignment of a service
`10 level. The method comprises applying individual instances
`of traffic classification paradigms to packet network flows
`based on selectable information obtained from a plurality of
`layers of a multi-layered communication protocol in order to
`define a characteristic class, then mapping the flow to the
`is defined traffic class. It is useful to note that the automatic
`classification is sufficiently robust to classify a complete
`enumeration of the possible traffic.
`In the present invention network managers need not know
`the technical aspects of each kind of traffic in order to
`20 configure traffic classes and service aggregates bundle traffic
`to provide a convenience to the user, by clarifying process-
`ing and enables the user to obtain group counts of all parts
`comprising a service.
`The invention will be better understood upon reference to
`25 the following detailed description in connection with the
`accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A depicts a representative client server relationship
`in accordance with a particular embodiment of the inven-
`tion;
`FIG. 1B depicts a functional perspective of the represen-
`35 tative client server relationship in accordance with a par-
`ticular embodiment of the invention;
`
`FIG. 1C depicts a representative internetworking envi-
`ronment in accordance with a particular embodiment of the
`invention;
`FIG. 1D depicts a relationship diagram of the layers of the
`TCP/IP protocol suite;
`FIGS. 2A-2B depict representative divisions of band-
`width;
`
`45
`
`FIG. 3 depicts a component diagram of processes and data
`structures in accordance with a particular embodiment of the
`invention; and
`FIGS. 4A-4B depict flowcharts of process steps in auto-
`s° matically classifying traffic in accordance with a particular
`embodiment of the invention.
`
`3
`In a copending U.S. patent application Ser. No. 08/742,
`994, now U.S. Pat. No. 6,038,216, in the name of Robert L.
`Packer, entitled "Method for Explicit Data Rate Control in
`a Packet Communication Environment Without Data Rate
`Supervision," a technique for automatically scheduling TCP 5
`packets for transmission is disclosed. Furthermore, in U.S.
`Pat. No. 5,802,106, in the name of Robert L. Packer, entitled
`"Method for Rapid Data Rate Detection in a Packet Com-
`munication Environment Without Data Rate Supervision," a
`technique for automatically determining the data rate of a
`TCP connection is disclosed. Finally, in a copending U.S.
`Pat. application Ser. No. 08/977,376, now abandoned, in the
`name of Robert L. Packer, entitled "Method for Managing
`Flow Bandwidth Utilization at Network, Transport and
`Application Layers in Store and Forward Network," a tech-
`nique for automatically allocating bandwidth based upon
`data rates of TCP connections according to a hierarchical
`classification paradigm is disclosed.
`Automated tools assist the network manager in configur-
`ing and managing the network equipped with the rate control
`techniques described in these copending applications. In a
`related copending application, a tool is described which
`enables a network manager to automatically produce poli-
`cies for traffic being automatically detected in a network. It
`is described in a copending U.S. patent application Ser. No.
`09/198,051, still pending, in the name of Guy Riddle,
`entitled "Method for Automatically Determining a Traffic
`Policy in a Packet Communications Network", based on
`U.S. Provisional Patent Application Ser. No. 60/066,864.
`The subject of the present invention is also a tool designed 30
`to assist the network manager.
`While these efforts teach methods for solving problems
`associated with scheduling transmissions, automatically
`determining data flow rate on a TCP connection, allocating
`bandwidth based upon a classification of network traffic and
`automatically determining a policy, respectively, there is no
`teaching in the prior art of methods for automatically
`classifying packet traffic based upon information gathered
`from a multiple layers in a multi-layer protocol network.
`Bandwidth has become the expensive commodity of the 40
`'90s, as traffic expands faster than resources, the need to
`"prioritize" a scarce resource, becomes ever more critical.
`One way to solve this is by applying "policies" to control
`traffic classified as to type of service required in order to
`more efficiently match resources with traffic.
`Traffic may be classified by type, e.g. E-mail, web surfing,
`file transfer, at various levels. For example, to classify by
`network paradigm, examining messages for an IEEE source/
`destination service access point (SAP) or a sub-layer access
`protocol (SNAP) yields a very broad indicator, i.e., SNA or
`IP. More specific types exist, such as whether an IP protocol
`field in an IP header indicates TCP or UDP. Well known
`connection ports provide indications at the application layer,
`i.e., SMTP or HTTP.
`Classification is not new. Firewall products like "Check- 55
`Point FireWall-1," a product of CheckPoint Software
`Technologies, Inc., a company with headquarters in Red-
`wood City, Calif., have rules for matching traffic. Bandwidth
`managers such as "Aponet," a product of Aponet, Inc., a
`company with headquarters in San Jose, Calif., classify by
`destination. The PacketShaper, a product of Packeteer, Inc.,
`a company with headquarters in Cupertino, Calif., allows a
`user to manually enter rules to match various traffic types for
`statistical tracking, i.e., counting by transaction, byte count,
`rates, etc. However, manual rule entry requires a level of
`expertise that limits the appeal for such a system to network
`savvy customers. What is really needed is a method for
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`1.0 Introduction
`The present invention provides techniques to automati-
`cally classify a plurality of heterogeneous packets in a
`packet telecommunications system for management of net-
`work bandwidth in systems such as a private area network,
`60 a wide area network or an internetwork. Systems according
`to the present invention enable network managers to: auto-
`matically define traffic classes, for which policies may then
`be created for specifying service levels for the traffic classes
`and isolating bandwidth resources associated with certain
`65 traffic classes. Inbound as well as outbound traffic may be
`managed. Table 1 provides a definitional list of terminology
`used herein.
`
`Cloudflare - Exhibit 1039, page 10
`
`Cloudflare - Exhibit 1039, page 10
`
`

`

`5
`
`TABLE 1
`
`LIST OF DEFINITIONAL TERMS
`
`ADMISSIONS
`CONTROL
`
`EXCEPTION
`
`EXCESS
`INFORMATION
`RATE(EIR)
`FLOW
`
`INSIDE
`
`ISOLATION
`
`OUTSIDE
`
`PARTITION
`POLICY
`POLICY
`INHERITANCE
`
`TRAFFIC
`CLASS
`
`URI
`
`A policy invoked whenever a system according to the
`invention detects that a guaranteed information rate
`cannot be maintained. An admissions control policy is
`analogous to a busy signal in the telephone world.
`CLASS SEARCH A search method based upon traversal of a N-ary tree
`ORDER
`data structure containing classes.
`COMMITTED
`A rate of data flow allocated to reserved service traffic 10
`INFORMATION
`for rate based bandwidth allocation for a committed
`RATE(CIR)
`bandwidth. Also called a guaranteed information rate
`(GIR).
`A class of traffic provided by the user which
`supersedes an automatically determined classification
`order.
`A rate of data flow allocated to reserved service traffic
`for rate based bandwidth allocation for uncommitted
`bandwidth resources.
`A flow is a single instance of a traffic class. For
`example, all packets in a TCP connection belong to the
`same flow. As do all packets in a UDP session.
`GUARANTEED A rate of data flow allocated to reserved service traffic
`INFORMATION
`for rate based bandwidth allocation for a committed
`RATE (GIR)
`bandwidth. Also called a committed information rate
`(CIR).
`On the system side of an access link. Outside clients
`and servers are on the other side of the access link.
`Isolation is the degree that bandwidth resources are
`allocable to traffic classes.
`On the opposite side of an access link as viewed from
`the perspective of the system on which the software
`resides.
`Partition is an arbitrary unit of network resources.
`A rule for the assignment of a service level to a flow.
`A method for assigning policies to flows for which no
`policy exists in a hierarchical arrangement of policies.
`For example, if a flow is determined to be comprised
`of FTP packets for Host A, and no corresponding
`policy exists, a policy associated with a parent node,
`such as an FTP policy, may be located and used.
`POLICY BASED An adjustment of a requested data rate for a particular
`SCALING
`flow based upon the policy associated with the flow
`and information about the flow's potential rate.
`SCALED RATE Assignment of a data rate based upon detected speed.
`SERVICE
`A service paradigm having a combination of
`LEVEL
`characteristics defined by a network manager to handle
`a particular class of traffic. Service levels may be
`designated as either reserved or unreserved.
`All traffic between a client and a server endpoints. A
`single instance of a traffic class is called a flow.
`Traffic classes have properties or class attributes such
`as, directionality, which is the property of traffic to be
`flowing inbound or outbound;
`UNRESERVED Unreserved service is a service level defined in terms
`SERVICE
`of priority in which no reservation of bandwidth is
`made.
`A Universal Resource Identifier is the name of the
`location field in a web reference address. It is also
`called a URL or Universal Resource Locator
`
`US 6,412,000 B1
`
`5
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`6
`The hardware configurations are in general standard and
`will be described only briefly. In accordance with known
`practice, server 20 includes one or more processors 30 which
`communicate with a number of peripheral devices via a bus
`subsystem 32. These peripheral devices typically include a
`storage subsystem 35, comprised of a memory subsystem
`35a and a file storage subsystem 35b holding computer
`programs (e.g., code or instructions) and data, a set of user
`interface input and output devices 37, and an interface to
`outside networks, which may employ Ethernet, Token Ring,
`ATM, IEEE 802.3, ITU X.25, Serial Link Internet Protocol
`(SLIP) or the public switched telephone network. This
`interface is shown schematically as a "Network Interface"
`block 40. It is coupled to corresponding interface devices in
`client computers via a network connection 45.
`Client 25 has the same general configuration, although
`typically with less storage and processing capability. Thus,
`while the client computer could be a terminal or a low-end
`personal computer, the server computer is generally a high-
`end workstation or mainframe, such as a SUN SPARC
`server. Corresponding elements and subsystems in the client
`computer are shown with corresponding, but primed, refer-
`ence numerals.
`Bus subsystem 32 is shown schematically as a single bus,
`but a typical system has a number of buses such as a local
`bus and one or more expansion buses (e.g., ADB, SCSI, ISA,
`EISA, MCA, NuBus, or PCI), as well as serial and parallel
`ports. Network connections are usually established through
`a device such as a network adapter on one of these expansion
`buses or a modem on a serial port. The client computer may
`be a desktop system or a portable system.
`The user interacts with the system using interface devices
`37' (or devices 37 in a standalone system). For example,
`client queries are entered via a keyboard, communicated to
`client processor 30', and thence to modem or network
`interface 40' over bus subsystem 32'. The query is then
`communicated to server 20 via network connection 45.
`Similarly, results of the query are communicated from the
`server to the client via network connection 45 for output on
`one of devices 37' (say a display or a printer), or may be
`stored on storage subsystem 35'.
`FIG. 1B is a functional diagram of a computer system
`such as that of FIG. 1A. FIG. 1B depicts a server 20, and a
`representative client 25 of a plurality of clients which may
`interact with the server 20 via the Internet 45 or any other
`communications method. Blocks to the right of the server
`are indicative of the processing steps and functions which
`occur in the server's program and data storage indicated by
`blocks 35a and 35b in FIG. 1A. A TCP/IP "stack" 44 works
`in conjunction with Operating System 42 to communicate
`with processes over a network or serial connection attaching
`Server 20 to Internet 45. Web server software 46 executes
`concurrently and cooperatively with other processes in
`server 20 to make data objects 50 and 51 available to
`requesting clients. A Common Gateway Interface (CGI)
`script 55 enables information from user clients to be acted
`upon by web server 46, or other processes within server 20.
`Responses to client queries may be returned to the clients in
`the form of a Hypertext Markup Language (HTML) docu-
`ment outputs which are then communicated via Internet 45
`back to the user.
`Client 25 in FIG. 1B possesses software implementing
`functional processes operatively disposed in its program and
`data storage as indicated by block 35a' in FIG. 1A. TCP/IP
`stack 44', works in conjunction with Operating System 42' to
`communicate with processes over a network or serial con-
`
`Cloudflare - Exhibit 1039, page 11
`
`1.1 Hardware Overview
`The method for automatically classifying heterogeneous
`packets in a packet telecommunications environment of the
`present invention is implemented in the C programming
`language and is operational on a computer system such as
`shown in FIG. 1A. This invention may be implemented in a
`client-server environment, but a client-server environment is
`not essential. This figure shows a conventional client-server
`computer system which includes a server 20 and numerous
`clients, one of which is shown as client 25. The use of the
`term "server" is used in the context of the invention, wherein
`the server receives queries from (typically remote) clients,
`does substantially all the processing necessary to formulate
`responses to the queries, and provides these responses to the
`clients. However, server 20 may itself act in the capacity of
`a client when it accesses remote databases located at another
`node acting as a database server.
`
`55
`
`60
`
`65
`
`Cloudflare - Exhibit 1039, page 11
`
`

`

`US 6,412,000 B1
`
`25
`
`7
`nection attaching Client 25 to Internet 45. Software imple-
`menting the function of a web browser 46'executes concur-
`rently and cooperatively with other processes in client 25 to
`make requests of server 20 for data objects 50 and 51. The
`user of the client may interact via the web browser 46' to
`make such queries of the server 20 via Internet 45 and to
`view responses from the server 20 via Internet 45 on the web
`browser 46'.
`Network Overview
`FIG. 1C is illustrative of the internetworking of a plurality 10
`of clients such as client 25 of FIGS. 1A and 1B and a
`plurality of servers such as server 20 of FIGS. 1A and 1B as
`described herein above. In FIG. 1C, network 60 is an
`example of a Token Ring or frame oriented network. Net-
`work 60 links host 61, such as an IBM RS6000 RISC
`workstation, which may be running the AIX operating
`system, to host 62, which is a personal computer, which may
`be running Windows 95, IBM OS/2 or a DOS operating
`system, and host 63, which may be an IBM AS/400
`computer, which may be running the OS/400 operating 20
`system. Network 60 is internetworked to network 70 via a
`system gateway which is depicted here as router 75, but
`which may also be a gateway having a firewall or a network
`bridge. Network 70 is an example of an Ethernet network
`that interconnects host 71, which is a SPARC workstation,
`which may be running SUNOS operating system with host
`72, which may be a Digital Equipment VAX6000 computer
`which may be running the VMS operating system.
`Router 75 is a network access point (NAP) of network 70
`and network 60. Router 75 employs a Token Ring adapter
`and Ethernet adapter. This enables router 75 to interface with
`the two heterogeneous networks. Router 75 is also aware of
`the Inter-network Protocols, such as ICMP and RIP, which
`are described herein below.
`FIG. 1D is illustrative of the constituents of the Trans-
`mission Control Protocol/Internet Protocol (TCP/IP) proto-
`col suite. The base layer of the TCP/IP protocol suite is the
`physical layer 80, which defines the mechanical, electrical,
`functional and procedural standards for the physical trans-
`mission of data over communications media, such as, for
`example, the network connection 45 of FIG. 1A. The
`physical layer may comprise electrical, mechanical or func-
`tional standards such as whether a network is packet switch-
`ing or frame-switching; or whether a network is based on a
`Carrier Sense Multiple Access/Collision Detection (CSMA/
`CD) or a frame relay paradigm.
`Overlying the physical layer is the data link layer 82. The
`data link layer provides the function and protocols to trans-
`fer data between network resources and to detect errors that
`may occur at the physical layer. Operating modes at the
`datalink layer comprise such standardized network topolo-
`gies as IEEE 802.3 Ethernet, IEEE 802.5 Token Ring, ITU
`X.25, or serial (SLIP) protocols.
`Network layer protocols 84 overlay the datalink layer and
`provide the means for establishing connections between
`networks. The standards of network layer protocols provide
`operational control procedures for internetworking commu-
`nications and routing information through multiple heterog-
`enous networks. Examples of network layer protocols are
`the Internet Protocol (IP) and the Internet Control Message
`Protocol (ICMP). The Address Resolution Protocol (ARP) is
`used to correlate an Internet address and a Media Access
`Address (MAC) for a particular host. The Routing Informa-
`tion Protocol (RIP) is a dynamic routing protocol for passing
`routing information between hosts on networks. The Internet
`Control Message Protocol (ICMP) is an internal protocol for
`passing control messages between hosts on various net-
`
`8
`works. ICMP messages provide feedback about events in the
`network environment or can help determine if a path exists
`to a particular host in the network environment. The latter is
`called a "Ping". The Internet Protocol (