A fast, parallel improved version of the iGreedy algorithm for large-scale anycast-aware geolocation

180 150W 120W 90W 60W 30W 000 30E 60E 90E 120E 150E 180
| | | | | | | | | | | | |
+90N-+-----+-----+-----+-----+----+-----+-----+-----+-----+-----+-----+
| . _..::__: ,-"-"._ |7 , _,.__ |
| _.___ _ _<_>`!(._`.`-. / _._ `_ ,_/ ' '-._.---.-.__|
|.{ " " `-==,',._\{ \ / {) / _ ">_,-' ` mt-2_|
+ \_.:--. `._ )`^-. "' , [_/( G e o __,/-' +
|'"' \ " _L 0o_,--' ) /. (| |
| | A n y,' >_.\\._<> 6 _,' / ' |
| `. c s / [~/_'` `"( l o <'} ) |
+30N \\ a .-.t) / `-'"..' `:._ c _) ' +
| ` \ ( `( / `:\ > \ ,-^. /' ' |
| `._, "" | \`' \| ?_) {\ |
| `=.---. `._._ i ,' "` |' ,- '. |
+000 |a `-._ | / `:`<_|h--._ +
| ( l > . | , `=.__.`-'\ |
| `. / | |{| ,-.,\ .|
| | ,' \ z / `' ," a \ |
+30S | / |_' | __ t/ +
| |o| '-' `-' i\.|
| |/ " n / |
| \. _ _ |
+60S / \ _ __ _ _ ___ __ _ ___| |_ +
| ,/ / _ \ | '_ \| | | |/ __/ _` / __| __| |
| ,-----"-..?----_/ ) / ___ \| | | | |_| | (_| (_| \__ \ |_ _ |
|.._( `----'/_/ \_\_| |_|\__, |\___\__,_|___/\__| -|
+90S-+-----+-----+-----+-----+-----+-----+--___/ /--+-----+-----+-----+
 Based on 1998 Map by Matthew Thomas |____/ Hacked on 2015 by 8^/

This repository contains a geolocation algorithm based on iGreedy that was published in the paper Latency-Based Anycast Geolocation: Algorithms, Software, and Data Sets.

The delta of this work is a performance aware implementation through multi-threading, implemented in Rust. In addition, we improve the iGreedy algorithm by geolocating IPs using the intersection of discs within each MIS cluster (see iGreedy paper for details) rather than the lowest circle in each set. This implementation outputs the most likely city (or airport) for each MIS cluster. Unicast targets produce a single location, whereas anycast targets produce multiple locations corresponding to different anycast sites.

The goal of this implementation is to reduce processing time for LACeS (an Open, Fast, Responsible and Efficient Longitudinal Anycast Census System). This code is used to produce daily anycast censuses, publicly available.

It supports both CSV and scamper warts files. The latter for the LACeS pipeline. The output is a single geolocation results file.

Instead of providing an input file, a RIPE Atlas measurement ID can be used or a live measurement can be scheduled (using a RIPE Atlas API key). See notes below regarding probe selection.

Given a set of RTT (round-trip time) measurements from geographically distributed vantage points (VPs) to a target IP, the algorithm determines the target's location(s):

1. RTT to distance — Each VP's RTT is converted to a maximum geographic radius (a disc) using the speed of light in fiber, centered on the VP's known location. The target must lie somewhere within this disc.

2. Enumeration (MIS) — Discs are sorted by radius (ascending). A greedy Maximum Independent Set (MIS) is built: each disc that does not overlap with any already-selected disc is added. Each MIS disc represents a distinct network site. A single MIS disc means unicast; multiple means anycast.

3. Clustering — For each MIS disc, all other discs that overlap with it (and only it—discs overlapping multiple MIS discs are excluded as ambiguous) are collected into a cluster. These discs all likely measured the same site.

4. Intersection & geolocation — Within the cluster:

   • Find the smallest disc in the cluster (tightest constraint). This is always the MIS disc itself.
   • Collect all candidate cities inside that disc.
   • Progressively intersect with each cluster disc (smallest to largest). If adding the next disc would remove all candidates, stop and use the last non-empty set.
   • Apply the relative population filter (--pop_ratio): keep only cities with pop >= max_pop ×ばつ ratio, where max_pop is the largest population among remaining candidates.
   • Select the best city using: score = α ×ばつ (pop / Σpop) − (1 − α) ×ばつ (dist / Σdist), where distance is measured from the disc's center.

5. Output — One row per detected site, each with the geolocated city, its coordinates, and the MIS disc VP.

The original iGreedy algorithm geolocates each site from its MIS disc alone. We instead intersect the MIS disc with the other discs in its cluster (step 4 above). Both approaches are approximations, and they fail in different ways.

Single-disc (iGreedy). The geolocation of an anycast site is located within the MIS disc that found it. In some cases the MIS disc may be very large, in which case the accuracy of the geolocation is affected. I.e., there may be many candidate cities, and it will pick the most likely based on population and distance. Our analysis shows this often leads to false geolocations, especially when ran on latency data collected using VPs with sparse coverage in certain regions.

Intersection (this implementation). Large MIS discs are likely to have intersections with other non-MIS discs. We use those to intersect our MIS disc and narrow the possible location of the anycast site reached. This substantially improves geolocation in regions with sparse coverage where multiple VPs reach the same site (with medium to high latencies). However, this may also lead to false geolocations e.g., when an intersecting non-MIS disc is reaching a different anycast site (creating a fake intersecting area). We limit the occurrence of this by only using intersecting discs that intersect only this MIS disc, but it may still happen.

Why we keep the intersection. Both methods may lead to false geolocations within the MIS disc. This is especially prevalent when there are large MIS discs, which we observe in areas with poor VP coverage. In such cases, we find the accuracy can be improved substantially by using other non-MIS discs that intersect with this MIS disc (and this MIS disc only). Whilst it is possible we intersect with non-MIS discs that happened to reach a different anycast site, we find it is quite rare. It would have to intersect no other MIS disc and create an intersection that maintains valid cities (elsewise it will simply not be used). Using intersecting discs also allows us to extend the script to output unicast geolocation.

The most decisive difference is observability. The --accuracy flag reports num_constraints (how many discs actually narrowed the candidate set) and candidate_diameter (the spread of the surviving candidates), so low-confidence geolocations can be identified and filtered. Rows combining a large radius with a low num_constraints should be treated as weak.

We provide pre-compiled binaries for Linux and macOS.

curl -LO https://github.com/rhendriks/MiGreedy/releases/latest/download/migreedy-linux-x86_64.tar.gz
tar -xzvf migreedy-linux-x86_64.tar.gz
./migreedy --input path/to/measurements.csv --output path/to/results.csv

curl -LO https://github.com/rhendriks/MiGreedy/releases/latest/download/migreedy-macos-aarch64.tar.gz
tar -xzvf migreedy-macos-aarch64.tar.gz
./migreedy --input path/to/measurements.csv --output path/to/results.csv

curl -LO https://github.com/rhendriks/MiGreedy/releases/latest/download/migreedy-macos-x86_64.tar.gz
tar -xzvf migreedy-macos-x86_64.tar.gz
./migreedy --input path/to/measurements.csv --output path/to/results.csv

The code can be ran using Docker.

Pull the latest pre-built image from the GitHub Container Registry:

docker pull ghcr.io/rhendriks/migreedy:main

You need a local directory containing your input CSV file (e.g., measurements.csv). This directory will be mounted into the Docker container.

# Example: Create a directory and move your data into it
mkdir igreedy_data
mv measurements.csv igreedy_data/

Execute the docker run command, which mounts your data directory and passes the necessary arguments to the MiGreedy script.

docker run --rm \
 -v "$(pwd)"/igreedy_data:/app/data \
 ghcr.io/rhendriks/migreedy:main \
 --input /app/data/measurements.csv \
 --output /app/data/results.csv

docker run --rm `
 -v "${PWD}\igreedy_data:/app/data" `
 ghcr.io/rhendriks/migreedy:main `
 --input /app/data/measurements.csv `
 --output /app/data/results.csv

After the command finishes, the output file results.csv will appear in your local igreedy_data directory.

1. Clone this repository:

   git clone https://github.com/rhendriks/MiGreedy
   cd MiGreedy

2. Install Rust:

   curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
   source $HOME/.cargo/env
   rustup update

3. Build the project using Cargo:

   cargo build --release

4. Run the compiled binary with the required arguments:

   ./target/release/migreedy --input path/to/measurements.csv --output path/to/results.csv

Exactly one input source is required: --input, --atlas, or --warts.

These apply only together with --measure:

You can geolocate targets directly from a RIPE Atlas measurement without any local data files. For example, measurement 2001 is a periodic ping towards K-root:

./migreedy --atlas 2001

This fetches the latest results from the RIPE Atlas API, runs the geolocation algorithm, and writes the output to atlas_2001.csv. You can also pass a full URL instead of a numeric ID:

./migreedy --atlas https://atlas.ripe.net/measurements/2001/

NOTE: RIPE Atlas probes may have wrong user-reported locations which result in wrong geolocation results. --atlas uses every probe in the measurement as-is; --measure screens them first (see below).

--measure takes a target instead of a measurement ID: MiGreedy picks the probes, schedules a one-off ping, waits for the results and geolocates them in one go.

Scheduling measurements needs a RIPE Atlas API key with the measurement creation permission, which you can make at atlas.ripe.net/keys. Store it once:

./migreedy --api_key <YOUR-KEY> --save_api_key

The key is written to ~/.config/migreedy/atlas.key with owner-only permissions. MiGreedy looks for a key in this order: --api_key, then the MIGREEDY_ATLAS_KEY environment variable, then that file.

./migreedy --measure 1.1.1.1

This selects 100 probes, pings the target from each of them, and writes the geolocated sites to atlas_<ID>.csv, where <ID> is the measurement RIPE Atlas created — the run is linked from the output so you can inspect it afterwards. Several targets can share one probe set and one run, as long as they are all IPv4 or all IPv6:

./migreedy --measure 1.1.1.1 8.8.8.8 9.9.9.9 --num_probes 200 --output results.csv

Measurements spend RIPE Atlas credits. Use --dry_run to see which probes would be used without scheduling anything (and without needing a key):

./migreedy --measure 1.1.1.1 --num_probes 20 --dry_run

We maximize geographical spread when choosing probes to improve geolocation accuracy. This is done using greedy farthest-point sampling, which is reported.

Selected 20 probes for 1 IPv4 target(s): 1.1.1.1.
Coverage: 19 countries, closest pair 3265 km apart, 17/20 probes on well-connected networks.

Alternatively, you can use your own list of probes. E.g., if you know the target is within Europe, you can create a list of European probes.

./migreedy --measure 1.1.1.1 --probes 6118,1010358,23002
./migreedy --measure 1.1.1.1 --probes my-probes.txt

RIPE Atlas probes have self reported geolocations. These can be inaccurate, which would result in wrong geolocation output. We filter these based on the following criteria:

TODO

NOTE: A robust method is to cross-verify probe locations with geolocation databases and filter those with conflicts.

Using --validate_probes verifies probe location validity using anchor measurements. It pings five globally spread anchors from the candidate probe. Probes reporting a speed-of-light violation to any of the anchors are dropped.

./migreedy --measure 1.1.1.1 --validate_probes

This is off by default as it incurs additional measurements.

NOTE: do not use 50% more candidates, too expensive perhaps 10% is more sensible. Because validation removes probes, MiGreedy selects 10% more candidates than asked for and keeps up to --num_probes validated probes.

NOTE: remove probes that answer no anchor at all

MiGreedy ships with embedded airports and cities datasets. The airports dataset is the original airport dataset (as used by iGreedy) with duplicate airports removed. The cities dataset contains all cities with a population of 500 or higher (sourced from GeoNames).

Population filtering:

• --min_pop <N> filters cities globally at load time (absolute threshold)
• --pop_ratio <R> filters cities per-geolocation, keeping only those with pop >= max_pop ×ばつ R (relative threshold)

These can be combined. For example, --min_pop 10000 --pop_ratio 0.5 first removes all cities under 10k, then during each geolocation keeps only the top 50% by population among candidates.

Select a dataset with the -d flag:

./migreedy --atlas 11501 -d cities
./migreedy --atlas 11501 -d cities --min_pop 15000
./migreedy --input measurements.csv --output results.csv -d airports

City datasets are sourced from GeoNames and licensed under CC BY 4.0.

The input CSV file must have a header row, and its columns are read positionally in this order:

When --vps is given, the lat and lon columns are looked up from the VPs file instead and must be omitted, leaving target,hostname,rtt.

A path ending in .gz is decompressed first, so a gzipped CSV is read directly:

./migreedy --input measurements.csv.gz --output results.csv

A path ending in .parquet is read as Parquet. Parquet files carry their own column names, so unlike CSV their columns are matched by name and in any order.

This reads MAnycastR latency output as it is written, whose columns are rx, addr, ttl, rtt:

MAnycastR stores each address as 16 IPv6-mapped bytes rather than as text. This format is supported.

A VPs file gives each vantage point's location, so measurements that identify their VP only by name can be turned into discs. It is required with --warts and optional with --input.

The format is whitespace-separated hostname lat lon, one per line, with no header:

hlz2-nz.ark.caida.org -37.79 175.28
fra-de.ark.caida.org 50.11 8.74
hkg4-cn.ark.caida.org 22.36 114.12

Blank lines and lines starting with # are ignored, malformed lines are skipped and counted, and if a hostname is listed more than once the first entry wins.

A VP is matched by its full hostname first, and otherwise by the label before the first dot on both sides — so san-us and san-us.ark.caida.org resolve to each other, and no DNS suffix is hardcoded. Measurements from a VP the file does not list are dropped and reported, which doubles as a way to restrict a run to a set of known-good vantage points.

Vantage points are named in the output using the spelling from this file, whatever the measurement called them.

--warts reads scamper output directly, with no sc_warts2json conversion step. .warts and .warts.gz are both read, gzip is decompressed in-process, and files are parsed in parallel.

# a directory of files
./migreedy --warts /data/2026-08-10/ --vps vps.txt --output results.csv
# explicit files, or a quoted glob
./migreedy --warts a.warts b.warts.gz --vps vps.txt --output results.csv
./migreedy --warts '/data/*.iffinder.warts.gz' --vps vps.txt --output results.csv

The vantage point for each file is taken from the monitor name recorded inside the file, falling back to the filename if that name is not one the VPs file lists.

Alias-resolution (dealias) records are currently supported — this is what CAIDA Ark's iffinder measurements contain. Each reply contributes the responding address, which is the address geolocated; for alias resolution this differs from the probed destination. Other record types are skipped.

The output CSV file will have a header and contain the following columns:

When --accuracy is set, two additional columns are appended:

candidate_diameter is computed exactly for up to 512 surviving candidates. Larger sets — which only arise from wide MIS discs, where the diameter is large and its exact value carries no information — use an iterated farthest-point sweep instead of an exhaustive pairwise comparison. That estimate is always a real distance between two candidates, so it never overstates the diameter, and it is never below half of the true value — in practice it is exact at city scale and within a few percent for globe-spanning candidate sets.

• Remi Hendriks
• GitHub: @rhendriks
• Contact: remi.hendriks@utwente.nl

Issues and pull requests are welcome!

This code was designed for our paper LACeS. Please use the following citation when using this code.

@inproceedings{10.1145/3730567.3764484,
 author = {Hendriks, Remi and Luckie, Matthew and Jonker, Mattijs and Sommese, Raffaele and van Rijswijk-Deij, Roland},
 title = {LACeS: An Open, Fast, Responsible and Efficient Longitudinal Anycast Census System},
 year = {2025},
 isbn = {9798400718601},
 publisher = {Association for Computing Machinery},
 address = {New York, NY, USA},
 url = {https://doi.org/10.1145/3730567.3764484},
 doi = {10.1145/3730567.3764484},
 abstract = {IP anycast replicates an address at multiple locations to reduce latency and enhance resilience. Due to anycast's crucial role in the modern Internet, earlier research introduced tools to perform anycast censuses. The first, iGreedy, uses latency measurements from geographically dispersed locations to map anycast deployments. The second, MAnycast2, uses anycast to perform a census of other anycast networks. MAnycast2's advantage is speed and coverage but suffers from problems with accuracy, while iGreedy is highly accurate but slower using author-defined probing rates and costlier. In this paper we address the shortcomings of both systems and present LACeS (Longitudinal Anycast Census System). Taking MAnycast2 as a basis, we completely redesign its measurement pipeline, and add support for distributed probing, additional protocols (DNS over UDP, TCP SYN/ACK, and IPv6) and latency measurements similar to iGreedy. We validate LACeS on an anycast testbed with 32 globally distributed nodes, compare against an external anycast production deployment, extensive latency measurements with RIPE Atlas and cross-check over 60\% of detected anycast using operator ground truth that shows LACeS achieves high accuracy. Finally, we provide a longitudinal analysis of anycast, covering 17+months, showing LACeS achieves high precision. We make continual daily LACeS censuses available to the community and release the source code of the tool under a permissive open source license.},
 booktitle = {Proceedings of the 2025 ACM Internet Measurement Conference},
 pages = {445–461},
 numpages = {17},
 keywords = {internet measurement, anycast, internet topology, routing, ip},
 location = {USA},
 series = {IMC '25}
}