(12) United States Patent
`Galloway et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7.433,304 B1
`Oct. 7, 2008
`
`USOO7433304B1
`
`(54) CLASSIFICATION DATASTRUCTURE
`ENABLING MULT-DMENSIONAL
`NETWORK TRAFFIC CLASSIFICATION AND
`CONTROL SCHEMES
`
`
`
`6,918, 124 B1* 7/2005 Novik et al. ................ T19,318
`7,106,732 B2* 9/2006 Brown .......
`... 370,389
`2002fOO23089 A1* 2, 2002 WoO ..........
`... TO7 101
`2002fOO55998 A1* 5, 2002 Riddle et al. ......
`... 709,224
`2002/0122422 A1* 9/2002 Kenney et al. ....
`... 370,392
`
`ck
`
`(75) Inventors: Brett Galloway, Los Altos, CA (US); E. R. E. E.O."
`George Powers, Los Gatos, CA (US)
`* cited by examiner
`(73) Assignee: Packeteer, Inc., Cupertino, CA (US)
`Primary Examiner Chau T. Nguyen
`(*) Notice:
`Subject to any disclaimer, the term of this
`Assistant Examiner Timothy J. Weidner
`patent is extended or adjusted under 35
`(74) Attorney, Agent, or Firm Baker Botts L.L.P.
`U.S.C. 154(b) by 1239 days.
`(21) Appl. No.: 10/236,149
`
`(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) Ole OOC
`reference trees within selected traffic class nodes of a given
`traffic classification tree. In one embodiment, an administra
`tor 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 traffic 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.
`
`(22) Filed:
`
`Sep. 6, 2002
`
`(51) Int. Cl.
`(2006.01)
`H04L 2/26
`(2006.01)
`G06F 7/00
`(2006.01)
`HO4L 2/56
`(52) U.S. Cl. ....................................... 370/229; 370/412
`(58) Field of Classification Search ................. 370/392;
`711/221
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`6,105,062 A * 8/2000
`6,285,658 B1* 9/2001
`6,308,166 B1 * 10/2001
`6,385,649 B1* 5/2002
`6,587,466 B1* 7/2003
`6,816,456 B1 * 1 1/2004
`
`Andrews et al. ............ 709,223
`Packer ........................ 370,230
`Breuker et al. .............. TOS/400
`Draves et al. ............... TO9,224
`Bhattacharya et al. . 370/395.21
`Tse-Au .................... 370/230.1
`
`
`
`3.
`:::::: -
`
`%
`
`w
`
`
`
`
`
`28 Claims, 10 Drawing Sheets
`
`% (6. N sy
`
`33 a
`
`
`
`Splunk Inc. Exhibit 1036 Page 1
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 1 of 10
`
`US 7.433,304 B1
`
`
`
`Splunk Inc. Exhibit 1036 Page 2
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 2 of 10
`
`US 7.433,304 B1
`
`
`
`150
`
`Administrator
`Interface
`
`137
`
`
`
`Traffic
`
`Classification
`Database
`
`L Measurement
`Engine
`
`140
`
`
`
`
`
`Flow
`Database
`
`
`
`Data Packet
`In
`
`
`
`Packet
`Processor
`
`
`
`
`
`Host
`Database
`
`134
`
`Flow Control
`Module
`
`Data Packet
`Out
`
`131
`
`132
`
`Fig. 2
`
`Splunk Inc. Exhibit 1036 Page 3
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 3 of 10
`
`US 7.433,304 B1
`
`Receive Data
`Packet
`
`2O2
`
`204
`
`
`
`New Data
`Flow?
`
`Ye
`
`Control
`Block?
`
`Fetch/Update
`Control Block
`
`Construct
`Control Block
`
`Identify
`Traffic Class
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NO
`
`218
`
`Fetch/Update
`Control Block
`
`
`
`
`
`Changes
`To Flow?
`
`P = getControls
`(Traffic Class)
`
`Pass Packet to
`Flow Control
`Module (P)
`
`
`
`
`
`
`
`
`
`
`
`Record Bandwidth
`Utilization Data In
`Association with
`Traffic Class
`
`
`
`Splunk Inc. Exhibit 1036 Page 4
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 4 of 10
`
`US 7.433,304 B1
`
`
`
`Splunk Inc. Exhibit 1036 Page 5
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 5 of 10
`
`US 7.433,304 B1
`
`
`
`Splunk Inc. Exhibit 1036 Page 6
`
`

`

`U.S. Patent
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 6 of 10
`Sheet 6 of 10
`
`US 7.433,304 B1
`US 7,433,304 B1
`
`
`
`*apetergenreny,
`
`4yaag4boonesay)
`fo“tgVi
`
`"rerpeenttt
`
`myM
`
`(so)AHCJLOLS(WsQSS~ae
`iyms(orpreyon
`(«)aYSee*,>
`
`fetes
`
`Retires,
`
`pearMier,
`
`ey,
`
`uOrpue7)amOMebg>£8ene
`
`ttt,
`
`“hy
`
`\
`
`Y
`f
`
`Y S S S
`
`s
`
`ert,nri""enayBid
`fac)Ca),OLPYates,ye"tag
`inca”
`ommY
`
`ettonrayWeyos*yH
`
`Splunk Inc.
`
`Exhibit 1036
`
`Page 7
`
`Splunk Inc. Exhibit 1036 Page 7
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 7 of 10
`
`US 7.433,304 B1
`
`42c
`
`l
`Alia
`
`44c
`
`als
`
`
`
`40c
`y
`
`as
`
`E 44c
`
`60
`
`|
`
`Central Management
`Server
`
`
`
`Management
`Console
`
`64
`
`
`
`
`
`
`
`22c
`
`Computer
`Network
`
`
`
`42b
`
`4Ob
`y
`-
`Alia
`s
`-
`44b
`44b E |
`I
`42b
`
`9
`
`
`
`21b
`
`22b
`
`Splunk Inc. Exhibit 1036 Page 8
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 8 of 10
`
`US 7.433,304 B1
`
`
`
`
`
`
`
`Y
`$33
`Skiii. w
`
`
`
`
`
`it
`
`irises:
`a
`
`Qabout
`
`
`
`/ Qutbound
`
`wa-a-
`
`iiak. ...wei
`
`
`
`
`
`
`
`?ny
`a
`i
`/ ,
`
`Splunk Inc. Exhibit 1036 Page 9
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 9 of 10
`
`US 7.433,304 B1
`
`Computer
`Network
`
`
`
`40a
`
`
`
`Computer
`Network
`
`Splunk Inc. Exhibit 1036 Page 10
`
`

`

`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 10 of 10
`
`US 7.433,304 B1
`
`
`
`
`
`
`
`
`
`Node - Root
`Node
`
`
`
`
`
`
`
`
`
`Reference
`Tree?
`
`For All
`Reference Trees
`
`
`
`Tree = Next
`Referenced Tree; Node
`= Referenced Node
`
`End For All
`Reference
`Trees
`
`
`
`Retrieve Child
`Peer Nodes
`
`Matching
`Node?
`
`Return (Null)
`
`
`
`YeS
`
`Node =
`Matching Node
`
`Splunk Inc. Exhibit 1036 Page 11
`
`

`

`US 7,433,304 B1
`
`1.
`CLASSIFICATION DATASTRUCTURE
`ENABLING MULT-DIMIENSIONAL
`NETWORK TRAFFIC CLASSIFICATION AND
`CONTROL SCHEMES
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`2
`“Method for Automatically Classifying Traffic with
`Enhanced Hierarchy in a Packet Communications Network.”
`
`FIELD OF THE INVENTION
`
`The present invention relates to network traffic classifica
`tion mechanisms and, more particularly, to methods appara
`tuses and systems enabling a multi-dimensional network traf
`fic classification and control scheme.
`
`BACKGROUND OF THE INVENTION
`
`Efficientallocation 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 TCP/IP protocol suite, which implements
`the world-wide data communications network environment
`called the Internet and is employed in many 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 of juxtaposing 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 of certain embodiments
`of the invention, the following provides an explanation of
`certain technical aspects of a packet based telecommunica
`tions network environment. Internet/Intranet technology is
`based largely on the TCP/IP protocol suite. At the network
`level, IP provides a “datagram' delivery service that 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 of a byte stream between two IP 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 of unacknowledged 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 of the
`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 of unacknowl
`edged data. The timeout length is based on a running average
`of the Round Trip Time (RTT) for acknowledgement receipt,
`i.e., if an acknowledgement is not received within (typically)
`the smoothed RTT+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
`tive 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.
`
`This application makes reference to the following com
`monly owned U.S. patent applications and patents, which are
`10
`incorporated herein by reference in their entirety for all pur
`poses:
`U.S. patent application Ser. No. 08/762,828 now U.S. Pat.
`No. 5,802,106 in the name of Robert L. Packer, entitled
`“Method for Rapid Data Rate Detection in a Packet Commu
`15
`nication Environment Without Data Rate Supervision:
`U.S. patent application Ser. No. 08/970,693 now U.S. Pat.
`No. 6,018,516, in the name of Robert L. Packer, entitled
`“Method for Minimizing Unneeded Retransmission of Pack
`ets in a Packet Communication Environment Supporting a
`Plurality of Data Link Rates.”
`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 Commu
`nication Environment without Data Rate Supervision.”
`25
`U.S. patent application Ser. No. 09/977,642 now U.S. 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
`Network:
`U.S. patent application Ser. No. 09/106,924 now U.S. Pat.
`No. 6,115,357, in the name of Robert L. Packer and Brett D.
`Gallow way, entitled “Method for Pacing Data Flow in a
`Packet-based Network:
`U.S. patent application Ser. No. 09/046,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 TCPWindow Size:
`U.S. patent application Ser. No. 09/479.356 now U.S. Pat.
`No. 6,285,658, 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
`Network:
`U.S. patent application Ser. No. 09/198,090 now U.S. Pat.
`No. 6,412,000, in the name of Guy Riddle and Robert L.
`Packer, entitled “Method for Automatically Classifying Traf
`fic in a Packet Communications Network:
`U.S. patent application Ser. No. 09/198,051, in the name of
`Guy Riddle, entitled “Method for Automatically Determining
`a Traffic Policy in a Packet Communications Network:
`50
`U.S. patent application Ser. No. 09/206,772, in the name of
`Robert L. Packer, Brett D. Galloway and Ted Thi, entitled
`“Method for Data Rate Control for Heterogeneous or Peer
`Internetworking:
`U.S. patent application Ser. No. 09/966.538, in the name of
`55
`Guy Riddle, entitled “Dynamic Partitioning of Network
`Resources:
`U.S. patent application Ser. No. 10/039,992, in the Michael
`J. Quinn and Mary L. Laier, entitled “Method and Apparatus
`for Fast Lookup of Related Classification Entities in a Tree
`Ordered Classification Hierarchy:
`U.S. patent application Ser. No. 10/108,085, in the name of
`Wei-Lung Lai, Jon Eric Okholm, and Michael J. Quinn,
`entitled “Output Scheduling Data Structure Facilitating Hier
`archical Network Resource Allocation Scheme; and
`U.S. patent application Ser. No. 10/155,936, in the name of
`Guy Riddle, Robert L. Packer and Mark Hill, entitled
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`Splunk Inc. Exhibit 1036 Page 12
`
`

`

`US 7,433,304 B1
`
`10
`
`15
`
`3
`A crude form of bandwidth management in TCP/IP 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 TCP 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
`TCP 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 retransmission of data
`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 inbound 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.S. 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 of data transmission from
`a sending host, resulting in just-in-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, U.S. Pat. No.
`6,412,000, above, discloses automatic classification of net
`work traffic for use in connection and bandwidth allocation
`mechanisms. U.S. 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 and/or 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 some net
`work devices, these partitions can be configured to ensure a
`minimum bandwidth and/or 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 and/or maximum bandwidth. Such partitions can
`be applied on a per-application basis (protecting and/or cap
`ping bandwidth for all traffic associated with an application)
`or a per-user basis (protecting and/or capping bandwidth for
`aparticular 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.
`
`4
`To facilitate the implementation, configuration and man
`agement 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. In addition, each ACE
`has an associated action that indicates what the routing sys
`tem should do with the packet when a match occurs. ACLs
`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
`ACL into a hash table to expedite the look up process during
`operation of the system.
`In addition, U.S. 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 of traffic 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. In
`addition, patent application Ser. No. 10/039,992 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 of traffic classification and/or policy configu
`rations or configuration Subsets in a manner that is consistent
`across different deployment modes.
`In light of the foregoing, a need in the art exists for meth
`ods, apparatuses and systems allowing for a traffic classifica
`tion scheme that facilitates configuration of 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
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Splunk Inc. Exhibit 1036 Page 13
`
`

`

`5
`work devices employing traffic classification functionality, or
`within a single network device. Embodiments of the present
`invention substantially fulfill these needs.
`
`SUMMARY OF THE INVENTION
`
`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-dimensional,
`hierarchical network resource allocation schemes. The
`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 traffic 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
`traffic 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 and 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
`of policy sharing across multiple links. The present invention,
`in one embodiment, also facilitates the implementation of a
`system or domain-level workflow interface that features man
`aged access links as configurable objects as opposed to the
`network devices operating on the access links.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`DESCRIPTION OF THE DRAWINGS
`
`40
`
`45
`
`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 functional 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 multi-dimensional traf
`fic classification scheme for a given access link according to
`an embodiment of the present invention.
`FIG. 4B is a diagram illustrating a prior art hierarchical
`traffic classification configuration required to approximate
`the multi-dimensional traffic classification scheme depicted
`in FIG. 4A.
`FIG. 4C is a diagram illustrating a multi-dimensional traf
`fic classification scheme according to another embodiment of
`the present invention.
`FIG.5 is a functional block diagram illustrating a computer
`network environment including a plurality of bandwidth
`management devices operably connected to a central man
`60
`agement server according to an embodiment of the present
`invention.
`FIG. 6 is a diagram illustrating a multi-dimensional traffic
`classification scheme for a plurality of access links.
`FIG. 7A is a functional block diagram illustrating a com
`65
`puter network environment in which a single bandwidth man
`agement device manages data flows traversing a plurality of
`
`50
`
`55
`
`US 7,433,304 B1
`
`6
`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.
`TA
`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
`EMBODIMENT(S)
`I. Exemplary Operating Environment
`
`FIG. 1 sets forth a packet-based computer network envi
`ronment including a bandwidth management device 30. As
`FIG. 1 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 50 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 and 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 communications environment,
`employing TCP/IP protocols, and/or 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 flows and, depending on the classi
`fication, enforce respective bandwidth utilization controls on
`the data flows to control bandwidth utilization across and
`optimize network application performance across access link
`21. In addition, FIG. 7 illustrates an alternative deployment
`configuration for bandwidth management device 30. As FIG.
`7 shows, bandwidth management device 30 is deployed in an
`Internet Service Provider(ISP) domain 52 to manage network
`traffic between a plurality of separate local area networks 40a,
`40b, 40c and wide area network 50.
`A. Bandwidth Management Device
`FIG. 2 is a block diagram illustrating functionality, accord
`ing to one embodiment of the 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 flows, as
`discussed more fully below. In one embodiment, traffic clas
`sification engine 137 stores traffic classes associated with
`data flows encountered during operation of bandwidth 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 engine 137 stores traffic classes, in association with
`pointers to bandwidth utilization controls or pointers to data
`
`Splunk Inc. Exhibit 1036 Page 14
`
`

`

`US 7,433,304 B1
`
`10
`
`15
`
`7
`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 an aggregate and/or per-traffic-class
`level.
`Administrator interface 150 facilitates the configuration of
`bandwidth management device 30 to adjust or change opera
`tional and configuration parameters associated with the
`device. For example, administrator interface 150 allows
`administrators to select identified traffic classes and associate
`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
`In 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' and “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 from examination of data 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 flow 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
`TCP 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 traffic 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 blockhashtable
`including a key comprising a hashed value computed from a
`string comprising the inside IP address, outside IP address,
`inside port number, outside port number, and protocol type
`(e.g., TCP, UDP, etc.) associated with a pointer to the corre
`
`8
`sponding 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 acc