(12)
`
`United States Patent
`Riddle
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,385,924 B1
`Jun. 10, 2008
`
`USOO7385924B1
`
`(54) ENHANCED FLOW DATA RECORDS
`INCLUDING TRAFFIC TYPE DATA
`
`(75) Inventor: Guy Riddle, Los Gatos, CA (US)
`
`M
`
`YW-
`
`y
`
`ayS.
`
`3/2004 Calabrez et al.
`6,701,359 B1
`6,738,352 B1* 5/2004 Yamada et al. ............. 370.238
`6,798,763 B1
`9/2004 Kimura et al.
`... 370,229
`6,894,972 B1* 5/2005 Phaal - - - - -
`... 726, 13
`7,120,931 B1 * 10/2006 Cheriton ........
`7,193.968 B1* 3/2007 Kapoor et al. .............. 370,235
`2002/0122427 A1
`9/2002 Kamenisky et al.
`(73) Assignee: Packeteer, Inc., Cupertino, CA (US)
`(*) Notice:
`Subject to any disclaimer, the term of this S8. A.
`1929: WE
`past issists, listed under 35
`2003/0.112764 A 6/2003 Gaspard et al.
`* cited by examiner
`(21) Appl. No.: 10/676,383
`Primary Examiner Doris H. To
`(22) Filed:
`Sep. 30, 2003
`Assistant Examiner—Ian N. Moore
`(74) Attorney, Agent, or Firm—Mark J. Spolyar
`
`(51) Int. Cl.
`(2006.01)
`GOIR 3L/08
`(52) U.S. Cl. ....................... 370/235; 370/252; 370/389
`(58) Field of Classification Search ............. 370/395.3,
`37Of 395.31, 3955, 230, 428,429,419, 235
`370/359 381 389 392 252.255 395 34.
`370/395.52: 7 1 ?203209 2 11: 70972.3824 4.
`709,223 224: 726/12 13 7.3/153
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`4, 1990 Sriram
`4.914,650 A
`5,828,846 A * 10/1998 Kirby et al. ................ TO9,238
`6,003,077 A 12/1999 Bawden et al.
`6,023.456 A
`2/2000 Chapman et al.
`6,046,980 A
`4/2000 Packer
`6,219,050 B1
`4/2001 Schaffer
`6,285,660 B1
`9, 2001 Ronen
`6,397,359 B1
`5, 2002 Chandra et al.
`6,584,467 B1
`6/2003 Haught et al.
`6,681,232 B1
`1/2004 Sistanizadeh et al.
`
`50
`
`ABSTRACT
`(57)
`flow-based
`d
`d
`di
`Method
`ethods, apparatuses and systems directed to a flow-based,
`traffic-classification-aware data collection and reporting sys
`tem that combine flow-based data collection technologies
`with enhanced traffic classification functionality to allow for
`analysis and reporting into aspects of network operations
`that prior art systems cannot provide. Embodiments provide
`enhanced views into the operation of computer network
`infrastructures to facilitate monitoring, administration, com
`pliance and other tasks associated with networks. When a
`traffic flow terminates, a traffic monitoring device emits a
`flow data record (FDR) containing measurements variables
`and other attributes for an individual flow. A data collector
`gathers the flow data records and enters them into a data
`base. A network management application can then query the
`database with selected commands to derive reports charac
`terizing operation of the network Suitable to diagnose prob
`lems or view conditions associated with the network.
`
`26 Claims, 7 Drawing Sheets
`
`
`
`
`
`
`
`Traffic Monitoring
`Device
`
`Cloudflare - Exhibit 1020, page 1
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet 1 of 7
`
`US 7,385,924 B1
`
`
`
`50
`
`Traffic Monitoring
`Device
`
`40
`
`Fig. 1A
`
`Cloudflare - Exhibit 1020, page 2
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet 2 of 7
`
`US 7,385,924 B1
`
`50
`
`
`
`Computer
`
`Cloudflare - Exhibit 1020, page 3
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet 3 of 7
`
`US 7,385,924 B1
`
`130
`
`Management
`Device
`
`44
`
`
`
`Administrator
`Interface
`
`150
`
`
`
`
`
`137
`
`Traffic
`
`Classification
`Database
`
`
`
`134
`
`Flow
`Database
`
`Host
`
`
`
`
`
`
`
`
`
`L Measurement
`Engine
`
`140
`
`138
`
`139
`
`Management
`Information Base
`
`FDR. Emitter
`
`
`
`Data Packet
`In
`
`
`
`Packet
`Processor
`
`Flow Control
`Module
`
`Data Packet
`Out
`
`131
`
`132 Fig. 3
`
`Cloudflare - Exhibit 1020, page 4
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet 4 of 7
`
`US 7,385,924 B1
`
`
`
`Receive Data
`Packet
`
`Flow
`
`N
`
`Construct
`
`y- use
`
`Yes
`
`Fetch/Update
`Flow Object
`
`Record Flow
`Measurement
`Variables
`
`Identify
`Traffic Type
`
`Notify FDR
`Emitter
`
`Fig. 4
`
`Cloudflare - Exhibit 1020, page 5
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet S of 7
`
`US 7,385,924 B1
`
`250
`
`252
`
`254
`
`No
`
`FDR. Emitter
`Process
`
`Copy Flow
`Attributes and
`Measurement
`Variables
`
`Compose &
`Store Flow Data
`Record
`
`Increment
`FDR Counter
`
`256
`
`
`
`FDR Counter
`(a) Threshold?
`
`YeS
`
`258
`
`Get Global
`MIB Variables
`
`F1 9. 5
`
`260
`
`Compose
`FDRMessage
`
`262
`
`
`
`
`
`Transmit FDR
`Record to Data
`Collector
`
`
`
`264
`
`Reset FDR
`Counter
`
`Cloudflare - Exhibit 1020, page 6
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet 6 of 7
`
`US 7,385,924 B1
`
`
`
`Receive Data
`Packet
`
`Construct
`
`- e. Block
`
`New Data
`FOW2
`
`Fetch/Update
`Control Block
`
`Write Traffic
`Class & Policies
`into Control Block
`
`Pass Packet to
`Flow Control
`Module (P)
`
`Record Flow
`Measurement
`Variables
`
`Identify
`Traffic Class
`
`Notify FDR
`Emitter
`
`Cloudflare - Exhibit 1020, page 7
`
`

`

`U.S. Patent
`
`Jun. 10, 2008
`
`Sheet 7 Of 7
`
`US 7,385,924 B1
`
`302
`
`Receive
`Message
`
`Mapping
`Message?
`
`
`
`306
`
`Store Mapping
`Message in
`Mapping Table
`
`FDR
`Message?
`
`Discard
`Message
`
`
`
`
`
`
`
`
`
`
`
`
`
`308
`
`
`
`30
`
`
`
`
`
`Store Message
`Header in Header
`Table
`
`Store FDRS in
`FDR Tables
`
`Fig. 7
`
`Cloudflare - Exhibit 1020, page 8
`
`

`

`1.
`ENHANCED FLOW DATA RECORDS
`INCLUDING TRAFFIC TYPE DATA
`
`US 7,385,924 B1
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS AND PATENTS
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`This application makes reference to the following com
`monly owned U.S. patent applications and patents, which
`are incorporated herein by reference in their entirety for alt
`purposes:
`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 Com
`munication Environment Without Data Rate Supervision:
`25
`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 Com
`munication 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 For
`ward 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.
`Galloway, 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 For
`ward 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
`Traffic in a Packet Communications Network:
`U.S. patent application Ser. No. 09/198,051, now aban
`doned, 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. No. 6,456,630, 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. 10/039,992, now U.S.
`Pat. No. 7,032,072, in the name of Michael J. Quinn and
`
`50
`
`55
`
`60
`
`65
`
`2
`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, currently
`pending, in the name of Wei-Lung Lai, Jon Eric Okholm,
`and Michael J. Quinn, entitled “Output Scheduling Data
`Structure Facilitating Hierarchical Network Resource Allo
`cation Scheme:
`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 Classi
`fying Traffic With Enhanced Hierarchy. In A Packet Com
`munications Network.”
`U.S. patent application Ser. No. 10/236,149, currently
`pending, in the name of Brett Galloway and George Powers,
`entitled “Classification Data Structure enabling Multi-Di
`mensional Network Traffic Classification and Control
`Schemes:
`U.S. patent application Ser. No. 10/453,345, currently
`pending, in the name of Scott Hankins, Michael R. Morford,
`and Michael J. Quinn, entitled “Flow-Based Packet Cap
`ture;’ and
`U.S. patent application Ser. No. 10/611.573, currently
`pending, in the name of Roopesh Varier, David Jacobson,
`and Guy Riddle, entitled “Network Traffic Synchronization
`Mechanism.”
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer networks and,
`more particularly, to methods, apparatuses and systems
`directed to data collection schemes that allow for enhanced
`informational queries relating to the operation of computer
`network environments.
`
`BACKGROUND OF THE INVENTION
`
`Efficient allocation of network resources, such as avail
`able 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 imple
`ments the world-wide data communications network envi
`ronment called the Internet and is employed in many local
`area networks, omits 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
`conflict and produces certain inefficiencies. Certain loading
`conditions degrade performance of networked applications
`and can even cause instabilities which could lead to over
`loads that could stop data transfer temporarily. The above
`identified U.S. patents and patent applications provide
`explanations of certain technical aspects of a packet based
`telecommunications network environment, such as Internet/
`Intranet technology based largely on the TCP/IP protocol
`Suite, and describe the deployment of bandwidth manage
`ment solutions to monitor and/or manage network environ
`ments using Such protocols and technologies.
`The management of such networks requires regular moni
`toring and collection of data characterizing various attributes
`of the network, its operation and/or the traffic flowing
`through it. For example, Cisco Systems, Inc. of San Jose,
`Calif. offers a feature set of data monitoring and collection
`technologies in connection with its routers, called Netflow(R).
`The Cisco IOS(R) NetFlow feature set allows for the tracking
`
`Cloudflare - Exhibit 1020, page 9
`
`

`

`3
`of individual IP flows as they are received at a router or
`Switching device. According to the technology, after a flow
`has terminated, a suitably configured router or Switch gen
`erates a NetFlow record characterizing various attributes of
`the flow. The NetFlow record is ultimately transmitted as a
`datagram to a NetFlow Data Collector that stores and,
`optionally, filters the record. A NetFlow Record includes a
`variety of attributes, such as source and destination IP
`addresses, packet count, byte count, start and end time
`stamps, source and destination TCP/UDP ports, Quality of
`Service attributes, and routing-related information (e.g.,
`nexthop and Autonomous System (AS) data). Such Net
`Flow(R) records are similar to call records, which are gener
`ated after the termination of telephone calls and used by the
`telephone industry as the basis of billing for long distance
`calls, for example.
`Most network devices maintain data characterizing utili
`Zation, operation and/or performance of the network
`devices, and/or the network on which the devices operate, in
`limited, volatile memory, rather than using persistent storage
`(e.g., hard disks or other non-volatile memory). Conse
`quently, network management applications commonly use
`the Simple Network Management Protocol (SNMP) to poll
`network devices (using the Management Information Base
`(MIB) associated with the network device) at regular time
`intervals and maintain the sampled raw data in a persistent
`data store. The network management application, such as a
`reporting package, then processes the raw data to allow for
`the creation of reports derived from the raw data detailing
`operation and/or performance of the device and/or the
`network. Management Information Bases typically contain
`low-level information characterizing the operation of the
`network device, such as the number of bytes or packets
`encountered on an interface, and do not provide information
`concerning the characteristics of data flows.
`Using a reporting package, a network administrator may
`then analyze the data to yield information about the perfor
`mance or utilization of the network and/or network devices
`associated with the network. Indeed, Various applications
`can then access the Data Collector to analyze the data for a
`variety of purposes, including accounting, billing, network
`planning, traffic engineering, and user or application moni
`toring. There are public-domain implementations of collec
`tors for standard NetFlow records. These are, however,
`unable to answer questions such as “which hosts are running
`the busiest Kazaa (or other peer-to-peer file sharing) serv
`ers” (as NetFlow records are not suitable for analyzing and
`classifying network traffic that does not use registered IP
`port numbers).
`Packeteer, Inc. of Cupertino, Calif. develops bandwidth
`monitoring, management, and reporting software and sys
`tems. Its PacketSeekerR) systems and PacketShaper(R) band
`width management devices, among other things, provide
`“application aware' monitoring of network traffic enabling
`classification of network traffic flows on a per application
`basis. The Packetshaper(R) bandwidth management device
`includes functionality allowing for classification of network
`traffic based on information from layers 2 to 7 of the OSI
`reference model. As discussed in the above-identified pat
`ents and patent applications, the bandwidth management
`device includes a measurement engine operative to record or
`maintain numeric totals of a particular measurement variable
`at periodic intervals on a traffic classification basis. The
`bandwidth management device further includes a manage
`ment information base including standard network objects
`maintaining counts relating, for example, to the operation of
`its network interfaces and processors. Packeteer's Report
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`US 7,385,924 B1
`
`4
`CenterTM leverages the powerful network utilization and
`application performance statistics available in Packet
`shaper R bandwidth management devices and offers a cen
`tralized reporting platform to monitor and manage large
`deployments efficiently by streamlining collection, colla
`tion, storage, analysis, and distribution of measured statis
`tics.
`While the measurement engine is sufficient to achieve its
`intended purpose, some useful data for analyzing network
`usage and/or diagnosing problems is not available histori
`cally, but is only kept in memory while the PacketSeeker,
`PacketShaper or other bandwidth management device is
`running. In particular, the reports on “top talkers' and
`“traffic history” are not available for specific intervals in the
`past nor available after the device crashes, possibly due to
`Some kind of attack or power outage. Furthermore, data
`maintained by the measurement engine, is generally not
`flow-based, and cannot answer questions like “which clients
`are running port scanners.” Furthermore, as discussed
`above, NetFlow records characterize individual flows; how
`ever, standard NetFlow records cannot answer Such ques
`tions or others requiring classification of flows beyond the
`attributes maintained by NetFlow records.
`In light of the foregoing, a need in the art exists for
`methods, apparatuses and systems that enable a flow-based,
`traffic-classification-aware data collection and reporting sys
`tem. A need further exists in the art for methods, apparatuses
`and systems allowing for enhanced informational queries
`relating to the operation of networks. Embodiments of the
`present invention substantially fulfill these needs.
`SUMMARY OF THE INVENTION
`
`The present invention provides methods, apparatuses and
`systems directed to a flow-based, traffic-classification-aware
`data collection and reporting system. Embodiments of the
`present invention combine flow-based data collection tech
`nologies with enhanced traffic classification functionality to
`allow for analysis and reporting into aspects of network
`operations that prior art systems cannot provide. Embodi
`ments of the present invention provide deeper insight into
`the operation of computer networks and the application
`traffic traversing the networks. Embodiments of the present
`invention provide enhanced views into the operation of
`computer network infrastructures to facilitate monitoring,
`administration, compliance and other tasks associated with
`networks. In one embodiment, when a traffic flow termi
`nates, a traffic monitoring device emits a flow data record
`(FDR) containing measurements variables, classification
`information, and other attributes for an individual flow. A
`data collector gathers the flow data records and enters them
`into a database. A network management application can then
`query the database with selected commands to derive reports
`characterizing operation of the network Suitable to diagnose
`problems or view conditions associated with the network.
`DESCRIPTION OF THE DRAWINGS
`
`60
`
`65
`
`FIG. 1A is a functional block diagram showing a traffic
`monitoring device according to an embodiment of the
`present invention.
`FIG. 1B is a functional block diagram illustrating a
`computer network environment including a bandwidth man
`agement device according to an embodiment of the present
`invention.
`FIG. 2 is an functional block diagram illustrating a
`computer network environment including a bandwidth man
`agement device and a data collector.
`
`Cloudflare - Exhibit 1020, page 10
`
`

`

`US 7,385,924 B1
`
`5
`FIG. 3 is a functional block diagram setting forth the
`functionality in a bandwidth management device according
`to an embodiment of the present invention.
`FIG. 4 is a flow chart diagram providing a method,
`according to an embodiment of the present invention,
`directed to the processing of packets.
`FIG. 5 is a flow chart diagram showing a method, accord
`ing to an embodiment of the present invention, directed to
`composing and transmitting flow data records to a data
`collection node.
`FIG. 6 is a flow chart diagram illustrating a method
`directed to enforcement of bandwidth utilization controls on
`network traffic traversing an access links.
`FIG. 7 is a flow chart diagram providing a method
`directed to processing messages including flow data records.
`
`10
`
`15
`
`6
`memory 76, such as a hard disk drive or other suitable
`memory device, such writable CD, DVD, or tape drives. In
`one embodiment, traffic monitoring device 30 collects and
`transmits flow data records to a remote, persistent data store,
`for example, in datagrams, XML messages and the like.
`FIGS. 1B and 2 illustrate an operating environment where
`traffic monitoring device 30 is a bandwidth management
`device 130 (see discussion below).
`As FIGS. 1A, 1B and 2 show, the traffic monitoring device
`30 (or bandwidth management device 130), in one embodi
`ment, is disposed on the link between a Local area network
`40 and router 22. In other embodiments, multiple traffic
`monitoring devices can be disposed at Strategic points in a
`given network infrastructure to achieve various objectives.
`In addition, packet monitoring device 30 need not be directly
`connected to the link between two network devices, but may
`also be connected to a mirror port. In addition, the traffic
`monitoring functionality described herein may be deployed
`in multiple network devices and used in redundant network
`topologies by integrating the network traffic synchronization
`functionality described in U.S. application Ser. No. 10/611,
`573, above.
`A. Flow-Based Traffic Monitoring
`As discussed herein, traffic monitoring device 30 is opera
`tive to detect or recognize flows between end systems,
`classify the data flows based on one or more flow attributes
`and, upon the termination of individual flows, compose flow
`data records including data fields characterizing one or more
`attributes associated with the individual flows. The flow data
`records, in one embodiment, are ultimately transmitted to a
`data collector 44 which stores the data in a database allowing
`applications to query the database to generate reports char
`acterizing the operation of the network in a variety of ways
`that were not possible prior to the invention described
`herein. FIG. 4 illustrates a method, according to an embodi
`ment of the present invention, directed to a flow-aware
`process that classifies flows and notifies a flow data record
`emitter that a flow has ended. FIG. 5 provides a method,
`according to an embodiment of the present invention,
`directed to composing flow data records and transmitting a
`plurality of flow data records in a datagram to a remote data
`collector 44.
`As FIG. 4 illustrates, a packet processor 82 receives a data
`packet (102) and determines whether a flow object has
`already been created for the flow to which the data packet is
`a part (104). A flow object is a data structure including fields
`whose values characterize various attributes of the flow,
`including Source and destination IP addresses, port numbers,
`traffic type identifiers and the like. A flow object can also
`include other attributes, such as packet count, byte count,
`first packet time, last packet time, etc. If a flow object is not
`found, packet processor 82 constructs a new flow object
`(106). Packet processor 82 then determines whether the
`received packet is part of an existing flow or a new data flow
`(108). In one embodiment, flows are generally TCP and
`UDP flows. However, any suitable transport layer flow can
`be recognized and detected. In one embodiment, flows are
`identified based on the following flow attributes: 1) source
`IP address, 2) destination IP address, 3) source port number,
`4) destination port number, and 5) protocol (derived from the
`“protocol field in IPv4 headers, and the “NextEHeader” field
`in IPv6 headers). One skilled in the art will recognize that
`flows can be identified in relation to a variety of attributes
`and combinations of attributes. In addition, methods for
`determining new data flows and assigning packets to exist
`ing data flows are well known in the art and also depend on
`
`DESCRIPTION OF PREFERRED
`EMBODIMENT(S)
`
`FIG. 1A illustrates a basic network environment in which
`an embodiment of the present invention operates. FIG. 1A
`shows a first network device 40, such as a hub, Switch or
`router, interconnecting two end-systems (here, client com
`puter 42 and host 44). FIG. 1A also provides a second
`network device 22, Such as a router, operably connected to
`network cloud 50. Such as an open, wide-area network. As
`FIG. 1A shows, packet traffic monitoring device 30 com
`prises traffic monitoring module 75, and first and second
`network interfaces 71, 72, which operably connect traffic
`monitoring device 30 to the communications path between
`first network device 40 and second network device 22.
`Traffic monitoring module 75 generally refers to the func
`tionality implemented by traffic monitoring device 30. In
`one embodiment, traffic monitoring module 75 is a combi
`nation of hardware and software, such as a central process
`ing unit, memory, a system bus, an operating system and one
`or more software modules implementing the functionality
`described herein. In one embodiment, traffic monitoring
`module 75 includes a packet processor 82, a traffic type
`identifier 84, and a flow data record emitter 86. In one
`embodiment, the packet processor 82 is operative to process
`data packets, such as storing packets in a buffer structure,
`detecting new data flows, and parsing the data packets for
`various attributes (such as Source and destination addresses,
`and the like) and maintaining one or more measurement
`variables or statistics in connection with the flows. The
`traffic type identifier84, as discussed more fully below, is
`operative to classify data flows based on one or more
`attributes associated with the data flows. The flow data
`record emitter 86 is operative to compose flow data records
`characterizing the data flows that traverse the traffic moni
`toring module 30, and transmit the flow data records to a
`data collection node, such as data collector 44.
`As discussed below, the functionality of traffic monitoring
`device 30 can be integrated into a variety of network
`devices, such as firewalls, gateways, proxies, packet capture
`devices (see U.S. application Ser. No. 10/453,345) and
`bandwidth managers, that are typically located at Strategic
`points in computer networks. In one embodiment, first and
`second network interfaces 71, 72 are implemented as a
`combination of hardware and Software, Such as network
`interface cards and associated Software drivers. In addition,
`the first and second network interfaces can be wired network
`interfaces, such as Ethernet interfaces, and/or wireless net
`work interfaces, such as 802.11, BlueTooth, satellite-based
`interfaces, and the like. As FIG. 1A illustrates, traffic moni
`toring device 30, in one embodiment, includes persistent
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Cloudflare - Exhibit 1020, page 11
`
`

`

`7
`the particular transport layer protocol employed. For a TCP
`flow, packet processor 82 can determine a new data flow by
`detecting SYN and/or SYN/ACK packets. However, a new
`data flow can simply be a data flow for which there is no
`corresponding flow object. For example, with UDP and GRE
`flows (where there is no explicit connection mechanism,
`Such as SYN packets), a new flow is recognized by associ
`ating the source and destination addresses and port numbers
`to the flow and the flow type (e.g., UDP, GRE, etc.).
`Accordingly, when a UDP packet identifies a new address/
`port pair, the attributes discussed above are stored in a data
`structure along with the time of last packet. A new UDP flow
`between the same address/port pairs can be determined by
`comparing the last packet time to a threshold value (e.g., 2
`minutes). If the difference between the time of the latest
`packet and the time of the last packet is greater than the
`threshold, the new packet is deemed part of a new flow. In
`another implementation, a background and/or separate pro
`cess can periodically compare the last packet times associ
`ated with a flow to a threshold period of time and deem the
`flow terminated if the last packet time is beyond the thresh
`old period of time.
`If the packet is part of an existing flow, the packet
`processor 82 associates the packet with the corresponding
`flow object and updates flow object attributes as required
`(110). For example, the packet processor 82, in one embodi
`ment, increments the packet count associated with the flow
`(116). If the packet represents a new data flow, traffic type
`identifier 84 operates on the flow object and, potentially,
`attributes of the packet and other packets associated with the
`flow to determine a traffic type and/or traffic class associated
`with the flow (114). In one embodiment, the packet (or a
`pointer to the packet stored in a buffer structure) and the flow
`object (or a pointer thereto) is passed to the traffic type
`identifier84 to determine a traffic type. As discussed in more
`detail below, identification of a traffic class or type can
`employ information gleaned from Layers 2 thru 7 of the OSI
`reference model. The determination of traffic types and
`traffic classes is discussed in more detail below at Sections
`B. 1. and B.3. Similarly, if the packet represents a change to
`the data flow (112), packet processor 82 passes the packet
`and flow object to the traffic type identifier84 to determine
`the traffic type. Packet processor 82 then records or updates
`various flow measurement variables, such as packet count,
`byte count, last packet time and the like (116). As FIG. 4
`illustrates, if the packet indicates the end of the flow (118),
`packet processor 82 notifies the flow data record emitter 86
`(120).
`FIG. 5 provides a method, according to an embodiment,
`performed by flow data record emitter 86 in response to a
`notification from packet processor 82 that a flow has ended.
`As discussed above, while a flow is active, packet processor
`82 processes the packets and records flow measurements
`variables in a flow object associated with the flow. When the
`flow is terminated, packet processor 82 signals the flow data
`record emitter 86, passing it a pointer to the flow object in
`a buffer structure. As FIG. 5 illustrates, when signaled, the
`flow data record emitter 86 copies the flow attribute and
`measurement variables from the flow object needed to
`compose a flow data record from the buffer (250). In one
`embodiment, when the data is copied, flow data record
`emitter 86 signals packet processor 82, which releases the
`pointer to the flow object in the buffer space allocated the
`flow object space back to the pool of available pointers for
`use with a new flow. Flow data record emitter 86 then
`composes a flow data record for the flow and stores it in
`memory (252).
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,385,924 B1
`
`10
`
`15
`
`8
`
`A.1. FDR Emitter
`As FIG. 5 illustrates, flow data record emitter 86 essen
`tially composes and collects a plurality of flow data records,
`and transmits the plurality of flow data records in a flow data
`record (FDR) message to a data collector 44. Specifically,
`and in one implementation, flow data record emitter 86
`maintains a FDR counter (254) to track the number of flow
`data records stored in memory. When the FDR counter
`reaches a predetermined threshold (256), flow data record
`emitter composes a flow data record message including the
`collected flow data records. In one embodiment, the flow
`data record message comprises a header including an iden
`tifier for traffic monitoring device 30 and global data non
`specific to the flow data records (such as, system uptime,
`CPU idle time, a time stamp, and the like). The body of the
`FDR message comprises up to a threshold number of flow
`data records. The threshold number of flow data records can
`be set to different values to achieve a variety of objectives.
`In one embodiment, an FDR message is a single UDP
`datagram; accordingly, the threshold or maximum number
`of flow data records depends on the maximum transmit unit
`(MTU) supported by the computer network environment,
`the size of the FDR message header, and the individual sizes
`of the flow data records. When the FDR counter reaches a
`threshold value (256), flow data record emitter 86, accesses
`predetermined MIB variables (258), as discussed above, and
`composes a FDR message including the global variables and
`the flow data records (260). Flow data record emitter 86 then
`transmits the FDR message to a data collector (262) and
`resets the FDR counter (264).
`B. Integration of Flow-Based Packet Capture and Band
`width Management Devices
`As discussed above, the traffic monitoring and flow data
`record functionality described above, in one embodiment,
`can be integrated into a bandwidth management device 130
`operative to mana