I 1111111111111111 11111 111111111111111 111111111111111 IIIII IIIIII IIII IIII IIII
`US008843634B2
`
`c12) United States Patent
`Riddle
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,843,634 B2
`Sep.23,2014
`
`(58) Field of Classification Search
`CPC ....................................................... H04L 65/80
`USPC .. .. ... ... ... ... ... .. ... ... ... ... .. ... ... ... ... ... .. ... ... 709/226
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`(54) PARTITION CONFIGURATION AND
`CREATION MECHANISMS FOR NETWORK
`TRAFFIC MANAGEMENT DEVICES
`
`(75)
`
`Inventor: Guy Riddle, Los Gatos, CA (US)
`
`(73) Assignee: Blue Coat Systems, Inc., Sunnyvale, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 556 days.
`
`(21) Appl. No.: 13/080,928
`
`(22) Filed:
`
`Apr. 6, 2011
`
`(65)
`
`Prior Publication Data
`
`6,412,000 Bl*
`6,430,154 Bl
`6,591,299 B2
`6,647,419 Bl
`6,735,633 Bl *
`7,453,804 Bl
`2003/0061263 Al*
`2004/0199635 Al
`2005/0249220 Al
`2006/0080273 Al *
`2006/0190482 Al*
`
`6/2002 Riddle et al. .................. 709/224
`8/2002 Hunt et al.
`7/2003 Riddle et al.
`11/2003 Mogul
`5/2004 Welch et al.
`11/2008 Feroz et al.
`3/2003 Riddle
`10/2004 Ta et al.
`11/2005 Olsen et al.
`4/2006 Degenaro et al.
`8/2006 Kishan et al.
`
`.......... 709/233
`
`.......... 709/104
`
`................. 707 /l
`707/103 Y
`
`US 2011/0182180Al
`
`Jul. 28, 2011
`
`* cited by examiner
`
`Related U.S. Application Data
`
`(63)
`
`Continuation of application No. 11/241,007, filed on
`Sep. 30, 2005, now Pat. No. 7,925,756.
`
`Primary Examiner - Oleg Survillo
`Joseph M Cousins
`Assistant Examiner -
`(74) Attorney, Agent, or Firm - Baker Botts L.L.P.
`
`(51)
`
`(52)
`
`(2006.01)
`(2013.01)
`(2013.01)
`(2006.01)
`(2013.01)
`(2013.01)
`
`Int. Cl.
`G06F 151173
`H04L 121873
`H04L 121801
`H04L 12124
`H04L 121869
`H04L 12/851
`U.S. Cl.
`CPC .......... H04L 4110893 (2013.01); H04L 471522
`(2013.01); H04L 47110 (2013.01); H04L
`4110896 (2013.01); H04L 47/2441 (2013.01);
`H04L 47160 (2013.01)
`709/226; 340/2.8; 340/2.9; 370/431;
`711/150
`
`USPC
`
`ABSTRACT
`(57)
`Partition configuration and creation mechanisms for network
`traffic management devices. In some implementations, the
`present invention enhances the predictability of partition hier(cid:173)
`archies that use weighting values and fixed rate guarantees. In
`some implementations, the present invention includes a con(cid:173)
`figuration interface that constrains the manner in which par(cid:173)
`titions can be configured to achieve predictable and efficient
`results. In some implementations, the present invention
`includes a partition creation and deletion layer that operates
`to dynamically create partitions based on one or more parti(cid:173)
`tion patterns.
`
`13 Claims, 10 Drawing Sheets
`
`VMWARE 1021
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 1 of 10
`
`US 8,843,634 B2
`
`43
`
`21a
`
`22b
`
`21
`
`Cc
`ess -l.
`
`22
`
`50
`
`Fig._1
`
`(Inside)
`
`130
`
`40
`
`44
`
`IIE:I
`E!!!9
`liiiJ
`
`(
`
`42
`
`42
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 2 of 10
`
`US 8,843,634 B2
`
`50
`
`44
`
`130
`
`Application Traffic Management
`Device
`
`Network Device Application
`Processor
`
`Packet
`Processor
`
`Flow Control
`Module
`
`Traffic
`Classification
`Engine
`
`Flow
`Database
`
`Host
`Database
`
`Measurement
`Engine
`
`Administrator
`Interface
`
`72
`
`92
`
`96
`
`135
`
`140
`
`75
`
`Fig._2
`
`42
`
`71
`
`94
`
`76
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 3 of 10
`
`US 8,843,634 B2
`
`Processor
`
`900
`
`~
`
`902
`
`904
`
`924
`
`925
`
`Cache
`
`Network
`Interface
`
`Network
`Interface
`
`Host Bridge
`
`910
`
`High Performance I/O Bus 2.D.6.
`
`912
`
`914
`
`I/O Bus
`Bridge
`
`System
`Memory
`
`Standard I/O Bus .2Q8_
`
`920
`
`926
`
`Mass Storage
`
`I/O Ports
`
`Fig._2A
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 4 of 10
`
`US 8,843,634 B2
`
`202
`
`Receive
`Packet
`
`206
`
`No
`
`Construct
`Flow Object
`
`207
`
`Compute Initial
`Flow Rate
`
`208
`
`Update Flow
`Object Attributes
`
`Pass Packet Pointer to
`T raffle Classification
`Engine
`
`Pass Packet Pointer to Flow
`Control Module
`
`214
`
`216
`
`218
`
`Record Measurement
`Statistics
`
`Fig._3
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 5 of 10
`
`US 8,843,634 B2
`
`Read Packet onto
`Flow and Partition
`Queues
`
`302
`
`304
`
`Receive
`Packet
`
`Identify
`Partition
`
`314
`
`Push Packet on
`Flow Queue
`
`308
`
`312
`
`316
`
`Fig._4A
`
`Instantiate Partition( s)
`in Output Scheduling -~-(cid:173)
`Data Structure
`
`Create Flow Queue;
`Push Packet on Flow
`Queue
`
`Recompute Per-Flow
`Bandwidth Allocation
`for Partition
`
`Push Flow Queue
`onto Low Priority
`Partition Queue
`
`Apply Per-Flow
`Rate Modification
`to Packet
`
`324
`
`322
`
`Push Flow Queue
`onto High Priority
`Partition Queue
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 6 of 10
`
`US 8,843,634 B2
`
`Read Packet from
`Selected Partition
`onto Output Queue
`
`352
`
`Q = Low Priority
`Partition Queue
`
`351
`
`Q = High Priority
`Partition Queue
`
`Find Queue
`Priority
`
`Priority = Low
`
`Return
`
`Fig._4C
`
`356
`3 7 4
`
`Priority=
`High
`
`Pop Flow
`Queue from Q
`
`Pop Packet from
`Flow Queue
`
`Push Packet onto
`Output Queue
`
`354
`
`Fig._4B
`
`358
`
`362
`
`Delete Flow
`Queue
`
`Find Queue
`Priority
`
`Push Flow Queue onto
`Low/High Priority
`Partition Queue
`
`Update Partition
`Time Stamp based
`on Partition Rate
`
`366
`
`368
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 7 of 10
`
`US 8,843,634 B2
`
`Partition Configuration
`
`Fig._6
`
`55
`
`Packet
`Processing
`
`0 Partition Queues
`
`75
`------.[)
`Output Scheduling
`Data Structure
`
`p 5 {
`
`'~' p~'----r------r----,---,------,---,--,
`jhpl
`
`80
`
`Output Queue
`
`Output 0
`
`Scheduling
`Process
`
`In
`
`{
`
`p 7
`
`P8
`
`{
`
`IIPI
`L..:I hp....L..I --'-----'----'----'--'--__._____,I
`
`Fig. -5
`
`L . ! I lp_J_I --'---'---_i__.'----'-__,__---'~
`60a
`
`IL...; h P'-'-1 --'-----'----'-----'-__,___....,__~
`60b
`
`

`

`~
`
`Fig._7A
`
`~ rt a
`
`V1 .
`d
`
`~
`~
`~
`... O'\
`~
`~
`
`~ ---~
`rJ1
`d
`
`0
`~
`0 ...,
`00
`~
`~
`rJ1 ::r
`
`~
`0
`N
`V'
`N
`~
`rJ1
`
`"""
`
`

`

`~ e
`
`Fig._7B
`
`0
`,...
`0 .....
`-a
`~
`~ (0
`
`N
`~
`N
`~
`
`""'
`0 ,...
`
`r.,:i
`
`~ "°' ~
`
`~
`
`"1:$;
`1:$;
`00
`d
`
`~ rt a
`
`(11 .
`d
`
`

`

`U.S. Patent
`
`Sep.23,2014
`
`Sheet 10 of 10
`
`US 8,843,634 B2
`
`502
`
`504
`
`506
`
`508
`
`Find
`Partition
`
`Apply
`Classification
`Rule(s)
`
`Apply Policy
`Action to Identify
`Partition
`
`Access Partition
`Pattern to Create
`Partition
`
`Fig._8
`
`

`

`US 8,843,634 B2
`
`1
`PARTITION CONFIGURATION AND
`CREATION MECHANISMS FOR NETWORK
`TRAFFIC MANAGEMENT DEVICES
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation of U.S. application Ser.
`No. 11/241,007 filed Sep. 30, 2005, entitled "Partition Con(cid:173)
`figuration and Creation Mechanisms for Network Traffic
`Management Devices," now U.S. Pat. No. 7,925,756.
`This application makes reference to the following com(cid:173)
`monly owned U.S. patent applications and patents, which are
`incorporated herein by reference in their entirety for all pur(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`work, Transport andApplication Layers in Store and Forward
`Network;"
`U.S. patent application Ser. No. 09/106,924 now U.S. Pat. 35
`No. 6,115,357, in the name of Robert L. Packer and Brett D.
`Galloway, entitled "Method for Pacing Data Flow in a Packet(cid:173)
`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 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
`"System for Managing Flow Bandwidth Utilization at Net(cid:173)
`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.
`Packer, entitled "Method for Automatically Classifying Traf(cid:173)
`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;"
`U.S. patent application Ser. No. 09/206,772, now U.S. Pat. 55
`No. 6,456,360, in the name of Robert L. Packer, Brett D.
`Galloway and Ted Thi, entitled "Method for Data Rate Con(cid:173)
`trol for Heterogeneous or Peer Intemetworking;"
`U.S. patent application Ser. No. 09/710,442, in the name of
`Todd Krautkremer and Guy Riddle, entitled "Application 60
`Service Level Mediation and Method of Using the Same;"
`U.S. patent application Ser. No. 09/966,538, in the name of
`Guy Riddle, entitled "Dynamic Partitioning of Network
`Resources;"
`U.S. patent application Ser. No. 10/015,826 in the name of
`Guy Riddle, entitled "Dynamic Tunnel Probing in a Commu(cid:173)
`nications Network;"
`
`25
`
`2
`U.S. patent application Ser. No. 10/039,992, in the name of
`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(cid:173)
`archical Network Resource Allocation Scheme;"
`U.S. patent application Ser. No. 10/178,617, in the name of
`10 Robert E. Purvy, entitled "Methods, Apparatuses and Sys(cid:173)
`tems Facilitating Analysis of Network Device Performance;"
`U.S. patent application Ser. No. 10/155,936 now U.S. Pat.
`No. 6,591,299, in the name of Guy Riddle, Robert L. Packer,
`and Mark Hill, entitled "Method For Automatically Classify-
`15 ing Traffic With Enhanced Hierarchy In A Packet Communi(cid:173)
`cations Network;"
`U.S. patent application Ser. No. 10/236,149, in the name of
`Brett Galloway and George Powers, entitled "Classification
`Data Structure enabling Multi-Dimensional Network Traffic
`20 Classification and Control Schemes;"
`U.S. patent application Ser. No. 10/334,467, in the name of
`Mark Hill, entitled "Methods, Apparatuses and Systems
`Facilitating Analysis of the Performance of Network Traffic
`Classification Configurations;"
`U.S. patent application Ser. No. 10/453,345, in the name of
`Scott Hankins, Michael R. Morford, and Michael J. Quinn,
`entitled "Flow-Based Packet Capture;"
`U.S. patent application Ser. No. 10/676,383 in the name of
`Guy Riddle, entitled "Enhanced Flow Data Records Includ-
`30 ing Traffic Type Data;"
`U.S. patent application Ser. No. 10/720,329, in the name of
`Weng-Chin Yung, Mark Hill and Anne Cesa Klein, entitled
`"Heuristic Behavior Pattern Matching of Data Flows in
`Enhanced Network Traffic Classification;"
`U.S. patent application Ser. No. 10/812,198 in the name of
`Michael Robert Morford and Robert E. Purvy, entitled
`"Adaptive, Application-Aware Selection of Differentiated
`Network Services;"
`U.S. patent application Ser. No. 10/843, 185 in the name of
`40 Guy Riddle, Curtis Vance Bradford and Maddie Cheng,
`entitled "Packet Load Shedding;"
`U.S. patent application Ser. No. 10/938,435 in the name of
`Guy Riddle, entitled "Classification and Management of Net(cid:173)
`work Traffic Based on Attributes Orthogonal to Explicit
`45 Packet Attributes;"
`U.S. patent application Ser. No. 11/027,744 in the name of
`Mark Urban, entitled "Adaptive Correlation of Service Level
`Agreement and Network Application Performance;" and
`U.S. application Ser. No. 11/053,596 in the name of Azeem
`50 Feroz, Wei-Lung Lai, Roopesh Varier, James Stabile and Eric
`Okholm, entitled "Aggregate Network Resource Utilization
`Control Scheme."
`
`FIELD OF THE INVENTION
`
`The present invention relates to network traffic manage(cid:173)
`ment systems and, more particularly, to methods, apparatuses
`and systems directed to partition configuration and creation
`mechanisms that enhance the predictability and use of net(cid:173)
`work resource allocation schemes.
`
`BACKGROUND OF THE INVENTION
`
`Enterprises have become increasingly dependent on com-
`65 puter network infrastructures to provide services and accom(cid:173)
`plish mission-critical tasks. Indeed, the performance, secu(cid:173)
`rity, and efficiency of these network infrastructures have
`
`

`

`US 8,843,634 B2
`
`3
`become critical as enterprises increase their reliance on dis(cid:173)
`tributed computing environments and wide area computer
`networks. To that end, a variety of network devices have been
`created to provide data gathering, reporting, and/or opera(cid:173)
`tional functions, such as firewalls, gateways, packet capture
`devices, bandwidth management devices, application traffic
`monitoring devices, and the like. For example, the TCP/IP
`protocol suite, which is widely implemented throughout the
`world-wide data communications network environment
`called the Internet and many wide and local area networks,
`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 character(cid:173)
`istic has the consequence of juxtaposing very high-speed
`packets and very low-speed packets in potential conflict and
`produces certain inefficiencies. Certain loading conditions
`degrade performance of networked applications and can even
`cause instabilities which could lead to overloads that could
`stop data transfer temporarily.
`To facilitate monitoring, management and control of net(cid:173)
`work environments, a variety of network devices, applica(cid:173)
`tions, technologies and services have been developed. For
`example, certain data flow rate control mechanisms have been
`developed to provide a means to control and optimize effi(cid:173)
`ciency of data transfer as well as allocate available bandwidth
`among a variety of business enterprise functionalities. For
`example, U.S. Pat. No. 6,038,216 discloses a method for
`explicit data rate control in a packet-based network environ(cid:173)
`ment 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 buffering of packets, and reduce the inefficiencies
`associated with dropped packets. Bandwidth management
`devices also 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 network traffic for use in connection with
`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 administrators to specify policies operative to
`control and/or prioritize the bandwidth allocated to individual
`data flows according to traffic classifications. In addition,
`certain bandwidth management devices, as well as certain
`routers, allow network administrators to specify aggregate
`bandwidth utilization controls to divide available bandwidth
`into partitions. With some network devices, these partitions
`can be configured to provide a minimum bandwidth guaran(cid:173)
`tee, and/or cap bandwidth, as to a particular class of traffic. An 50
`administrator specifies a traffic class (such as FTP data, or
`data flows involving a specific user or network application)
`and the size of the reserved virtual link-i.e., minimum guar(cid:173)
`anteed bandwidth and/or maximum bandwidth. Such parti(cid:173)
`tions can be applied on a per-application basis (protecting 55
`and/or capping bandwidth for all traffic associated with an
`application) or a per-user basis ( controlling, prioritizing, pro(cid:173)
`tecting and/or capping bandwidth for a particular user). In
`addition, certain bandwidth management devices allow
`administrators to define a partition hierarchy by configuring 60
`one or more partitions dividing the access link and further
`dividing the parent partitions into one or more child parti(cid:173)
`tions. U.S. patent application Ser. No. 10/108,085 discloses
`data structures and methods for implementing a partition
`hierarchy.
`Certain network traffic management devices, such as the
`PacketShaper® network traffic management device, offered
`
`4
`by Packeteer®, Inc. of Cupertino, Calif., support the concur(cid:173)
`rent use ofaggregate bandwidth policies ( e.g., partitions), and
`per-flow bandwidth policies, such as rate policies enforced by
`the TCP Rate control technologies disclosed in U.S. Pat. No.
`6,038,216. A partition is essentially a bandwidth allocation
`and queuing mechanism. That is, after a packet processor
`classifies each packet and enqueues each packet onto a parti(cid:173)
`tion queue associated with the appropriate partition, another
`process, typically, loops through the partition queues to
`10 dequeue packets off the queues and populate an output queue.
`Aggregate bandwidth allocation among the different parti(cid:173)
`tions essentially establishes a preference by which a flow
`control mechanism arbitrates among the corresponding par-
`15 titian queues. For example, a flow control module, while
`arbitrating among the partition queues, may read more pack(cid:173)
`ets from partitions having a higher allocation of bandwidth
`relative to partitions that have lower allocations. For example,
`as disclosed in U.S. application Ser. No. 10/108,085, incor-
`20 porated by reference above, the bandwidth allocated to a
`given partition affects the rate at which the partition is
`selected by an output scheduling process and therefore the
`length of time packets are buffered in the corresponding par(cid:173)
`tition queue. In addition, TCP Rate Control technologies can
`25 be used to effect per-flow rate policies to control or influence
`the rate at which packets are received at a network device and,
`therefore, use of inbound network bandwidth and the amount
`of data that is queued at any given time.
`While partitions and per-flow rate policies are effective for
`30 their intended purposes, the proper configuration of partitions
`in conjunction with per-flow policies can be problematic. For
`example, network traffic application systems allow users to
`configure minimum and/or maximum bandwidth guarantees
`for one or more partitions. To simply configuration, some
`35 network traffic management systems also allow users to con(cid:173)
`figure a weighting or priority scheme for partitions and/or
`data flows that indicate the relative importance of the network
`traffic falling within a partition or matching a given traffic
`classification. The network traffic management device itself
`40 applies these weighting parameters using conventional algo(cid:173)
`rithms. During execution, the weighing or priority values,
`however, are often difficult to reconcile with the minimum
`and maximum bandwidth guarantees corresponding to one or
`more partitions, as it can become problematic to allocate
`45 bandwidth to data flows using weights, while at the same time
`observing the minimum and/or maximum guarantees associ(cid:173)
`ated with one or more partitions. The resulting effect from
`various configurations can be unpredictable, and also far from
`what the user intended.
`In light of the foregoing, a need in the art exists for meth-
`ods, apparatuses and systems directed to bandwidth control
`mechanism that addresses the problems discussed above.
`Embodiments of the present invention substantially fulfill this
`need.
`
`SUMMARY OF THE INVENTION
`
`The present invention provides methods, apparatuses and
`systems directed to partition configuration and creation
`mechanisms for network traffic management devices. In
`some implementations, the present invention enhances the
`predictability of partition hierarchies that use weighting val(cid:173)
`ues and fixed rate guarantees. In some implementations, the
`present invention includes a configuration interface that con-
`65 strains the manner in which partitions can be configured to
`achieve predictable and efficient results. In some implemen(cid:173)
`tations, the present invention includes a partition creation and
`
`

`

`US 8,843,634 B2
`
`5
`deletion layer that operates to dynamically create partitions
`based on one or more partition patterns.
`
`DESCRIPTION OF THE DRAWING(S)
`
`FIG.1 is a functional block diagram illustrating a computer
`network system architecture in which an embodiment of the
`present invention may operate.
`FIG. 2 is a functional block diagram illustrating the func(cid:173)
`tionality of a network traffic management device, according 10
`to one implementation of the present invention.
`FIG. 2A is functional block diagram illustrating the hard(cid:173)
`ware components of a network device according to one
`implementation of the present invention.
`FIG. 3 is a flow chart diagram showing a method, according 15
`to one implementation of the present invention, directed to
`processing data flows.
`FIG. 4A is a flow chart diagram illustrating a process
`involving placing a packet onto a flow queue and a partition
`queue.
`FIG. 4B is a flow chart diagram providing a method involv(cid:173)
`ing scheduling a packet for output from an network traffic
`management device.
`FIG. 4C is a flow chart diagram illustrating the decisional
`logic associated with placing a flow queue onto a high priority
`or low priority partition queue.
`FIG. 5 is a process flow diagram illustrating the overall
`process flow associated with the scheduling of packets for
`output.
`FIG. 6 sets forth an exemplary hierarchical partition con(cid:173)
`figuration according to an embodiment of the present inven(cid:173)
`tion.
`FIGS. 7A and 7B illustrate exemplary hierarchical parti(cid:173)
`tion configurations according to another embodiment of the
`present invention.
`FIG. 8 is a flow chart diagram illustrating operation of a
`partition creation and deletion layer according to one imple(cid:173)
`mentation of the present invention.
`
`6
`implementation, is deployed at the edge of network 40. As
`discussed more fully below, network traffic management
`device 130 is operative to classify and manage data flows
`traversing access link 21. In one implementation, network
`traffic management device 130 also includes functionality
`operative to monitor the performance of the network (such as
`network latency) and/or network applications. Network traf(cid:173)
`fic management device 130 may be disposed at a variety of
`locations in a network environment to control data flow and
`partition access to resources.
`As FIG. 2 illustrates, network traffic management device
`130, in one implementation, comprises network device appli(cid:173)
`cation processor 75, and first and second network interfaces
`71, 72, which operably connect network traffic management
`device 130 to the communications path between router 22 and
`network 40. Network device application processor 75 gener-
`ally refers to the functionality implemented by network traffic
`management device 130, such as network traffic management
`functionality described herein. As described in more detail
`20 below, in one embodiment, network device application pro(cid:173)
`cessor 75 is a combination of hardware and software, such as
`a central processing unit, memory, a system bus, an operating
`system, device drivers, and one or more software modules
`implementing the functions performed by network traffic
`25 management device 130. For didactic purposes, network traf(cid:173)
`fic management device 130 is configured to manage network
`traffic traversing access link 21. The above-identified patents
`and patent applications, incorporated by reference herein,
`disclose various functionalities and features that may be
`30 incorporated into network traffic management devices
`according to various implementations of the present inven(cid:173)
`tion.
`In one embodiment, first and second network interfaces 71,
`72 are the hardware communications interfaces that receive
`35 and transmit packets over the computer network environ(cid:173)
`ment. In one implementation, first and second network inter(cid:173)
`faces 71, 72 reside on separate network interface cards oper(cid:173)
`ably connected to the system bus of network traffic
`management device 130. In another implementation, first and
`40 second network interfaces reside on the same network inter(cid:173)
`face card. In addition, the first and second network interfaces
`71, 72 can be wired network interfaces, such as Ethernet
`(IEEE 802.3) interfaces, and/or wireless network interfaces,
`such as IEEE 802.11, BlueTooth, satellite-based interfaces,
`45 and the like. As FIG. 2 illustrates, network traffic manage(cid:173)
`ment device 130, in one embodiment, includes persistent
`memory 76, such as a hard disk drive or other suitable
`memory device, such writable CD, DVD, or tape drives. In
`other implementations, network traffic management device
`50 130 can include additional network interfaces, beyond net(cid:173)
`work interfaces 71 and 72, to support additional access links
`or other functionality. Furthermore, U.S. application Ser. No.
`10/843, 185 provides a description of the operation of various
`modules (according to one possible implementation of the
`55 present invention), such as network interface drivers, and data
`structures for receiving into memory and processing packets
`encountered at network interfaces 71, 72.
`FIG. 2A illustrates for didactic purposes an exemplary
`computing platform, and hardware architecture, for network
`60 device 30. In one implementation, network device 30 com(cid:173)
`prises a processor 902, a system memory 914, network inter(cid:173)
`faces 924 & 925, and one or more software applications
`(including network device application 75 shown in FIG. 2)
`and drivers enabling the functions described herein.
`The present invention can be implemented on a wide vari(cid:173)
`ety of computer system architectures. For example, FIG. 2A
`illustrates, hardware system 900 having components suitable
`
`DESCRIPTION OF PREFERRED
`EMBODIMENT(S)
`
`FIG. 1 illustrates an exemplary network environment in
`which embodiments of the present invention may operate. Of
`course, the present invention can be applied to a variety of
`network architectures. FIG. 1 illustrates, for didactic pur(cid:173)
`poses, a network 50, such as wide area network, interconnect(cid:173)
`ing a first enterprise network 40, supporting a central operat(cid:173)
`ing or headquarters facility, and a second enterprise network
`40a, supporting a branch office facility. Network 50 may also
`be operably connected to other networks, such as network
`40b, associated with the same administrative domain as net(cid:173)
`works 40, 40a, or a different administrative domain.As FIGS.
`1 and 2 show, the first 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 network 40. The
`computer network environment, including network 40 and
`network 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(cid:173)
`sion stations or routing nodes. First network 40, and networks
`40a & 40b, can each be a local area network, a wide area 65
`network, or any other suitable network. As FIGS. 1 and 2
`illustrate, network traffic management device 130, in one
`
`

`

`US 8,843,634 B2
`
`8
`7
`for network device 30 in accordance with one implementation
`tern provides an interface between the software applications
`of the present invention. In the illustrated embodiment, the
`being executed on the system and the hardware components
`hardware system 900 includes processor 902 and a cache
`of the system. According to one embodiment of the present
`memory 904 coupled to each other as shown. Additionally,
`invention, the operating system is the Windows® 95/98/NT/
`the hardware system 900 includes a high performance input/
`XP operating system, available from Microsoft Corporation
`output (I/O) bus 906 and a standard I/O bus 908. Host bridge
`of Redmond, Wash. However, the present invention may be
`910 couples processor 902 to high performance I/O bus 906,
`used with other conventional operating systems, such as the
`whereas I/O bus bridge 912 couples the two buses 906 and
`Apple Macintosh Operating System, available from Apple
`908 to each other. Coupled to bus 906 are network/commu(cid:173)
`Computer Inc. of Cupertino, Calif., UNIX operating systems,
`nication interface 924, and system memory 914. The hard(cid:173)
`10 LINUX operating systems, and the like. Of course, other
`ware system may further include video memory (not shown)
`implementations are possible. For example, the functionality
`and a display device coupled to the video memory. Coupled to
`of network device 30 may be implemented by a plurality of
`bus 908 are mass storage 920 and I/O ports 926. The hardware
`server blades communicating over a backplane.
`system may optionally include a keyboard and pointing
`As FIG. 2 illustrates, network device application processor
`device (not shown) coupled to bus 908. Collectively, these 15
`75, in one implementation, includes a packet processor 92,
`elements are intended to represent a broad category of com(cid:173)
`flow control module 94, and traffic classification engine 96.
`puter hardware systems, including but not limited to general
`Network device application processor 75, in one implemen(cid:173)
`purpose computer systems based on the Pentium® processor
`tation, further comprises host database 134, flow database
`manufactured by Intel Corporation of Santa Clara, Calif., as
`20 135, measurement engine 140, management information
`well as any other suitable processor.
`base 138, and administrator interface 150. In one embodi(cid:173)
`The elements of computer hardware system 900 perform
`ment, the packet processor 92 is operative to process data
`their conventional functions known in the art. In particular,
`network interfaces 924, 925 are used to provide communica(cid:173)
`packets, such as detecting new data flows, parsing the data
`tion between system 900 and any of a wide range of networks,
`packets for various attributes (such as source and destination
`such as an Ethernet (e.g., IEEE 802.3) network, etc. Mass
`25 addresses, and the like) and storing packet attributes in a
`storage 920 is used to provide permanent storage for the data
`buffer structure, and maintaining one or more flow variables
`and progranmiing
`instructions
`to perform
`the above
`or statistics (such as packet count, current rate, etc.) in con(cid:173)
`described functions implemented in the system controller,
`nection with the data flows and/or the source/destination
`whereas system memory 914 ( e.g., DRAM) is used to provide
`hosts. The traffic classification engine 96, as discussed more
`temporary storage for the data and progranmiing instructions 30
`fully below, is operative to classify data flows, such as iden(cid:173)
`when executed by processor 902. I/O ports 926 are one or
`tify network applications corresponding to the flows, based
`more serial and/or parallel communication ports used to pro(cid:173)
`on one or more attributes of the data flows. In one implemen(cid:173)
`vide communication between additional peripheral devices,
`tation, traffic classification engine 96 is operative to apply one
`which may be coupled to hardware system 900.
`or more policy actions that are operative to identify partition
`Hardware system 900 may include a variety of system 35
`names