`
`(12) United States Patent
`Galloway et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,433,304 B1
`Oct. 7, 2008
`
`(54) CLASSIFICATION DATA STRUCTURE
`ENABLING MULTI-DIMENSIONAL
`NETWORK TRAFFIC CLASSIFICATION AND
`CONTROL SCHEMES
`
`(75)
`
`Inventors: Brett Galloway, Los Altos, CA (US);
`George Powers, Los Gatos, CA (US)
`
`(73)
`
`Assignee: Packeteer, Inc., Cupertino, CA (US)
`
`* )
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1239 days.
`
`(21)
`
`Appl. No.: 10/236,149
`
`(22)
`
`Filed:
`
`Sep. 6, 2002
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Int. CI.
`HO4L 12/26
`GO6F 7/00
`HO4L 12/56
`U.S. Cl.
`Field of Classification Search
`
`(2006.01)
`(2006.01)
`(2006.01)
`
` 370/229; 370/412
` 370/392;
`711/221
`See application file for complete search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
` 709/223
`6,105,062 A * 8/2000 Andrews et al.
` 370/230
`6,285,658 B1 * 9/2001 Packer
` 705/400
`6,308,166 Bl * 10/2001 Breuker et al.
` 709/224
`6,385,649 B1 *
`5/2002 Draves et al.
`6,587,466 B1 * 7/2003 Bhattacharya et al. . 370/395.21
`6,816,456 131* 11/2004 Tse-Au
` 370/230.1
`
`6,918,124 B1 * 7/2005 Novik et al.
`7,106,732 B2 * 9/2006 Brown
`2002/0023089 Al * 2/2002 Woo
`2002/0055998 Al *
`5/2002 Riddle et al.
`2002/0122422 Al * 9/2002 Kenney et al
`2003/0188065 Al * 10/2003 Golla et al.
`2003/0229623 Al * 12/2003 Chang et al.
`
`
`
`719/318
`370/389
`707/101
`709/224
`370/392
`710/243
`707/3
`
`* cited by examiner
`
`Primary Examiner—Chau 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 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.
`
`28 Claims, 10 Drawing Sheets
`
`81
`
`Access
`Link
`
`8-
`
`inbourel
`
`Outbound
`
`91
`
`AppiicetiOn
`
`TC1
`
`Tv
`
`8$
`
`Dept
`
`9)
`
`TC2
`
`• TC3
`
`TC4
`
`TC5
`
`C6
`
`T(7
`
`TC3'
`
`TC4'
`
`TC9
`
`TC6'
`
`TC2
`
`TC •
`
`91
`
`anditien
`
`TC9
`
`✓. I
`
`Cloudflare - Exhibit 1036, page 1
`
`Cloudflare - Exhibit 1036, page 1
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 1 of 10
`
`US 7,433,304 B1
`
`28
`
`50
`
`Computer
`Network
`
`26
`
`25
`
`24
`
`22
`
`42
`
`44
`
`40
`
`24
`
`24
`
`(Outside)
`
`Inside)
`
`Ca.
`
`30
`
`Fig._1
`
`42
`
`42
`
`Cloudflare - Exhibit 1036, page 2
`
`Cloudflare - 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
`
`135
`
`Flow
`Database
`
`Packet
`Processor
`
`Data Packet
`In
`
`140
`Measurement 1..)
`
`1
`
`Engine
`
`Host
`Database
`
`134
`
`riFlow
`
`Control
`Module
`
`Data Packet
`Out
`
`131
`
`132
`
`Fig._2
`
`Cloudflare - Exhibit 1036, page 3
`
`Cloudflare - Exhibit 1036, page 3
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 3 of 10
`
`US 7,433,304 B1
`
`Receive Data
`Packet
`
`202
`
`204
`
`Yes
`
`New Data
`Flow?
`
`218
`
`Fetch/Update
`Control Block
`
`220
`
`No
`
`Changes
`To Flow?
`
`208
`No
`
`Control
`Block?
`
`Yes
`
`210
`
`Fetch/Update
`Control Block
`
`212
`
`Construct
`Control Block
`
`Yes
`
`216
`
`Identify
`Traffic Class
`-J
`214
`
`P = getControls
`(Traffic Class)
`
`-4(
`
`Fig._3
`
`222
`
`J
`
`224
`
`J
`
`Pass Packet to
`Flow Control
`Module (P)
`
`Record Bandwidth
`Utilization Data In
`Association with
`Traffic Class
`
`Cloudflare - Exhibit 1036, page 4
`
`Cloudflare - Exhibit 1036, page 4
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 4 of 10
`
`US 7,433,304 B1
`
`2A\ o
`
`tl
`
`—
`
`r
`
`t3
`
`ti
`
`•
`
`io ;
`
`0
`.0
`
`'34
`
`.•-•\
`et
`
`<7t
`
`•
`
`at
`a
`
`ad
`
`•4:1' .
`V0 \
`
`ii
`
`C
`
`al
`..,...)
`
`1$
`.....-
`
`F
`
`at., y,
`
`(3,
`
`oo
`cf
`
`Cloudflare - Exhibit 1036, page 5
`
`Cloudflare - Exhibit 1036, page 5
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 5 of 10
`
`US 7,433,304 B1
`
`I N
`
`I
`
`eaa
`
`0
`
`0
`
`A
`
`I
`
`fat
`
`< :7;
`
`µ
`
`.0.•••••••..
`
`I
`
`k
`
`Fs
`
`O
`
`r)
`
`4
`s
`
`"Th
`
`emv,
`
`eTh
`
`Cloudflare - Exhibit 1036, page 6
`
`Cloudflare - Exhibit 1036, page 6
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 6 of 10
`
`US 7,433,304 B1
`
`t..
`
`ti
`
`;34\ g",,
`
`O
`
`5
`%.? ,C
`•cC
`
`O
`
`ea
`CO
`
`0.
`
`C.
`
`^M. ........
`
`-6_
`
`1-
`
`Cloudflare - Exhibit 1036, page 7
`
`Cloudflare - Exhibit 1036, page 7
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 7 of 10
`
`US 7,433,304 B1
`
`42c
`
`44c
`
`40c
`
`BEI
`EMI
`
`44c
`
`111111
`
`60
`
`Central Management
`Server
`
`42c
`
`BM Device
`Con fig. Database
`
`• . -
`
`30c
`
`21c
`
`22c
`
`1
`Management
`Console
`
`64
`
`42b
`
`62
`
`44b
`
`40b
`
`4c=6.
`1112
`
`44b
`
`111111
`
`42b
`
`04
`
`30b
`
`Computer
`Network
`
`21b
`
`22b
`
`22a
`
`40a
`
`43
`
`42a
`
`42a
`
`(Outside)
`
`Inside)
`
`WS!
`
`30a
`
`Fig._5
`
`42a
`
`42a
`
`44a
`
`Cloudflare - Exhibit 1036, page 8
`
`Cloudflare - Exhibit 1036, page 8
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 8 of 10
`
`US 7,433,304 B1
`
`95
`
`Admin
`Domain
`
`System Level
`
`96
`
`Link
`
`Link Level
`
`r.
`
`Link
`
`97
`
`Link
`h
`
`91
`
`96
`I
`
`95
`t
`
`96
`
`Link.
`3
`
`Virtual
`Sub Link
`
`Virtual
`Sub Link
`
`9'7
`
`98
`
`97
`
`98
`
`Inbound
`
`€3utbound.
`
`Inbound
`
`Outbound
`
`98
`
`Inbound
`
`€)utbounf
`
`Security
`
`TC1'
`
`F a. 6
`
`FC3"
`
`TC4'
`
`TC.51
`
`TC6'
`
`Traffic
`
`Q
`
`rcr
`
`€8'
`
`T€.2
`
`TC4
`
`TChi
`
`TC9
`
`Cloudflare - Exhibit 1036, page 9
`
`Cloudflare - Exhibit 1036, page 9
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 9 of 10
`
`US 7,433,304 B1
`
`WAN Link
`
`50
`
`Link
`
`Link
`2
`
`Link
`3
`
`WAN
`CLOUD
`
`Fig._7B
`
`52
`
`ISP CLOUD
`
`30
`
`40a
`
`Computer
`Network
`
`40c
`
`Computer
`Network
`
`24
`
`24
`
`24
`
`24
`
`24
`
`24
`
`40b
`
`Computer
`Network
`
`Fig._7A
`
`24
`
`24
`
`24
`
`Cloudflare - Exhibit 1036, page 10
`
`Cloudflare - Exhibit 1036, page 10
`
`
`
`U.S. Patent
`
`Oct. 7, 2008
`
`Sheet 10 of 10
`
`US 7,433,304 B1
`
`302
`
`Node --= Root
`Node
`
`304
`
`Reference
`Tree?
`
`No
`
`es
`
`308
`
`306
`
`For All
`Reference Trees
`
`Tree = Next
`Referenced Tree; Node
`= Referenced Node
`
`Fig._8
`
`Return
`Policy
`
`315
`
`316
`
`310
`
`
`
`312
`
`Child
`Nodes?
`
`314
`
`Retrieve Child
`Peer Nodes
`
`Goto A
`
`End For All
`Reference
`Trees
`
`Y
`
`318
`
`319
`
`Return (Null)
`
`Matching
`Node?
`
`Yes
`
`320
`
`Node =
`Matching Node
`
`Cloudflare - Exhibit 1036, page 11
`
`Cloudflare - Exhibit 1036, page 11
`
`
`
`US 7,433,304 B1
`
`1
`CLASSIFICATION DATA STRUCTURE
`ENABLING MULTI-DIMENSIONAL
`NETWORK TRAFFIC CLASSIFICATION AND
`CONTROL SCHEMES
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`5
`
`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
`
`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 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 perfonnance 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 (KIT) for acknowledgement receipt,
`i.e., if an acknowledgement is not received within (typically)
`the smoothed RTF+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 RIO). 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.
`Cloudflare - Exhibit 1036, page 12
`
`25
`
`30
`
`This application makes reference to the following com-
`monly owned U.S. patent applications and patents, which are to
`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- is
`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 20
`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;"
`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.
`Gallowway, entitled "Method for Pacing Data Flow in a
`Packet-based Network;"
`U.S. patent application Ser. No. 09/046,776 now U.S. Pat. 35
`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/479,356 now U.S. Pat.
`No. 6,285,658, in the name of Robert L. Packer, entitled 40
`"System for Managing Flow Bandwidth Utilization at Net-
`work, Transport andApplication 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. as
`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 forAutomatically Determining
`a Traffic Policy in a Packet Communications Network;"
`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- 60
`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
`
`so
`
`65
`
`Cloudflare - Exhibit 1036, page 12
`
`
`
`US 7,433,304 B1
`
`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
`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.
`
`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
`5 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
`10 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-
`ts 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
`20 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
`25 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.
`30 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
`35 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
`40 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 desk-
`45 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-
`50 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-
`ss renting 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
`60 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
`65 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-
`Cloudflare - Exhibit 1036, page 13
`
`Cloudflare - Exhibit 1036, page 13
`
`
`
`US 7,433,304 B1
`
`5
`work devices employing traffic classification functionality, or
`within a single network device. Embodiments of the present
`invention substantially fulfill these needs.
`
`SUMMARY OF TI IF, INVENTION
`
`5
`
`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 to
`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 15
`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 20
`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 25
`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 workflow interface that features man-
`aged access links as configurable objects as opposed to the
`network devices operating on the access links.
`
`30
`
`35
`
`DESCRIPTION OF THE DRAWINGS
`
`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.
`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
`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
`Cloudflare - Exhibit 1036, page 14
`
`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- S5
`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
`
`Cloudflare - Exhibit 1036, page 14
`
`
`
`US 7,433,304 B1
`
`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. Fora 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 para