Srovnání přesnosti aktivních geolokačních technik

Článek popisuje způsoby geolokace zařízení s IP adresou. Hlavní část je věnována aktivním geolokačním metodám založených na měření zpoždění a principu jejich činnosti. Závěr práce obsahuje srovnání přesnosti těchto metod.

---

The Comparison of Precision of Active Geolocation Methods

The paper describes methods for geolocation of devices with an IP address. The main part is devoted to active IP geolocation methods based on latency measurement and their principle. The conclusion contains the precision comparison of these methods.

Keywords: geoloaction; latency measurement;

---

Úvod

Poměrně novou službou v IP sítích je geolokace, která slouží ke vzdálenému zjištění geografické polohy uživatele. Určení polohy pro uživatele přináší zvýšení pohodlí – zobrazovaný obsah je přizpůsobený poloze, negativem této služby je její časté využití pro účely reklamy. V současné době pro geolokaci v pevných IP sítích existují dva přístupy – pasivní a aktivní metody. Pasivní metody využívají statických záznamů především v databázích, případně prohledávání DNS záznamů. Protipólem k pasivním technikám jsou techniky aktivní, které využívají korelace mezi síťovým zpožděním a geografickou vzdáleností.

Pasivní IP geolokační metody

Pasivní metody jsou v současnosti častěji používanými ke geolokaci. Nejznámější z těchto služeb jsou databáze GeoIP, IP2Location, Quova, Geobytes a HostIP.Info. Většina kvalitních databází je však komerčních, protože jsou velice náročné na správu. Kvůli manuální správě se v nich často vyskytují chybné záznamy – například stejná pozice pro skupinu IP adres, které patří zařízením nacházejícím se na různých místech. Tyto metody mají také problém s konvergencí při přesunu stanice do nové lokace. Zároveň s nástupem IPv6 dojde k výraznému zvětšení objemu těchto databází. Výhodou pasivních technik je však jejich rychlost a relativní přesnost.

Aktivní IP geolokační metody

Aktivní IP geolokace je založena na měření zpoždění a dalších síťových parametrů mezi stanicí se známou polohou (referenčním bodem) a lokalizovanou stanicí. Většinou se k lokalizaci jedné stanice používá větší množství referenčních bodů (řádově desítky). Ke zjištění velikosti zpoždění se nejčastěji používá nástroj ping, který se dotáže na vzdálenou stanici a čeká na její odpověď – tím získá dobu přenosu ke vzdálené stanici a zpět. Druhým používaným nástrojem je traceroute, jež zjistí IP adresy stanic mezi komunikujícími stranami. Oba nástroje pracují na třetí vrstvě referenčního modelu OSI (Open Systems Interconnection) a využívají protokolu ICMP (Internet Control Message Protocol).

Princip většiny aktivních metod je založen na korelaci mezi zpožděním a geografickou vzdáleností. To je dáno vlivem zpoždění způsobeného rychlostí šíření signálu v médiu, které je hlavní složkou zpoždění na dlouhých vzdálenostech. Podrobněji se o zdrojích a obvyklé velikosti parciálních zpoždění píše v [1].

Metoda GeoPing

GeoPing je nejstarší geolokační metoda založená na měření zpoždění. Ke své činnosti potřebuje velké množství pasivních referenčních bodů (uzlů se známou polohou) a několik aktivních sond (uzlů provádějících měření). Nevýhodou této metody je určení výsledné polohy jako místa, kde leží jeden z referenčních bodů, čímž je omezena přesnost metody. Proto je důležité disponovat množinou s co největším počtem referenčních bodů, které jsou geograficky rovnoměrně rozloženy a jsou připojeny spolehlivým vysokorychlostním spojem. Dále je nutné mít N aktivních sond (doporučeno 7–9), které dokáží změřit dobu zpoždění k jednotlivým referenčním bodům a cílové stanici. I tyto sondy by měly být geograficky rovnoměrně rozmístěny.

Princip metody je v porovnávání vektorů zpoždění příslušejících referenčním bodům a lokalizované stanici. Vektor zpoždění obsahuje změřenou dobou přenosu informace mezi referenčním bodem a všemi sondami. Stejný vektor je změřen pro lokalizovanou stanici a následně je srovnán s vektory referenčních bodů k nalezení nejvíce podobného vektoru. Pro určení nejpodobnějšího vektoru je vytvořen N–rozměrný prostor, v němž je nalezen vektor s nejmenší euklidovskou vzdáleností k hledanému vektoru podle

(1)

kde d₁ až d_N představuje minimální zpoždění mezi referenčním bodem a sondami a d'₁ až d'_N je minimální zpoždění mezi lokalizovanou stanicí a sondami [2]. Dle [3] je medián chyby metody GeoPing 203 km a průměrná chyba má velikost 270 km.

Metoda ShortestPing

Principiálně nejjednodušší IP geolokační metodou založenou na měření zpoždění je ShortestPing. Tato metoda vyžaduje velké množství rovnoměrně rozmístěných referenčních bodů se známou polohou. Metoda zjišťuje zpoždění mezi lokalizovanou stanicí a všemi referenčními body, výsledná pozice je přisouzena poloze referenčního bodu s nejmenší hodnotou zpoždění. Přestože je tato metoda jednoduchá a výslednou pozici přisuzuje jednomu z referenčních bodů, v některých případech dosahuje tato metoda lepších výsledků než některé složitější metody (např. GeoPing). V publikaci [3] je uveden medián chyby 293 km a průměrná chyba 259 km.

Metoda Constraint Based Geolocation (CBG)

Constraint Based Geolocation ke své činnosti využívá trilaterace známé z rádiového určování polohy. Princip metody tkví ve využití vztahu mezi geografickou vzdáleností a zpožděním k vytvoření tzv. hranice nejvzdálenějšího možného umístění stanice. Tato hranice je určena přepočtem zpoždění na základě tzv. Bestline, což je přímka vytvořená při kalibraci a udává vztah mezi zpožděním a vzdáleností pro příslušný referenční bod. CBG pro činnost potřebuje množinu aktivních referenčních bodů se známou polohou.

Obr. 1 Graf zpoždění v závislosti na geografické vzdálenosti zjištěný při kalibraci metody CBG.

Před měřením je provedena kalibrace – každý referenční bod změří zpoždění k ostatním referenčním bodů a k naměřené hodnotě zpoždění přiřadí geografickou vzdálenost. Tyto hodnoty jsou vyneseny do grafu (Obr. 1), kde je vyznačena tzv. Baseline přímka, která reprezentuje nejzazší fyzicky možnou vzdálenost pro naměřené zpoždění – bere v úvahu jen zpoždění vzniklé rychlostí šíření signálu. Druhá přímka v obrázku je tzv. Bestline, která také leží pod všemi body grafu, ale zároveň k nim má nejblíže – tím reprezentuje největší poměr zpoždění a vzdálenosti zjištěné kalibrací [4]. Výpočet Bestline probíhá pomocí metod lineárního programování, kdy se minimalizuje funkce

(2)

za podmínky

(3)

Výsledná Bestline ve tvaru

(4)

představuje rovnici, pomocí které je při geolokalizaci přepočítáváno změřené zpoždění (x) na geografickou vzdálenost (y), pro vybraný referenční bod (i). K výpočtu je použito zpoždění změřené mezi referenčními body (d_ij) a geografická vzdálenost mezi nimi (g_ij), za podmínky, že i ≠ j. Výsledkem je směrnice přímky (m_i) a posunutí na ose y (b_i).

Samotná lokalizace pak probíhá tak, že každý referenční bod změří zpoždění k cílové stanici. Toto zpoždění následně přepočítá dle rovnice (4) pro svoji Bestline na vzdálenost, která se rovná poloměru kruhu, ve kterém se cílová stanice nachází. Cílová pozice stanice je pak určena průnikem kruhů jednotlivých referenčních bodů a nalezením těžiště této oblasti průniku. Velikost průniku určuje také chybovou oblast, ve které se cílová stanice může nacházet. Na obrázku 2 b) je průnik kruhů – oblast, kde se nachází cílová stanice. Dle publikace [3] srovnávající IP geolokační metody má metoda CBG medián chyby roven 174 km a průměrná chyba má velikost 227 km.

Obr. 2 zobrazení principu geolokačních metod založených na vytváření hranic (kruhů) okolo referenčních bodů (křížky). Průnik kruhů definuje oblast, ve které se cíl nachází. Na obrázku a) je nadhodnocení velikosti kruhů, zde je cíl bezpečně uvnitř průniku, b) zobrazuje minimalizování velikostí kruhů, stále však bezpečné pro lokalizaci a na c) je chyba při lokalizaci, kdy některé hranice (kruhy) byly podhodnoceny a průnik všech kruhů není možný stejně jako lokalizace cíle (T).

Metoda Speed of Internet (SOI)

Metoda Speed of Internet je založena na podobném principu jako CBG – vytvoření hranice nejzazší vzdálenosti, kde se cíl může nacházet. Ke své činnosti tedy také potřebuje množinu aktivních referenčních bodů se známou polohou. Rozdíl oproti CBG je v přepočítání zpoždění na vzdálenost, kdy je použita konstanta ⁴⁄₉·c namísto přímky vypočítané z kalibračních dat [4]. SOI tedy nepotřebuje kalibrační měření, čímž je zmenšena zátěž sítě. Nevýhodou je poté menší přesnost, větší oblast průniku – obr. 2 a), ale také možnost, že se kruhy neprotnou. To může nastat při podhodnocení vzdáleností, podobně jako na obrázku 2 c), kde neexistuje průnik oblastí a není tedy možné určit pozici cíle [3]. Dle [5] je medián chyby metody Speed of Internet 285 km a průměrná chyba má velikost 334 km.

Metoda Octant

Metoda Octant principiálně vychází z metody CBG, oproti ní však může referenční bod zjistit nejen oblast, kde se cílová stanice nachází, ale navíc i oblast, kde se cílová stanice nemůže nacházet. Tyto oblasti (X_i) se označují jako pozitivní (Ω) a negativní informace (Φ). Negativní informace udává místo, kde se stanice nemůže nacházet – jedná se o kruhovou oblast blízko referenčnímu bodu. Spojením s pozitivní informací (známou z CBG) vznikne mezikruží, ve kterém se cílová stanice nachází. Cílová oblast (β) je pak určena podle

(5)

jako průnik mezikruží, čímž může vzniknout nekonvexní oblast (Obr. 3), která je pak popsána Bézierovými křivkami. Těžiště této oblasti je pak prohlášeno za polohu cíle (T).

Obr. 3 Princip metody Octant založený na pozitivních a negativních informacích, oblast možného výskytu stanice je definována jako mezikruží, cílová poloha je poté určena jako průnik těchto mezikruží.

Pro mapování zpoždění na vzdálenost se obdobně jako u CBG používá kalibračních dat mezi referenčními body, která jsou následně vynesena do grafu (Obr. 4). K přepočtu je však využita konvexní obálka všech změřených dat – její spodní strana pro pozitivní informace a horní strana pro negativní informace [6].

Obr. 4 Graf zpoždění v závislosti na geografické vzdálenosti zjištěný při kalibraci metody Octant. Plnou čarou je vyznačena konvexní obálka, která je použita pro výpočet pozitivních a negativních informací.

Octant umožňuje také jako negativní informaci použít obydlenost území a vyřadit tak z výsledku moře a další nepravděpodobné oblasti. Dále Octant zjištěnou polohu zpřesňuje použitím zpětného převodu DNS a hledáním polohy mezilehlých prvků (směrovačů). V publikaci [3] je uveden pro metodu Octant medián chyby 87 km a průměrná chyba má velikost 154 km.

Metoda GeoWeight

GeoWeight je opět metoda založená na principech metody CBG. Před první lokalizací je také nutné provést kalibraci metody změřením zpoždění mezi referenčními body. Následně jsou vytvořena rovnoměrná pásma vzdáleností, kterým jsou přiřazena odpovídající naměřená zpoždění a podle počtu přisouzených zpoždění je každé vzdálenosti přidělena odpovídající pravděpodobnost. Při lokalizování stanice jsou pak změřenému zpoždění ke stanici přiřazena pásma vzdáleností a pravděpodobnost výskytu stanice. Výsledná pozice je určena průnikem oblastí, jen se tentokrát jedná o protínající se mezikruží s nejvyšším součtem pravděpodobností – viz Obr. 5 [7]. Metoda GeoWeight má, dle autorů [7] metody, medián chyby 44 km, průměrná velikost chyby uváděná není.

Obr. 5 Metoda GeoWeight pro různá rozmezí vzdáleností od referenčních bodů definuje pravděpodobnosti výskytu stanice. Cílová oblast je určena průnikem prstenců s nejvyšším součtem pravděpodobností.

Metoda Spotter

Metoda Spotter také vychází z metody CBG a využívá kalibrace mezi jednotlivými referenčními body (L₁,..., L_n). Kalibrační data jsou poté podrobena statistické analýze a na tomto základě je vytvořeno normální (Gaussovské) rozdělení pravděpodobnosti vzdáleností. Následně je změřeno zpoždění (d_i) od referenčního bodu k lokalizované stanici (T) a dle toho je vytvořena kružnice (se středem v referenčním bodě L_i), na jejímž blízkém okolí je definována hustota pravděpodobnosti dle zkalibrovaného Gaussova rozdělení. Průnik hustot pravděpodobnosti všech referenčních bodů vytvoří v místě průniku region s vysokou pravděpodobností výskytu cílové stanice podle

(6)

kde

označuje funkci pravděpodobnosti pro příslušný referenční bod, τ je odhadovaná pozice cíle, H je region výskytu cíle a AH je obsah tohoto regionu. Funkce pravděpodobností a jejich oblast průniku názorně ilustruje obrázek 6, převzatý z [8].

Obr. 6 Lokalizace pomocí metody Spotter, za použití tří referenčních bodů (L₁ až L₃), okolo kterých je vyneseno rozložení pravděpodobnosti. Pozice cíle je určena v místě průniku pravděpodobností (červený vrchol), obrázek je převzat z [8].

Autoři metody umožňují využít jejich lokalizační metodu online a v publikaci [8] uvádějí pouze medián chyby 30 km.

Srovnání přesnosti aktivních geolokačních metod

Srovnání přesnosti jednotlivých aktivních geolokačních metod obsahuje Tab. 1, kde je pro výše uvedené metody zobrazena velikost průměrné chyby a medián chyby. Z důvodu porovnatelnosti výsledků byly vybrány hodnoty zjištěné na severoamerickém kontinentě za použití přibližně sta referenčních bodů. Většina výsledků pochází z publikace [3]. Výsledky pro metodu SOI jsou z [4], pro metodu Geoweight z [7] a pro metodu Spotter z [8]. Jiné zdroje jsou použity především proto, že se jedná o nové metody, které doposud nebyly testovány v jiných renomovaných publikacích.

Tab. 1 Srovnání přesnosti aktivních geolokačních metod.

Metoda	průměrná chyba	medián chyby
GeoPing	270 km	203 km
ShortestPing	259 km	293 km
Constraint Based Geolocation (CBG)	227 km	174 km
Speed of Internet (SOI)	334 km	285 km
Octant	153 km	87 km
Geoweight	–	44 km
Spotter	–	30 km

Z tabulky 1 je možné vyčíst, že dosahované chyby aktivních metod jsou velmi velké a pohybují se v řádech desítek až stovek kilometrů. To je dáno především nepřesností při převodu zpoždění na geografickou vzdálenost, kdy zpoždění 500 μs znamená rozdíl přibližně 100 km. Takové zpoždění snadno vznikne při velkém zatížení některého mezilehlého zařízení – například směrovače nebo přepínače. Další problémy působí nepřímé směrování, které uměle prodlužuje trasu k cíli a tím i zvyšuje celkové zpoždění.

Nejnovější aktivní geolokační metody se stávají více výpočetně náročnějšími a díky tomu roste i jejich přesnost – metody Octant, Geoweight a Spotter mají medián chyby pod 100 km. Nejnovější metoda Spotter je dokonce srovnatelná s pasivními metodami, které dokáží lokalizovat stanici na úrovni města a lépe (cca 30 km). U pasivních metod však dochází k chybám pro velké skupiny IP adres, kterým je obvykle přiřazena pouze jedna lokalita. K ověření prohlašované lokality je proto možné využít právě metod aktivních, které prozatím nepodají lepší výsledek než metody pasivní, ale poloha jimi zjištěná je zaručená na základě rychlosti šíření signálu mezi stanicemi. Díky tomu je možné například zneplatnit v databázích ty záznamy, pro které platí, že prohlašovaná vzdálenost od referenčního bodu je vyšší než vzdálenost zjištěná z doby zpoždění a rychlosti šíření signálu médiem.

Závěr

Tento článek přináší shrnutí současného vývoje v oblasti IP geolokace na bázi měření zpoždění. V článku jsou představeny základní metody a jejich princip. Rozdíly mezi metodami jsou ve způsobu jakým je zpoždění mapováno na geografickou vzdálenost. Jednoduché metody používají mapování pomocí lineární funkce, kdežto pokročilejší metody využívají statistických dat z kalibrace a předchozích měření.

Přestože aktivní metody nedosahují přesnosti pasivních metod, jejich výhoda spočívá v nezávislosti na manuálně spravovaných databázích. Vzhledem k tomu, že některé aktivní metody využívají k výpočtu skutečnou rychlost šíření signálu, je možné je použít k ověření dat z pasivních geolokačních služeb.

Literatura

[1] Balej, J., Komosný, D. Zdroje zpoždění při komunikaci v Internetu, Elektrorevue, 2010, 2010/42, 7.
[2] Padmanabhan, V. N., Subramanian, L. An investigation of geographic mapping techniques for internet hosts, SIGCOMM Comput. Commun. Rev., ACM, 2001, 31, 173-185.
[3] Eriksson, B., Barford, P., Maggs, B., Nowak, R. Posit: An Adaptive Framework for Lightweight IP Geolocation, CS Department, Boston University, 2011.
[4] Katz–Bassett, E., John, J. P., Krishnamurthy, A., Wetherall, D., Anderson, T., Chawathe, Y. Towards IP geolocation using delay and topology measurements, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, ACM, 2006, 71-84.
[5] Gueye, B., Ziviani, A., Crovella, M., Fdida, S. Constraint–based geolocation of internet hosts, IEEE/ACM Trans. Netw., IEEE Press, 2006, 14, 1219-1232.
[6] Wong, B., Stoyanov, I., Sirer, E. G. Octant: a comprehensive framework for the geolocalization of internet hosts, Proceedings of the 4th USENIX conference on Networked systems design & implementation, USENIX Association, 2007.
[7] Arif, M. J., Karunasekera, S., Kulkarni, S. GeoWeight: internet host geolocation based on a probability model for latency measurements, Proceedings of the Thirty-Third Australasian Conferenc on Computer Science – Volume 102, Australian Computer Society, Inc., 2010, 89-98.
[8] Laki, S., Mátray, P., Hága, P., Sebok, T., Csabai, I., Vattay, G. Spotter: A model based active geolocation service, INFOCOM, IEEE, 2011, 3173-3181.