(12) Unlted States Patent
`(10) Patent N0.:
`US 6,412,000 B1
`
`Riddle et al.
`(45) Date of Patent:
`Jun. 25, 2002
`
`U5006412000B1
`
`(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)
`
`........ 709/226
`2/1996 Waclawsky et a1.
`5,495,426 A *
`.......... 709/224
`5,838,919 A * 11/1998 Schwaller et a1.
`5,870,561 A *
`2/1999 Jawis et a1.
`................ 709/238
`..
`5,903,559 A *
`5/1999 Acharya et al.
`709/236
`
`7/1999 Venkatraman .......
`5,923,849 A *
`709/224
`2/2000 Chapman et al.
`6,028,842 A *
`370/252
`
`............
`6,046,980 A *
`4/2000 Packer
`370/230
`
`709/238
`6,137,782 A * 10/2000 Sharon et a1.
`6,209,033 B1 *
`3/2001 Datta et al.
`................. 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
`.
`Flled3
`
`NOV- 23: 1998
`
`(22)
`
`Related US. Application Data
`Provisional application No. 60/066,864, filed on NOV. 25,
`1997.
`
`(60)
`
`G06F 15/173
`Int (:17
`(51)
`iiiiiiiiiiiiiiiiiiiiii709/224709/223. 709/230.
`(52) US Cl
`'
`' 709/238709/242 370/230f 370035? 370/252f
`’
`’
`’ 370/355’. 370/356
`.
`(58) Field of Search ................................. 709/223—226
`709/230 235—236 238—239 242 246?
`370/2291230 235’ 252_253’ 355,—356,
`’
`’
`401’ 466—469
`’
`
`(56)
`
`References Cited
`US. PATENT DOCUMENTS
`
`Primary Examiner—Zarni Maung
`Assistant Examiner—Bharat Barot
`(74) Attorney, Agent, or Firm—Townsend and Townsend
`d C
`LLP; K
`th R. All
`enne
`
`rew
`
`an
`(57)
`
`en
`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 0 tra
`c c a551 cation ara 1 ms to
`ac et net-
`.
`f
`ffi
`1
`.fi
`.
`P
`dig
`P k
`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
`
`
`PARSE FLOW
`SPECIFICATION
`FROM A PACKET
`OF THE FLOW
`
`COM PARE FLOW
`SPECIFICATION
`WITH EXISTING
`CLASSIFICATION TREE
`
`
`
`
`/402
`
`/404
`
`
`
`
`SAVED
`’
`
`7
`TRAFFIC BELONGS
`TO A SERVICE
`
`GGREGAT
`7
`
`
`425‘
`y
`'
`CREATE NEW
`
`
`FOR SAVED
`CREATE TRAFFIC CLASS
`TRAFFIC CLASS
`
`
`TRAFFIC
`MATCHING ALL
`COMPONENTS OF
`SERVICE AGGREGATE
`
`401
`
`\L
`
`
`
`
`
`406
`
`YES
`
`ENTER INTO A
`SAVED LIST
`CHARACTERISTICS
`OF THE TRAFFIC
`
`/408
`
`
`DUPLICATES
`
`
`DETERMINE BYTE
`COUNT FOR TRAFFIC
`AND INCLUDE WITH
`TRAFFIC SPECIFICATION ‘
`IN SAVED LIST
`
`5
`
`RETURN
`
`
`
`
`
`403
`
`3..
`Li. L, 117— j
`TRAFFIC FROM
`RETRIEVE CLASSIFIED / 420
`
`SAVED LIST
`
`
`
`SAVED
`TRAFFIC A SERVER
`AT UNREOISTERED
`IP PORT?
`
`/428
`
`
`
`//432
`
`TOO
`MANY CLASSES
`7
`
`YES
`
`NO MORE AUTO
`CLASSIFICATION
`
`
`
`
`
`EX 1008 Page 1
`EX 1008 Page 1
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 1 0f 7
`
`US 6,412,000 B1
`
`
`
`SERVER
`
`_a
`
`
`
`NETWORKIF
`
`NETWORKIF
`
`37'
`
`
`FIG.1A(PRIORART)
`
`
`
`OOOOOOOO
`
`
`
`OOOOOO0
`
`0000000
`
`
`
`
`
`
`
`
`30
`
`EX 1008 Page 2
`EX 1008 Page 2
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 2 0f 7
`
`US 6,412,000 B1
`
`
`
`p
`__
`
`<
`
`SERVER
`
`25
`
`I-r'r‘l—r-r'l—l—r’r—r—l—r—V—r‘r‘ —'
`rrrrrrrrrrrrrrrr
`rrrrrrrrrrrrrrrr
`
`.,
`'
`
`CLIENT
`
`<
`
`
`
`,_,_,_,_.__—_r_'_'_ WEB
`
`CGI
`
`WEB
`SERVER
`
`OPERATING
`SYSTEM
`
`TCP/IP
`
`55
`
`46
`
`4
`
`2
`
`44
`
`DATA OBJECT
`1
`
`50
`
`DATA OBJECT
`N
`
`51
`
`QUERY
`FROM USER l
`
`T
`
`HTML OUTPUT
`TO USER
`
`45
`
`44'
`
`42'
`
`46
`
`TCP/IP
`
`OPERAT'NG
`SYSTEM
`
`BROWSER
`
`FIG. 1B
`(PRIOR ART)
`
`EX 1008 Page 3
`EX 1008 Page 3
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 3 0f 7
`
`US 6,412,000 B1
`
`
`
`
`
`ROUTER
`
`VAX6000
`
`FIG.1C(PRIORART)
`
`Illlllllllllllllll
`
`
`IBMCOMPATIBILE
`
`IBMAS/4OO
`
`
`IBMRS/6000
`
`EX 1008 Page 4
`EX 1008 Page 4
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 4 0f 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. 1 D
`
`(PRIOR ART)
`
`202
`
`
`
`DEPT A
`INSIDE HOST
`
`
`
`SUBNET A
`
`
`
`
`FTP
`OUTSIDE
`PORT 2.0
`
`WEB
`
`I201
`
`205
`
`208
`
`204
`
` DEPT B
`INSIDE HOST
`
`SUBNET B
`
`
`
`
`205
`
`DEFAULT
`
`FIG. 2A
`
`
`
`210n
`
`WEB
`
`212
`
`EX 1008 Page 5
`EX 1008 Page 5
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 5 0f 7
`
`US 6,412,000 B1
`
`220
`
`
`
`DEPT A
`
`DEPT B
`
`
`
`
`
`DEFAULT
`
`DEPT B
`
`203
`
`5
`
`226
`
`228
`
`232
`
`FIG. 28
`
`|:> CLASSlFIER
`
`304
`
`
`
`KNOWLEDGE
`BASE
`
`O—-—->
`+4.)
`
`302
`
`1
`
`CLASS A
`
`
`iii/3
`
`CLASS B
`
`CLASS C
`
`FIG. 3
`
`TRAFFIC a
`
`TRAFFIC b
`
`
`
`
`
`
`
`308
`
`
`
`
`
`
`
`EX 1008 Page 6
`EX 1008 Page 6
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 6 0f 7
`
`US 6,412,000 B1
`
`401
`
`I
` PARSE FLOW
`
` 402
`SPECIFICATION
`
`FROM A PACKET
`OF THE FLOW
`
`
`
`
` COMPARE FLOW
`
` 404
`SPECIFICATION
`WITH EXISTING
`CLASSIFICATION TREE
`
`
`
`
` RETURN
`
`
`
`TRAFFI
`MATCHES A
`
`CLASS?
`
`
`
`
` ENTER INTO A
` 408
`SAVED LIST
`
`CHARACTERISTICS
`OF THE TRAFFIC
`
`SUPPRESS
`DUPLICATES
`
`3/410
`
`DETERMINE BYTE
`COUNT FOR TRAFFIC
`AND INCLUDE WITH
`TRAFFIC SPECIFICATION
`IN SAVED LIST
`
`‘
`
`=
`
`412
`
`2/
`
`=
`
`
`
`
`
`RETURN
`
`
`
`FIG. 4A
`
`EX 1008 Page 7
`EX 1008 Page 7
`
`

`

`US. Patent
`
`Jun. 25, 2002
`
`Sheet 7 0f 7
`
`US 6,412,000 B1
`
` 403
`
`
`
`RETRIEVE CLASSIFIED
`TRAFFIC FROM
`SAVED LIST
`
`420
`
`YES
`
`
`TRAFFIC WELL
`
`
`KNOWN?
`
`
`NO
`
`SAVED r
`TRAFFIC A SERVER
`AT UNREGISTERED
`IP PORT?
`
`423
`
`NO
`
`YES
`
`
`
`NO
`
`
`
`TRAFFIC BELONGS
`TO A SERVICE
`GGREGAT
`7
`
`YES
`
`425
`
`CREATE NEW
`TRAFFIC CLASS
`FOR SAVED
`
`TRAFFIC
`
`CREATE TRAFFIC CLASS
`MATCHING ALL
`COMPONENTS OF
`SERVICE AGGREGATE
`
`
`
`
`NO
`
`
`TOO
`
`MANY CLASSES
`?
`
`
`
`432
`
`
`
`YES
`
`NO MORE AUTO
`CLASSIFICATION
`
`FIG. 4B
`
`428
`
`EX 1008 Page 8
`EX 1008 Page 8
`
`

`

`US 6,412,000 B1
`
`1
`METHOD FOR AUTOMATICALLY
`CLASSIFYING TRAFFIC IN A PACKET
`COMMUNICATIONS NETWORK
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`This application claims priority from a commonly owned
`US. 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 US. Patent Applica-
`tion is hereby incorporated by reference in its entirety for all
`purposes: US. 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 US. Patent Application, which are incor-
`porated by reference herein in their entirety for all purposes:
`US. 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;
`US. patent application Ser. No. 08/977,376, now US.
`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 Networ ,” relates to a technique
`for automatically allocating bandwidth based upon data
`rates of TCP connections according to a hierarchical
`classification paradigm; and.
`US. patent application Ser. No. 08/742,994, now US.
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`p acket
`invention relates to digital
`This
`telecommunications, and particularly to management of
`network bandwidth based on information ascertainable from
`
`55
`
`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
`
`60
`
`65
`
`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
`
`i.e. policies to assign available
`bandwidth management,
`bandwidth from a single logical link to network flows.
`
`EX 1008 Page 9
`EX 1008 Page 9
`
`

`

`US 6,412,000 B1
`
`3
`In a copending US. patent application Ser. No. 08/742,
`994, now US. 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 US.
`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 US.
`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 US. 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 Networ ”, based on
`US. 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
`
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`FIGS. 4A—4B depict flowcharts of process steps in auto-
`matically classifying traffic in accordance with a particular
`embodiment of the invention.
`
`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
`
`55
`
`60
`
`65
`
`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.
`
`EX 1008 Page 10
`EX 1008 Page 10
`
`

`

`US 6,412,000 B1
`
`5
`
`TABLE 1
`
`LIST OF DEFINITIONAL TERMS
`
`ADMISSIONS
`CONTROL
`
`EXCEPTION
`
`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.
`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 Hos 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 po icy associated with the flow
`and information about tie 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 tra.:c. Service levels may be
`designated as either reserved or unreserved.
`All traffic between a client and a server endpoints. A
`single instance of a tra::c class is called a flow.
`Traffic classes have pro 3erties or class attributes such
`as, directionality, which is the property of traffic to be
`flowing inbound or outbound;
`Unreserved service is a service level defined in terms
`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
`
`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 X25, 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. ATCP/IP “stac ” 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-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`EX 1008 Page 11
`EX 1008 Page 11
`
`INSIDE
`
`ISOLATION
`
`OUTSIDE
`
`PARTITION
`POLICY
`POLICY
`INHERITANCE
`
`TRAFFIC
`CLASS
`
`UNRESERVED
`SERVICE
`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.
`
`

`

`US 6,412,000 B1
`
`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 08/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/
`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-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`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 applications and utilities, a few of which are
`illustrated here. For example, File Transfer Protocol (FTP) is
`a standard TCP/IP protocol for transferring files from one
`machine to another. FTP clients establish sessions through
`TCP connections with FTP servers in order to obtain files.
`
`Telnet is a standard TCP/IP protocol for remote terminal
`connection. A Telnet client acts as a terminal emulator and
`
`establishes a connection using TCP as the transport mecha-
`nism with a Telnet server. The Simple Network Management
`Protocol (SNMP) is a standard for managing TCP/IP net-
`works. SNMP task