`U3006684250B2
`
`(12) United States Patent
`(10) Patent No.:
`US 6,684,250 132
`
`Anderson et al.
`(45) Date of Patent:
`Jan. 27, 2004
`
`(54) METHOD AND APPARATUS FOR
`ESTIMATING A GEOGRAPHIC LOCATION
`
`(75)
`
`OF A NETWORKED ENTITY
`Inventors: Mark Anderson, Westminster, CO
`(US); Ajay Bansal, Cupertino, CA
`(US); Brad Doctor, Broomfield, CO
`(US); George Hadjiyiannis, Boston,
`MA (US); Christopher Herringshaw,
`West W'ardsboro, VT (US); Eli E.
`Karplus, Baden Wiirttemberg (DE);
`Derald Muniz, Midlothian, TX (US)
`
`(73) Assignee: Quova, Inc., Mountain View, CA (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 261 days.
`
`.
`..
`,
`(21) Appl No . 09/825 675
`
`(22)
`(65)
`
`(60)
`
`Filed:
`
`AP“ 3! 2001
`Prior Publication Data
`US 2003/0074471 A1 Apr. 17, 2003
`
`Related US. Application Data
`Provisional application No. 60/194,761, filed on Apr. 3,
`2000, and provisional application No. 60/241,776, filed on
`Oct. 18 2000.
`,
`
`Int Cl 7
`G 06F 15/16
`(51)
`,
`.
`.
`
`709/225’ 709/228’ 370/392
`(52)
`(58) Field of Search ................................. 709/203, 206;
`709/220, 223’ 224’ 225’ 226’ 227’ 228’
`238; 707/102; 370/392, 242; 312’ 255’
`401; 455/424; 379/242; 710/1
`
`(56)
`
`References Clted
`U.S. PATENT DOCUMENTS
`4,939,726 A
`7/1990 Flammer et al.
`............ 370/231
`
`8/1991 Dighe et al. .......... 370/400
`5,042,032 A
`................ 370/231
`5,115,433 A
`5/1992 Baran et al.
`
`AU
`W0
`$8
`W0
`wo
`W0
`W0
`W0
`W0
`W0
`
`FOREIGN PATENT DOCUMENTS
`5456 AU
`2/2000
`W0 9613108
`10/1995
`33189993338:
`12/133:
`W0 0022495
`4/2000
`wo 0067450
`5/2000
`WO 02013459
`9/2000
`WO 00/67450
`11/2000
`W0 0157696 A1
`2/2001
`W0 0213459 A2
`8/2001
`W0 0217139 A1
`8/2001
`OTHER PUBLICATIONS
`
`Harrenstein & Stahl & Feinler; “NICNAME/WHOIS”; Net—
`work Working Group; Request for Comments: 954; Obso-
`letes: RFC 812;
`littp://www.ietf.org/rcf/rcf0954txt
`; 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%lakely, Sokoloff, Taylor &
`Zafman LIP
`
`ABSTRACT
`
`(57)
`.
`d
`h d
`A
`a?
`an apparatusoperates [O aSSOCIale a geo-
`me} 0
`graphic location assoc1ated With a network address. At least
`one data collection 0 eration is
`erformed to obtain infor-
`P
`P
`
`mation pertaining to a network address. The retrieved infor—
`mation is processed to identify a plurality of geographic
`locations potentially associated with the network address,
`and to attach a confidence factor to each of the plurality Of
`geographic locations. An estimated geographic location is
`selected from the plurality of geographic locations as being
`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
`ions.
`yyeighted agreement Within the plurality ot geographic loca-
`
`.-
`.
`135 Clalms’ 64 Drawmg Sheets
`
`(List continued on next page.)
`
`(25 of 64 Drawing Sheet(s) Filed in Color)
`
`......................
`?
`DATA
`M:
`
`-
`
`7
`1
`
`2 will?
`
`
`
`AGENT
`
`n
`COLLECTION
`AGENT
`
`fl
`
`fl
`
`3
`DATA
`;
`,
`‘*
`= 001E110
`5
`m T’
`;
`DATA
`1
`:
`CDLLECTlUN
`‘
`1
`AGENTW
`1
`;
`7
`T
`1
`1
`1
`DATA
`1
`1
`“WWW” 4- 1
`1
`AGENT
`;
`;
`1
`:
`__,
`l
`3
`I
`‘
`:
`‘— l
`1
`1
`‘
`12 1
`
`001221.01 5. 5
`:
`I j I
`:
`
`i
`
`5
`:
`=
`5
`-
`I
`
`.
`:
`:
`:
`.
`E
`'
`
`:
`:
`
`
`
`
`DATA
`
`z
`
`BROKER
`g
`
`
`
`;
`:
`
`g
`
`033,550,110,”
`25
`
`CONHDENCE
`MAPS
`E
`
`JEMOGRAPHTC/
`GEOGRAPHlC
`DATABASE 31
`
`VVVVVVVVV
`s
`c
`
`{$841115
`m
`
`UNIFlED
`MAPFTNG
`PROCESS
`m
`
`
`
`$3001: 253
`
`segues/(1‘3?
`
`
`
`
`
`W,
`--------------------------------
`39
`
`WAREHOUSE
`
`‘0
`
`Page 1 of 100
`
`GOOGLE EXHIBIT 1019
`
`Page 1 of 100
`
`GOOGLE EXHIBIT 1019
`
`

`

`Us 6,684,250 B2
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`/1994 Levy et a1.
`................. 379/242
`5,291,550 A *
`/1995 Allen
`.. 370/217
`5,418,713 A
`
`5/1995 Faulk, Jr. et a1.
`.. 709/223
`5,421,024 A
`/1996 Flammer, III
`.. 370/400
`5,488,608 A
`......
`/1996 Macera et a1.
`.. 709/249
`5,490,252 A
`
`/1996 Waclawsky et a1.
`..... 710/1
`5,493,689 A *
`6/1997 Brugger ....................... 705/54
`5,636,276 A
`8/1997 Dunn ...................... 455/456.1
`5,659,596 A
`/1998 Blakeley et a1.
`..... 370/392
`5,734,651 A *
`/1998 Saigh ct a1.
`.. 709/229
`5,734,823 A
`/1998 Saigh ..........
`707/10
`5,734,891 A
`7/1998 McGarvcy
`.. 370/254
`5,777,989 A
`/1998 Allen ..........
`705/27
`5,794,217 A
`/1999 Jarvis et a1.
`.. 709/238
`5,870,561 A *
`.. 379/219
`/1999 Velamuri et a1.
`5,878,126 A
`
`.......... 709/217
`7/1999 Dunworth et a1.
`5,930,474 A
`................... 709/203
`8/1999 Lee et a1.
`5,937,163 A
`8/1999 Levy ..............
`.. 709/218
`5,944,790 A
`
`.. 709/219
`9/1999 Merriman et al.
`5,948,061 A
`.......
`.. 709/223
`5,978,845 A * 11/1999 Reisacher
`
`.. 370/255
`6,009,081 A * 12/1999 Wheeler et a1.
`1/2000 Altschuler et a1.
`..... 707/2
`6,012,052 A
`6,012,088 A
`1/2000 Li et a1.
`..........
`.. 709/219
`.. 709/219
`6,012,090 A *
`1/2000 Chung et a1.
`
`.............. 705/14
`6,014,634 A
`1/2000 Scroggie et a1.
`6,035,332 A
`3/2000 Ingrassia, Jr. et a1.
`...... 709/224
`6,091,959 A
`7/2000 Souissi et a1.
`......... 340/82549
`..... 370/400
`6,130,890 A
`10/2000 Leinwand et a1.
`
`.. 709/229
`6,151,631 A
`11/2000 Ansell et a1.
`
`6,167,259 A * 12/2000 Shah ..............
`.. 455/424
`
`2/2001 Hummelsheim
`.. 701/118
`6,192,312 B1
`
`.. 709/220
`..
`6,243,746 B1
`/2001 Sondur et a1.
`
`
`.. 342/450
`6,249,252 B1
`/2001 Dupray ........
`.................. 370/401
`6,259,701 B1 ’*
`7/2001 Shur et a1.
`6,272,343 B1
`8/2001 Pon et a1.
`................... 455/434
`6,356,929 B1 ’*
`1’2002 Gall et a1.
`.. 709/201
`......
`6,442,565 B1 *
`/2002 Tyra et a1.
`.. 707/102
`6,477,150 B1 * 11/2002 Maggenti et a1.
`.. 370/312
`6,542,739 B1 *
`4/2003 Garner
`....................... 455/427
`
`
`
`OTHER PUBLICATIONS
`
`Kessler and Shepard; “A Primer on Internet and TCP/TP
`Tools and Utilities”; Network Working Group; Request for
`Comments: 2151; FYI: 30; Obsoletes: RFC 1739; Category:
`Informational; Http://www.ictff.org/rfc/rfc2151.txt;
`June
`1997; (pp. 1—46).
`
`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: FootprintTM
`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 W'ooley, Forbes Magazine; “We know Where You
`Live”;
`http://forbes/200/1113/
`6613332a.html;$sessionaid$Q4DBXOQAACPO; Nov. 13,
`2000; (2 Pages).
`
`Mathew A. Debellis; “Digital Envoy Greets $1.1 Million”;
`VC & Startups; http://'Www.redherring.corn/vc/2000/0229/
`vc—digitalenvoy022900.html; Feb. 29, 2000; (3 pages).
`
`Page 2 of 100
`
`Nicole Harris, staff reporter of the Wall Street Journal;
`Digital Envoy Offers a Way To‘Gco—Targct’;
`filc://C:/
`WINNT/Profiles/jwilkins/Te111porary%2OInternet%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.coIn/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. exabytenel/lambert/
`subnet/subnetimaskingidefinitionhtm,
`John Lambert,
`1999.
`
`“Subnet Addressing”, Network Computing, by Ron Cooney,
`www.11etworkcomputing.com/unixworld,tutorial/001.html,
`(no date given).
`“ICMP”, internetcom Webopedia, www/pcwebopediacom/
`Term/I/ICMP.htm1, Jul. 28, 1997.
`“DHCP”, internet.cam Webopediu, www.pcwebopedia.com/
`TERM/D/DHCPhtml, 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.
`LS. patent application Ser. No. 09/541,451, Parekh et al.,
`filed Mar. 31, 2000.
`LS. patent application Ser. No. 09/632,959, Parekh, filed
`Aug. 4, 2000.
`LS. patent application Ser. No. 06/132,147, Parekh, filed
`May 3, 1999.
`L .S. patent application Ser. No. 60/194,761, Herringshaw ct
`
`LS. patent application Ser. No. 60/226,405, Yerushalmi,
`filed Sep. 20, 2001.
`LS. patent application Ser. No. 60/133,939, Manar et al.,
`filed Mar. 11, 1999.
`LS. 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 175, 2001; pp. 221729.
`Narushige Shiode, “Analyzing the Geography of Internet
`Address
`Space”
`http://geogucl.nk/casa/martine/inter-
`netspace; pp. 1—3; (date unknown).
`“Geographic Location Representation in DNS”; http://www.
`bovine.net/~jlawson/hmc/dns/location.html; Mar. 28, 2002;
`pp. 1—3.
`URI RAZ; “How to Find a Host’s Geographical Location?”;
`http://www.private.org.il/IP2geo.html; Mar. 28, 2002; pp.
`1—3.
`
`Tomasz Imielinski and Julio C. N avas; “Geographic
`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.
`
` a ., filed Apr. 3, 2000.
`
`Page 2 of 100
`
`

`

`US 6,684,250 B2
`
`Page 3
`
`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 Earth is the
`Internet?”; Center for Advanced Spatial Analysis, University
`College London; Mar. 1998; http://www.geog.ulc.ae.uk/
`casa/martin/internetspace/paperitelecomhtml; Mar.
`28,
`2002; PP. 1—15.
`Venkata N. Padmanadhan and Lakshminarayanan Subrama-
`nian; “Determining the Geographic Location of Internet
`Hosts”;
`http://www.research.microsoft.com—~padmanab/;
`Microsoft Research, University of California Berkley.
`Michael F.Schwartz; “Applying an Information Gathering
`Architecture to NetFind: AWhite Pages Tool for a Changing
`and Growing Internet”; University of Colorado Technical
`Report; Dec. 1993; IEEE/ACM Transactions on Network-
`ing; 1723.
`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://www.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://'www.cis.ohio—state.edu/cgi—
`bin/rfc1712html; pp. 1—6.
`
`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.
`
`http://www.
`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.
`
`Lakshminarayanan Subramanian and Venkata N. Padma-
`nadhan, Randy H. Katz; “Geographic Properties of Internet
`Routing: Analysis and Implications”; Technical Report
`MSR—TR—2001—89; Microsoft Research; Redmond, WA,
`USA; Sep. 2001; pp. 1—12.
`
`David Moore, Ram Periakaruppan, Jim Donohoe, K. Claffy;
`“Where in the World is Netgo.caida.org?”; Cooperative
`Association of Internet Data Analysis— CAIDA; http://www.
`caida.org/outreach/papers/2000/inet
`netgeo.html;
`San
`Diego, CA; pp. 1—13; (date unknown).
`
`“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/usersfljaker/
`publicihtml, (no date given).
`
`PCT—International Search Report—PCT/USO1/11163—
`Aug. 20, 2001.
`
`* cited by examiner
`
`Page 3 of 100
`
`Page 3 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 1 0f 64
`
`US 6,684,250 B2
`
`29232,2.553
`295ijmag/m6:252:
`EaEmszwoE2058
`
`
`
`E562920anmzfifiwkfiw:
`
`<55
`
`mwzormmis
`
`a{A.05
`
`>mm>_._m_o
`
`
`
`.vlomm>mwmzo_H<wo._om_w
`
`mE<
`
`mzazmmmmiomm
`
`a55%
`
`Ow
`
`Emkm>m-n'29.20386”
`
`29.50380
`
`$55530
`
`Ezmmhé
`
`Em:
`
`Page 4 of 100
`
`Page 4 of 100
`
`
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 2 0f 64
`
`US 6,684,250 B2
`
`%
`
`>mm>_._m5
`
`02520
`
`$555
`
`>mm>_._m5
`
`02520
`
`$250
`
`me
`
`02520
`
`$550
`
`
`
`02520>mm>_._m5
`
`0
`
`>mm>_._m5
`
`0254.5
`
`@EE%
`
`m0
`
`5:225
`
`02500055;
`
`02520
`
`>mm>_.m5 SE55
`<._.<o %
`
`<._.<n_
`
`m_m>._<2<
`
`mm>mmw
`
`<55
`
`0035:0235
`
`oin
`
`$20530
`
`52<Exm_
`
`2955.505.5
`
`
`
`SE5505>0<2<52<
`
`5.5
`
`29.53.50
`
`02_I0<_2
`
`5
`
`29.55.50
`
`02:20.32
`
`a
`
`5.5
`
`2955.50
`
`m_2__._0<_>_
`
`Page 5 of 100
`
`Page 5 of 100
`
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 3 0f 64
`
`US 6,684,250 B2
`
`%
`
`wziogm
`
`w_>__.:._mo.3<
`
`87:2:
`
`<._.<o
`
`20:05.50
`
`mm<m§<o
`
`mm,
`
`
`
`<29
`
`20:05.50
`
`EEEOGE
`
`
`w_m>._<2<a%
`
`IN.m._:m_o_>_\o_In_<mwo_>_mE
`
`
`
`mmmoommmm<_>_
`
`
`
`wz_n_n_<_>_mQZmQEzoo
`
`o_In_<mGOmw
`
`
`
`£228am._.<n__._omzoomm<m<p<o
`
`:8
`
`magic
`
`%
`
`521E850Ea
`
`oil/E83mwzofimss
`
`<20
`
`20:93.60
`
`mmxomm
`
`_2923uN55
`
`”mm>mmm
`
`fl
`
`zocbmjoo
`
`._.2mo<
`
`wr
`
`<._.<o
`
`zocbmjoo
`
`H2m0<
`
`2‘
`
`<._.<n_
`
`zocbmjoo
`
`H2m®<
`
`«BE
`
`75;ng
`
`._.zm_w<
`
`a
`
`«53
`
`20:05.50
`
`Emo<
`
`wlr
`
`SE
`
`zocbmjoo
`
`Emma.
`
`Page 6 of 100
`
`Page 6 of 100
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 4 0f 64
`
`US 6,684,250 B2
`
`JOB REQUEST TO DATA
`COLLECTION BROKER
`
`32
`
`COLLECTION BROKER ACCEPTS REQUEST AND
`IDS COLLECTION AGENTS TO SERVICE REQUEST
`
`(N) COLLECTION AGENTS ACCEPT JOB AND REPORT
`SUBMISSION SUCCESSFUL
`
`COLLECTION BROKER WRITES START MARK AND
`SESSION ID TO COLLECTION DATABASE
`
`46
`
`COLLECTION AGENTS PERFORM SEARCHES TO COLLECT
`RAW DATA AND STORES RESULTS FOR BATCH UPDATE48
`
`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
`
`DATA TO DATA WAREHOUSE
`
`ANALYSIS MODULE PROCESSES RAW DATA AND WRITES
`
`FIG. 3
`
`Page 7 of 100
`
`Page 7 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 5 0f 64
`
`US 6,684,250 B2
`
`
`
`._<3.5<EmjoO
`
`
`
`Ez<mb®mm>>._.2m__;_o
`
`O
`
`
`
`zoF<_>_mOH_2_zo_._.<_>Eou_2_
`
`
`
`wmm<m<k<ozo_._.o:n_omn_
`
`
`
`mmzozmmSSska
`
`
`
`m_m>..<z<zo:.<oo._om_w
`
`<v
`.05
`
`4/‘|I\
`
`szimm
`
`2220395
`
`<20
`
`>><m
`
`
`
` <552GEES0mm
`
`mo;
`
`0:5QO
`
`<H<o
`
`hmmagm
`
`Hamjo
`
`29255
`
`
`
` mhmmzom—m292039653002Dmmmoomm
`
`mm>>Hiju
`
`mmwz/omm
`
`.2530
`
`mm>>Emjo
`
`\mmmgomm
`
`Page 8 of 100
`
`Page 8 of 100
`
`
`

`

`S”U
`
`m
`
`2
`
`m
`
`e
`
`4
`
`US 6,684,250 B2
`
`>52EIEV8952
`
`
`
`mmmmoa<VEOBEZ
`
`
`%625E22mm$mmto£372
`
`n,mmzoxmmss222387:
`m:52P295548SE
`n.Ea2253809u$295N£52£0sz
`0m
`0352925282mEaEwE:58%
`M333E50:5QO<20
`Emma.
`mm8$552ESEZv225ijSE
`Biz:55:37.0E5529258;
`:25ME9/:anEam8528$
`
` 0:5QO<20E5522258;E9,:anEam8EnemaNE>Emm£532£9552
`
`
`
`Emw<zo_._.om_._._oo<53
`
`mzu
`.05
`
`Page 9 of 100
`
`Page 9 of 100
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 7 0f 64
`
`US 6,684,250 B2
`
`DATA
`CRALILITCHITNEN
`
`DATA
`C(IT/IITAII—CERITNEN
`
`CLIENT
`MACHINE
`DATABASE
`
`CLIENT
`MACHINE
`DATABASE
`
`CLIENT
`MACHINE
`DATABASE
`
`PRODUCT
`STAGING
`DATABASE
`
`PRODUCT
`GENERATION
`SYSTEM
`
`PROCESS
`
`RESEARCH
`DATABASE
`
`PRIMARY
`WAREHOUSE
`
`BACKUP DATA
`WAREHOUSE
`
`UNIFIED
`MAPPING
`
`FIG. 5
`
`Page 10 of 100
`
`Page 10 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 8 0f 64
`
`US 6,684,250 B2
`
`REQUEST IS SENT TO DATA
`
`COLLECTION AGENT (DCA)
`
`DCA NEGOTIATES WITH DATA
`
`COLLECTION BROKER (DCB)
`
`PROCESS
`
`DOA BEGINS
`DATA COLLECTION
`
`DCB WRITES
`START AND
`SUID TO DB
`
`DCA
`
`AGENT
`
`DCA
`
`BROKER
`
`DB, AND THE LOOP IS CLOSED
`
`DOA INFORM DCB THAT IT IS
`FINISHED. DCA WAITS FOR
`FURTHER INSTRUCTIONS
`
`UPON NOTIFICATION, THE
`DCBS FLUSH THEIR SESSION
`INFORMATION INTO THE
`
`DCB WAITS
`UNTIL ALL
`DCAS HAVE
`REPORTED
`IN, AT WHICH
`POINT
`THE DCAS ARE
`INSTRUCTED TO
`INSERT RESULTS
`INTO THE DB,
`AND FLUSH
`LOCAL
`INFORMATION
`STORES
`
`DCA STORES
`SESSION
`INFORMAT'ON
`LOCALLY TO
`FACILITATE
`BATCH TO THE
`COLLECTIONS
`DATABASE
`
`FIG. 6
`
`Page 11 of 100
`
`Page 11 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 9 0f 64
`
`US 6,684,250 B2
`
`
`
`OPERATORS MAY OBTAIN REAL-TIME
`STATUS OF PARTICULAR JOBS FROM
`AN OPERATOR ENTERS
`
`
`
`THE DCB, VIA THE WEB INTERFACE,
`A JOB TO BE EXECUTED VIA
`
`
`USING THE GENERATED USID.
`THE WEB INTERFACE
`
`
`
`
`OPERATORS MAY ALSO INTERRU PT
`JOBS, PAUSE THEM, RESTART, ETC.
`
`
`
`WEB INTERFACE.
`
`
` DCB ACCEPTS THIS REQUEST IF IT
`- ADMINISTRATIVE
`
`
`WORDSTATION
`IS A SCHEDULED JOB, NOTIFICATION
`
`
`IS SENT BACK TO THE WEB INTERFACE.
`
`
`OTHERWISE, THE REQUEST IS ANALYZED
`AND SENT ON THE APPROPRIATE
`DCA MACHINES
`
`
`
`
`
`
`
`
`
`DCB MACHINE PRIMARILY
`COMMUNICATION WITH THE DB
` DCA
`
`
`
`REGARDING DCA STATUS. ACTUAL
`— DATA COLLECTION
`
`
`
`INFORMATION INSERTION IS
`BROKER
`
`
`PERFORMED BY THE DCBS, PER A DCB
`REQUEST THE DCB 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
`
`Page 12 of 100
`
`Page 12 of 100
`
`

`

`S”U
`
`nuJ
`
`2n.
`
`Mf0wm
`
`US 6,684,250 B2
`
`ZOEEQEME20552.ME
`
`$8152,Ea225530
`
`4£95548mmmsoxmmssSEB7,E3825
`
`%8:225
`
`9E5
`
`SE3%
`
`Tw<ooEOE<20IV
`
`
`
`m4<>mm._.z_813%7:
`
`
`
`
`
`mm<m<H<c29.53.50«BEME.
`
`
`
`th_>>o._n_m<uo5:.55m”.<55
`
`on”EEEOEQ5:822223
`t£32325SE325nEEEEEm:tommgéaw225ijE3WE$13:
`
`
`
`
`mmzozmm<>><._.<n_m:.:.D<o._n_:Io._.<m_mo;<._.<n_
`
`
`9;.sz>m<mom§mhQ2<éQEEmEz.whim
`
`
`
`._<o_mOHm_I.20:.<_>Eo¢2_._<o:.m_._.<._.w<H<Q
`
`
`
`
`
`>><mmmmo;mm<m<p<ozo_._.om_._.5o<20m2:
`
`Page 13 of 100
`
`29272
`
`
`
`@mzxoszazammoog
`
`
`wQOIEE8259._._<mm=._mn_<mdooEm_m>._<2<
`
`
`
`
`
`zozbmzzooxmoEmz<mmm:£3992m_w>._<z<
`
`
`
`.82230958mmEoSEEEm<.52:
`«EB5550ommz._.<I._.mzo_m_ommmo”.
`
`
`
`
`w.UE
`
`Page 13 of 100
`
`
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 11 0f 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 OUEUE
`
`72
`
`RUN CONSOLIDATED DOMAINS ALGORITHM
`E
`
`INSIIEJIi‘RIANTO
`WAREHOUSE
`
`YES
`
`SATISFIED?
`E
`
`NO
`
`RE-INSERT NETWORK ADDRESS INTO MAIN QUEUE AND FLAG
`AS HAVING FAILED CONSOLIDATED DOMAIN ALGORITHM
`
`@
`
`ADDRESS INTO MAIN QUEUE
`
`RUN BLOCKING ALGORITHM(S) TO DETERMINE
`BLOCK SIZE AROUND NETWORK ADDRESS
`
`INSERT BLOCK (IF GENERATED) WITH NETWORK
`
`FIG. 9A
`
`Page 14 of 100
`
`Page 14 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 12 0f 64
`
`US 6,684,250 B2
`
`RUN EXACT ALGORITHMS ON NETWORK ADDRESS
`
`(OR 1 OR MORE NETWORK ADDRESS IN BLOCK)
`
`YES
`
`INSET INTO DATA
`
`WAREHOUSE %
`
`
` SUCCESSFUL AND
`BLOCKING VERIFIED?
`
`
`fl
`
`NO
`
`RUN INEXACT ALGORITHMS AND UNIFIED MAPPING PROCESS
`
`92
`
`ON NETWORK ADDRESS (0R 1 OR MORE NETWORK
`ADDRESS IN BLOCK)
`
`YES
`
`INSET INTO DATA
`WAREHOUSE %
`
`N0
`
`FORWARD TO RESOLUTION MANUAL RESOLUTION
`
`FIG. 9B
`
`Page 15 of 100
`
`Page 15 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 13 0f 64
`
`US 6,684,250 B2
`
`102
`
`ROUTER
`
`1.1.1.259
`
`
`PC
`
`FIG. 10A
`
`
`
`FIG. 10B
`
`Page 16 of 100
`
`Page 16 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 14 0f 64
`
`US 6,684,250 B2
`
`NFmobfiszH
`
`
`
`>o<mzoo<mozmamzoo
`
`fl”@52meDE
`
`._.n_._w22200..
`
`22.553
`
`m_mmI._.2>m
`
`mmmoomm
`
`:CE
`
`
`
`
`
`8.59:2zo_H<z__>_m_m_Eo20:.<oo._
`
`Page 17 of 100
`
`Page 17 of 100
`
`
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 15 0f 64
`
`US 6,684,250 B2
`
`of.
`
`
`
`
`
`8388DoomooovooomDoom0830
`
`
`
`xoo._m_vEO>>EZ7:mmooz”6mmmEsz<NHGHHAH
`
`Page 18 of 100
`
`Page 18 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 16 0f 64
`
`US 6,684,250 B2
`
`500K
`
`PDPBLATIGH
`
`50K
`
`CITY
`
`fianfidenne
`Factor
`
`String Length
`
`FIG. 123
`
`Page 19 of 100
`
`Page 19 of 100
`
`

`

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

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 18 0f 64
`
`US 6,684,250 B2
`
`f 19!]
`
`
`
`113“Index
`
`Connect
`
`xvi
`
`FIG . 14!;
`
`Page 21 of 100
`
`Page 21 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 19 0f 64
`
`US 6,684,250 B2
`
`
`
`mOhOdm—MOZMQEZOO
`
`
`Era-III.-III-Inn".-
`
`
`LENGTH OF STRING
`
`FIG. 14B
`
`Page 22 of 100
`
`Page 22 of 100
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 20 0f 64
`
`US 6,684,250 B2
`
`
`
`
`
`NumberofLocationEatermiuatesGeneratedbytheString
`
`§
`
`2.4 C)
`
`M
`
`{)3
`
`d.
`
`5
`
`'
`
`'7.-
`
`7
`
`Length of String
`
`FIG. 1M1
`
`Page 23 of 100
`
`Page 23 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 21 0f 64
`
`US 6,684,250 B2
`
`196
`
`45
`
`25
`
`20
`
`31,1":
`
`5
`
`Length of String
`
`FIG. 140
`
`500000
`
`0".c 4..ma
`
`Population
`
`Page 24 of 100
`
`Page 24 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 22 0f 64
`
`US 6,684,250 B2
`
`100
`
`Connect
`
`
`
`:5;Index
`
`1V1
`
`3%
`
`50
`
`d0
`
`4
`
`.
`J"
`
`:3)
`
`"d
`
`Length of String
`
`FIG-
`
`lfiE
`
`Page 25 of 100
`
`Page 25 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 23 0f 64
`
`US 6,684,250 B2
`
`1
`
`Q9
`
`4.: 0,8
`3
`m m
`E
`,
`o
`g €106
`+4
`33? 0,5
`
`0.4
`
`“S
`a
`‘H
`5 U3
`Q4 9‘2
`a?
`
`DJ
`
`
`
`-at:
`
`.AC
`
`25
`
`”h";
`-~-
`
`25‘
`
`(15:1
`
`an
`
`10
`
`:5
`
`O
`a G
`
`1.3-0
`
`1 053+:
`
`10000
`
`U
`
`Distance in.Hiles to Last Known East
`
`FIG. 14?
`
`Page 26 of 100
`
`Page 26 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 24 0f 64
`
`US 6,684,250 B2
`
`
`
` .91 SJ" Humhe:ofHopsBetween.Thisfies:anflLastKngwuHop
`
`
`
`
`
`Distance in Miles to Last Known Hnfit
`
`FIG- 14G
`
`Page 27 of 100
`
`Page 27 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 25 0f 64
`
`US 6,684,250 B2
`
`204
`
`flop
`PapulationofThiSHostandLastKnown
`
`
`v5
`
`'nimum
`
`..
`
`:3
`
`6
`f0
`
`7
`500
`_.
`7
`Distance in Hiles to Last Knnwn Host
`
`5000
`
`FIG. 1&3
`
`Page 28 of 100
`
`Page 28 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 26 0f 64
`
`US 6,684,250 B2
`
`~206
`
`ty0fthiS'HflStandLastKnflwngap
`
`
`Cannect
`
`1vi
`
`flimum
`
`m
`
`E,C
`11”“
`
`500
`
`5000
`
`Distance in Miles to Last Knawn Host
`
`FIG-
`
`1&1
`
`Page 29 of 100
`
`Page 29 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 27 0f 64
`
`US 6,684,250 B2
`
`09
`
`93
`
`G]
`
`KnownHost Q 0‘:
`RapRatioofEEXt
`
`04
`
`10
`
`1000
`I
`I
`I
`10413
`Bistance in Miles t0 Last Known Host
`
`10000
`
`FIG.
`
`léJ
`
`Page 30 of 100
`
`Page 30 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 28 0f 64
`
`US 6,684,250 B2
`
`[Q U!
`
`
`
`m
`
`N m
`
`
`
` in EmberofHopsBetweenThisHostandNextKnuwHap
`
`Distance in Miles. to Next Known Host
`
`FIG. 14K
`
`Page 31 of 100
`
`Page 31 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 29 0f 64
`
`US 6,684,250 B2
`
`Q)
`
`1-0
`
`KflOWflHop
`PopulatianofThisHostandNext
`
`#0
`
`580
`
`Distance in 51135 to “Ext Known Host
`
`FEG. 14L
`
`nimmm
`
`Page 32 of 100
`
`Page 32 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 30 0f 64
`
`US 6,684,250 B2
`
`’3'0‘
`
`453
`
`CanngctivityofThisEastandHex}:RumHarp
`
`am
`
`n
`
`“:3
`
`,w33
`
`5%.
`
`
`
`Page 33 of 100
`
`Page 33 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 31 0f 64
`
`US 6,684,250 B2
`
`216
`
`_____________
`
`53
`
`
`
`mO._.0<n_MOZMQEZOO
`
`POPULATION
`
`1o7
`
`FIG 14N
`
`Page 34 of 100
`
`Page 34 of 100
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 32 0f 64
`
`US 6,684,250 B2
`
`'85E
`
`8
`
`Index
`
`Cannectivity
`
`Q
`
`20
`
`48
`
`,
`
`.3
`
`
`
`Means of Last Known Hop an& Next Known Hop Connectivity Indices
`
`FIG. 1&0
`
`Page 35 of 100
`
`Page 35 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 33 0f 64
`
`US 6,684,250 B2
`
`220
`
`____J____
`
`____l.
`
` mOFOdm
`
`MOZMDEZOO
`
`CONNECTIVITY INDEX
`
`0
`
`90
`
`100
`
`FIG. 14F
`
`Page 36 of 100
`
`Page 36 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 34 0f 64
`
`US 6,684,250 B2
`
`222
`
` mOFOJE
`
`mozmQEZOO_
`
`POSITION OF IST CHARACTER OF WORD IN HOSTNAME
`
`FIG. 14Q
`
`Page 37 of 100
`
`Page 37 of 100
`
`

`

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

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 36 0f 64
`
`US 6,684,250 B2
`
`HopRatio
`
`5%
`
`100
`
`156
`
`QQG
`
`26;
`
`3&6
`
`35G
`
`40%
`
`$59
`
`$93
`
`Distance in Miles Between Last Known Hop and Net
`
`FIG. 16A
`
`Page 39 of 100
`
`Page 39 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 37 0f 64
`
`US 6,684,250 B2
`
`262
`
`EOFo/E
`
`5O5051
`
`moszEZOO
`
`u-_—-———_|
`
`-___..--_1.
`
`NUMBER OF NODES IN REGISTERED BLOCK
`
`FIG. 16B
`
`Page 40 of 100
`
`Page 40 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 38 0f 64
`
`US 6,684,250 B2
`
`HopRatio
`
`'3-
`
`1 C6
`
`1 50
`
`200
`
`2 SD
`
`300
`
`3 50
`
`41W?
`
`451.:-
`
`75"}
`
`DiStance in Miles Betwean Last Known Hop and. Net
`
`FIG. 16C
`
`Page 41 of 100
`
`Page 41 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 39 0f 64
`
`US 6,684,250 B2
`
`266
`
`moszEZOO
`
` KOFOXE
`
`CONNECTIVITY INDEX
`
`FIG. 16D
`
`Page 42 of 100
`
`Page 42 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 40 0f 64
`
`US 6,684,250 B2
`
`268
`
`MOZMQEZOO
`
` mOFoxE
`
`POPULATION
`
`FIG. 16E
`
`Page 43 of 100
`
`Page 43 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 41 0f 64
`
`US 6,684,250 B2
`
`INITIATE EXTERNAL DATA COLLECTION
`
`270
`
`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
`
`OUTPUT MULTIPLE GEOGRAPHIC
`LOCATIONS AND ASSOCIATED CONFIDENCE
`FACTORS TO THE LOCATION FILTER
`
`28
`
`FIG. 17
`
`Page 44 of 100
`
`Page 44 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 42 0f 64
`
`US 6,684,250 B2
`
`«NJ
`
`‘ ”‘0
`
`£00
`
`499
`
`890
`
`806
`
`TGfiO
`
`Distance in Miles Between Last Known Hop and DNS
`
`FIG. 13A
`
`Page 45 of 100
`
`H
`
`‘
`
`'12
`
`'2?
`
`as
`
`G
`-.-4
`4.5
`
`fl
`fl.‘
`
`9m
`
`Page 45 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 43 0f 64
`
`US 6,684,250 B2
`
`292
`
`MOZMQEZOO
`
` mOFO/E
`
`DISTANCE IN MILES BETWEEN NET AND DNS
`
`FIG. 18B
`
`Page 46 of 100
`
`Page 46 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 44 0f 64
`
`US 6,684,250 B2
`
`HopRatio
`
`‘3
`
`235’
`
`51310
`
`300 i
`
`m
`
`1 {19.}
`
`Distance in Miles Between Next Known Hop and DES
`
`FIG- 186
`
`Page 47 of 100
`
`Page 47 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 45 0f 64
`
`US 6,684,250 B2
`
`296
`
`mOZMDEZOO
`
` MO._.O<n_
`
`CONNECTIVITY INDEX
`
`90
`
`100
`
`FIG. 18D
`
`Page 48 of 100
`
`Page 48 of 100
`
`

`

`US. Patent
`
`Jan.27,2004
`
`Sheet46 0f64
`
`US 6,684,250 B2
`
`mom
`
`OOOOON
`
`oooomr
`
`ooooor
`
`ZO_.r<n_Dn_On_
`
`
`
`HOlOVd EONElCIHNOO
`
`Page 49 of 100
`
`Page 49 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 47 0f 64
`
`US 6,684,250 B2
`
`
`
`HapRatio
`
`{3"
`
`.) m
`
`0
`
`me:
`
`:50
`
`2m 2250
`
`3
`
`1‘51”}
`
`4-00
`
`4:30
`
`500
`
`Distance in Miles Between Last Rum Hop anfi ASH
`
`FIG. 19$
`
`Page 50 of 100
`
`Page 50 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 48 0f 64
`
`US 6,684,250 B2
`
`mom
`
`
`
`XOOIEm<Z_mmoOZnoNam—>52
`
`HOiOVd EONElCIHNOO
`
`Page 51 of 100
`
`Page 51 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 49 0f 64
`
`US 6,684,250 B2
`
`
`
`m (It
`
`HopRatia
`
`R0-
`
`150
`
`200
`
`250
`
`300
`
`350
`
`400.
`
`450
`
`500
`
`Distance in Miles Between Next Known Hop and ASE
`
`FIG. 19C
`
`Page 52 of 100
`
`Page 52 of 100
`
`

`

`US. Patent
`
`Jan.27,2004
`
`Sheet50 0f64
`
`US 6,684,250 B2
`
`mom
`
`00?
`
`xmoZ_>|_._>_._.Um_ZZOO
`
`
`
`HOLOVfl EIONEICIHNOO
`
`Page 53 of 100
`
`Page 53 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 51 0f 64
`
`US 6,684,250 B2
`
`wow
`
`
`
`ZO_._.<._Dn_On_
`
`HOlOVfl EONEGHNOO
`
`Page 54 of 100
`
`Page 54 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 52 0f 64
`
`US 6,684,250 B2
`
`
`
`TheStoredConfidenceFactnroftheLastKnownHop
`
`
`
`
`
`
`
`‘
`
`2
`
`M
`
`$
`
`5
`
`
`d
`
`?
`
`B
`
`u
`
`¥0
`
`Number nf flops Between This Host and the Last Known Hap
`
`FIG“ 20&
`
`Page 55 of 100
`
`Page 55 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 53 0f 64
`
`US 6,684,250 B2
`
`HopRatio
`
`4;
`
`,»
`
`UT
`
`Pa.)
`
`25
`
`A
`
`w '11
`
`4
`
`Number uf Hops Between This Host and the Last Knawu Hap
`
`FIG- ZGB
`
`Page 56 of 100
`
`Page 56 of 100
`
`

`

`U
`
`Pm:S.vmm
`
`ta
`
`t
`
`J
`
`m
`
`US 6,684,250 B2
`
`m...................................................S
`
`...............................................E
`
`m.............................................v
`
`M2..m....................................................Smnm.m.................................................N?a
`
`uwm...................................................om%m..................................................mw
`
`3
`
`IIIIIIIIIIIIIIIIIIIIIIIIIN
`
`oooorDoor09‘E.
`
`
`
`
`
`AOOAdZQFm—ZvO...mm..___>_Z_moz<._.m_omelrmOIm
`
`Page 57 of 100
`
`Page 57 of 100
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 55 0f 64
`
`US 6,684,250 B2
`
`330
`
`
`
`gM888"é
`
`
`5
`
`
`
`7
`
`a
`
`910
`
`
`
`g 3
`
`12 3
`
`4
`
` TheStoredConfidenceFactoroftheNextKnownHop
`
`Number of flaps Between This Host and the Hext Known Hap
`
`FIG- 21A
`
`Page 58 of 100
`
`Page 58 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 56 0f 64
`
`US 6,684,250 B2
`
`Q
`
`C]
`
`C)
`
`HapRatig
`
`l
`
`1E
`
`2
`
`
`A?
`
`3
`
`33
`
`4
`
`Number of Hops Between This Host and the Next Knawn Hop
`
`FIG. 213
`
`Page 59 of 100
`
`Page 59 of 100
`
`

`

`S.U
`
`et
`
`nuJ
`
`US 6,684,250 B2
`
`on”2.«mm
`
`...............................................Sm...................................................S
`
`
`
`m........................2wm,man“lllllllllllllllllllllllllllllllllllllllllllllllllNV0n...H
`
`m..............................................vMOy...................................................mmaHmGs..............................................mm
`
`0j.—
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIN
`
`
`
`Decor009‘00?OF
`
`
`
`AOOJMZQHMZVOFmm.=_>_z.wOZ<._.w_Q._.wm_._.mOIw
`
`Page 60 of 100
`
`Page 60 of 100
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 58 0f 64
`
`US 6,684,250 B2
`
`
`
`
`BOTH LKH
`
`HAVE GENERATE LOCATION
`DETERMINANTS
`
`£2
`
`340
`
`
`
`RECEIVE LOCATION DETERMINANTS
`FROM LKH AND HKH9 LDMS 44
`
`
`
`
`
`
`IDENTIFY LOCATION DETERMINANT
`WITH HIGHEST CONFIDENCE FACTOR
`
`
`
`ASSIGN CONFIDENCE FACTOR TO IDENTIFIED
`LOCATION DETERMINANT BASED ON (1) JOINT
`
`
`CONFIDENCE FACTORS AND (2) DISTANCE
`
`
`BETWEEN LKH AND NKH LOCATION
`DETERMINANTS USING CONFIDENCE MAP 348
`
`
`
`OUTPUT LOCATION DETERMINANT AND
`CONFIDENCE FACTOR TO LOCATION
`FILTER
`
`
`
`
`
`
`FIG. 22
`
`Page 61 of 100
`
`Page 61 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 59 0f 64
`
`US 6,684,250 B2
`
`
`
` MeanfianfidenceFactorofLastKnownflapand
`
`NextKnownHop
`
`
`
`
`
`
`
`Distance in Miles Between Last Known.Hop and Next Knflwn pr
`FIG. 23
`
`Page 62 of 100
`
`Page 62 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 60 0f 64
`
`US 6,684,250 B2
`
`RUN HIGH ACCURACY LDM (E.G, SUFFIX LDM) TO
`GENERATE FILTER LOCATION DETERMINANT
`AND ASSOCIATED CONFIDENCE FACTOR 32
`
`DELIVER FILTER LOCATION DETERMINANT
`AND CONFIDENCE FACTOR TO
`FILTER BROKER
`
`
`
`FILTER PROCESS DETERMINANT WHATEVER
`FILTER LOCATION DETERMINANT IS
`STATE/ROUTINE COUNTRY
`
`FILTER PROCESS INTERCEPTS MULTIPLE
`LOCATION DETERMINANT OUTPUT—TED BY
`COLLECTION OF LDMS AND CHECK EACH
`LOCATION DETERMINANT FOR AGREEMENT
`WITH FILTER LOCATION DETERMINANT
`
`68
`
`ADD TO INPUT
`STACK FOR
`LOCATION
`SYNTHESIS
`PROCESS
`
`
`
`fl
`
`REMOVE FROM
`INPUT STACK
`FOR LOCATION
`SYNTHESIS
`PROCESS
`
`
`
`
`fl
`
`NO
`
`
`
`
`YES
`SUFFICIENT
`AGREEMENT?
`
`
`
`FIG. 24
`
`Page 63 of 100
`
`Page 63 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 61 0f 64
`
`US 6,684,250 B2
`
`380
`
`,/
`
`COMPARE LOCATION DETERMINANTS
`AGAINST EACH OTHER
`
`BUILD CONFIRMATION
`CONFIDENCE FACTOR TABLE
`
`38
`
`COLLAPSE SEPARATE CONFIDENCE
`FACTOR INTO A COMBINED
`CONFIDENCE FACTOR
`
`IDENTIFY LOCATION DETERMINANT
`
`THAT HAS HIGHEST DEGREE OF CONFIDENCE
`FACTOR—WEIGHED AGREEMENT WITH
`
`ALL OTHER LOCATION DETERMINANTS
`
`FIG. 25
`
`Page 64 of 100
`
`Page 64 of 100
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 62 0f 64
`
`US 6,684,250 B2
`
`400
`
`/
`
`O
`
`7O 80
`40 50 60
`30
`1O 20
`INTERNAL CONFIDENCE
`
`90 100
`
`FIG. 26
`
`402
`
`OO1>0
`
`"I""1""I"
`I
`__I._-J—--l__
`
`
`
`
`
`<mDOO<>.:.=m<m_0mn_szommm
`
`O
`
`10
`
`20
`
`30
`
`4O
`
`50
`
`60
`
`INTERNAL CONFIDENCE
`
`404
`
`FIG. 27
`
`Page 65 of 100
`
`Page 65 of 100
`
`
`
`

`

`PS”U
`
`US 6,684,250 B2
`
`Emommam>o<mzoo<>5_m<momn_Fzmomma>o<maoo<>55<,
`
`
`
`44A.m.NII_O2_0R._3,J3E_n8_TF_o.0_ONIL2n4..2|_a_.J_u._0
`O.....................99_m............o..................mcm8E_0fl........mnNV..._7aW8-.--I-m0Jm6Hn/H"SN-J00O._55CG_oOLIJ4
`
`
`In0_1u000mw00m.wmmmmm3mm1moan.
`
`406
`
`411
`
`0Om1
`
`0
`
`0
`
`INTERNAL CONFIDENCE
`
`FIG. 29
`
`Page 66 of 100
`
`Page 66 of 100
`
`
`

`

`US. Patent
`
`Jan. 27, 2004
`
`Sheet 64 0f 64
`
`US 6,684,250 B2
`
`500
`
`/
`
`510
`
`VIDEO DISPLAY
`
`508
`
`‘
`
`512
`
`ALPHA—NUMERIC
`INPUT DEVICE
`
`514
`
`CURSOR CONTROL
`
`DEVICE
`
`DEVICE
`
`COMPUTER-READABLE
`MEDIUM
`
`INSTRUCTIONS
`
`518
`
`SIGNAL GENERATION
`
`502
`
`524
`
`504
`
`5 24
`
`506
`
`520
`
`PROCESSOR
`
`—I
`
`INSTRUCTIONS
`
`
`
`
`INSTRUCTIONS
`
`STATIC
`MEMORY
`
`NETWORK
`
`INTERFACE
`
`FIG. 30
`
`Page 67