`
`USOU7433304BI
`
`(12) United States Patent
`Galloway et at.
`
`[10) Patent No.:
`
`(45) Date of Patent:
`
`US 7,433,304 Bl
`Oct. 7, 2008
`
`(54) CLASSIFICATION DATA STRUCTURE
`ENABLING MULTI—DLVIENSIONAL
`NETWORK TRAFFIC (IIASSIFIC‘A'I‘ION AND
`CONTROL SCHEMES
`
`(75}
`
`Inventors: Brett Galloway. Los Altos. CA (US):
`George Powers. I_.os Gatos. CA (US)
`
`(73) Assignee: Paeketeer. Inc.. Cupertino, CA (US)
`
`( "‘
`
`) Notice:
`
`Subject to any disclaimer. the term of this
`patent is extended or adjusted under 35
`USC‘. 15403) by 1239 days.
`
`(21) Appl.No.: 101236.149
`
`(22)
`
`Filed:
`
`Sep. 6, 2002
`
`(51)
`
`Int. (11.
`11041. 12/26
`G06!" 7/00
`HML J 2/56
`(52) U.S. Cl.
`(58} Field ofClassilication Search
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`37012292370t412
`3707392:
`71 ”221
`
`See application file for complete search history.
`
`(56)
`
`References Cited
`U .S. PATENT DOCUMENTS
`
`7093223
`8.";2000 Andrewsetal.
`6.105.062 A ‘V
`932001 PaCker .................. 3705230
`6.285.658 Bl "‘
`1052001 Brcukcrctal.
`7057400
`6.308.160 131*
`532003 Dravesctal.
`7093224
`6.385.649 131*
`752003 Bhattacharyn et al.
`. 370895.21
`6.587.466 Bl ’°'
`6.816.456 Bl“ 1132004 Tse-Au .................... 370.2301
`
`
`
`7:"2005 Novik et a1.
`6.918.124 Bl "‘
`9-0006 Brown
`7.106.732 32“
`252002 Woo .....
`200230023089 Al *
`5t2002 Riddle et a].
`200230055998 Al ‘V
`9.52002 Kenney el al.
`200130122422 Al ’°‘
`1052003 (jolltt et al.
`200330188065 Al ”
`200370229623 Al "’ 122003 Chang et a].
`
`..
`
`7l9.-'318
`.. 3703389
`
`.. 707-"101
`.. 709,224
`..... 370.3392
`
`.. 7105243
`707:"3
`
`* cited by examiner
`
`Primmj’ Examiner Chan T. Nguyen
`Assistant Examiner Timothy J Weidner
`(74) Attorney. Agent, or Firm—Baker Botts L.L.P.
`
`[57)
`
`ABSTRACT
`
`Methods. apparatuses and systems facilitating hierarchical
`network traffic
`classification and resource
`allocation
`schemes. In one embodiment. the present invention provides
`traffic classification data structure facilitating creation and
`configuration of multi-dimensional. hierarchical network
`resource allocation schemes. The present invention features a
`hierarchical network traffic classification scheme that allows
`
`users to logically embed (or otherwise associate] one or more
`reference trees within selected traific class nodes or a given
`lrailic classification tree In one embodiment. an administra-
`tor can create a pool of ret'erenceable traffic classification
`trees and select such trees or sub-trees from the pool to
`achieve a variety ot'dilierent traflic classification configura-
`tions. The present invention. in one embodiment. also facili-
`tates the implementation of a system or domain-level work-
`flow interface that
`features managed access
`links as
`configurable objects as opposed to the network devices oper-
`ating on the access links.
`
`28 Claims, 10 Drawing Sheets
`
`Application --
`
`I
`
`
`
`EX1036
`
`Palo Alto Networks V. Sable Networks
`
`IPR2020-01712
`
`EX1036
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheetl of 10
`
`US 7,433,304 B1
`
`
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheet 2 of 10
`
`US 7,433,304 B1
`
`
`
`Administrator
`
`150
`
`
`Interface
`
`137
`
`
`ClaSSIficatlon
`[)31abase
`
`En ine
`g
`
`Host
`
`Database
`
`134
`
`
`Ttaffic. I. Measurement
`140
`
`
`
`
`
`
`
`
`
`Data Packet
`
`In
`
`Packet
`
`Processor
`
`Flow Control
`
`Data Packet
`
`Module
`
`Out
`
`131
`
`132
`
`Fig. 2
`
`
`
`US. Patent
`
`Oct. 7, 2003
`
`Sheet 3 of 10
`
`US 7,433,304 B1
`
`Receive Data
`
`
`
`Control
`
`Block?
`
`Fetcthpdatc
`Control Block
`
`
`
`Packet
`
`
`
`
`
`
` lietc‘nfUpdate
`
`Control Block
`
`
`Changes
`To Flow?
`
`
`Construct
`
`Control Block
`
`Identify
`Traffic Class
`
`
`
`P = gctControls
`(Traffic Class)
`
`
`Pass Packet to
`Flow Control
`
`
`
`Module (P)
`
`
` Record Bandwidth
`Utilization Data In
`
`Association with
`Traffic Class
`
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheet 4 of 10
`
`US 7,433,304 B1
`
`
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheet 5 of 10
`
`Us 7,433,304 B1
`
`
`
`
`
`
`£319,148(Primart).
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheet 6 of 10
`
`Us 7,433,304 B1
`
` Mama
`
`Uq
`
`-
`
`Hg
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheet 7 of 10
`
`US 7,433,304 B1
`
`42c
`
`{1
`
` Central Management
`
`Server
`
`Computer
`Network
`
`
`
`
`
`US. Patent
`
`Oct. 7, 2008
`
`Sheet 8 of 10
`
`Us 7,433,304 B1
`
`
`-...'53
`
`
`m
`
`.
`..
`3.333.113: n
`
`Svsicm Lave}
`'
`
` Admin
`
`
`
`
`Viflim i
`_
`V Eff-“3i
`Sizbijnk
`gaming:
`_
`-
`
`
`
`
`:
`
`i
`
`
`
`Link. 1.1396
`
`ms
`
`_'
`
`1:224
`
`
`
`-@ 1691
`
`_ Tm;
`
`
`
`
`
`US. Patent
`
`Oct. 7, 2003
`
`Sheet 9 of 10
`
`US 7,433,304 B1
`
`50
`
`40a
`
`
`
`
`US. Patent
`
`Oct. 7, 2003
`
`Sheet 10 0f10
`
`US 7,433,304 B1
`
`Node 2 Root
`
`Node
`
`Reference
`
`Tree?
`
`
`Reference Trees
`
`
`For All
`
`
`
`
`
`
`
`Tree = Next
`
`Referenced Tree; Node
`= Referenced Node
`
`
`End For All
`Reference
`
`Trees
`
`Retrieve Child
`
`Peer Nodes
`
`
`Matching
`Node?
`
`Yes
`
`Retum (Null)
`
`Node =
`
`Matching Node
`
`
`
`US 1433.304 B]
`
`l
`CLASSIFICATION DATA STRUCTURE
`ENABLING MUL’I'I-DIMENSIONAI.
`NETWORK TRAFFIC CLASSIFICATION AND
`CONTROL SCHEMES
`
`2
`
`for Automatically Classifying Traflic with
`“Method
`Enhanced I-lietarchy in a Packet Communications Networ .”
`
`FIELD OF THE. INVENTION
`
`CTROSS-Rl'il’IiRliNCliS TO RliilsA'I'l'ilJ
`APPLICATIONS
`
`This application makes reference to the following com-
`monly owned U.S. patent applications and patents. which ar '
`incorporated herein by reference in their entirety for all pur-
`poses:
`U.S. patent application Ser. No. 08f762,828 now U .8. Pat.
`No. 5.802.106 in the name of Robert L. Packer, entitled
`“Method for Rapid Data Rate Detection in a Packet Commie
`nication Environment Without Data Rate Supervisionz"
`U.S. patent application Ser. No. 08970693 now U.S. Pat.
`No. 6,018,516, in the name of Robert I... Packer. entitled
`“Method for Minimizing Unneedcd Retransmission of Pack-
`ets in a Packet Communication Environment Supporting a
`Plurality of Data Link Rates;"
`U.S. patent application Ser. No. 081742.994 now US. Pat.
`No. 6,038,216. in the name of Robert I... Packer, entitled
`“Method for Explicit Data Rate Control in a Packet Commit-
`nication Environment without Data Rate Supervision?
`US. patent application Ser. No. 09971642 now U .5. Pat.
`No. 6.046.980.
`in the name of Robert L. Packer. entitled
`“System for Managing Flow Bandwidth Utilization at Net—
`work. Transport and Application Layers in Store and Forward
`Networ :"
`U.S. patent application Ser. No. 09l106,924 now U.S. Pat.
`No. 6.115.357, in the name ofRobert L. Packer and Brett D.
`Gallowway. entitled “Method for Pacing Data Flow in a
`Packet-based Network“
`U.S. patent application Ser. No. (BIO-46,776 now U.S. Pat.
`No. 6.205.120, in the name of Robert L. Packer and Guy
`Riddle. entitled “Method for Transparently Determining and
`Setting an Optimal Minimum Required TCP Window Size,”
`U.S. patent application Ser. No. 09;“479356 now U.S. Pat.
`No. 6.285.658,
`in the name of Robert L. Packer. entitled
`“System for Managing Flow Bandwidth Utiliration at Net-
`work, Transport and Application Layers in Store and Forward
`Networ ';“
`U .S. patent application Ser. No. 09;r 198.090 now US. Pat.
`No. 6,412,000. in the name of Guy Riddle and Robert L.
`Packer. entitled “Method for Automatically Classifying "fraf-
`lie in a Packet Communications Network;"
`U.S. patcnl application Ser. No.09f198.051. in the name of
`Guy Riddle, entitled “Method ihrAtitomatically Determining
`a Trafl'ic Policy in a Packet Communications Networ ';"
`U.S. patent application Ser. No. 092‘206,772, in the name of
`Robert I... Packer, Brett 1). Galloway and "fed 'lhi. entitled
`“Method for Data Rate Control for Heterogeneous or Peer
`Internetworkingi"
`US. patent application Ser. No. 09f966,538, in the name of
`Guy Riddle. entitled “Dynamic Partitioning of Network
`Resources,"
`U.S. patent application Ser. No. IOJO39,992. in the Michael
`.1. Quinn and Mary L. Laier. entitled “Method and Apparatus
`for Fast Lookup ol‘Relatcd Classification Entities in a "free
`Ordered Classification Hierarchyz"
`US. patent application Ser. No. 10)r 1 08.085. in the name of
`WeivLung Lai, Jon Eric Okholm. and Michael 1. Quinn,
`entitled “Output Scheduling Data Structure Facilitating Hier—
`archical Network Resource Allocation Schemez" and
`U.S. patent application Ser. No. lOr‘l 55.936. in the nameof
`Guy Riddle, Robert
`I... Packer and Mark Hill, entitled
`
`10
`
`3t]
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`The present invention relates to network tralfic classifica-
`tion mechanisms and, more particularly, to methods appara—
`tuses and systems enabling a multidimensional network traf-
`fic classification and control scheme.
`
`BACKGROUND OF T HE INVENTION
`
`Efficient allocation of network resources, such as available
`network bandwidth. has become critical as enterprises
`increase reliance on distributed computing environments and
`wide area computer networks to accomplish critical tasks.
`The widely-used 'I'CPII P protocol suite, which implements
`the world-wide data communications network environment
`
`called the Internet and is employed in malty local area net-
`works, omits any explicit supervisory function over the rate of
`data transport over the various devices that comprise the
`network. While there are certain perceived advantages, this
`characteristic has the consequence ofj uxtaposing very high-
`speed packets and very low-speed packets in potential con-
`flict and produces certain inefficiencies. Certain loading con-
`ditions degrade performance of networked applications and
`can even cause instabilities which could lead to overloads that
`could stop data transfer temporarily.
`In order to understand the context ofcertain embodiments
`of the invention, the following provides an explanation of
`certain technical aspects of a packet based telecommunica-
`tions network environment. Internettlntranet technology is
`based largely on the TCPIIP protocol suite. At the network
`level. IP provides a “datagram” delivery service --lhat is. IP is
`a protocol allowing for delivery of a datagram or packet
`between two hosts. By contrast. TCP provides a transport
`level service on top of the datagram service allowing for
`guaranteed delivery ofa byte stream between two ll’ hosts. In
`other words. TCP is responsible for ensuring at the transmit-
`ting host that message data is divided into packets to be sent.
`and for reassembling. at the receiving host. the packets back
`into the complete message.
`TCP has “flow control" mechanisms operative at the end
`stations only to limit the rate at which a TCP endpoint will
`emit data. but it does not employ explicit data rate control.
`The basic flow control mechanism is a “sliding window". a
`window which by its sliding operation essentially limits the
`amount oftutacknowledged transmit data that a transmitter is
`allowed to emit. Another flow control mechanism is a con
`
`gestion window, which is a refinement of the sliding window
`scheme involving a conservative expansion to make use oflhe
`full, allowable window.
`The sliding window flow control mechanism works in con-
`junction with the Retransmit Timeout Mechanism (RTO).
`which is a timeout to prompt a retransmission ofunacknowl-
`edged data. The timeout length is based on a running average
`ofthe Round Trip Time (RTT) for acknowledgement receipt,
`i.e., if an acknowledgement is not received within (typically)
`the smoothed R’I'I‘+4* mean deviation, then packet loss is
`inferred and the data pending acknowledgment is re-trans-
`mitted. Data rate flow control mechanisms which are opera-
`l'ivc 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—oif."—i.e., inhibit transmission in increasing multiples
`of the base RT'1' average as a reaction to consecutive packet
`loss.
`
`
`
`3
`
`4
`
`US ?,433,304 B]
`
`A crude form of bandwidth management in TCPKIP net-
`works (that is. policies operable to allocate available band-
`width from a single logical link to network flows) is accom-
`plished by a combination of TC P end systems and routers
`which queue packets and discard packets when some conges-
`tion threshold is exceeded. The discarded and therefore unac-
`knowledged packet serves as a feedback mechanism to the
`TC P transmitter. Routers support various queuing options to
`provide for some level of bandwidth management. These
`options generally provide a rough ability to partition and
`prioritize separate classes of traffic. However. configuring
`these queuing options with any precision or without side
`effects is in fact very difficult. and in some cases. not possible.
`Seemingly simple things. such as the length of the queue.
`have a profound effect on traffic characteristics. Discarding
`packets as a feedback mechanism to TCP end systems may
`cause large. uneven delays perceptible to interactive users.
`Moreover. while routers can slow down inbound network
`traffic by dropping packets as a feedback mechanism to a TCP
`transmitter. this method often results in retransniissionofdata
`packets, wasting network traffic and, especially.
`inbound
`capacity of a WAN link. In addition. routers can only explic-
`itly control outbound traffic and cannot prevent inbound traf-
`fic from over-utilizing a WAN link. A 5% load or less on
`outbound traffic can correspond to a 100% load on inbound
`traffic, due to the typical imbalance between an outbound
`stream of acknowledgements and an inbotmd stream of data.
`In response. certain data flow rate control mechanisms
`have been developed to provide a means to control and opti-
`mize efficiency of data transfer as well as allocate available
`bandwidth among a variety of business enterprise function-
`alities. For example. U .5. Pat. No. 6,038,216 discloses a
`method for explicit data rate control in a packet-based net-
`work environment without data rate supervision. Data rate
`control directly moderates the rate ofdata transmission from
`a sending host, resulting in justnin-time data transmission to
`control inbound traffic and reduce the inefficiencies associ-
`
`ated with dropped packets. Bandwidth management devices
`allow for explicit data rate control for flows associated with a
`particular traffic classification. For example. US Pat. No.
`6.412.000, above. discloses automatic classification of net—
`work traffic for use in connection and bandwidth allocation
`
`mechanisms. US. Pat. No. 6.046.980 discloses systems and
`methods allowing for application layer control of bandwidth
`utilization in packet-based computer networks. For example.
`bandwidth management devices allow network administra-
`tors to specify policies operative to control auditor prioritize
`the bandwidth allocated to individual data flows according to
`traffic classifications. In addition, certain bandwidth manage—
`ment devices, as well as certain routers. allow network admin-
`istrators to specify aggregate bandwidth utilization controls
`to divide available bandwidth into partitions. With sortie net-
`work devices. these partitions can be configured to ensure a
`minimum bandwidth andfor cap bandwidth as to a particular
`class of traffic. An administrator specifies a traffic class (such
`as FTP data, or data flows involving a specific user} and the
`size of the reserved virtual link—i.e.. minimum guaranteed
`bandwidth andlor maximum bandwidth. Such partitions can
`be applied on a per-application basis (protecting andfor cap-
`ping bandwidth f'or all traffic associated with an application}
`or a per-user basis (protecting andt'or capping bandwidth for
`a particular user). In addition, certain bandwidth management
`devices allow administrators to define a partition hierarchy by
`configuring one or more partitions dividing the access link
`and further dividing the parent partitions into one or more
`child partitions.
`
`10
`
`3o
`
`4E]
`
`45
`
`50
`
`55
`
`60
`
`65
`
`To facilitate the implementation, configuration and man»
`agetnent tasks associated with bandwidth management and
`other network devices including traffic classification func-
`tionality, various traffic classification configuration models
`and data structures have been implemented. For example.
`various routers allow network administrators to configure
`access control lists (ACLs) consisting of an ordered set of
`access control entries (ACES). Each ACE contains a number
`of fields that are matched against the attributes of a packet
`entering or exiting a given interface. [11 addition. cach ACE
`has an associated action that indicates what the routing sys-
`tem should do with the packet when a match occurs. ACIJS
`can be configured to accomplish or facilitate a variety of
`tasks. such as security, redirection, caching. encryption. net—
`work address translation. and policy routing. Once config~
`ured by an administrator, the routing system compiles the
`AC1. into a hash table to expedite the look up process during
`operation of the system.
`In addition. U.3. Pat. No. 6.412.000 discloses methods and
`system that automatically classify network traffic according
`to a set of classification attributes. As this application teaches,
`the traffic classification configuration can be arranged in a
`hierarchy, where classification of a particular packet or data
`flow transverses a network traffic classification tree until a
`
`matching leaf traffic class. if any, is found. Such prior art
`classification trees are data structures reflecting the hierarchi -
`cal aspect oftrallic class relationships. wherein each node of
`the tree represents a traffic class and includes a set of
`attributes or matching rules characterizing the traffic class.
`The traffic classification, at each level of the hierarchy, deter-
`mines whether the data flow or packet matches the attributes
`of a given traffic class node and. if so. continues the process
`for child traffic class nodes down to the leaf nodes. In certain
`
`modes. unmatched data flows map to a default traffic class. [it
`addition. patent application Ser. No. 101039392 discloses
`methods for caching portions of hierarchical classification
`trees in hash tables to optimize traffic classification lookups.
`Although these hierarchical traffic classification schemes
`are suitable for their intended purposes. they do have certain
`limitations. For example. the hierarchical configuration con-
`strains current implementation of bandwidth utilization con-
`trols and other orthogonal controls or policy types (such as
`security policies, encryption policies. caching policies. etc).
`For example. a particular classification scheme may be desir~
`able for bandwidth utilization controls, while a separate clas-
`sification scheme may be desirable for a security policy
`scheme. Prior art systems. however, confine network admin-
`istrators to a single traffic classification configuration hierar-
`chy that is used for purposes of determining appropriate poli—
`cies. Moreover, the traffic classification tree data structure,
`described above. is also problematic when trying to classify
`network traffic on two different axes in that the classification
`
`tree corresponding to a first classification axis must be repli-
`cated at all leaf nodes of the traffic classification tree repre-
`senting a network traffic classification on a second classifica-
`tion axis. Furthermore. the hierarchical traffic classification
`technologies associated with the prior art do not facilitate
`natural sharing oftraffic classification andlor policy configu—
`rations or configuration subsets in a manner that is consistent
`across different deployment modes.
`In light ofthe foregoing. a need in the art exists for meth-
`ods, apparatuses and systems allowing for a traffic classifica-
`tion scheme that facilitates configuration 01‘ network traffic
`classification schemes
`suitable for
`implementation of
`orthogonal policies. A need in the art also exists for methods,
`apparatuses and systems that facilitate the natural sharing of
`traffic classification configurations, for example, across net-
`
`
`
`5
`
`6
`
`US 1433304 B]
`
`work devices employing traflic classification functionality. or
`within a single network device. Embodiments of the present
`invention substantially fulfill these needs.
`
`SUMMARY OF THE lNVlZiNTlON
`
`The present invention provides methods. apparatuses and
`systems facilitating hierarchical network traffic classification
`and resource allocation schemes. In one embodiment. the
`present invention provides traffic classification data structure
`facilitating. creation and configuration of multi-ditncnsional.
`hierarchical network resource allocation schemes. The
`
`10
`
`present invention features a hierarchical network traffic clas-
`sification scheme that allows users to logically embed (or
`otherwise associate) one or more reference trees within
`selected traflic class nodes of a given traffic classification tree.
`In one embodiment. an administrator can create a pool of
`referenceable traffic classification trees and select such trees
`
`or sub-trees from the pool to achieve a variety of different
`tralfic classification configurations. In one embodiment, the
`ability to embed reference trees or reference sub—trees in
`traffic class nodes of other trees achieves, as discussed more
`fully below. a variety of advantages aSsociated with configu-
`ration rmd management of a given bandwidth management
`device or an administrative domain comprising a plurality of
`bandwidth management devices managing traffic across a
`plurality of access links. Embodiments of the present inven-
`tion allow for multidimensional axes of traffic classification
`
`and policy. the ability to specify named policy macros and
`conditional policies. as well as providing for a natural model
`ofpolicy sharing across multiple links. The present invention.
`in one embodiment. also facilitates the implementation of a
`system or domain-level workfiow interface that features titan-
`aged access links as configurable objects as opposed to the
`network devices operating on the access links.
`
`DESCRIPI‘ION OF TI Iii DRAWINGS
`
`FIG. 1 is a functional block diagram illustrating a computer
`network environment including a bandwidth management
`device according to an embodiment of the present invention.
`FIG. 2 is a fiinctional block diagram setting forth the func—
`tionality in a bandwidth management device according to an
`embodiment of the present invention.
`FIG. 3 is a flow chart providing a method directed to
`processing data packets to allow for enforcement of band-
`width utilization and other controls on network data flows.
`
`FIG. 4A is a diagram illustrating a rnulti-dimensional traf-
`fic classification scheme for a given access link according to
`an embodiment of the present invention.
`FIG. 41.3 is a diagram illustrating a prior art hierarchical
`traffic classification configuration required to approximate
`the multi-dimensional trafiic classification scheme depicted
`in F16. 4A.
`
`FIG. 4C is a diagram illustrating a multi-dimcnsional traf-
`fic classification scheme according to another embodiment of
`the present invention.
`FIG. 5 is a functional block diagram illustrating a computer
`network enviromnent including a plurality of bandwidth
`management devices operably connected to a central man-
`agement server according to an embodiment ofthe present
`invention.
`FIG. 6 is a diagram illustrating a multidimensional traffic
`classification scheme for a plurality ofaccess links.
`FIG. 7A is a functional block diagram illustrating a com—
`puter network enviromncnt in which a single bandwidth man-
`agement device manages data flows traversing a plttrality of
`
`3o
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`access links to a wide area network; FIG. 7B is a diagram
`setting forth a system link level view of the managed links
`corresponding to the computer network environment of FIG.
`7A.
`
`FIG. 8 is a flow chart diagram setting forth a method.
`according to one embodiment of the present
`invention.
`directed to traversing a hierarchical traffic classification data
`structure include one or more embedded reference trees.
`
`DESCRIPTION OF PREFERRED
`
`EMBODI MENT{S)
`
`I. Exomplary Operating Environment
`
`FIG. 1 sets forth a packet-based computer network envi-
`ronment including a bandwidth management device 30. As
`FIG. I shows. local area computer network 40 interconnects
`several TCP/IP end systems. including client devices 42 and
`server device 44. and provides access to resources operably
`connected to computer network 5t! via router 22 and access
`link 21. Access link 21 is a physical and/or logical connection
`between two networks. such as computer network 50 and
`local area network 40. Server 28 is a TCP end system con-
`nected to computer network 50 through router 26 zmd access
`link 25. Client devices 24 are additional TCP end systems
`operably connected to computer network 50 by any suitable
`means. such as through an Internet Services Provider (ISP).
`The computer network environment. including computer net-
`work 50 is a packet—based conununications environment,
`employing TCPIIP protocols. andfor other suitable protocols,
`and has a plurality of interconnected digital packet transmis-
`sion stations or routing nodes. Bandwidth management
`device 30 is provided between router 22 and local area com—
`puter network 40. Bandwidth management device 30 is
`operative to classify data flowa and. depending on the classi-
`fication. enforce respective bandwidth utilization controls on
`the data flows to control bandwidth utilization across and
`optimire network application performance across access link
`2]. In addition. FIG. 7 illustrates 2m alternative deployment
`configuration for bandwidth management device 30. As FIG.
`7 shows. bandwidth management device 30 is deployed in an
`Internet Service Provider (1 SP) domain 52 to manage network
`traffic between a plurality ofseparate local area networks 400.
`40b, 40c and wide area network 50.
`
`A. Bandwidth Management Device
`FIG. 2 is a block diagram illustrating functionality. accord-
`ing to one embodiment oftlte present invention. included in
`bandwidth management device 30.
`In one embodiment.
`bandwidth management device 30 comprises packet proces—
`sor 131. flow control module 132. measurement engine 140.
`traffic classification engine 137. and administrator interface
`150. Packet processor 131 is operative to detect new data
`flows and construct data structures including attributes char-
`acterizing the data flow. Flow control module 132 is operative
`to enforce bandwidth utilization controls on data flows tra-
`
`versing bandwidth management device 30. Traffic classifica—
`tion engine 137 is operative to analyze data flow attributes and
`identify traffic classes correSponding to the data floats. as
`discussed more fully below. In one embodiment, traffic clas-
`sification engine 137 stores traffic classes associated with
`data flows encountered during operation ofbandwidlh man-
`agement device 30. as well as manually created traffic classes
`and a hierarchical traffic class structure, if any. configured by
`a network administrator. In one embodiment, traffic classifi—
`cation enginc 13'? stores traffic classes. in association with
`pointers to bandwidth utilization controls or pointers to data
`
`
`
`7
`
`8
`
`US ?,433,304 B]
`
`structures defining such bandwidth utilization controls. Mea—
`surement engine 140 maintains measurement data relating to
`operation of bandwidth management device 30 to allow for
`monitoring of bandwidth utilization across access link 21
`with respect to a plurality of bandwidth utilization and other
`network statistics on alt aggregate andr'or per-traffic-class
`level.
`
`Administrator interface 150 facilitates the configuration of
`bandwidth numagement device 30 to adjust or change opera-
`tional and configuration parameters associated with tlte
`device. For example, administrator interface 150 allows
`administrators to select identified traffic classes and associate
`
`10
`
`them with bandwidth utilization controls, such as a partition.
`as well as other controls. Administrator interface 150 also
`
`displays various views associated with a hierarchical traffic
`classification scheme and allows administrators to configure
`or revise the hierarchical traffic classification scheme as dis-
`
`cussed more fully below. Administrator interface 150 can be
`a command line interface or a graphical user interface acces-
`sible, for example. through a conventional browser on client
`device 42.
`
`A.1. Packet Processing
`[11 one embodiment, when packet processor 131 encoun-
`ters a new data flow it stores the source and destination IP
`
`addresses contained in the packet headers in host database
`134. Packet processor 131 further constructs a control block
`object
`including attributes characterizing a specific flow
`between two end systems. In one embodiment. a control
`block object contains a flow specification object including
`such attributes as pointer to the “inside” artd “outside” IP
`addresses in host database 134, as well as other flow specifi-
`cation parameters. such as inside and outside port numbers.
`service type, protocol type and other parameters characteriz-
`ing the data flow. In one embodiment. such parameters can
`include information gleaned front examination ofdata within
`layers 2 through 7 of the OSI reference model. U.S. Pat. No.
`6.046.980. incorporated by reference herein, discloses clas-
`sification of data flows for use in a packet-based communi-
`cations environment. FIG. 1 illustrates the concept associated
`with inside and outside addresses. As discussed above. on one
`embodiment. a [low specification object includes an "inside”
`and “outside" address relative to bandwidth management
`device 30. See FIG. 1. For a TCP packet, packet processor 131
`can compute the inside and outside addresses based on the
`source and destination addresses of the packet and the direc-
`tion of the packet flow.
`In one embodiment. packet processor 131 creates and
`stores control block objects corresponding to data flows in
`flow database 135. In one embodiment. control block object
`attributes include a pointer to a corresponding flow specifi—
`cation object, as well as other flow state parameters, such as
`"I‘CP connection status, timing of last packets in the inbound
`and outbound directions, speed information. apparent round
`trip time. etc. Control block object attributes further include at
`least one traffic class identifier (or pointer(s) thereto) associ-
`ated with the data flow. as well as policy parameters (or
`pointers thereto) corresponding to the identified traflic class.
`In one embodiment. control block objects further include a
`list of traffic classes for which measurement data associated
`
`with the data flow should be logged. In one embodiment. to
`facilitate association of an existing control block object to
`subsequent packets associated with a data flow or connection.
`flow database 135 further maintains a control block hash table
`
`including a key comprising a bashed value computed from a
`string comprising the inside IP address, outside IP address,
`inside port ntunber. outside port number. and protocol type
`(e.g.. ’l‘CP, UDP, etc.) associated with a pointer to the corre-
`
`3t]
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`65
`
`spending control block object. According to this embodi-
`ment. to identify whether a control block object exists for a
`given data flow, packet processor 131 hashes the values iden-
`tified above and scans the hash table for a matching entry. If
`one exists. packet processor 131 associates the pointer to the
`corresponding control block object with the data flow.
`A.2. Flow Control Module
`As discussed above. flow control module 132 enforces
`bandwidth utilization controls (and. in some embodiments,
`other policies) on data flows traversing access link 21. A
`bandwidth utilization control for a particular data flow can
`comprise an aggregate control bandwidth utilization control.
`a per-flow bandwidth utilization control, or a combination of
`the two. Flow control module 132 can use any suitable func—
`tionality to enforce bandwidth utilization controls known in
`the art. including, but not limited to weighted fair queuing,
`class-based weighted fair queuing. Committed Access Rate
`(CAR) and “leaky bucket" techniques. Flow control module
`132 may incorporate any or a subset of the TCP rate control
`functionality described in the cross-referenced U.S. patents
`set forth above for controlling the rate of data flows. Band—
`width management device 30. however. can also be config—
`ured to implement a variety of different policy types, such as
`security policies. admission control policies, marking (diff-
`serv. VLAN. etc.) policies. redirection policies. caching poli-
`cies. transcoding policies. and network address translation
`(NAT) policies. Of course. one of ordinary skill in the art will
`recognize that other policy types can be incorporated into
`embodiments ofthe present invention.
`A.2a. Aggregate Bandwidth Utilization Control
`An aggregate bandwidth utilization control operates to
`manage bandwidth for aggregate data flows associated with a
`traffic class. An aggregate bandwidth utilization control can
`be configured to essentially partition the available bandwidth
`corresponding to a given access link. For example, a partition
`can be configured to protect a network traffic class by guar—