US 6,684,250 B2
`(10) Patent No:
`a2) United States Patent
`Andersonetal.
`(45) Date of Patent:
`Jan. 27, 2004
`
`
`US006684250B2
`
`(75)
`
`FOREIGN PATENT DOCUMENTS
`(54) METHOD AND APPARATUS FOR
`ESTIMATING A GEOGRAPHIC LOCATION
`5456 AU
`2/2000
`AU
`WOOBIS108
`10/1995
`wo
`OF A NETWORKED ENTITY
`mG.Soni
`ee
`uO
`Inventors: Mark Anderson, Westninster, co
`WO 0022495
`4/2000
`wo
`(US); Ajay Bansal, Cupertino, CA
`WO 0067450
`5/2000
`wo
`(US); Brad Doctor, Broomfield, CO
`WO 02013459
`9/2000
`wo
`(US); George Hadjiyiannis, Boston,
`WO 00/67450
`11/2000
`wo
`MA (US); Christopher Herringshaw,
`WO 0157696 Al
`—-.2/2001
`WO
`West Wardsboro, VT (US); Eli E.
`
`
`Karplus, Baden Wiirttemberg (DE); WO 0213459 A2—8/2001wo
`Derald Muniz, Midlothian, TX (US)
`wo
`WORDPIMIIES ext
`/200.
`OTHER PUBLICATIONS
`
`(73) Assignee: Quova, Inc., Mountain View, CA (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`US.C. 154(b) by 261 days.
`
`(21) Appl. No.: 09/825,675
`>
`“4.
`(22)
`Filed:
`Apr. 3, 2001
`(65)
`Prior Publication Data
`US 2003/0074471 A1 Apr. 17, 2003
`
`(60)
`
`Harrenstcin & Stahl & Feinler; “NICNAME/WHOIS”; Net-
`work Working Group; Request for Comments: 954; Obso-
`letes: RFC 812; http:/Awww.ietf.org/rcf/rcf0954.txt
`; Oct.
`1985; (pp. 1-4).
`
`(List continued on next page.)
`Primary Examiner—Hosain T. Alam
`Assistant Examiner—Khanh Quang Dinh
`(74) Attorney, Agent, or Firm—Blakely, Sokoloff, Taylor &
`Zafman LLP
`
`ABSTRACT
`
`(57)
`Related U.S. Application Data
`:
`aad
`ned.
`A
`Provisional application No. 60/194,761, filed on Apr. 3,
`anc
`met
`an apparatus operates to associate a geo-
`od
`2000, and provisional application No. 60/241,776,
`filed on
`graphic location associated with a network address. Atleast
`Oct. 18, 2000.
`one data collection operation is performed to obtain infor-
`mation pertaining to a network address. The retrieved infor-
`
`(G1) Unt.'Cle? ccrecerermermrenenenaseeneaces GO6F 15/16 sation ik prncemsed th identify @ plurality of genmraphite
`CO) U:8: Cl ancsmccmems DDI2ES: T0PIAZS) S70292,
`locations potentially associated with the network address,
`(58) Field of Search oo... 709/203, 206,
`and to attach a confidencefactor to each ofthe plurality of
`709/220, 223, 224, 225, 226, 227, 228,
`geographic locations. An estimated geographic location is
`238; 707/102; 370/392, 242, 312, 255,
`selected from the plurality of geographic locations as being
`401; 455/424; 379/242; 710/1
`a best estimate of a true geographic location of the network
`address, where the selection of the estimated geographic
`location is based upon a degree of confidence-factor
`weighted agreementwithin the plurality of geographic loca-
`Hons.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,939,726 A
`7/1990 Flammer Oak eres 370/231
`
`18433 A
`5/1902 Baran etal 2. 370281
`(List continued on next page.)
`
`135 Claims, 64 Drawing Sheets
`(25 of 64 Drawing Sheet(s) Filed in Color)
`
`: 12;aA fo ercsenmemngiaggen nnn ~
`
`‘
`:
`'
`DATA
`at
`2 OOTON A
`'
`ANALYSIS
`‘
`‘
`|!
`‘
`SERVER
`‘
`wl
`:
`DATA
`;
`:
`og
`‘ cocnol
`“3(
`«_,|
`iB
`: i i
`'
`=I
`|:
`:
`'
`[Baia
`:
`'
`UNIFIED
`+
`[Collection
`|]
`:
`MAPPING
`CONFIDENCE
`AGENT a
`‘
`‘
`PROCESS
`MAPS
`is}:
`:
`33
`5h
`1
`;
`'
`ANALYSIS
`
`1|DATA : :
`
`}CoLLection
`J,
`:
`'
`MODULE a8
`AGENT
`:
`SEMOGRAPHIC/
`i
`:
`:
`GEOGRAPHIC
`DOMAINS
`:
`:
`at
`:
`:
`DATABASE 34
`2B
`‘
`CONSOLIDATE
`DATA
`DATA
`:
`:
`:
`
`
`
`» T|BROKERAGENT 3
`|
`COLLECTION
`+_,|
`ALGORITHM.
`J,
`COLLECTION
`4
`ri
`:
`22
`<*>
`DATA
`:
`'
`| COLLECTION
`AGENT J
`DATA
`DEMOGRAPHIC?
`WAREHOUSE|GEOGRAPHIC
`30
`DATAB:
`+
`
`
`
`
`
`Google v. Mullen
`
`Google Exhibit 1063
`Google Exhibit 1063
`Google v. Mullen
`
`DATA
`COLLECTION
`BROKER
`i
`
`7
`DATABASE
`COLLEGTION
`8
`
`BLOCKING
`ALGORITHMS
`2
`
`:
`‘
`
`:
`
`
`
`
` 18
`
`
`
`

`

`US 6,684,250 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`OTHER PUBLICATIONS
`
`Kessler and Shepard; “A Primer on Internet and TCP/IP
`Tools and Utilities”; Network Working Group; Request for
`Comments: 2151; FYI: 30; Obsoletes: RFC 1739; Category:
`Informational; Http://www.ietff.org/rfc/rfe2151.txt;
`June
`1997; (pp. 146).
`
`D. Eastlake; IBM;“Domain Name System Security Exten-
`sions”; Network Working Group; Request for Comments:
`2535; Obsoletes: 2065; Updates: 2181, 1035, 1035; Cat-
`egory: Standards Track; http://www.ietff.org/rfc/rfc2535.txt;
`Mar. 1999 (pp. 1-42).
`
`Digital Island; “Content Delivery Services: Footprint™
`Streaming Solutions’; Digital Island San Francisco, CA
`94105 USA;(4 pages), no date.
`
`Digital Island; “TraceWare White Paper’; Digital Island San
`Francisco, CA 94105 USA; Jun. 1999; (8 pages), Jun. 1999.
`
`Scott Waoley, Forbes Magazine; “We know Where You
`Live”;
`http://forbes/200/1113/
`6613332a.html;$sessionaidS$Q4DBXOQAACPO; Nov. 13,
`2000; (2 Pages).
`
`Mathew A. Debellis; “Digital Envoy Greets $1.1 Million”;
`VC & Startups; http:/Avww.redherring.com/vc/2000/0229/
`ve-digitalenvoy022900.html; Feb. 29, 2000; (3 pages).
`
`3/1994 Levy et al. 379/242
`5,291,550 A *
`
`9/1995 Allen veces
`we 370/217
`5,418,713 A
`
`5/1995 Faulk, Jr. etal.
`.
`we. 709/223
`5,421,024 A
`1/1996 Flammer,III .....
`.. 370/400
`5,488,608 A
`
`2/1996 Maceraetal. ....
`709/249
`5,490,252 A
`2/1996 Waclawskyet al.
`.. FLO/L
`5,493,689 A *
`
`6/1997 Brugger .....ceeeeeesees 705/54
`5,636,276 A
`
`8/1997 Dunn .........
`. 455/456.1
`5,659,596 A
`3/1998 Blakeleyetal.
`w+. 370/392
`5,734,651 A *
`
`3/1998 Saigh et al.
`..
`... 709/229
`5,734,823 A
`3/1998 Saigh ...........
`.. TOT/10
`5,734,801 A
`7/1998 McGarvey....
`. 370/254
`5,777,989 A
`8/1998. Allen ove.
`.. 705/27
`5,794,217 A
`2/1999.
`Jarvis et al.
`..
`«. 709/238
`5,870,561 A *
`
`.
`we. 379/219
`3/1999 Velamuri et al.
`5,878,126 A
`7/1999 Dunworth et al.
`.......... 709/217
`5,930,474 A
`8/1999 Lee et al. vccsssneeees 709/203
`5,937,163 A
`8/1999 Levy wececeeeeees
`709/218
`5,944,790 A
`9/1999 Merriman etal.
`.. 709/219
`5,948,061 A
`5,978,845 A * 11/1999 Reisacher........
`++ 709/223
`6,009,081 A * 12/1999 Wheeleret al.
`..
`.. 370/255
`6,012,052 A
`1/2000 Altschuler etal.
`.. FO7/2
`6,012,088 A
`1/2000 Lictal. wu.
`709/219
`6,012,090 A *
`1/2000 Chungetal. .
`709/219
`
`6,014,634 A
`1/2000 Scroggie et al. 0... 705/14
`3/2000 Ingrassia, Jr. et al.
`....... 709/224
`6,035,332 A
`6,091,959 A
`7/2000 Souissi et al.
`......... 340/825 .49
`... 370/400
`6,130,890 A
`10/2000 Leinwandetal.
`
`.....
`.. 709/229
`6,151,631 A
`11/2000 Ansell et al.
`6,167,259 A * 12/2000 Shah ..........
`.. 455/424
`6,192,312 Bl
`2/2001 Hummelsheim .
`. 701/118
`....
`.. 709/220
`6,243,746 BL
`6/2001 Sonduret al.
`
`... 342/450
`6/2001 Dupray.........
`6,249,252 B1
`
`. 370/401
`6,259,701 B1 *
`7/2001 Shuretal. .
`
`.. 455/434
`6,272,343 Bl
`8/2001 Pon et al.
`..
`6,356,929 B1 *
`3/2002 Gall et al.
`....
`« 709/201
`6,442,565 B1 *
`8/2002 Tyra etal. ....
`we 707/102
`6,477,150 B1 * 11/2002 Maggenti et al
`ee. 370/312
`6,542,739 B1 *
`4/2003 Garner oo... eee 455/427
`
`
`
`
`
`
`
`
`Nicole Harris, staff reporter of the Wall Street Journal;
`Digital Envoy Offers
`a Way To‘Geo-Target’;
`file://C:/
`WINNT/Profiles/jwilkins/Temporary%20Internet%20Files/
`OLK12/WSJ.com%20—@%20From%20th% ... ; Apr. 12,
`2001; (pp. 1-3).
`“Prominent Internet Industry Executives Launch Quova,
`Provide Internet Intelligence to E-businesses”, www.quo-
`va.com/pressrelease.cfm., Sep. 18, 2000.
`“Quova Brings Geography to the Internet with Introduction
`of GeoPoint 2.0”, www.quova.com/pressrelease.cfm, Feb.
`12, 2001.
`“Subnet Masking Definition”, www. exabyte.net/lambert/
`subnet/subnet_maskingdefinition.htm,
`John Lambert,
`1999.
`
`“Subnet Addressing”, Network Computing, by Ron Cooney,
`www.networkcomputing.com/unixworld,tutorial/001-html,
`(no date given).
`“ICMP”, internet.com Webopedia, www/pcwebopedia.com/
`Term/I/ICMP.html, Jul. 28, 1997.
`“DHCP”, internet.com Webopedia, www.pcwebopedia.com/
`TERM/D/DHCP.html, Dec. 23, 1996.
`US. Provisional patent application 60/132,147, filed May 3,
`1999.
`
`US. Provisional patent application 60/133,939, filed May
`13, 1999.
`US. Utility patent application Ser. No. 09/541,451, filed
`Mar. 21, 2000.
`Lamm, et al. “Real-Time Geographic Visualization of
`World Wide Web Traffic’; WWW Journal, Issue 3; 1996.
`US. patent application Ser. No. 09/541,451, Parekhet al.,
`filed Mar. 31, 2000.
`US. patent application Ser. No. 09/632,959, Parekh, filed
`Aug. 4, 2000.
`USS. patent application Ser. No. 06/132,147, Parekh, filed
`May 3, 1999.
`
` USS. patent application Ser. No. 60/194,761, Herringshaw et
`
`al., filed Apr. 3, 2000.
`US. patent application Ser. No. 60/226,405, Yerushalmi,
`filed Sep. 20, 2001.
`USS. patent application Ser. No. 60/133,939, Manaretal.,
`filed Mar. 11, 1999.
`US. patent application Scr. No. 60/241,776, Doctor ct al.,
`filed Oct. 18, 2000.
`Orkut Buyukkokten, “Exploiting Geographical Location
`Information of Web Pages” Department of Computer Sci-
`ence, Stanford University, Stanford, CA 94305; pp. 1-6.
`Kevin S. McCurley, “Geospacial Mapping and Navigation
`of the Web”; IBM Almaden Research Center; San Jose, CA
`95120; May 1-5, 2001; pp. 221-229.
`Narushige Shiode, “Analyzing the Geography of Internet
`Address
`Space”
`_hittp://geog.ucl.uk/casa/martine/inter-
`netspace; pp. 1-3; (date unknown).
`“Geographic Location Representation in DNS”; http:/Avww.
`bovine.net/~jlawson/hme/dns/location.html,; Mar. 28, 2002;
`pp. 1-3.
`URI RAZ;“Howto Find a Host’s Geographical Location?”;
`http://www.private.org.il/IP2geo.html; Mar. 28, 2002; pp.
`13.
`
`and Julio C. Navas; “Geographic
`Tomasz Imielinski
`Addressing, Routing, and Resource Discovery with the
`Global Positioning System”; Computer Science Dept. Rut-
`gers, The State University, Piscataway, NJ 08855, Oct. 19,
`1996; pp.. 1-10.
`
`

`

`US 6,684,250 B2
`
`Page 3
`
`http:/Avww.
`Internet”;
`the
`“Mapping
`F;
`Filedrive
`jevans.com/pubnetmap.html; Oct. 1995; pp. 1-4.
`
`Julio C. Navas and Tomasz Imielinski; “On Reducing the
`Computational Cost of Geographic Routing”; Rutgers Uni-
`versity, New Brunswick, NJ; Jan. 24, 2000; pp. 1-28.
`
`John S. Quarterman, Smoot Carl—Mitchell, Gretchen Phil-
`lips; “Internet Integration Pinged and Mapped”; Internet
`Interaction Proc INET; 1994; pp. 522-1 through 522-10.
`
`Martin Hamilton; “Uniform Resource Identifiers & the
`Simple Discovery Protocol”; Dept. of Computer Studies,
`Loughborough University of Technology; June 20, 1995; pp.
`1-23.
`“GPS—Based
`Tomasz Imielinski and Julio C. Navas;
`Addressing and Routing”; Computer Science Dept. Rutgers,
`The State University, Piscataway, NJ 08855, Mar. 7, 1996;
`pp. 1-35.
`Martin Dodge and Narushige Shiode; “Where on Earthis the
`Internet?”; Center for Advanced Spatial Analysis, University
`Lakshminarayanan Subramanian and Venkata N. Padma-
`College London; Mar. 1998; http://www.geog.ulc.ac.uk/
`nadhan, Randy H. Katz; “Geographic Properties of Internet
`casa/martin/internetspace/paper—telecom.html; Mar.
`28,
`Routing: Analysis and Implications”; Technical Report
`2002; pp. 1-15.
`MSR-TR-2001-89; Microsoft Research; Redmond, WA,
`Venkata N. Padmanadhan and Lakshminarayanan Subrama-
`USA; Sep. 2001; pp. 1-12.
`nian; “Determining the Geographic Location of Internet
`Hosts”;—http:/Avww.research.microsoft.com—~padmanab/;
`David Moore, Ram Periakaruppan,Jim Donohoe,K. Claffy;
`Microsoft Research, University of California Berkley.
`“Where in the World is Netgo.caida.org?”; Cooperative
`Michael F.Schwartz; “Applying an Information Gathering
`Association of Internet Data Analysis— CAIDA;http:/Avww.
`Architecture to NetFind: A White Pages Tool for a Changing
`caida.org/outreach/papers/2000/inet
`netgeo-html;
`San
`and Growing Internet”; University of Colorado Technical
`Diego, CA; pp. 1-13; (date unknown).
`Report; Dec. 1993; IEEE/ACM Transactions on Network-
`ing; 1-23.
`C. Davis, P. Vixie, T. Goodwin, I. Dickerson; “A Means for
`Expressing Location Information in the Domain Name Sys-
`tem Status of this Memo”; http:/Awww.ckdhr.com—dns—los/
`rfc1876.txt; Jan. 1996; pp. 1-17.
`C. Farrell, M. Schulze, S. Pleitner, D. Baldoni; “DSN
`Encoding of Geographical Location”; Curtin University of
`Technology; Nov. 1994; http:/Avww.cis.ohio-state .edu/cgi—
`bin/rfc1712.html; pp. 1-6.
`
`“What’S Netmask? And Why do I Need One?”, www-
`johnscloset.net/primer/subnet.html, (no date given).
`
`“Using IP Subnet Masks”, www.wizard.com/users/baker/
`public_html, (no date given).
`
`PCT—International Search Report—PCT/US01/11163—
`Aug. 20, 2001.
`
`* cited by examiner
`
`

`

`Jan. 27, 2004
`
`Sheet 1 of 64
`
`US 6,684,250 B2
`
`U.S. Patent
`
`Ol
`
`NOILW901049
`
`WALSAS
`
`NOILV901039
`
`YAWOLSNO
`
`LANYS1NI
`
`Y4SN
`
`
`
`SISATYNYGNVWALSASLANYSLNI
`
`
`NOILOITI09ANIDNA(S)ANIHOVN
`NERESY.ASNOILVOIIdd¥
`
`vivdAYSAITIOHAINOLSND
`
`ANIHOVINYSN
`
`VLVd
`
`ISNOHAYVM
`
`0€
`
`VIDO
`
`9YAAYAS
`
`AdsAIS0
`
`INIDNA
`
`9YAAYIS
`
`LZo\d¥
`
`NOILW901039
`
`
`
`I
`
`YASMOdd
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 2 of 64
`
`US 6,684,250 B2
`
`6969
`
`69
`
`
`
`ANISNAINISNA
`
`
`
`YdAYASYAAYAS
`
`AddAI10
`
`ANISNA
`
`Y3AYAS
`
`9
`
`AYJAINI¢
`
`QNIOVIS
`
`(S)HSAYAS
`
`09
`
`SUILSILVLS
`
`OINISSIIOYd
`
`INISNA
`
`Ol
`
`Ad3Al14d
`
`AdaAI140 9}INSLSAS
`
`ANISNAAdaAI1S0
`VLVd 0¢
`
`VLVO
`
`SISATYNY
`
`YdAAYaS
`
`VLVd
`
`ASNOHIYVM
`
`0€
`
`YAWOLSNO
`
`LANVYLX4
`
`
`
`NOILIST1I09VLYG
`
`
`
`WALSASSISATVNVONY
`
`VLYO
`
`NOILOIT109
`
`INIHOV
`
`02
`
`NOILOIT109
`
`ANIHOVIN
`
`0¢
`
`VLVd
`
`NOILO3T109
`
`ANIHOV
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 3 of 64
`
`US 6,684,250 B2
`
`asJINGOW/DIHAVYDOWAC©SISKIVNY
`
`€992
`
`JLVaIMOSNO)3svaviva
`19eC
`te__
`/OIHdVYuDOWIGVLVO
`JIHdVH90IN|ASNOHIYYM
`aSvavivd0€
`smaunoow|||iitsargyzi
`YLVd¥5y0ud
`:YIAYSS
`veVLVG
`
`ONINDO19
`
`daldINA
`
`INIddVAW
`
`SSIIOUd
`
`JONAGISNOI
`
`SdVW
`
`JIHdVH90I9
`
`SISATVNV
`
`Vivd
`
`NOIL937109
`
`WHIIYODTY
`
`SNIVINOGTeviwd
`
`NOILOAT109
`
`Ydy0ud
`
`VLVO
`
`NOILO31109
`
`INI9DV
`
`8
`
`VLVd
`
`NOILOFT109
`
`INI9V
`
`8
`
`VLVd
`
`NOILO31100
`
`INADV
`
`VLVd
`
`NOIL9I7100
`
`INd9V
`
`8
`
`VLVd
`
`NOILOFT109
`
`INSOV
`
`8k
`
`vLVd
`
`NOILOIT109
`
`INIDV
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 4 of 64
`
`US 6,684,250 B2
`
`38
`
`JOB REQUEST TO DATA
`COLLECTION BROKER
`
`32
`
`COLLECTION BROKER ACCEPTS REQUEST AND
`IDS COLLECTION AGENTS TO SERVICE REQUEST
`
`42
`
`(N) COLLECTION AGENTS ACCEPT JOB AND REPORT
`SUBMISSION SUCCESSFUL
`
`Ad
`
`COLLECTION BROKER WRITES START MARK AND
`SESSION ID TO COLLECTION DATABASE
`
`AG
`
`COLLECTION AGENTS PERFORM SEARCHES TO COLLECT
`
`RAW DATA AND STORES RESULTS FOR BATCH UPDATE||
`
`COLLECTION AGENTS ADVISE COLLECTION BROKER THAT
`SEARCH COMPLETE AND COLLECTION BROKER
`INSTRUCTS UPLOAD TO COLLECTION DATABASE
`
`COLLECTION BROKER INSTRUCTS COLLECTION AGENTS
`TO FLUSH LOCAL STORAGE AND ENTER IDLE STATE
`
`ANALYSIS MODULE PROCESSES RAW DATA AND WRITES
`
`DATA TO DATA WAREHOUSE
`
`FIG. 3
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 5 of 64
`
`US 6,684,250 B2
`
`G4MINS94MLNAI
`
`
`
` IN3IT9ftYASMOUEYISMOUYE
`
`
`
`
`
`IN3I19WALOYIN3I19
`
`SLSANDAYNOILY901049INNOOOV
`
`
`
`NOILY9O1039JldIDAdS
`
`NOILVWHOANINOILVWHOSNI
`
`VLvdYLVd
`
`EFS
`
`GSNldad
`
`NOILV901049
`
`VLVG
`
`
`
`SISAIVNYNOILV¥901049
`
`VvOld
`
`
`
`
`
`Pp)OO$$490ddNOWSAVGJANVYLXA84MLNA
`
`
`
`MW¥04LSANDAY
`SASVAEVLVdNOILONGOYdASNOHAYVMVLVd©)
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 6 of 64
`
`US 6,684,250 B2
`
`QSHSINId
`
`YLVd
`
`ASNOHAYVM
`
`VLIWIdd9AZAIWNV
`
`
`
`SISATVNYVLVG
`
`Y3AYAS
`
`
`
`Y¥041S4N04Y
`
`914194dS¥NO
`
`d14194dS¥NO
`
`LNI9V
`
`¥O4LSANDIY
`
`44OLSSAYCAVMYOMLAN
`
`(QNILSILNOISSIY94¥40
`
`MANY3HLIA)GAZATYNY
`
`LUVLSFf3H)ONITHSINSVLVG
`
`
`
`I3u(144)NOLLVIWHOINI
`NOILW9010499
`
`savadn|}4SSAYGdVMHOMLIN
`
`SSIYddYMHOMLIN
`
`INA9DVNOILOIT109VLG
`
`(14H)NOLLVINYOSNI
`
`NOILOITI0O0VLVd
`
`FHLONITNAINAVIVO
`dyOld
`
`
`
`Y¥O4LSANDIY
`
`ld
`
`
`
`(44)NOLLVINYOSNI
`
`914194dS¥NO
`
`
`
`SSIYddYMYOMLIN
`
`LNA9V
`
`NOILO31100WLVG
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 7 of 64
`
`US 6,684,250 B2
`
`CLIENT
`MACHINE
`DATABASE
`
`CLIENT
`MACHINE
`DATABASE
`
`CLIENT
`MACHINE
`DATABASE
`
`PRODUCT
`STAGING
`DATABASE
`
`PRODUCT
`GENERATION
`SYSTEM
`
`PRIMARY
`WAREHOUSE
`
`BACKUP DATA
`WAREHOUSE
`
`PROCESS
`
`DATA
`COLLECTION
`MACHINE
`
`DATA
`COLLECTION
`MACHINE
`
`RESEARCH
`DATABASE
`
`UNIFIED
`MAPPING
`
`FIG. 5
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 8 of 64
`
`US 6,684,250 B2
`
`SUID TO DB
`
`DCA BEGINS
`DATACOLLECTION
`
`DCB WRITES
`START AND
`
`REQUEST IS SENT TO DATA
`COLLECTION AGENT (DCA)
`
`DCA NEGOTIATES WITH DATA
`COLLECTION BROKER (DCB)
`
`DCA
`DATA COLLECTION
`AGENT
`
`DCA
`DATA COLLECTION
`BROKER
`
`INSTRUCTED TO
`
`DB, AND THE LOOP IS CLOSED
`
`DCB WAITS
`UNTIL ALL
`DCAS HAVE
`REPORTED
`IN, AT WHICH
`POINT
`THE DCAS ARE
`
`INSERT RESULTS
`INTO THE DB,
`AND FLUSH
`LOCAL
`INFORMATION
`STORES
`
`DCA INFORM DGB THATIT IS
`FINISHED. DCA WAITS FOR
`FURTHERINSTRUCTIONS
`
`UPON NOTIFICATION, THE
`DCBS FLUSH THEIR SESSION
`INFORMATION INTO THE
`
`DCA STORES
`SESSION
`INFORMATION
`LOCALLY TO
`FACILITATE
`BATCH TO THE
`COLLECTIONS
`DATABASE
`
`FIG. 6
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 9 of 64
`
`US 6,684,250 B2
`
`
`
`
`AN OPERATOR ENTERS
`
`A JOB TO BE EXECUTED VIA
`
`THE WEB INTERFACE
`
`
`
`
`OPERATORS MAY OBTAIN REAL-TIME
`STATUS OF PARTICULAR JOBS FROM
`THE DCB, VIA THE WEB INTERFACE,
`USING THE GENERATED USID.
`OPERATORS MAYALSO INTERRUPT
`JOBS, PAUSE THEM, RESTART, ETC.
`
`
`
`WEB INTERFACE.
` DCB ACCEPTS THIS REQUEST.
`ADMINISTRATIVE
`IF IT
`WORDSTATION
`1S A SCHEDULED JOB, NOTIFICATION
`IS SENT BACK TO THE WEB INTERFACE.
`OTHERWISE, THE REQUEST 1S ANALYZED
`AND SENT ON THE APPROPRIATE
`DCA MACHINES
`
`
`
`
`
`
`
`
`
`
`
`DCB MACHINE PRIMARILY
`
` DCA
`COMMUNICATION WITH THE DB
`
`
`DATA
`COLLE
`REGARDING DCA STATUS. ACTUAL
`BROKER
`INFORMATION INSERTION IS
`
`
` PERFORMED BYTHE DCBS, PER A DCB
`
`
`
`REQUEST. THE DGB IS RESPONSIBLE FOR
`PERIODIC DATA FLUSHES DURING A
`LARGE JOB EXECUTION AS DETERMINED
`BY THE DCB
`
`
`
`
`
`
`
`DCB MACHINE ACCEPTS PERIODIC
`UPDATES REGARDING DCA STATUS,
`AND WHEN NECESSARY, TAKES
`APPROPRIATE ACTION. COMMUNICATION
`BETWEEN THE DCB AND DCA MACHINES
`
`
`PRIMARILY CONSISTS OF STATUS AND
`
`
`CONTROL MESSAGES DURING A JOB’S
`
`EXECUTION
`
`
`FIG. 7
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 10 of 64
`
`US 6,684,250 B2
`
`AVWOIGOld4dFINGOWSISATYNY
`
`
`
`NOILOITIOOVLVGJHLSSHSN14
`
`
`ISNOHIYVMVLVdJHLOVOIdAHOLVEYOdVLVd
`
`
`GANIIYAYVHOdW3LONV‘NOILVANHOANISLVLS
`
`
`
`VivdGANId4¥
`
`ASNOHAYVMVLVdOL
`
`AXVHOdWALSLI40ASVaVLVG
`
`
`
`S3ZIWINIWSIHLViVGG4NId4¥u
`
`
`
`NOILONGOYdAHLNOLOVdIN!SHL
`
`ASNOHAYVMVLGNOILOFT100
`
`SNOILII1109
`
`ViVdMVd
`
`SALVWLS
`
`SOILSILVLS
`
`<4—svyodWOusVLVd——>
`
`
`
`STWAYALNIGAHOLVENI
`
`
`
`OLNIMO14dSV90FHLWOusVLVd
`
`
`
`
`
`ASVEVLVNOILOIT100VLVdSH
`
`SISATVNY
`
`SNISSIO0Ud
`
`
`
`NOILOANNODYHOMLANVSASNFINGOWSISATVNY8‘L)JH
`SISATVNY (S)ANIHOV
`SGOHLAWGANISACT1VSlIdd¥STAGOW
`
`
`“GANIVLEOSILINSAYAHOLOVASILVSVTILLNA
`
`VLVGJGISLNOG34NLVHLSNOISIOIdYO
`
`
`
`
`
`TWOIHOLSIH‘NOILVWHYOANITWOILSILVLSVLVG
`
`
`
`
`
`
`
`MVSIYOLSISVEVLVGNOILIIT109VLVGSHL
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 11 of 64
`
`US 6,684,250 B2
`
`OBTAIN NETWORK ADDRESS(E.G., IP ADDRESS) TO BE MAPPED
`(E.G., FROM INTERNAL PROCESS OR FROM CUSTOMER)
`AND QUEUE IN MAIN QUEUE
`
`72
`
`RUN CONSOLIDATED DOMAINS ALGORITHM
`18
`ADDRESS INTO MAIN QUEUE
`
`INSERTINTO
`WAREHOUSE
`
`YES
`
`SATISFIED?
`76
`
`NO
`
`RE-INSERT NETWORK ADDRESS INTO MAIN QUEUE AND FLAG
`AS HAVING FAILED CONSOLIDATED DOMAIN ALGORITHM
`
`RUN BLOCKING ALGORITHM(S) TO DETERMINE
`BLOCK SIZE AROUND NETWORK ADDRESS
`
`INSERT BLOCK (IF GENERATED) WITH NETWORK
`
`FIG. 9A
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 12 of 64
`
`US 6,684,250 B2
`
`RUN EXACT ALGORITHMS ON NETWORK ADDRESS
`
`(OR 1 OR MORE NETWORK ADDRESSIN BLOCK)
`
` SUCCESSFUL AND
`BLOCKING VERIFIED?
`
`
`
`88
`NO
`
`YES
`
`INSET INTO DATA
`WAREHOUSE 4
`
`92
`
`RUN INEXACT ALGORITHMS AND UNIFIED MAPPING PROCESS
`ON NETWORK ADDRESS (OR 1 OR MORE NETWORK
`ADDRESSIN BLOCK)
`
`YES
`
`INSET INTO DATA
`WAREHOUSE gg
`
`NO
`
`FORWARD TO RESOLUTION MANUAL RESOLUTION
`
`FIG. 9B
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 13 of 64
`
`US 6,684,250 B2
`
`102
`
`PC
`1.1,1.259
`
` ROUTER
`
`
`FIG. 10A
`
`ROUTER 1
`
`FIG. 1OB
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 14 of 64
`
`US 6,684,250 B2
`
`XId4dNS
`
`OFTHOIMONVS
`
`vel
`
`oO}
`—N—_
`
`NOILV901
`
`$$490ud
`
`élYOLVISNVYL
`
`AOWENIDOVJONAGISNOO
`8cl=:‘SLINSAYGNA
`1d18NOILYIO1
`SISSHLNAS
`
`
`STINGOWNOLVNIWYSLAGNOILV901
`
`TTDIA
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 15 of 64
`
`US 6,684,250 B2
`
`OSl
`
`000010
`
`0002
`
`0009
`
`
`
`0005000r000€0002
`
`WOO18MHYOMLANNISAGON40YAEWAN
`
`VelOld
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 16 of 64
`
`US 6,684,250 B2
`
`fo £60
`
`45
`
`Ag
`
`a5
`
`30
`
`°
`
`can
`
`Confidence
`15 Factor
`
`19
`
`String Length
`
`FIG. 128
`
`500K
`
`50K
`
`a
`rei
`
`%:
`
`5
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 17 of 64
`
`US 6,684,250 B2
`
`
`
`RECEIVE INPUT (E.G., TRACE ROUTE)
`
`1
`NO
`
`
`
`
`
` HOST
`NAME INCLUDED |
`INPUT DATA?
`
`
` PARSE HOST NAME BY
`
`DELIMITER CHARACTERS 47
`
`
`
`
`
`RUN COMPARISONS ON WORD/PHRASES(1)
`INDIVIDUALLY AND (2) IN CONJUNCTION WITH
`NEIGHBOR WORDS TO DETECT PATTERNS
`
`
`CORRESPONDING TO PLACE NAMES/GEOGRAPHIC
`
`LOCATIONS
`480
`
`
`
`USE MULTIPLE CONFIDENCE MAPS TO
`ATTACH CONFIDENCE FACTORS TO
`IDENTIFY GEOGRAPHIC LOCATIONS
`
`
`
`
`
`
`
`
`OUTPUT MULTIPLE GEOGRAPHIC
`
`LOCATIONS AND ASSOCIATED CONFIDENCE
`FACTORS TO THE LOCATION FILTER
`
`FIG. 13
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 18 of 64
`
`US 6,684,250 B2
`
`100
`
`80
`
`‘9
`
`4g
`
`30
`
`
`
`ConnectivityIndex
`
`ne2
`
`°
`
`O02
`
`~y
`
`8
`
`a
`Oe
`
`—
`
`Hop Ratio
`
`FIG. 144
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 19 of 64
`
`US 6,684,250 B2
`
`CONFIDENCE
`
`FACTOR “yoftfttt
`
`05
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`LENGTH OF STRING
`
`FIG. 14B
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 20 of 64
`
`US 6,684,250 B2
`
`
`
`
`
`NumberofLocationBeterminatesGeneratedbytheString
`
`o
`
`hs
`
`tat
`
`1005
`
`SI 194
`
`5
`
`e
`
`7
`
`Length of String
`
`FIG. 14€
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 21 of 64
`
`US 6,684,250 B2
`
`500000,
`
`
`Population
`
`50000)
`
`Lie
`
`ih
`
`196
`
`45
`
`iF
`
`awh ah
`
`elt oe
`
`be
`
`ah
`
`‘ed
`
`Length of String
`
`Fic. 140
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 22 of 64
`
`US 6,684,250 B2
`
`100
`
`70
`
`60
`
`tyIndex
`
`ivi
`
`Connect
`
`2
`
`30
`
`4
`Length of String
`
`on
`
`oh
`
`™a
`
`FIG. 14E
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 23 of 64
`
`US 6,684,250 B2
`
`0.8
`
`0.8]
`
`ov]
`
`O,4
`
`6
`
`0.8
`
`0.4
`
`0.3
`
`O.2
`
`+0
`
`100
`
`1000
`
`1oc0o
`
`Tiistance in Miles to Last Enown Host
`
`FIG. L4F
`
`
`
`HopRatioofLastKnownHost
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 24 of 64
`
`US 6,684,250 B2
`
`
`
`soo
`
`4090
`
`
`
`
`
`NumberofHopsBetweenFhisHostandLastKnownHop
`
`10
`
`Tistance in Miles to Last KRnown Hast
`
`FIG. 14G
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 25 of 64
`
`US 6,684,250 B2
`
`204
`
`Populat
`
`£ThisHostandLastKnownHop
`
`ionoO
`
`nim o
`
`anoO
`
`500
`fistance in Miles to Last Known Host
`
`5000
`
`FIG. 146
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 26 of 64
`
`US 6,684,250 B2
`
`s 206
`
`
`
`:
`
`50
`
`tyofthisHostandLastZnownHop 20
`
`is
`
`10
`
`&
`
`G
`
`590
`
`5000
`
`Distance in Miles to Last Known Host
`
`FIG. 141
`
`par
`
`a2
`
`58
`
`F
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 27 of 64
`
`US 6,684,250 B2
`
` AS
`
`AO
`
`ra
`iy
`
`4
`
`el
`
`15
`
`40
`
`5
`
`0
`
`O
`10
`
`1000
`100
`Bistance in Miles to hast Known Host
`
`10000
`
`e
`8
`
`a 5
`
`8 %a =
`
`|3 a
`
`3Q
`
`u
`a
`iri
`
`FIG. 143
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 28 of 64
`
`US 6,684,250 B2
`
`
`
`tx}
`
`TAO
`
`
`
`HumberofHopsBetweenThisHostandNextKnowHop
`
`+0
`
`Distance in Miles to Next Known Host
`
`FIG. 14k
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 29 of 64
`
`US 6,684,250 B2
`
`
`
`
`
` inimumPopulationofThisHostandNextKnownHop
`
`Distance in Miles to Next Known Host
`
`Fic.
`
`1J4L
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 30 of 64
`
`US 6,684,250 B2
`
`
`
`
`
` inimenConnectivityofThisHostandNextEnownHop
`
`Distance in Miles to Next Enown Hoet
`
`FIG. 14M
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 31 of 64
`
`US 6,684,250 B2
`
`216 YOLOVA
`
`ADNACIANOO
`
`POPULATION
`
`FIG 14N
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 32 of 64
`
`US 6,684,250 B2
`
`ax OG
`
`90
`
`Comnectivity
`
`Index
`
`ne
`
`40
`
`ae
`
`Means of Last Known Hop and Next Known Hop Connectivity Indices
`
`Fie. 146
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 33 of 64
`
`US 6,684,250 B2
`
`220
`
`35
`
`aai1141111aee ee
`
` oOoNNNTC
`
`
`
`YOLOVAADNACISANOD
`
`90
`
`100
`
`CONNECTIVITY INDEX
`
`FIG. 14P
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 34 of 64
`
`US 6,684,250 B2
`
`222 YOLOVA
`
`SJONSGIANOO©
`
`POSITION OF 1ST CHARACTER OF WORD IN HOSTNAME
`
`FIG. 14Q
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 35 of 64
`
`US 6,684,250 B2
`
`242
`
`PARSE QUERY RESULTS TO
`EXTRACT GEOGRAPHIC
`INFORMATION
`
`INITIATE EXTERNAL DATA COLLECTION
`ROUTINE TO QUERY MULTIPLE IP
`REGISTERING AUTHORITIES
`(DRILL DOWN) TO OBTAIN NET RECORDS
`
`FACTORS TO THE LOCATION FILTER 50
`
`STORE GEOGRAPHIC INFORMATION IN
`ASSOCIATION WITH NETWORK ADDRESS
`RANGE (NETWORKBLOCK)
`
`USE MULTIPLE CONFIDENCE MAP
`TO ATTACH CONFIDENCE FACTORS
`TO GEOGRAPHIC LOCATIONS/
`INFORMATION
`
`OUTPUT MULTIPLE GEOGRAPHIC
`LOCATIONS AND ASSOCIATED CONFIDENCE
`
`FIG. 15
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 36 of 64
`
`US 6,684,250 B2
`
`HopRatio
`
`a 100
`
`180
`
`200
`
`250
`
`300
`
`380
`
`400
`
`450
`
`Distance in Miles Between Last Known Hop and Net
`
`FIG.
`
`164A
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 37 of 64
`
`US 6,684,250 B2
`
`262
`
`'1iti411ttt''1
`
`50
`
`oOwt
`
`YOLOWA
`
`oOoONN—-
`
`ADNACISANOO oO=
`
`e- ewe ee ee eee ee hee ee eee eh eee
`
`wee te te er eee
`
`cc eee er te eee ee eee
`
`starr tr rrr rrr tert tree
`
`0?
`
`NUMBER OF NODES IN REGISTERED BLOCK
`
`FIG. 16B
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 38 of 64
`
`US 6,684,250 B2
`
`HopRatio
`
`S00
`
`350
`
`400
`
`450
`
`OY
`
`of
`
`106
`
`150
`
`200
`
`250
`
`Distance imn Miles Between Last Known Hop and Net
`
`FIG.
`
`16€C
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 39 of 64
`
`US 6,684,250 B2
`
`AONACIANOO
`
`266 YOLOVA
`
`CONNECTIVITY INDEX
`
`FIG. 16D
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 40 of 64
`
`US 6,684,250 B2
`
`268 YOLOVA
`
`JONACISNOO
`
`POPULATION
`
`FIG. 16E
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 41 of 64
`
`US 6,684,250 B2
`
`270
`
`INITIATE EXTERNAL DATA COLLECTION
`ROUTINE TO QUERY DNS REGISTRIES
`FOR DNS RECORDS
`
`PARSE DNS RECORDS TO
`EXTRACT GEOGRAPHIC
`INFORMATION
`
`STORE GEOGRAPHIC INFORMATION IN
`ASSOCIATION WITH DOMAIN NAME
`
`USE MULTIPLE CONFIDENCE MAP
`TO ATTACH CONFIDENCE FACTORS
`TO GEOGRAPHIC LOCATIONS
`
`28
`
`OUTPUT MULTIPLE GEOGRAPHIC
`LOCATIONS AND ASSOCIATED CONFIDENCE
`FACTORS TO THE LOCATION FILTER
`
`FIG. 17
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 42 of 64
`
`US 6,684,250 B2
`
`¢i
`
`
`
`HopRatio
`
`
`
`
`
`20H)
`
`ane
`
`PO
`
`BOO
`
`{SR6
`
`i
`
`Distance in Miles Between Last Known Hop and DNS
`
`FIG. 184
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 43 of 64
`
`US 6,684,250 B2
`
`292
`
`a YOLOVA
`
`JONACISNOO
`
`DISTANCE IN MILES BETWEEN NET AND DNS
`
`FIG. 18B
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 44 of 64
`
`US 6,684,250 B2
`
`HopRatio
`
`0
`
`200
`
`400
`
`BCH}
`
`800
`
`
`nog
`
`Distance in Miles Between Next Known Hop and DNS
`
`Fic. 18c
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 45 of 64
`
`US 6,684,250 B2
`
`296 YOLOVA
`
`JONACIANOO
`
`CONNECTIVITY INDEX
`
`FIG. 18D
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 46 of 64
`
`US 6,684,250 B2
`
`0000S1
`
`000002 86¢
`
`OOO00L
`
`YOLOVA AONACISANOO
`
`NOILV1NdOd
`
`H81
`OIA
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 47 of 64
`
`US 6,684,250 B2
`
`HopRatio
`
`35
`
`««ADDSs«ASSCSOO
`
`SO 1M
`
`180) 2a
`
`Distance in Miles Between Last Known Hop and ASN
`
`FIG. 194
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 48 of 64
`
`US 6,684,250 B2
`
`COE
`
`
`
`OlgDlZOpO0!
`
`YOLOVA ADNACISANOD
`
`AOO18SVNISHCON4OYAEWNN
`
`dqd6lOl
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 49 of 64
`
`US 6,684,250 B2
`
`3 on
`
`200. SCCM ASS
`18D
`100
`so)
`Distance in Miles Between Next Known Hop and ASN
`
`FIG. 19¢
`
`HopRatio
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 50 of 64
`
`US 6,684,250 B2
`
`001 90€
`
`YOLOVA AONACISANOOD
`
`
`
`XAOGNIALIAILOANNOO
`
`dolDIA
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 51 of 64
`
`US 6,684,250 B2
`
`80¢
`
`NOILV1NdOd
`
`YOLOVA ADNACISANOOD
`
`HolDIA
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 52 of 64
`
`US 6,684,250 B2
`
` 4
`
`2
`4
`5
`8
`a
`1m
`Number of Hops Between This Host and the Last Known Hop
`
`FIG. 204
`
`
`
`TheStoredConfidenceFactoraftheLastKnownHop
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 53 of 64
`
`US 6,684,250 B2
`
`HopRatio
`
`1
`
`45
`
`2
`
`25
`
`24
`
`fad st
`
`4
`
`Number of Hops Between This Host and the Last Known Hop
`
`FIG. 208
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 54 of 64
`
`US 6,684,250 B2
`
` vee
`
`YOLOVA AONACIANOO
`
`{901
`
`
`
`SNG'‘LAN}OLSATINNIJONVLSICLSSLHYOHS
`
`JOCOIA
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 55 of 64
`
`US 6,684,250 B2
`
`330
`
`s
`
`8 s8
`
`1
`
`2
`
`a
`
`4
`
`5
`
`6
`
`8
`
`g
`
`10
`
`Number of Hops Between This Bost and the Next Known Hop
`
`FIG. 21A
`
`
`
`TheStoredConfidenceFactoroftheNextKnownHop
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 56 of 64
`
`US 6,684,250 B2
`
` opaeydog
`
`aay
`
`oa=
`
`Rumber of Hops Between This Host and the Next Known Hop
`
`FIG.
`
`2iB
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 57 of 64
`
`US 6,684,250 B2
`
`QOO0L vee
`
`0001OOL
`
`YOLOVA AONACIANOD
`
`
`
`{901'SNG'‘LAN}OLSATINNIJONVLSICLSALYOHS
`
`JICDIA
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 58 of 64
`
`US 6,684,250 B2
`
`
`
`
`BOTH LKH
`
`HAVE GENERATE LOCATION
`DETERMINANTS
`
`340
`
`RECEIVE LOCATION DETERMINANTS
`
`FROM LKH AND HKHS LDMS A4
`
`
`IDENTIFY LOCATION DETERMINANT
`WITH HIGHEST CONFIDENCE FACTOR
`
`
`
`
`
`
`
`
`ASSIGN CONFIDENCE FACTOR TO IDENTIFIED
`
`
`LOCATION DETERMINANT BASED ON (1) JOINT
`CONFIDENCE FACTORSAND (2) DISTANCE
`
`
`BETWEEN LKH AND NKH LOCATION
`DETERMINANTS USING CONFIDENCE MAP 348
`
`
`
`
`
`
`
`OUTPUT LOCATION DETERMINANT AND
`CONFIDENCE FACTOR TO LOCATION
`FILTER
`
`
`
`FIG, 22
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 59 of 64
`
`US 6,684,250 B2
`
`KnownHop MeanConfidenceFactorofLastKnownHopand
`
`
`
`Next
`
`Me
`
`zu
`
`a
`
`
`
`
`
`Bee
`
`BO
`
`
`
`Distance in Miles Between Last Known Hop and Next Kniwn Hop
`FIG. 23
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 60 of 64
`
`US 6,684,250 B2
`
`RUN HIGH ACCURACYLDM (E.G, SUFFIX LDM) TO
`GENERATEFILTER LOCATION DETERMINANT
`AND ASSOCIATED CONFIDENCE FACTOR
`
`36
`
`360
`
`DELIVER FILTER LOCATION DETERMINANT
`AND CONFIDENCE FACTOR TO
`FILTER BROKER
`
`68
`
`FILTER PROCESS DETERMINANT WHATEVER
`FILTER LOCATION DETERMINANT IS
`STATE/ROUTINE COUNTRY
`
`FILTER PROCESS INTERCEPTS MULTIPLE
`LOCATION DETERMINANT OUTPUTTED BY
`COLLECTION OF LDMS AND CHECK EACH
`LOCATION DETERMINANT FOR AGREEMENT
`WITH FILTER LOCATION DETERMINANT
`
`REMOVE FROM
`INPUT STACK
`FOR LOCATION
`SYNTHESIS
`PROCESS
`
`
`
`
`374
`
`NO
`
`
`
`
`SUFFICIENT
`YES
`AGREEMENT?
`
`
`FIG. 24
`
`ADD TO INPUT
`STACK FOR
`LOCATION
`SYNTHESIS
`PROCESS
`
`
`
`372
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 61 of 64
`
`US 6,684,250 B2
`
`380
`
`COMPARE LOCATION DETERMINANTS
`AGAINST EACH OTHER
`
`BUILD CONFIRMATION
`CONFIDENCE FACTOR TABLE
`
`38
`
`IDENTIFY LOCATION DETERMINANT
`THAT HAS HIGHEST DEGREE OF CONFIDENCE
`FACTOR-WEIGHED AGREEMENTWITH
`ALL OTHER LOCATION DETERMINANTS
`
`COLLAPSE SEPARATE CONFIDENCE
`FACTOR INTO A COMBINED
`CONFIDENCE FACTOR
`
`FIG. 25
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 62 of 64
`
`US 6,684,250 B2
`
`400
`
`CORRECT
`
`INCORRECT
`
`0
`
`70 80
`40 50 60
`30
`10 20
`INTERNAL CONFIDENCE
`
`90 100
`
`FIG. 26
`
`402
`
`-TP TT VT TE
`1
`—-_=_b ee de oe el
`
`0
`
`10
`
`20
`
`30
`
`40
`
`100
`
`INTERNAL CONFIDENCE
`
`
`
`
`
`AOVENDOVALINEVdOddLNSAOY3d
`
`404
`
`FIG, 27
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 63 of 64
`
`US 6,684,250 B2
`
`408
`
`406
`
`i--
`
`Jd--
`
`Jn. -
`
`Or--
`
`70
`
`80
`
`INTERNAL CONFIDENCE
`
`FIG. 28
`
`-eaeec
`
`?J1!
`
`ere 4
`
`i]
`
`1
`
`c
`
`0
`
`10
`
`20 30 40 50
`
`60 70 80
`
`90 100
`
`INTERNAL CONFIDENCE
`
`FIG, 29
`
`SOaomnreonwntON
`
`0 0 0 0 0 0 0 0 0 0 0
`
`D
`
`AOVENDOVALIIEGVEOddLNADYSd
`
`
`
`
`
`AOVENDOVALNIaVdOudLNADYAd
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 27, 2004
`
`Sheet 64 of 64
`
`US 6,684,250 B2
`
`500
`
`x
`
`510
`
`VIDEO DISPLAY
`
`512
`
`514
`
`ALPHA-NUMERIC
`INPUT DEVICE
`
`CURSOR CONTROL
`
`DEVICE
`INSTRUCTIONS
`
`COMPUTER-READABLE
`MEDIUM
`
`518
`
`SIGNAL GENERATION
`
`DEVICE
`
`508
`
`502
`
`524
`
`504
`
`524
`
`506
`
`520
`
`PROCESSOR
`
`NSS
`
`INSTRUCTIONS
`
`
`
`
`INSTRUCTIONS
`
`STATIC
`MEMORY
`
`NETWORK
`
`INTERFACE
`
`FIG. 30
`
`

`

`US 6,684,250 B2
`
`1
`METHOD AND APPARATUS FOR
`ESTIMATING A GEOGRAPHIC LOCATION
`OF A NETWORKED ENTITY
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application claims the benefit of U.S. Provisional
`Application No. 60/194,761, filed Apr. 3, 2000 and U.S.
`Provisional Application No. 60/241,776 filed Oct. 18, 2000.
`FIELD OF THE INVENTION
`
`invention relates generally to the field of
`The present
`geographic location determination and, more specifically, to
`a method and apparatus for estimating the geographic loca-
`tion of a network entity, such as a node coupled to the
`Internet.
`
`BACKGROUND OF THE INVENTION
`
`Geography plays a fundamental role in everyday life and
`effects,
`for example, of the products that consumers
`purchase, shows displayed on TV, and languages spoken.
`Information concerning the geographic location of a net-
`worked entity, such as a network nade, may be useful for any
`numberof reasons.
`
`Geographic location maybe utilized to infer demographic
`characteristics of a network user. Accordingly, geographic
`information maybe utilized to direct advertisementsor offer
`other information via a network that has a higher likelihood
`of being the relevant to a network user at a specific geo-
`graphic location.
`Geographic information mayalso be utilized by network-
`based content distribution systems as part of a Digital Rights
`Management (DRM)program oran authorization process to
`determine whetherparticular content mayvalidly be distrib-
`uted to a certain network location. For example, in terms of
`a broadcast or distribution agreement, certain content may
`be blocked from distribution to certain geographic areas or
`locations.
`
`Content delivered to a specific network entity, at a known
`geographic location, may also be customized according to
`the known geographic location. For example,
`localized
`news, weather, and events listings may be targeted at a
`network entity where the geographic location of the net-
`worked entity is known. Furthermore content may be pre-
`sented in a local language and format.
`Knowingthe location of network entity can also be useful
`in combating fraud. For example, where a credit card
`transaction is initiated at a network entity, the location of
`which is known and far removed from a geographic location
`associated with a owner of credit card, a credit card fraud
`check may beinitiated to establish the validity of the credit
`c