Rework mkgeo to use bandwidth constraints
authorTom Hughes <tom@compton.nu>
Thu, 21 Feb 2013 12:09:03 +0000 (12:09 +0000)
committerTom Hughes <tom@compton.nu>
Fri, 22 Feb 2013 15:19:45 +0000 (15:19 +0000)
Makefile
bandwidth/tile.openstreetmap.yml [new file with mode: 0644]
bin/mkgeo
bin/sumlogs [new file with mode: 0755]
src/tile.openstreetmap

index d10b156..2440c50 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -34,7 +34,7 @@ data/switch2osm.org: src/switch2osm
 data/switch2osm.com: src/switch2osm
 data/stateofthemap.eu: src/stateofthemap-eu
 
-data/tile.openstreetmap.org kml/tile.openstreetmap.org.kml: src/tile.openstreetmap bin/mkgeo lib/countries.xml
+data/tile.openstreetmap.org kml/tile.openstreetmap.org.kml: src/tile.openstreetmap bandwidth/tile.openstreetmap.yml bin/mkgeo lib/countries.xml
        bin/mkgeo tile.openstreetmap tile.openstreetmap.org
 
 data/%:
diff --git a/bandwidth/tile.openstreetmap.yml b/bandwidth/tile.openstreetmap.yml
new file mode 100644 (file)
index 0000000..251f844
--- /dev/null
@@ -0,0 +1,214 @@
+---
+AD: 5349.47671727546
+AE: 222846.129776495
+AF: 8719.08079638648
+AG: 2820.70967362202
+AL: 106836.765432033
+AM: 113889.323451308
+AN: 1115.58047527875
+AO: 6877.27524651279
+AR: 1171564.71151058
+AT: 3647519.46748228
+AU: 3189081.63648027
+AW: 3631.0199420643
+AZ: 81929.2194047174
+BA: 2043935.76285071
+BB: 5983.76381844292
+BD: 25393.4082855996
+BE: 3165992.62304099
+BF: 3150.63105418394
+BG: 797921.256246398
+BH: 10539.3101086345
+BI: 10350.3168783306
+BJ: 2035.64638245573
+BM: 1372.54651964418
+BN: 5747.68102146386
+BO: 38726.3085424866
+BQ: 394.978435416985
+BR: 1269284.24653927
+BS: 8567.85989405149
+BT: 548.352823549485
+BW: 2280.52386132833
+BY: 5650248.48728848
+BZ: 1264.0593812309
+CA: 2549567.98453676
+CF: 221.486878332461
+CG: 1585.11901632774
+CH: 2416835.65132024
+CI: 11572.2064321032
+CK: 146.18637818714
+CL: 408051.694538153
+CM: 33943.8972877354
+CN: 1158023.61453614
+CO: 1243776.61186871
+CR: 119432.738504939
+CS: 42418.4354474789
+CU: 5312.11422224385
+CV: 668.832767651298
+CW: 4933.37293973511
+CY: 103835.632079335
+CZ: 2792089.4383328
+DE: 44377875.8935704
+DJ: 2599.01431160968
+DK: 1783533.45416731
+DO: 46863.6505888536
+DZ: 115600.613936926
+EC: 473054.060239688
+EE: 446466.067262127
+EG: 239718.888702816
+ES: 3889026.54337899
+ET: 7206.70562026363
+EU: 89989.7636734693
+FI: 2370076.09005323
+FJ: 1297.30991221596
+FK: 85.9854869172901
+FM: 0.175823879072838
+FO: 6688.23350213591
+FR: 13508134.3724113
+GA: 2501.33994540258
+GD: 454.416260564222
+GE: 332217.258810281
+GF: 1593.04979892725
+GH: 9447.97620605375
+GI: 1686.90360261146
+GL: 1971.18433843761
+GM: 77.5657585620861
+GN: 766.897466040798
+GP: 15670.711311334
+GQ: 356.467773990196
+GR: 476373.288161489
+GT: 76097.8856939527
+GU: 1339.85976657975
+GY: 2091.44565212532
+HK: 219421.922474012
+HN: 19775.256034115
+HR: 619479.526242566
+HT: 26776.2938517956
+HU: 1669412.58477757
+ID: 491948.291194916
+IE: 572528.10196343
+IL: 1794511.92476306
+IN: 2204122.56354825
+IQ: 68338.4964971362
+IR: 415591.10364667
+IS: 285501.197227079
+IT: 4965848.84746727
+JM: 8766.63616157993
+JO: 36402.7647476227
+JP: 1421884.136192
+KE: 42719.1800523062
+KG: 207355.3321123
+KH: 28722.3818285435
+KM: 49.2048436766536
+KP: 139.001539096227
+KR: 464652.265761606
+KW: 35109.2744466733
+KY: 774.544615710049
+KZ: 983048.083460232
+LA: 15823.3319873645
+LB: 47820.2858018224
+LI: 8530.03382009976
+LK: 30910.1662829829
+LR: 347.642968979419
+LS: 401.583166686864
+LT: 1960816.73770731
+LU: 235520.170237137
+LV: 3707396.38922391
+LY: 17158.9789567263
+MA: 172220.437795867
+MC: 2348.22065251032
+MD: 1443169.08042018
+ME: 48473.9406404934
+MG: 6698.14020268392
+MH: 46.928645812047
+MK: 174332.441365713
+ML: 4275.86503728313
+MM: 23918.8181208634
+MN: 13004.638184457
+MO: 4980.39766243689
+MP: 23.1759336940907
+MQ: 8095.57190511172
+MR: 1528.07994256948
+MT: 23730.547528288
+MU: 7948.27889872266
+MV: 3020.32415652345
+MW: 929.131221497545
+MX: 667422.015189339
+MY: 159067.891459259
+MZ: 20048.5220143068
+NA: 13163.9244721628
+NC: 19020.1021446033
+NE: 1366.62447333669
+NG: 26566.7818638241
+NI: 14965.4181567412
+NL: 9012532.3470438
+NO: 675240.403999219
+NP: 48304.6628318832
+NZ: 333770.707808022
+OM: 28570.9332588592
+PA: 19277.9370030871
+PE: 94291.8578601933
+PF: 2074.54785169309
+PG: 710.142976469131
+PH: 1019936.06266057
+PK: 116157.279631036
+PL: 10000293.4867693
+PM: 528.242630477244
+PR: 22382.9407301239
+PS: 55611.3527858184
+PT: 627095.007320115
+PY: 20068.9745011165
+QA: 70709.2096056646
+RE: 12599.5916520007
+RO: 4130415.29028071
+RS: 769614.015999613
+RU: 52182191.7167279
+RW: 5536.23354393801
+SA: 201140.063893613
+SC: 556.244287553859
+SD: 6300.86384904937
+SE: 1513041.50454965
+SG: 347803.88159837
+SI: 451801.003550709
+SK: 892703.93034932
+SL: 982.102564628783
+SM: 161.53410642307
+SN: 21123.3005687355
+SO: 488.733784070616
+SR: 4392.05322989126
+ST: 4941.51680375344
+SV: 13562.8182786506
+SX: 18.2549261354416
+SY: 861.725990381934
+SZ: 88.7591918445934
+TC: 120.465833799525
+TD: 18.3066110629238
+TG: 4339.41228979337
+TH: 270325.341509953
+TJ: 15702.8374573322
+TM: 8420.36966051584
+TN: 137082.56779108
+TR: 930644.995496107
+TT: 83980.5000021083
+TW: 434199.707679817
+TZ: 20191.4170455782
+UA: 11737038.5486755
+UG: 7616.69916128508
+UK: 11707464.6518006
+US: 23649006.9657448
+UY: 139663.307041628
+UZ: 109436.071145167
+VA: 498.991815291329
+VC: 195.167042454408
+VE: 205590.513640052
+VG: 750.670776952226
+VI: 203.201987622498
+VN: 293256.709420163
+VU: 3.14786575202092
+WF: 0.784627932850745
+WS: 284.971665010098
+YE: 10632.8501562712
+YT: 356.217910659792
+ZA: 254841.998048933
+ZM: 3777.13576874
+ZW: 2887.85124819038
index f7e6d81..a47ea81 100755 (executable)
--- a/bin/mkgeo
+++ b/bin/mkgeo
@@ -15,11 +15,23 @@ my $source = shift @ARGV;
 my $zone = shift @ARGV;
 my $servers = YAML::LoadFile("src/${source}");
 
-foreach my $server (values %$servers)
+# Initialise server details
+while (my($name,$server) = each %$servers)
 {
-    $server->{status} = "down";
+    $server->{name} = $name;
+    $server->{bandwidth} = $server->{bandwidth} * 1024 * 1024;
+
+    if ($ENV{PINGDOM_USERNAME} && $ENV{PINGDOM_PASSWORD})
+    {
+        $server->{status} = "down";
+    }
+    else
+    {
+        $server->{status} = "up";
+    }
 }
 
+# If pingdom support is enabled then check which servers are up
 if ($ENV{PINGDOM_USERNAME} && $ENV{PINGDOM_PASSWORD})
 {
     my $ua = LWP::UserAgent->new;
@@ -44,15 +56,24 @@ if ($ENV{PINGDOM_USERNAME} && $ENV{PINGDOM_PASSWORD})
 }
 
 my %countries = ();
+my @mappings = ();
 
+# Create a parser for the country database
 my $countries = XML::TreeBuilder->new;
 
+# Parse the country database
 $countries->parsefile("lib/countries.xml");
 
+# Load the per-country bandwidth details
+my $bandwidth = YAML::LoadFile("bandwidth/${source}.yml");
+
+# Fill in country table and work out which servers each can use
 foreach my $country ($countries->look_down("_tag" => "country"))
 {
     my $code = $country->look_down("_tag" => "countryCode")->as_text;
     my $name = $country->look_down("_tag" => "countryName")->as_text;
+    my $population = $country->look_down("_tag" => "population")->as_text;
+    my $bandwidth = $bandwidth->{$code} || 0;
     my $continent = $country->look_down("_tag" => "continent")->as_text;
     my $west = $country->look_down("_tag" => "west")->as_text;
     my $north = $country->look_down("_tag" => "north")->as_text;
@@ -60,46 +81,70 @@ foreach my $country ($countries->look_down("_tag" => "country"))
     my $south = $country->look_down("_tag" => "south")->as_text;
     my $lat = centre_lat( $south, $north );
     my $lon = centre_lon( $west, $east );
-    my @servers;
 
-    foreach my $servername (keys %$servers)
+    $countries{$code} = {
+        code => $code, name => $name, continent => $continent,
+        bandwidth => $bandwidth, lat => $lat, lon => $lon
+    };
+
+    foreach my $server (values %$servers)
     {
-        my $server = $servers->{$servername};
         my $match = match_country($server, $code, $continent);
 
-        if ($match eq "preferred" || $match eq "allowed")
+        if ($server->{status} eq "up" && $match ne "denied")
         {
             my $priority = $match eq "preferred" ? 20 : 10;
             my $distance = distance($lat, $lon, $server->{lat}, $server->{lon});
 
-            $priority = $priority * 10 if $server->{status} eq "up";
-
-#            print STDERR "$servername is $match for $name with distance $distance\n";
-
-            push @servers, { name => $servername, priority => $priority, distance => $distance };
+            push @mappings, {
+                country => $countries{$code}, server => $server,
+                priority => $priority, distance => $distance
+            };
         }
     }
-
-    $countries{$code} = {
-        code => $code, name => $name, continent => $continent,
-        lat => $lat, lon => $lon, servers => \@servers
-    };
 }
 
+# Discard the parsed country database
 $countries->delete;
 
+# Loop over the mappings, trying to assign each country to the
+# nearest server, but subject to the bandwidth limits;
+foreach my $mapping (sort {  $b->{priority} <=> $a->{priority} || $a->{distance} <=> $b->{distance} } @mappings)
+{
+    my $country = $mapping->{country};
+    my $server = $mapping->{server};
+
+    if ($country->{bandwidth} <= $server->{bandwidth} && !exists($country->{server}))
+    {
+        $country->{server} = $server;
+        $server->{bandwidth} = $server->{bandwidth} - $country->{bandwidth};
+    }
+}
+
+# Loop over the mappings again, assigning anything that is left
+# as best we can, and allowing bandwidth limits to be exeeded
+foreach my $mapping (sort {  $b->{priority} <=> $a->{priority} || $a->{distance} <=> $b->{distance} } @mappings)
+{
+    my $country = $mapping->{country};
+    my $server = $mapping->{server};
+
+    $country->{server} = $server unless exists($country->{server});
+}
+
+# Open output files
 my $zonefile = IO::File->new("> data/${zone}") || die "$!";
 my $kmlfile = IO::File->new("> kml/${zone}.kml") || die "$!";
 my $kmlwriter = XML::Writer->new(OUTPUT => $kmlfile, ENCODING => 'utf-8');
 
+# Output the KML header
 $kmlwriter->xmlDecl();
 $kmlwriter->startTag("kml", "xmlns" => "http://www.opengis.net/kml/2.2");
 $kmlwriter->startTag("Document");
 
+# Output details for each country
 foreach my $country (values %countries)
 {
-    my @servers = sort { $b->{priority} <=> $a->{priority} || $a->{distance} <=> $b->{distance} } @{$country->{servers}};
-    my $server = $servers->{$servers[0]->{name}};
+    my $server = $country->{server};
     my $clon = $country->{lon};
     my $clat = $country->{lat};
     my $slon = $server->{lon};
@@ -114,7 +159,7 @@ foreach my $country (values %countries)
         $slon = $slon - 360;
     }
 
-    $zonefile->print("C\L$country->{code}\E.${zone}:$servers[0]->{name}.${zone}:600\n");
+    $zonefile->print("C\L$country->{code}\E.${zone}:$server->{name}.${zone}:600\n");
 
     $kmlwriter->startTag("Placemark");
     $kmlwriter->dataElement("name", $country->{name});
@@ -124,20 +169,26 @@ foreach my $country (values %countries)
     $kmlwriter->endTag("Placemark");
 }
 
+# Output default records for IPs that can't be mapped to a country
 foreach my $server (grep { $servers->{$_}->{default} } keys %$servers)
 {
     $zonefile->print("Cxx.${zone}:${server}.${zone}:600\n");
 }
 
+# End the KML file
 $kmlwriter->endTag("Document");
 $kmlwriter->endTag("kml");
 $kmlwriter->end();
 
+# Close the output files
 $kmlfile->close();
 $zonefile->close();
 
 exit 0;
 
+#
+# Find the centre value between two latitudes
+#
 sub centre_lat
 {
     my $south = shift;
@@ -146,6 +197,9 @@ sub centre_lat
     return ( $south + $north ) / 2;
 }
 
+#
+# Find the centre value between two longitudes
+#
 sub centre_lon
 {
     my $west = shift;
@@ -166,6 +220,9 @@ sub centre_lon
     return $lon
 }
 
+#
+# Match a country against a server
+#
 sub match_country
 {
     my $server = shift;
@@ -197,9 +254,21 @@ sub match_country
     {
         $match = "allowed";
     }
+    elsif ($server->{denied} &&
+        $server->{denied}->{countries} &&
+        grep { $_ eq $country } @{$server->{preferred}->{countries}})
+    {
+        $match = "denied";
+    }
+    elsif ($server->{denied} &&
+           $server->{denied}->{continents} &&
+           grep { $_ eq $continent } @{$server->{preferred}->{continents}})
+    {
+        $match = "denied";
+    }
     elsif ($server->{allowed})
     {
-        $match = "none";
+        $match = "denied";
     }
     else
     {
@@ -209,6 +278,9 @@ sub match_country
     return $match;
 }
 
+#
+# Compute the great circle distance between two points
+#
 sub distance
 {
     my $lat1 = deg2rad(shift);
diff --git a/bin/sumlogs b/bin/sumlogs
new file mode 100755 (executable)
index 0000000..0db3ac6
--- /dev/null
@@ -0,0 +1,56 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Net::Patricia;
+use YAML;
+
+my $pt = new Net::Patricia;
+
+open(COUNTRIES, "< /etc/powerdns/countries.conf") || die "Can't open /etc/powerdns/countries.conf";
+
+while (my $line = <COUNTRIES>)
+{
+    if ($line =~ /^(\d+\.\d+\.\d+\.\d+\/\d+)\s+:127\.\d+\.\d+\.\d+:([a-z]{2})/)
+    {
+        my $address = $1;
+        my $country = uc($2);
+
+        $pt->add_string($address, $country);
+    }
+}
+
+close(COUNTRIES);
+
+my $total_bytes = 0;
+my %country_bytes;
+
+while (my $record = <>)
+{
+    if ($record =~ /^\d+\.\d+\s+\d+\s+(\d+\.\d+\.\d+\.\d+)\s+TCP_[A-Z_]+\/\d+\s+(\d+) /)
+    {
+        my $ip = $1;
+        my $bytes = $2;
+        my $country = $pt->match_string($ip);
+
+        $country_bytes{$country} += $bytes if defined($country);
+
+        $total_bytes += $bytes;
+    }
+    else
+    {
+        warn $record;
+    }
+}
+
+my %country_bandwidth;
+
+while (my($country,$bytes) = each %country_bytes)
+{
+    $country_bandwidth{$country} = $bytes * 250 * 1024 * 1024 / $total_bytes;
+}
+
+print Dump(\%country_bandwidth);
+
+exit 0;
index 25c90d3..b71d1f6 100644 (file)
@@ -5,14 +5,6 @@ london:
   pingdom: 546503
   bandwidth: 100
   default: true
-  preferred:
-    continents:
-      - EU
-      - NA
-      - OC
-      - AF
-    countries:
-      - GB
 
 # Sj√∂bo, SE
 sjobo:
@@ -20,23 +12,6 @@ sjobo:
   lon: 13.70273
   pingdom: 546505
   bandwidth: 80
-  allowed:
-    continents:
-      - EU
-      - AS
-  preferred:
-    countries:
-      - DK
-      - FI
-      - AX
-      - SJ
-      - SE
-      - GL
-      - FO
-      - PL
-      - DE
-      - CH
-      - LI
 
 # Moscow, RU
 moscow:
@@ -44,26 +19,9 @@ moscow:
   lon: 37.617
   pingdom: 659912
   bandwidth: 60
-  allowed:
-    countries:
-      - RU
-      - UA
-      - BY
-      - MD
-      - KZ
-      - AM
-      - AZ
-      - GE
   preferred:
     countries:
       - RU
-      - UA
-      - BY
-      - MD
-      - KZ
-      - AM
-      - AZ
-      - GE
 
 # Brisbane, AU
 brisbane:
@@ -74,15 +32,6 @@ brisbane:
   allowed:
     continents:
       - OC
-    countries:
-      - AU
-      - NZ
-  preferred:
-    continents:
-      - OC
-    countries:
-      - AU
-      - NZ
 
 # Pau, FR
 pau:
@@ -93,18 +42,6 @@ pau:
   allowed:
     continents:
       - EU
-    countries:
-  preferred:
-    countries:
-      - FR
-      - ES
-      - PT
-      - AD
-      - GI
-      - IT
-      - MC
-      - SM
-      - VA
 
 # Amsterdam, NL
 amsterdam:
@@ -112,31 +49,13 @@ amsterdam:
   lon: 4.89222
   pingdom: 766251
   bandwidth: 30
-  allowed:
-    continents:
-      - EU
-    countries:
-      - IS
-  preferred:
-    countries:
-      - NL
-      - BE
-      - LU
-      - IS
-      - EE
-      - LV
-      - LT
-      - CZ
 
 # Oslo, NO
 oslo:
   lat: 59.94944
   lon: 10.75639
   pingdom: 769267
+  bandwidth: 20
   allowed:
     continents:
       - EU
-    countries:
-  preferred:
-    countries:
-      - NO