`
`
`
`
`
`
`
`US 7,664,048 B1
`(10) Patent No.:
`a2) United States Patent
`
`
`
`
`
`
`
`
`Feb. 16, 2010
`(45) Date of Patent:
`Yungetal.
`
`
`
`
`US007664048B1
`
`
`
`
`
`
`
`(54) HEURISTIC BEHAVIOR PATTERN
`
`
`
`MATCHINGOF DATA FLOWS IN ENHANCED
`
`
`
`NETWORK TRAFFIC CLASSIFICATION
`
`
`
`
`
`Inventors: Weng-Chin Yung, Folsom, CA (US);
`
`
`
`
`
`
`MarkHill, Los Altos, CA (US); Anne
`
`
`
`
`Cesa Klein, Cupertino, CA (US)
`
`(75)
`
`
`
`
`
`
`
`
`
`
`
`(73) Assignee: Packeteer, Inc., Cupertino, CA (US)
`:
`:
`:
`:
`:
`
`
`
`
`
`
`
`
`(*) Notice:
`Subject to any disclaimer, the term ofthis
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`
`U.S.C. 154(b) by 870 days.
`
`
`
`
`(21) Appl. No.: 10/720,329
`
`
`
`
`Nov. 24, 2003
`
`(22)
`
`Filed:
`
`
`
`
`
`
`
`6,681,232 Bl
`
`
`6,690,918 B2
`
`
`6,701,359 BL
`
`
`6,738,352 Bl
`
`
`6,798,763 BL
`
`
`6,894,972 Bl
`
`7,010,611 B1*
`
`
`7,120,931 Bl
`
`
`7,154,416 Bl
`
`
`7,155,502 BL
`
`
`7,193,968 Bl
`
`
`7,215,637 Bl
`
`
`7,224,679 B2
`
`
`
`
`
`
`1/2004 Sistanizadeh
`
`
`2/2004 Evans
`
`
`3/2004. Calabrez
`
`
`5/2004 Yamada
`
`
`9/2004 Kimura
`
`
`
`5/2005 Phaal
`
`
`3/2006 Wiryaman et al.
`
`
`10/2006 Cheriton
`
`12/2006 S.
`
`
`/
`veg
`
`
`12/2006 Galloway
`
`
`3/2007 Kapoor
`
`
`5/2007 Ferguson
`
`
`5/2007 Solomon
`
`
`
`
`.......... 709/232
`
`
`
`(51)
`
`
`
`(56)
`
`
`
`
`Int. Cl.
`
`
`
`(2006.01)
`FOAL 12/26
`
`
`
`
`
`
`(52) U.S.Cwee 370/253; 370/235; 370/252;
`709/224
`:
`:
`:
`
`
`
`
`
`(58) Field of Classification Search ................. 370/223,
`
`
`
`
`
`370/224, 229, 230, 231, 236.1, 238, 235,
`
`
`
`
`
`370/253, 252; 709/224, 226, 233, 235, 246
`
`
`
`
`
`
`
`See application file for complete search history.
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`4/1990 Sriram
`4,914,650 A
`
`
`
`10/1998 Kirby
`5,828,846 A
`12/1999 Bawden
`6,003,077 A
`
`
`
`
`
`
`2/2000 Chapman
`6,023,456 A
`
`
`
`
`
`3/2000 Packer ....... ce eee 370/231
`6,038,216 A *
`
`
`
`
`
`4/2000 Packer ...... eee 370/230
`6,046,980 A *
`
`
`
`
`
`
`9/2000 Bennett etal. 0.0.0.0... 709/236
`6,122,670 A *
`
`
`
`
`
`
`
`6,144,636 A * 11/2000 Aimoto etal. 0.0... 370/229
`
`
`
`
`6,219,050 Bl
`4/2001 Schaffer
`6,285,660 Bl
`9/2001 Ronen
`
`
`
`
`
`
`
`
`
`6,363,056 Bl
`3/2002 Beigi
`6,397,359 Bl
`5/2002 Chandra
`
`
`
`
`
`
`
`
`
`6,584,467 Bl
`6/2003 Haught
`
`
`
`
`
`6,591,299 B2*
`7/2003 Riddle etal. ........0.... 709/224
`
`
`
`
`
`6,625,648 Bl
`9/2003 Schwaller
`
`
`
`
`6,628,938 Bl
`9/2003 Rachabathuni
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`Pazos, C.M. et al., “Flow Control and Bandwidth Management in
`
`
`
`
`
`
`
`
`
`Next Generation Internets” IEEE, Jun. 22, 1998,pp. 123-132.*
`
`(Continued)
`
`
`
`
`Pri
`Examiner—Donald L Mill
`rmary &xanine s
`.
`
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm—Baker Botts L.L.P.
`
`
`
`
`
`(57)
`
`ABSTRACT
`
`
`
`
`
`
`
`
`
`
`
`Methods, apparatuses and systemsfacilitating enhanced clas-
`
`
`
`
`
`
`
`sification of network traffic that extends beyond analysis of
`
`
`
`
`
`
`
`explicitly presented packet attributes and holistically ana-
`
`
`
`
`
`
`
`
`lyzes data flows, and in some implementations, related data
`
`
`
`
`
`
`
`flows against knownapplication behaviorpatternsto classify
`
`
`
`
`
`
`
`
`the data flows. Implementations of the present invention
`
`
`
`
`
`
`
`facilitate the classification of encrypted or compressed net-
`
`
`
`
`
`
`
`
`worktraffic, or where the higher layer information in the data
`
`
`
`
`
`
`flows are formatted according to a non-public or proprietary
`protocol.
`
`
`
`
`
`31 Claims, 11 Drawing Sheets
`
`
`
`Pattern Match
`
`
`
`
`Based on Suspected
`
`
`Application Type
`
`
`
`
`
`
`
`
`
`Packet Size
`
`
`Match Entry in
`
`
`Pattern?
`
`
`360
`
`
`
`362
`
`
`
`
`
`
`
`
`Does Packet
`
`
`
`
`Size match Next
`
`
`
`
`Entry in Pattern?
`
`
`
`
`
`
`Return No
`Match
`
`
`
`366
`
`
`
`
`
`364
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 1
`
`Splunk Inc. Exhibit 1005 Page 1
`
`

`

`
`
`US 7,664,048 B1
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`Hill
`
`Hill
`
`Morford
`
`Riddle
`
`
`Muppala
`Kamentsky
`
`Lupo
`Walsh
`
`
`Gaspard
`McCormack
`
`
`7,292,531
`
`7,296,288
`
`7,324,447
`
`7,385,924
`
`7,554,983
`2002/0122427
`
`2002/0143901
`
`2003/0035385
`
`2003/0112764
`
`2003/0185210
`
`
`Bl
`
`Bl
`
`Bl
`
`Bl
`
`Bl
`
`Al
`
`Al
`
`Al
`
`Al
`
`Al
`
`
`11/2007
`11/2007
`1/2008
`
`6/2008
`
`6/2009
`
`9/2002
`
`10/2002
`
`2/2003
`
`6/2003
`
`10/2003
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2004/0125815 Al
`
`2006/0045014 Al
`
`
`
`
`
`
`7/2004 Shimazu
`
`
`3/2006 Charzinski
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`Ye, Guanhuaet al., “Using explicit congestion notification in stream
`
`
`
`
`
`
`
`
`control transmisson provided in networks”, IEEE, May 19-22, 2003,
`
`
`pp. 704-709.*
`
`
`
`
`
`
`
`Yung, U.S. Appl. No. 10/917,952, entitled: Examination of connec-
`
`
`
`
`
`
`tion handshaketo enhance classification of encrypted networktraffic,
`
`
`Aug. 2004.
`
`
`* cited by examiner
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 2
`
`Splunk Inc. Exhibit 1005 Page 2
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`
`Sheet 1 of 11
`
`
`
`US 7,664,048 B1
`
`50
`
`
`
`
`
`
`
`
`
`
`Traffic Monitoring
`
`Device
`
`
`
`
`
`
`
`
`
`
` Traffic
`
`
`Classification
`
`Engine
`
`40
`
`
`
`
`Fig.1
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 3
`
`Splunk Inc. Exhibit 1005 Page 3
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 2 of 11
`
`
`
`US 7,664,048 B1
`
`
`
`
`
`50
` Computer
`
`
`
`Network
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 4
`
`Splunk Inc. Exhibit 1005 Page 4
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 3 of 11
`
`
`
`US 7,664,048 B1
`
`
`
`137
`
`
`
`150
`
`
`
`
`
`Interface
`
`
`
`
`
`
`
`
`
`140
`
`
`
`
`Classification
`
`Engine
`
`
`
`
`Flow
`Database
`
`
`
`
` Administrator
`Traffic ooMeasurement
`
`
`
`Engine
`
`
`s
`
`138
`
` Management
`
`
`
`Information Base
`
`
`
`
`
`
`134
`
`
`
`
`
`
`Data Packet
`
`In
`
`
`
`139
`
`
`
`
`Traffic Discovery
`
`Module
`
`
`
`
`
`
`Host
`Database
`
`
`
`
`Packet
`Processor
`
`
`
`
`
`
`
`
`
`
`
`
`
`Flow Control
`Data Packet
`
`
`Module
`
`Out
`
`
`
`
`131
`132
`
`Fig.3
`
`Splunk Inc.
`
`Exhibit1005
`
`Page5
`
`Splunk Inc. Exhibit 1005 Page 5
`
`

`

`Flow
`
`
`
`
`
`Construct
`
`
`
`
`
`
`Object? Flowoe
`
`
`106
`
`
`
`
`
`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 4 of 11
`
`
`
`US 7,664,048 B1
`
`
`102
`
`;
`
`Receive Data
`
`Packet
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`11 0
`
`
`
`Fetch/Update
`
`
`
`Flow Object
`
`
`
`
`
`
`
`
`
`
`Changes
`To Flow?
`
`
`Identify
`
`Traffic Class
`
`
`
`
`
`
`
`114
`
`
`
`
`
`
`
`
`
`
`Flag Packet Data
`for Traffic
`
`
`
`
`Discovery
`
`
`
`
`
`Variables
`
`
`
`Record Flow
`
`Measurement
`
`
`116
`
`
`
`118
`
`
`
`1:
`Fig.4
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page6é
`
`Splunk Inc. Exhibit 1005 Page 6
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 5 of 11
`
`
`
`US 7,664,048 B1
`
` Ist Packet of
`
`
`
`
`
`
`New Flow?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`304
`
`.
`
`
`
`
`Continue Pattern
`No
`
`
`
`
`Matching for
`
`Flow?
`
`
`
`
`
`
`
`
`305
`
`
`
`
`
`322
`
`
`Increment
`
`Related Flow
`
`Count
`
`
`
`
`
`
`Return Previous
`Classification
`
`
`
`
`
`Classify as
`
`
`
`
`
`
`
`
`
`Unknown
`
`
`
`
`
`
`
`
`Pattern Match
`Related Flow
`
`
`
`Exhausted for
`
`
`
`Count >
`
`
`Flow?
`Threshold?
`
`
`
`
`
`
`
`
`
`
`
`
`
` Pattern Match
`
`
`
`Classify as
`
`
`
`based on Suspected
`Suspected
`
`
`
`Application Type
`Application
`
`
`
`
`Identify
`
`Suspected
`
`Application
`
`
`
`
`
`
`Classify as Unknown;
`
`
`
`End Pattern Match
`
`
`
`For Flow
`
` Process Flow for
`
`
`
`
`
`
`Related Flow
`
`
`Tracking
`
`
`
`
`
`
`
`
`
`
`Fig.5A
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 7
`
`Splunk Inc. Exhibit 1005 Page 7
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 6 of 11
`
`
`
`US 7,664,048 B1
`
`|
`
`Identify
`
`
`Cuenertad
`
`
`Wa mopPeeiue
`Application
`
`
`
`|
`
`
`
`Select First Application
`—-
`
`
`
`330
`
`
`
`
`
`
`
`
`
`
`
`
`Protocol
`
`
`
`
`Advance to Next
`
`
`Match
`
`Application
`
`
`Application?
`
`344
`
`
`
`
`
` 342
`
`Match"ie&
`
`
`
`
`
`
`
`
`
`
`lst Packet
`
`Size Matches
`
`9
`Pattern’
`
`
`
`
`
`
`Return "No
`
`
`
`
`346
`
`
`
`
`
`
`Compute Packet
`
`
`Data Entropy
`
`Value
`
`
`
`
`
`
`
`
`
`
`Entropy Value
`
`Match
`
`Pattern?
`
`340
`
`
`
`
`
`
`Return Suspected
`
`
`
`
`
`
`
`Application
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page8
`
`Splunk Inc. Exhibit 1005 Page 8
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 7 of 11
`
`
`
`US 7,664,048 B1
`
`
`
`
`
`
`
`
`
`350
`
`
`
`
`
`
`Related Flow
`
`
`
`Tracking
`
`
`
`
`
`
`Record Arrival Time
`
`
`
`
`
`of 1st Packet; Host
`
`
`
`Address and Suspected
`
`Application
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Related Flow Count
`New Host
`
`
`
`
`
`
`
`Address/Suspected
`=0; Last Flow Time
`
`
`
`
`
`Application Pair?
`= 1st Packet Time
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Is A
`
`b/w Ist
`
`
`
`Packet Time and
`
`
`
`Last Flow Time >
`
`Limit?
`
`
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page9
`
`Splunk Inc. Exhibit 1005 Page 9
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 8 of 11
`
`
`
`US 7,664,048 B1
`
`
`
`
`
`
`
`
`
`Pattern Match
`
`
`Based on Suspected
`
`
`Application Type
`
`
`
`
`
`
`
`360
`
`
`
`
`
`
`Packet Size
`
`
`Match Entry in
`
`Pattern?
`
`362
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`366
`
` Does Packet
`
`
`
`
`
`
`
`Size match Next
`
`
`
`Entry in Pattern?
`
`
`
`
`
`
`
`
`
` Return Match
`
`
`
`
`
`
`Fig.5D
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 10
`
`Splunk Inc. Exhibit 1005 Page 10
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 9 of 11
`
`
`
`US 7,664,048 B1
`
`
`Client Device
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Computer
`
`
`
`Tunnel Proxy
`
`Server
`
`
`
`
`
`
`Network
`
`
`
`
`
`
`
`Network Network
`
`
`Computer
`
`
`
`
`
`Resource
`
`
`
`
`Fig.6
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 11
`
`Splunk Inc. Exhibit 1005 Page 11
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 10 of 11
`
`
`
`US 7,664,048 B1
`
`
`
`202
`
`
`
`
`
`Receive Data
`
`Packet
`
`
`212
`
`_?
`
`
`
`Control
`
`
`
`No
`
`
`
`Construct
`
`
`
`
`
`
`
`
`
`Fetch/Update
`
`
`Control Block
`
`
`
`204 Yes
`208
`
`Yes New Data
`
`Flow?
`
`
`
`
`
`
`
`
`
`
`
`Changes
`To Flow?
`
`
`
`Identify
`
`
`Traffic Class
`
`
`Write Traffic
`
`
`
`Class & Policies
`
`
`
`A 214
`
`into Control Block
`
`
`
`
`
`
`
`
`219
`
`
`
`
`
`
`
`
`
`
`
`Flag Packet Data
`
`
`
`
`for Traffic
`
`Discovery
`N
`
`
`
`Pass Packet to
`
`
`Flow Control
`
`Module(P)
`
`
`
`Record Flow
`
`Measurement
`
`
`Variables
`
`220
`
`
`
`222
`
`
`
`Fig. 7
`
`—
`
`224
`
`
`
`Splunk Inc.
`
`Exhibit1005
`
`Page 12
`
`Splunk Inc. Exhibit 1005 Page 12
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Feb. 16, 2010
`
`
`
`
`Sheet 11 of 11
`
`
`
`US 7,664,048 B1
`
`Pass to
`
`Classification
`
`
`
`
`
`
`402
`
`
`
`
`
`
`
`
`Traffic Class
`
`Identified?
`
`
`
`
`
`Flag for Traffic
`
`Discovery
`
`
`
`
`
`
`
`Yes
`
`
`
`
`
`Traffic Class
`
`Identified By
`Auto-Discovery?
`
`
`
`Engine
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Pass to Pattern
`
`
`Matching
`
`Classification
`
`Mechanism
`
`
`Fig.8
`
`SplunkInc.
`
`Exhibit 1005
`
`Page 13
`
`Splunk Inc. Exhibit 1005 Page 13
`
`

`

`
`
`US 7,664,048 B1
`
`
`1
`HEURISTIC BEHAVIOR PATTERN
`
`
`
`MATCHING OF DATA FLOWS IN ENHANCED
`
`
`
`NETWORK TRAFFIC CLASSIFICATION
`
`
`
`
`
`
`CROSS-REFERENCE TO RELATED
`
`APPLICATIONS AND PATENTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 all pur-
`
`poses:
`
`
`
`
`
`
`
`
`
`US. 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-
`
`
`
`
`
`
`nication Environment Without Data Rate Supervision;”
`
`
`
`
`
`
`
`
`
`USS. 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;”
`
`
`
`
`
`
`
`
`
`US. patent application Ser. No. 08/742,994 now U.S. Pat.
`
`
`
`
`
`
`
`No. 6,038,216, in the name of Robert L. Packer, entitled
`
`
`
`
`
`
`
`“Method for Explicit Data Rate Control in a Packet Commu-
`
`
`
`
`
`
`nication Environment without Data Rate Supervision;”
`25
`
`
`
`
`
`
`
`
`
`US. 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;”
`
`
`
`
`
`
`
`
`
`US. 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 ina Packet-
`
`
`based Network;”
`
`
`
`
`
`
`
`
`
`USS. 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;”
`
`
`
`
`
`
`
`
`
`US. patent application Ser. No. 09/479,356 now U.S. Pat.
`
`
`
`
`
`
`
`No. 6,285,658, in the name of Robert L. Packer, entitled
`
`
`
`
`
`
`
`“System for Managing Flow Bandwidth Utilization at net-
`
`
`
`
`
`
`
`
`work, Transport and Application Layers in Store and Forward
`
`Network;”
`
`
`
`
`
`
`
`
`
`US. patent application Ser. No. 09/198,090 now U.S. Pat.
`
`
`
`
`
`
`
`
`No. 6,412,000, in the name of Guy Riddle and Robert L.
`
`
`
`
`
`
`Packer, entitled “Method for Automatically Classifying Traf-
`
`
`
`
`fic in a Packet Communications Network;”
`
`
`
`
`
`
`
`
`USS. patent application Ser. No. 09/198,051, in the name of
`
`
`
`
`
`
`GuyRiddle,entitled “Method forAutomatically Determining
`
`
`
`
`
`
`a Traffic Policy in a Packet Communications Network,”
`
`
`
`
`
`
`
`
`USS. 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;”
`
`
`
`
`
`
`
`
`USS. 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;”
`
`
`
`
`
`
`
`
`USS. 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;”
`
`
`
`
`
`
`
`
`US. 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-
`
`
`
`
`
`
`ing Traffic With Enhanced Hierarchy In A Packet Communi-
`
`
`cations Network;”
`
`20
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`
`
`
`
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`
`
`
`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
`
`
`
`
`Classification and Control Schemes;”
`
`
`
`
`
`
`
`
`U.S. patent application Ser. No. 10/295,391, in the name of
`
`
`
`
`
`
`
`
`
`Mark Hill, Guy Riddle and Robert Purvy, entitled “Methods,
`
`
`
`
`
`
`Apparatuses, and Systems Allowing for Bandwidth Manage-
`
`
`
`
`
`ment Schemes Responsive to Utilization Characteristics
`
`
`
`
`Associated with Individual Users;”
`
`
`
`
`
`
`
`
`U.S. patent application Ser. No. 10/334,467, in the name of
`
`
`
`
`
`
`
`Mark Hilt, 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;” and
`
`
`
`
`
`
`
`
`
`U'S. patent application Ser. No. 10/611,573, 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,
`
`
`
`
`
`moreparticularly, to enhanced network traffic classification
`
`
`
`
`
`
`mechanisms that allow for identification of encrypted data
`
`
`
`
`
`
`
`flows, or data flows where attributes necessary to proper
`classification are otherwise obscured or unknown.
`
`
`
`
`
`
`
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Efficient allocation of network resources, such as available
`
`
`
`
`
`
`network bandwidth, has become critical as enterprises
`
`
`
`
`
`increasereliance on distributed computing environments and
`
`
`
`
`
`
`wide area computer networks to accomplish critical tasks.
`
`
`
`
`
`The widely-used Transport Control Protocol (TCP)/Internet
`
`
`
`
`
`
`
`Protocol (IP) protocol suite, which implements the world-
`wide data communications network environmentcalled the
`
`
`
`
`
`
`
`
`
`
`
`
`
`Internet and is employed in manylocal area networks, omits
`
`
`
`
`
`
`
`
`any explicit supervisory function overthe rate of data trans-
`
`
`
`
`
`
`
`
`port over the various devices that comprise the network.
`
`
`
`
`
`
`
`While there are certain perceived advantages, this character-
`
`
`
`
`
`
`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 ofnetworked 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—thatis, IP is
`
`
`
`
`
`
`
`
`a protocol allowing for delivery of a datagram or packet
`
`
`
`
`
`
`
`
`between two hosts. By contrast, TCP provides a transport
`
`
`
`
`
`
`
`
`
`
`level service on top of the datagram service allowing for
`
`
`
`
`
`
`
`guaranteed delivery ofa byte stream between two IP hosts. In
`
`
`
`
`
`
`
`
`other words, TCPis 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” mechanismsoperative 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 whichbyits sliding operation essentially limits the
`
`
`
`
`
`
`amount of unacknowledgedtransmit data that a transmitteris
`SplunkInc.
`Exhibit 1005
`Page 14
`
`Splunk Inc. Exhibit 1005 Page 14
`
`

`

`
`3
`allowed to emit. Another flow control mechanism is a con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`gestion window, whichis a refinementofthe sliding window
`
`
`
`
`
`
`schemeinvolving a conservative expansion to make use ofthe
`
`
`
`full, allowable window.
`
`
`
`
`
`
`
`
`Thesliding window flow control mechanism worksin con-
`
`
`
`
`
`
`
`junction with the Retransmit Timeout Mechanism (RTO),
`
`
`
`
`
`whichis a timeout to prompta retransmission of unacknow]-
`
`
`
`
`
`
`
`
`edged data. The timeout length is based on a running average
`
`
`
`
`
`
`
`of the Round Trip Time (RTT) for acknowledgmentreceipt,
`
`
`
`
`
`
`
`i.e. if an acknowledgmentis not received within (typically)
`
`
`
`
`
`
`
`the smoothed RTT+4*mean deviation, then packet loss is
`
`
`
`
`
`
`
`inferred and the data pending acknowledgmentis re-trans-
`
`
`
`
`
`
`
`
`
`mitted. Data rate flow control mechanisms which are opera-
`
`
`
`
`
`
`
`
`tive end-to-end without explicit data rate control draw a
`
`
`
`
`
`
`
`strong inference of congestion from packet loss (inferred,
`
`
`
`
`
`
`
`
`typically, by RTO). TCP end systems, for example, will
`
`
`
`
`
`
`“back-off;’—.e., inhibit transmission in increasing multiples
`
`
`
`
`
`
`
`of the base RTT average as a reaction to consecutive packet
`loss.
`
`
`
`
`
`
`
`
`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 queuepackets and discard packets when some conges-
`tion threshold is exceeded. The discarded andtherefore unac-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`knowledged packet serves as a feedback mechanism to the
`
`
`
`
`
`
`
`TCPtransmitter. 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 ofdata
`40
`
`
`
`
`
`
`
`packets, wasting network traffic and, especially,
`inbound
`
`
`
`
`
`
`
`
`capacity of a Wide Area Network (WAN)link. In addition,
`
`
`
`
`
`
`
`
`routers can only explicitly control outboundtraffic and cannot
`
`
`
`
`
`
`prevent inboundtraffic from over-utilizing a WAN link. A5%
`
`
`
`
`
`
`
`load or less on outboundtraffic can correspondto a 100% load
`45
`
`
`
`
`
`
`
`
`on inboundtraffic, due to the typical imbalance between an
`
`
`
`
`
`
`outbound stream of acknowledgments and an inboundstream
`of data.
`
`
`
`
`
`
`
`
`
`
`In response, certain data flow rate control mechanisms
`
`
`
`
`
`
`
`
`have been developed to provide a meansto control and opti-
`
`
`
`
`
`
`
`mize efficiency of data transfer as well as allocate available
`
`
`
`
`
`
`bandwidth amonga 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 inboundtraffic and reduce the inefficiencies associ-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ated with dropped packets. Bandwidth management devices
`
`
`
`
`
`
`
`
`
`
`allow for explicit data rate control for flows associated with a
`
`
`
`
`
`
`
`
`particulartraffic classification. For example, U.S. Pat. No.
`
`
`
`
`
`
`6,412,000, above, discloses automatic classification of net-
`worktraffic 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 managementdevices allow network administra-
`
`
`
`
`
`
`
`tors to specify policies operative to control and/orprioritize
`
`
`4
`
`
`
`
`
`
`
`the bandwidth allocated to individual data lows according to
`
`
`
`
`
`
`traffic classifications. In addition, certain bandwidth manage-
`
`
`
`
`
`
`
`
`mentdevices, as well as certain routers, allow network admin-
`
`
`
`
`
`
`istrators to specify aggregate bandwidth utilization controls
`
`
`
`
`
`
`
`
`
`to divide available bandwidth into partitions. With somenet-
`
`
`
`
`
`
`
`work devices, these partitions can be configured to ensure a
`
`
`
`
`
`
`minimum bandwidth and/or cap bandwidth as to a particular
`
`
`
`
`
`
`
`class oftraffic. An administrator specifies a traffic class (such
`
`
`
`
`
`
`
`
`
`as File Transfer Protocol (FTP) data, or data flows involving
`
`
`
`
`
`
`
`
`
`a specific user) andthe size of the reserved virtual link—1.e.,
`
`
`
`
`
`
`minimum guaranteed bandwidth and/or maximum band-
`
`
`
`
`
`
`width. Such partitions can be applied on a per-application
`
`
`
`
`
`
`
`
`basis (protecting and/or capping bandwidth for alltraffic
`
`
`
`
`
`
`associated with an application) or a per-user basis (control-
`
`
`
`
`
`
`
`ling, prioritizing, 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. While the systems and methods discussed
`
`
`
`
`
`
`
`
`abovethat allow for traffic classification and application of
`
`
`
`
`bandwidth utilization controls on a per-traffic-classification
`
`
`
`
`
`
`
`
`basis operate effectively for their intended purposes, they
`
`
`
`
`
`
`
`possess certain limitations. As discussed more fully below,
`
`
`
`
`
`
`
`
`identification oftraffic types associated with data flowstra-
`
`
`
`
`
`
`
`versing an access link involves the application of matching
`
`
`
`
`
`
`criteria or rulesto explicitly presented or readily discoverable
`
`
`
`
`
`
`attributes of individual packets against an application signa-
`
`
`
`
`
`
`
`
`ture which may comprise a protocol identifier (e.g., TCP,
`
`
`
`
`
`
`
`HyperText Transport Protocol (HTTP), User Datagram Pro-
`
`
`
`
`
`
`tocol (UDP), Multipurpose Internet Mail Extensions (MIME)
`
`
`
`
`
`
`
`types, etc.), a port number, and even an application-specific
`
`
`
`
`
`
`
`string oftext in the payload ofa packet. Afteridentification of
`
`
`
`
`
`
`
`
`a traffic type correspondingto a data flow, a bandwidth man-
`
`
`
`
`
`
`
`agement device associates and subsequently applies band-
`
`
`
`
`
`
`
`width utilization controls (e.g., a policy or partition) to the
`
`
`
`
`
`
`
`data flow correspondingto the identified traffic classification
`
`
`
`
`
`
`
`or type. Accordingly, simple changes to an application, such
`
`
`
`
`
`
`
`
`
`as a string of text appearing in the payload or the use of
`
`
`
`
`
`
`
`
`encryption text may allow the application to evade proper
`
`
`
`
`
`
`classification and corresponding bandwidth utilization con-
`
`
`
`trols or admission policies.
`
`
`
`
`
`Indeed, a common use of bandwidth management devices
`
`
`
`
`
`
`
`
`
`is to limit the bandwidth being consumedby unruly, band-
`
`
`
`
`
`width-intensive applications, such as peer-to-peer applica-
`
`
`
`
`
`
`
`
`tions (e.g., Kazaa, Napster, etc.), and/or other unauthorized
`
`
`
`
`
`
`
`applications. Indeed, the rich Layer 7 classification function-
`
`
`
`
`
`
`ality of Packetshaper® bandwidth management devices
`
`
`
`
`
`
`offered by Packeteer®, Inc. of Cupertino, Calif. is an attrac-
`
`
`
`
`
`
`
`
`tive feature for network administrator, as it allows for accu-
`
`
`
`
`
`
`
`rate identification of a variety of application types. Thistraffic
`
`
`
`
`
`
`classification functionality, in many instances, uses a combi-
`
`
`
`
`
`
`
`
`nation of known protocol types, port numbers and applica-
`
`
`
`
`
`
`tion-specific attributes to differentiate between various appli-
`
`
`
`
`
`
`
`cationtraffic traversing the network. An increasing number of
`
`
`
`
`
`
`
`such peer-to-peer applications, however, employ data com-
`
`
`
`
`
`
`pression, encryption technology, and/or proprietary protocols
`
`
`
`
`
`
`that obscure or prevent identification of various application-
`
`
`
`
`
`
`
`specific attributes, often leaving well-knownport numbers as
`
`
`
`
`
`
`
`
`
`the only basis for classification. In fact, as networked appli-
`
`
`
`
`
`
`
`cations get increasingly complicated, data encryption has
`
`
`
`
`
`
`
`becomea touted feature. Indeed, encryption addresses the
`
`
`
`
`
`
`
`
`concern of security and privacy issues, but it also makes it
`
`
`
`
`
`
`
`much more difficult to identify unauthorized applications
`
`
`
`
`
`
`
`using encryption, such as the peer-to-peer applications
`
`
`
`
`
`
`“Farthstation 5” and “Winny.” In addition,traffic classifica-
`
`
`
`
`
`
`
`
`tion based solely on well-known port numbers can be prob-
`SplunkInc.
`Exhibit 1005
`Page 15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`US 7,664,048 B1
`
`20
`
`25
`
`30
`
`35
`
`50
`
`55
`
`60
`
`65
`
`Splunk Inc. Exhibit 1005 Page 15
`
`

`

`
`
`US 7,664,048 B1
`
`
`6
`
`
`
`
`
`
`
`
`the
`public or proprietary protocol. In one embodiment,
`
`
`
`
`
`
`enhancedclassification functionality analyzes the behavioral
`
`
`
`
`
`
`
`attributes of encrypted data flows against a knowledge base of
`
`
`
`
`
`
`
`
`known application behavior patterns to classify the data
`
`
`
`
`
`
`
`In one embodiment,
`the enhanced classification
`flows.
`
`
`
`
`
`
`
`mechanismsdescribed herein operate seamlessly with other
`
`
`
`
`
`
`
`Layer 7 traffic classification mechanisms that operate on
`
`
`
`
`attributes of the packets themselves. Implementations of the
`
`
`
`
`
`
`
`present invention can be incorporated into a variety of net-
`
`
`
`
`
`
`
`
`workdevices, suchas traffic monitoring devices, packet cap-
`
`
`
`
`
`
`
`ture devices, firewalls, and bandwidth managementdevices.
`
`
`5
`
`
`
`
`
`
`
`
`lematic, especially where the application uses dynamic port
`
`
`
`
`
`
`
`numberassignments or an application incorrectly uses a well-
`
`
`
`
`
`
`known port number, leading to misclassification of the data
`
`
`
`
`
`
`
`flows. In addition, classifying such encrypted networktraffic
`
`
`
`
`
`
`
`as “unknown” and applying a particular rate or admission
`
`
`
`
`
`
`
`policy to unknowntraffic classes undermines the granular
`
`
`
`
`
`
`control otherwise provided by bandwidth management
`
`
`
`
`
`
`
`
`devices and, further, may cause legitimate, encryptedtraffic
`to suffer as a result.
`
`
`
`
`
`
`
`
`
`
`In addition, network savvy users (such as students in a
`
`
`
`
`
`
`
`campus or university environment) have also become aware
`
`
`
`
`
`
`
`that bandwidth management devices have been deployed to
`
`
`
`
`
`
`limit or restrict unauthorized peer-to-peer applicationtraffic.
`
`
`
`
`
`
`
`
`
`As a result, users often attempt to bypass or thwart the band-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 1 is a functional block diagram showingatraffic
`width management schemeeffected by such bandwidth man-
`
`
`
`
`
`
`
`
`
`
`
`monitoring device according to an embodimentofthe present
`agementdevices by creating communications tunnels (proxy
`invention.
`
`
`
`
`
`
`
`tunnels) through which unauthorized or restricted network
`
`
`
`
`
`
`traffic is sent. The attributes discernible from the content of
`
`
`
`
`
`
`
`
`FIG. 2 isa functional block diagram illustrating a computer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network environment including a bandwidth management
`these tunneled data flows, however, often reveal little infor-
`
`
`
`
`
`
`20
`
`
`
`
`
`
`
`
`device according to an embodimentofthe present invention.
`mation aboutits true nature. For example, commercial HTTP
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.3 is a functional block diagram setting forth the func-
`tunnel services (such as loopholesoftware.com, TotalRc.net,
`
`
`
`
`
`
`
`
`
`
`
`
`tionality in a bandwidth management device according to an
`and http-tunnel.com, etc.) allow users to send all network
`
`
`
`
`
`
`
`
`
`
`
`
`embodimentof the present invention.
`traffic in the form of HTTPtraffic through a HTTP tunnel
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG.4 is a flow chart diagram providing a method, accord-
`between atunnelclient and an HTTP proxyserver maintained
`
`
`
`
`
`
`
`
`