US 6,591,299 132
`(10) Patent N0.:
`(12) United States Patent
`Riddle et al. *Jul. 8, 2003 (:45) Date of Patent:
`
`
`
`USOO6591299B2
`
`5,495,426 A
`5,539,659 A *
`5,781,726 A *
`5,838,919 A
`5,870,561 A
`5,903,559 A
`5,923,849 A
`6,028,842 A
`6,046,980 A
`6,092,115 A *
`6,137,782 A
`6,205,121 Bl *
`6,209,033 B1
`6,262,976 B1 *
`6,263,368 B1 *
`6,412,000 B1 *
`6,457,051 B1 *
`
`2/1996 Waclawsky et a1.
`7/1996 McKee et al.
`.............. 709/224
`7/1998 Pereira ....................... 709/200
`11/1998 Schwaller et a1.
`2/1999 Jarvis et a1.
`5/1999 Acharya et a1.
`7/1999 Venkatraman
`2/2000 Chapman et al.
`4/2000 Packer
`7/2000 Choudhury et a1.
`10/2000 Sharon et a1.
`3/2001 Heuer
`........................ 370/250
`3/2001 Datta et a1.
`7/2001 McNamara ................. 709/220
`7/2001 Martin ............. 709/224
`
`..... 709/224
`6/2002 Riddle et a1.
`
`............... 709/224
`9/2002 Riddle et a1.
`
`........ 709/235
`
`* cited by examiner
`
`Primary Examiner—Bharat Barot
`(74) Attorney, Agent, or Firm—Townsend and Townsend
`and Crew LLP; Kenneth R. Allen
`
`(57)
`
`ABSTRACT
`
`.
`.
`.
`.
`In packet commumcatlon, a method tor automat1cally clas-
`sifying PaCket
`flOWS for use in allocating bandwidth
`resources and the like by a rule of assignment of a service
`level. By rendering discoverable the attributes of a flow
`specification for packet flows, a finer grained hierarchy of
`classification is provided automatically that
`is based on
`information which is specific to the type of program or
`application supported by the flow and thus allowing greater
`flexibility in control over different flows Within the same
`application. 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 to define a characteristic class;
`then
`mapping the flow to the defined traffic class. The flow
`specification is provided with some application-specific
`attributes; some of Which are discoverable. The discoverable
`
`attributes lead to an ability to automatically create sub-nodes
`of nodes for finer-grained control.
`
`17 Claims, 7 Drawing Sheets
`
`
`
`
`
`
`(54) METHOD FOR AUTOMATICALLY
`CLASSIFYING TRAFFIC WITH ENHANCED
`HIERARCHY IN A PACKET
`COMMUNICATIONS NETWORK
`
`(75)
`
`Inventors: Guy Riddle; L05 Gatos, CA (US);
`Robert L. Packer, Rancho Santa Fe;
`CA (Us); Mark Hill, L05 Alma CA
`(US)
`
`.
`.
`(73) Asslgneei Packeteer, 1110-, Clipertlno, 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.
`
`This patent is subject to a terminal dis—
`claimer.
`
`(21) Appl. No.: 10/155,936
`
`(22)
`(65)
`
`Filed:
`
`May 24a 2002
`Prior Publication Data
`US 2002/0143939 A1 Oct. 3, 2002
`
`Related US. Application Data
`
`(63)
`
`(60)
`
`Continuation—in—part of application No. 09/990,354, filed on
`Nov. 23, 2001, now Pat. No. 6,457,051, which is a continu—
`athHOIaPPhC'dLIOHNQ09/198>090:fi16d0HN0V~239 1998;
`now .Pfit’ NO’ 6’212’900’
`,
`Pr0v151onal application No 60/066 864 filed on Nov 25
`1997.
`
`Int. (:1.7 .............................................. G06F 15/173
`(51)
`(52) US. Cl.
`....................... 709/224; 709/223; 709/230;
`709/234; 709/238; 709/242; 370/230; 370/235;
`370/252; 370/351; 370/355; 370/356
`(58) Field of Search ......................... 709/200, 220—226,
`709/230, 232, 234—236; 238—239; 242,
`245—246; 370/224232, 235_237, 252_255,
`351—356
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,251,152 A
`
`10/1993 Notess
`
`
`
`:Eégtrlgp‘pg,
`SD
`n N
`
`/ “’2
`rm:
`
`
`
`/'
`
`cmmrsxisncs
`‘
`ormaTRAFFIC
`p
`‘
`1 l
`1
`fi—l
`
`
`
`
`
`
`
`
`
`
`
`0
`
`YES
`
`1
`
`2%?XEFE’WS‘
`TRAFHCWELLW...
`m
`5‘
`mmmsma
`w my
`@mcasmm N
`,
`y
`Km
`save;
`"v5
`RAFFIC BELON§
`TO Asswvxce
`
`7
`
`.
`m 4
`no
`4,,
`came “was
`war,»
`camsmums
`man: 92w
`CLASS MAYGH‘NG
`
`cuss so: Nzxr
`1mmcuss FOR
`ALI comfiuutm a
`SAVEDAmtaurE
`mama
`;
`
`SAVEDYRAF [C
`AGGREGATE
`
`
`
`
`
`
`
`
`
`VMWARE 1006
`
`VMWARE 1006
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 1 0f 7
`
`US 6,591,299 B2
`
`45
`
`40
`
`40'
`
`25
`
`CLIENT
`
`SERVER
`
`2O
`
`32
`
`NETWORKIF
`
`37
`
`NETWORKIF
`
`37'
`
`FIG.1A(PRIORART)
`
`
`
`OOOOOOO0
`
`0000000
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 2 0f7
`
`US 6,591,299 132
`
`20
`
`EEEEEEEEEEEEEEEE"""
`”M—
`
`
`
`SERVER
`
`55
`
`46
`
`CGI
`
`WEB
`SERVER
`
`OPERATING 42
`SYSTEM
`
`DATAOBJECT
`1
`
`50
`
`44
`
`DATA OBJECT
`N
`
`51
`
`TCP/IP
`
`QUERY
`FROM USER (1
`
`T
`
`HTML OUTPUT
`TO USER
`
`45
`
`25
`
`
`
`CLIENT
`
`ii
`
`TCP/IP
`
`OPERAT'NG
`SYSTEM
`
`WEB
`BROWSER
`
`44‘
`
`42'
`
`46
`
`FIG. 1 B
`
`(PRIOR ART)
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 3 0f 7
`
`US 6,591,299 B2
`
`ooomX<>
`
`0?.0E
`
`Cm<moan:
`
`oo$w<Em.
`
`
`
`
`
`ooonm_>_m:
`
`m..__m=.r<n=>_OO
`
`Em_
`
`mm
`
`m _
`
`=___z==_==n.
`
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 4 0f 7
`
`US 6,591,299 B2
`
`88\>
`
`
`
`
`
`
`
`
`HTTP SNMP RPC
`
`
`
`
`LEGEND
`
`88 Session/Application Layer
`86 Transport Layer
`84 Network Layer
`82 Data Link Layer
`80
`Physical Layer
`
`FIG. 1D
`
`(PRIOR ART)
`
`
`
`
`j201
`
`DEPT A
`INSIDE HOST
`SUBNET A
`
`202
`
`FTP
`OUTSIDE
`
`PORT 20
`
`
`
`205
`
`208
`
`210
`
`212
`
`205
`
`DEFAULT
`
`FIG. 2A
`
`
`
`204
`
`DEPT B
`INSIDE HOST
`
`SUBNET B
`
`
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 5 0f 7
`
`US 6,591,299 B2
`
`#——> WEB
`
`DEPT A
`
`220
`
`
`
`—>
`
`DEPT B
`
`DEPT A
`
`224
`
`
`
`225
`
`a DEFAULT J
`
`DEPTB
`
`FIG. 28
`
`203
`
`226
`
`228
`
`230
`
`232
`
`>
`
`CLASSIFIER
`
`304
`
`O————>
`
`
`
`KNOWLEDGE
`
`306
`
`
`
`j308
`
`302
`
`I
`
`TRAFFIC a
`
`TRAFFIC b
`
`TRAFFIC C
`
`
`
`CLASS B
`
`CLASS C
`
`FIG. 3
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 6 0f 7
`
`US 6,591,299 B2
`
`401
`
`I
`
`
`PARSE FLOW
`
`
`SPECIFICATION
`
`
`FROM A PACKET
`OF THE FLOW
`
`
`
`COMPARE FLOW
`SPECIFICATION
`
`
`WITH EXISTING
`CLASSIFICATION TREE
`
`
`
`402
`
`404
`
`
`
`TRAFFIC
`MATCHES THE
`
`CLASS?
`
`
`
`RETURN
`
`
`
`
`ENTER INTO A
`SAVED LIST
`
`
`CHARACTERISTICS
`
`
`OF THE TRAFFIC
`
`
`
`408
`
`SUPPRESS
`DUPLICATES
`
`3/410
`
`DETERMINE BYTE
`COUNT FOR TRAFFIC
`AND INCLUDE WITH
`FLOW SPECIFICATION
`IN SAVED LIST
`
`_
`
`412
`
`5/
`
`_
`
`
`
`
`
`RETURN
`
`
`
`FIG. 4A
`
`

`

`US. Patent
`
`Jul. 8, 2003
`
`Sheet 7 0f 7
`
`US 6,591,299 B2
`
`
`
`RETRIEVE CLASSIFIED
`TRAFFIC FROM
`SAVED LIST
`
`420
`
`403
`j
`
`421
`
`DISCOVERING
`
`ATTRIBUTES?
`
`
`
`
`
`
`SAVED
`TRAFFIC WELL—
`KNOWN?
`
`
`
`YES
`
`
`SAVED
`
`TRAFFIC A SERVER
`
`AT UNREGISTERED
`
`IP PORT?
`
`
`
`SAVED
`
`
`TRAFFIC BELONGS
`
`TO A SERVICE
`‘ GGREGAT
`
`
`
`428
`424
`
`CREATE TRAFFIC
`
`
`
`
`CLASS MATCHING
`CREATE NEW
`CREATE TRAFFIC
`
`CLASS FOR NEXT
`TRAFFIC CLASS FOR
`ALL COMPONENTS
`
`
`
`
`SAVED TRAFFIC
`SAVED ATTRIBUTE
`OF SERVICE
`
`
`
`AGGREGATE
`
`
`
`
`434
`
`NO
`
`
`TRAFFIC
`
`HAS ATTRS NOT
`
`
`I ISCO¥ERED
`
`
`436
`
`YES
`
`NO
`
`RETAIN
`SAVED
`
`432
`
`
`TOO
`MANY CLASSES
`?
`
`
`
`
`
`YES
`
`CLASSIFICATION
`
`FIG. 4B
`
`
`
`

`

`US 6,591,299 B2
`
`1
`METHOD FOR AUTOMATICALLY
`CLASSIFYING TRAFFIC WITH ENHANCED
`HIERARCHY IN A PACKET
`COMMUNICATIONS NETWORK
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`10
`
`15
`
`2
`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.
`BACKGROUND OF THE INVENTION
`
`invention relates to digital packet
`This
`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
`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”.
`
`This application claims priority from a commonly owned
`U.S. Provisional Patent Application, Serial No. 60/066,864,
`filed 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.”
`This is a continuation—in—part of U.S. application Ser. No.
`09/990,354 filed Nov. 23, 2001, now U.S. Pat. No. 6,457,
`051,
`in the name of Guy Riddle and Robert L. Packer,
`entitled Method For Automatically Classifying Traffic In A
`Packet Communications Network, which is a continuation
`of application Ser. No. 09/198,090 filed Nov. 23, 1998, now
`U.S. Pat. No. 6,412,000, also in the name of Guy Riddle and
`Robert I.. Packer, also entitled Method For Automatically ,
`Classifying Traffic In A Packet Communications Network.
`The following related commonly-owned U.S. patent
`application is hereby incorporated by reference in its entirety
`for all purposes: U.S. patent application Ser. No. 09/198,
`051, filed Nov. 23, 1998, still pending, in the name of Guy
`Riddle, entitled “Method for Automatically Determining a
`Traffic Policy in a Packet Communications Network.”
`Further, this application makes reference to the following
`commonly owned U.S. Patents and Applications, which are
`incorporated 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 automatically deter-
`mining the data rate of a TCP connection;
`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 Com-
`munication Environment Without a Data Rate Supervision,”
`relates to a technique for automatically scheduling TCP
`packets for transmission;
`U.S. Pat. No. 6,046,980, in the name of Robert L. Packer,
`entitled “Method for Managing Flow Bandwidth Utilization
`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 connec-
`tions according to a hierarchical classification paradigm; and
`U.S. patent application Ser. No. 08/742,994 now U.S. Pat.
`No. 6,038,216 issued Mar. 14, 2000, 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 automatically
`scheduling TCP packets for transmission.
`STATEMENT AS TO RIGHTS TO INVENTIONS
`MADE UNDER FEDERALLY SPONSORED
`RESEARCH OR DEVELOPMENT
`
`40
`
`45
`
`LnU\
`
`NOT APPLICABLE
`
`REFERENCE TO A “SEQUENCE LISTING,” A
`TABLE, OR A COMPUTER PROGRAM LISTING
`APPENDIX SUBMITTED ON A COMPACT
`DISK
`
`NOT APPLICABLE
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`
`60
`
`65
`
`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
`
`

`

`US 6,591,299 B2
`
`3
`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 band-
`width management 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 avail-
`able bandwidth from a single logical link to network flows.
`In 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 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 Utilization at Network, Trans-
`port and Application Layers in Store and Forward Network,”
`a technique for automatically allocating bandwidth based
`upon data rates of TCP connections according to a hierar-
`chical 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. Provi-
`sional Patent Application Serial 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 an expensive commodity as traffic
`expands faster than resources and the need to “prioritize” a
`scarce rcsourcc bccomcs ever more critical. One way to
`solve this is by applying “policies” to control traffic classi-
`fied as to type of service required in order to more efficiently
`match resources with traffic.
`
`10
`
`15
`
`40
`
`45
`
`4
`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 P 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. Prior
`bandwidth managers 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 rulc cntry 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 analyzing
`real traffic in a customer’s network and automatically pro-
`ducing 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. By rendering discoverable the attributes of a flow
`specification for packet flows, a finer grained hierarchy of
`classification is provided automatically that
`is based on
`information which is specific to the type of program or
`application supported by the flow and thus allowing greater
`flexibility in control over different flows within the same
`application. 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. The flow specification is
`provided with some application—specific attributes, some of
`which are discoverable. The discoverable attributes lead to
`an ability to automatically create sub-nodes of nodes for
`finer-grained control. The automatic classification is suffi-
`ciently 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
`
`60
`
`65
`
`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;
`
`

`

`US 6,591,299 B2
`
`5
`FIG. 1D depicts a relationship diagram of the layers of the
`TCPHP 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
`OF THE INVENTION
`
`1.0 Introduction
`
`10
`
`15
`
`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. Below is a definitional list of terminology used
`herein.
`List of Definitional Terms
`
`ADMISSIONS CONTROLApolicy invoked whenever a
`system according to the invention detects that a guaranteed
`information rate cannot be maintained. An admissions con-
`trol policy is analogous to a busy signal in the telephone
`world.
`
`CLASS SEARCH ORDER A search method based upon
`traversal of a N—ary tree data structure containing classes.
`COMMITTED INFORMATION RATE (CIR) A rate of
`data flow allocated to reserved service traffic for rate based
`bandwidth allocation for a committed bandwidth. Also
`
`called a guaranteed information rate (GIR).
`EXCEPTION A class of traffic provided by the user which
`supersedes an automatically determined classification order.
`EXCESS INFORMATION RATE (EIR) A rate of data
`flow allocated to reserved service traffic for rate based
`bandwidth allocation for uncommitted bandwidth resources.
`
`FLOW A flow is a single instance of a connection or
`packet—exchange activity. For example, all packets in a TCP
`connection belong to the same flow, as do all packets in a
`UDP session. Aflow always is associated with a traffic class.
`GUARANTEED INFORMATION RATE (GIR) A rate of
`data flow allocated to reserved service traffic for rate based
`bandwidth allocation for a committed bandwidth. Also
`
`called a committed information rate (CIR).
`INSIDE On the LAN side of the bandwidth management
`device.
`
`MATCHING RULE A description which is used to deter-
`mine whether a flow matches a traflic class, e.g., “inside
`servicezhttp”, which will match any flows which are con-
`nected to an HTTP server on the “inside” of the bandwidth
`
`management device. Also known as “traffic specifications”.
`OUTSIDE On the WAN or Internet side of the bandwidth
`
`management device.
`PARTITION Partition is an arbitrary unit of network
`resources.
`
`POLICYA rule assigned to a given class that defines how
`the traffic associated with the class will be handled during
`bandwidth management.
`
`40
`
`45
`
`60
`
`65
`
`6
`POLICY INHERITANCE A method for assigning poli-
`cies to flows for which no policy exists in a hierarchical
`arrangement of policies. For example, if a flow matches the
`traffic class for FTP traffic to Host A, and no corresponding
`policy exists, a policy associated with a less specific node,
`such as the traffic class which matches FTP traffic to any
`host, may be located and used.
`POLICY BASED SCALING An adjustment of a
`rcqucstcd data ratc for a particular flow based upon thc
`policy associated with the flow and information about the
`fiow’s potential rate.
`SCALED RATE Assignment of a data rate based upon
`detected speed.
`SERVICE LEVEL A service paradigm having a combi-
`nation of characteristics defined by a network manager to
`handle a particular class of traffic. Service levels may be
`designated as either reserved or unreserved.
`TRAFFIC CLASS A logical grouping of traffic flows that
`share the same characteristicsisuch as application,
`protocol, address, or set of addresses. A traffic class is
`defined with a series of matching rules.
`TRAFFIC SPECIFICATION See “matching rule”.
`URI 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
`1.1 Hardware Overview
`
`The method for classifying heterogeneous packets in a
`packet
`telecommunications environment of the present
`invention may be implemented in the C programming lan-
`guage and made 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
`clicnts, onc of which is shown as clicnt 25. Thc use of thc
`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.
`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 35]) 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-
`cnd workstation or mainframc, such as a SUN SPARC
`server. Corresponding elements and subsystems in the client
`computer are shown with corresponding, but primed, refer-
`ence numerals.
`
`

`

`US 6,591,299 B2
`
`10
`
`15
`
`7
`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 I
`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 3561' in FIG. 1A. TCP/1P
`stack 44', works in conjunction with Operating System 42' to
`communicate with processes over a network or serial con-
`nection attaching Client 25 to Internet 45. Software imple-
`menting the function of a web browser 46' executes eon-
`currently 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 prior art Token Ring or frame oriented net-
`work. Network 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, IBM 03/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
`
`40
`
`45
`
`60
`
`65
`
`8
`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
`VAX 6000 computer which may be running the VMS
`operating system (formerly available from Digital Equip-
`ment Corporation).
`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
`X25, 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