`Riddle et al.
`
`USOO641200OB1
`(10) Patent No.:
`US 6,412,000 B1
`(45) Date of Patent:
`Jun. 25, 2002
`
`(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)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`(21) Appl. No.: 09/198,090
`(22) Filed:
`Nov. 23, 1998
`Related U.S. Application Data
`(60) Provisional application No. 60/066,864, filed on Nov. 25,
`1997.
`(51) Int. Cl."
`G06F 15/173
`
`5,495.426 A * 2/1996 Waclawsky et al. ........ 709/226
`5,838,919 A * 11/1998 Schwaller et al. .......... 709/224
`5,870,561. A * 2/1999 Jarvis et al. ................ 709/238
`5,903.559 A * 5/1999 Acharya et al. ............ 709/236
`5,923,849 A * 7/1999 Venkatraman .............. 709/224
`6,028,842 A * 2/2000 Chapman et al. ........... 370/252
`6,046,980 A
`4/2000 Packer ....................... 370/230
`6,137,782 A * 10/2000 Sharon et al. .............. 709/238
`6,209,033 B1 * 3/2001 Datta et al. ................. 709/224
`
`* cited by examiner
`
`Primary Examiner Zarni Maung
`ASSistant Examiner Bharat Barot
`(74) Attorney, Agent, or Firm Townsend and Townsend
`d Crew LLP, Kenneth R. All
`C
`CW
`CC
`C
`(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.
`
`(52) US C - - - - - - - - - - - - - - - - - - - - - - - - -709.224,709/223; 709/230;
`
`O
`
`709:23s. 709/242. 3701230. 370/23 5. 3701252.
`s
`s
`s 370/355. 370,356
`(58) Field of Search
`709223-226
`709230 235 236.23s239.242.246.
`370229. 230 235 252-253. 355.356.
`s
`s
`401 466 469
`s
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,251,152 A * 10/1993 Notess ....................... 709/224
`
`15 Claims, 7 Drawing Sheets
`
`401
`
`l,
`
`PARSE FLOW
`SPECIFICATION
`FROMA PACKET
`OF THE FLOW
`
`-402
`
`COMPARE FLOW
`SPECIFICAON
`WITH EXISTING
`CLASSIFICAONREE
`
`
`
`406
`
`RETURN
`
`YES
`
`ENTERNTO A
`SAWEDLIS
`CHARACTERISTICS
`OF THE TRAFFIC
`
`- 408
`
`...axama.......maa-..........:-
`SPRESS
`OJPICAES
`
`DETERMINEBYTE
`COUNT FORTRAFFEC
`AND INCLUDE WITH
`TRAFFIC SPECIFICATION
`NSAVEDLIST
`
`RETURN
`
`MM -
`
`43
`--- ------ ,
`
`RETRIEVE CLASSIFIED
`TRAFFIC FROM
`SAWEDEIST
`
`- 420
`
`
`
`
`
`
`
`
`
`-- 422
`
`SAWE)
`TRAFFICWEL
`KNOWN
`
`NO
`
`SAWED
`TRAFFIC ASERVER
`ATUNREGISTERED
`PORT
`
`
`
`
`
`
`
`
`
`- 426
`SAVED Y{
`RAFFICBELONGS
`TO ASERVICE
`taCSGREGA
`
`425-.
`CRAt NW
`TRAFFIC CLASS
`FORSAWED
`TRAFFIC
`
`
`
`YES
`
`CREATE TRAFFIC CASS
`MATCHENG ALL
`COMPONNTS OF
`SERVICEAGGREGATE
`
`-428
`
`--432
`
`TOO
`MANY CLASSES
`
`YES
`
`
`
`NOMORE AUTO
`CLASSIFICATION
`
`Splunk Inc. Exhibit 1039 Page 1
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 1 of 7
`
`US 6,412,000 B1
`
`
`
`:
`
`,
`
`
`
`
`
`O CO. O. O. O. O
`
`O O. O. O. O. O. O.
`
`O
`O
`O
`O
`O
`O
`O
`
`Splunk Inc. Exhibit 1039 Page 2
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 2 of 7
`
`US 6,412,000 B1
`
`SERVER
`
`5 5
`
`CG
`
`WEB
`SERVER
`
`OPERATING 42
`SYSTEM
`
`TCP/IP
`
`4 4
`
`DATA OBJECT/ -50
`1
`
`DATA OBJECT1 - 51
`N
`
`Fr8, SER
`
`HTML OUTPUT
`TO USER
`
`45
`
`25
`
`---------------- rea
`-----------r-r- - - -
`----------------
`----------
`
`
`
`CLENT
`
`.
`
`44'
`
`TCP/IP
`
`OPERATING 42
`SYSTEM
`
`WEB
`BROWSER
`
`46
`
`FIG. 1B
`(PRIOR ART)
`
`Splunk Inc. Exhibit 1039 Page 3
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 3 of 7
`
`US 6,412,000 B1
`
`
`
`
`
`s
`
`i
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1039 Page 4
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 4 of 7
`
`US 6,412,000 B1
`
`
`
`
`
`
`
`LEGEND
`88 Session/Application Layer
`86 Transport Layer
`84 Network Layer
`82 Data Link Layer
`80 Physical Layer
`
`FIG 1D
`(PRIOR ART)
`
`o
`
`2O6
`
`
`
`FTP
`OUTSIDE
`PORT 2.0
`
`WEB
`
`FTP
`
`WEB
`
`208
`
`21 O
`
`212
`
`
`
`
`
`
`
`
`
`
`2O2
`
`DEPTA
`NSIDE HOST
`SUBNET A
`
`204
`
`
`
`205
`
`DEPT B
`INSIDE HOST
`SUBNET B
`
`DEFAULT
`
`FIG. 2A
`
`Splunk Inc. Exhibit 1039 Page 5
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 5 of 7
`
`US 6,412,000 B1
`
`FIG. 2B
`
`) CLASSIFIER
`
`304
`
`302
`
`LASS A
`
`C-b-
`--O
`
`\
`
`
`
`
`
`
`
`
`
`
`
`306
`
`KNOWLEDGE
`BASE
`
`TRAFFIca
`
`TRAFFIC b
`
`TRAFFIC C
`
`
`
`"
`
`FIG. 3
`
`Splunk Inc. Exhibit 1039 Page 6
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 6 of 7
`
`US 6,412,000 B1
`
`401
`
`l,
`
`
`
`
`
`
`
`
`
`RETURN
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PARSE FLOW
`SPECIFICATION
`FROMA PACKET
`OF THE FLOW
`
`COMPARE FLOW
`SPECIFICATION
`WITH EXISTING
`CLASSIFICATION TREE
`
`
`
`
`
`402
`
`404
`
`TRAFFIC
`MATCHES A
`CLASS2
`
`ENTER INTO A
`SAVED LIST
`CHARACTERISTICS
`OF THE TRAFFIC
`
`
`
`408
`
`SUPPRESS
`DUPLICATES
`
`DETERMINE BYTE
`COUNT FORTRAFFIC
`AND INCLUDE WITH
`TRAFFIC SPECIFICATION
`IN SAVED LIST
`
`
`
`-410
`
`-412
`/
`
`:
`
`:
`
`RETURN
`
`FIG. 4A
`
`Splunk Inc. Exhibit 1039 Page 7
`
`
`
`U.S. Patent
`
`Jun. 25, 2002
`
`Sheet 7 of 7
`
`US 6,412,000 B1
`
`403
`
`RETRIEVE CLASSIFIED
`TRAFFC FROM
`SAVEDLIST
`
`42O
`
`YES
`
`TRAFFIC WELL
`KNOWNP
`
`NO
`
`423
`SAVEDS
`TRAFFIC ASERVER
`A UNREGISTERED
`P PORT2
`
`NO
`
`YES
`
`
`
`NO
`
`
`
`TRAFFIC BELONGS
`TO ASERVICE
`AGGREGAT
`
`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
`
`FIG. 4B
`
`Splunk Inc. Exhibit 1039 Page 8
`
`
`
`US 6,412,000 B1
`
`1
`METHOD FOR AUTOMATICALLY
`CLASSIFYING TRAFFIC IN A PACKET
`COMMUNICATIONS NETWORK
`
`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
`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/
`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
`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
`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.
`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
`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
`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.
`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
`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
`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
`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.
`
`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 relate S 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
`monitoring, 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
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Splunk Inc. Exhibit 1039 Page 9
`
`
`
`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
`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
`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
`’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
`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
`
`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
`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
`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
`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
`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
`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;
`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
`matically classifying traffic in accordance with a particular
`embodiment of the invention.
`
`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,
`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
`traffic classes. Inbound as well as outbound traffic may be
`managed. Table 1 provides a definitional list of terminology
`used herein.
`
`US 6,412,000 B1
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Splunk Inc. Exhibit 1039 Page 10
`
`
`
`US 6,412,000 B1
`
`S
`
`TABLE 1.
`
`LIST OF DEFINITIONAL TERMS
`
`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. A. ATCP/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
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`ADMISSIONS
`CONTROL
`
`EXCEPTION
`
`INSIDE
`
`ISOLATION
`
`OUTSIDE
`
`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
`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
`EXCESS
`INFORMATION for rate based bandwidth allocation for uncommitted
`RATE(EIR)
`bandwidth resources.
`FLOW
`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.
`PARTITION
`A rule for the assignment of a service level to a flow.
`POLICY
`A method for assigning policies to flows for which no
`POLICY
`INHERITANCE 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.
`A service paradigm having a combination of
`SERVICE
`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
`
`TRAFFIC
`CLASS
`
`URI
`
`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.
`
`Splunk Inc. Exhibit 1039 Page 11
`
`
`
`US 6,412,000 B1
`
`15
`
`35
`
`40
`
`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
`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
`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/
`45
`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
`
`50
`
`55
`
`60
`
`65
`
`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 (IP) provides the basic
`mechanism for routing packets of information in the Inter
`net. IP is a non-reliable communication protocol. It provides
`a “best efforts' delivery service and does not commit net
`work resources to a particular transaction, nor does it
`perform retransmissions or give acknowledgments.
`The transport layer protocols 86 provide end-to-end trans
`port Services acroSS multiple heterogenous networks. The
`User Datagram Protocol (UDP) provides a connectionless,
`datagram oriented Service which provides a non-reliable
`delivery mechanism for streams of information. The Trans
`mission Control Protocol (TCP) provides a reliable session
`based Service for delivery of Sequenced packets of informa
`tion across the Internet. TCP provides a connection oriented
`reliable mechanism for information delivery.
`The session, or application layer 88 provides a list of
`network applicatio