geolocate gateways and kd-tree
authorKali Kaneko <kali@leap.se>
Thu, 13 Dec 2018 13:45:27 +0000 (08:45 -0500)
committerKali Kaneko (leap communications) <kali@leap.se>
Thu, 13 Dec 2018 14:13:44 +0000 (15:13 +0100)
during initialization, we fetch the eip-config.json file from the
configured provider. we geolocate the gateways (using a golang package
that has some cities missing, hence the workaround) and
initialize a KD-Tree with the gateways.

using the KD-Tree, it is very cheap to calculate the nearest gateway for
every request, which is provider as a filed in the json to the client -
as a suggestion to be used or not in the gateway selection process.

gateways.go [new file with mode: 0644]
geo.go [new file with mode: 0644]
main.go

diff --git a/gateways.go b/gateways.go
new file mode 100644 (file)
index 0000000..404f40a
--- /dev/null
@@ -0,0 +1,89 @@
+// Copyright (c) 2018 LEAP Encryption Access Project
+
+package main
+
+import (
+       "encoding/json"
+       "fmt"
+       "net/http"
+)
+
+const (
+       // yes, I am cheating. The config file is also exposed on the top-level
+       // domain, which is served behind a letsencrypt certificate. this saves passing
+       // the certificate for the ca etc.
+       eipAPI = "https://black.riseup.net/1/config/eip-service.json"
+)
+
+type bonafide struct {
+       client *http.Client
+       eip    *eipService
+}
+
+type eipService struct {
+       Gateways  []gateway
+       Locations map[string]struct {
+               CountryCode string
+               Hemisphere  string
+               Name        string
+               Timezone    string
+       }
+}
+
+type gateway struct {
+       Host        string
+       Location    string
+       IPAddress   string `json:"ip_address"`
+       Coordinates coordinates
+}
+
+type coordinates struct {
+       Latitude  float64
+       Longitude float64
+}
+
+func newBonafide() *bonafide {
+       client := &http.Client{}
+       return &bonafide{client, nil}
+}
+
+func (b *bonafide) getGateways() ([]gateway, error) {
+       if b.eip == nil {
+               err := b.fetchEipJSON()
+               if err != nil {
+                       return nil, err
+               }
+       }
+       return b.eip.Gateways, nil
+}
+
+func (b *bonafide) fetchEipJSON() error {
+       resp, err := b.client.Post(eipAPI, "", nil)
+       if err != nil {
+               return err
+       }
+       defer resp.Body.Close()
+       if resp.StatusCode != 200 {
+               return fmt.Errorf("get eip json has failed with status: %s", resp.Status)
+       }
+       var eip eipService
+       decoder := json.NewDecoder(resp.Body)
+       err = decoder.Decode(&eip)
+       if err != nil {
+               return err
+       }
+       b.eip = &eip
+       return nil
+}
+
+func (b *bonafide) listGateways() error {
+       if b.eip == nil {
+               return fmt.Errorf("cannot list gateways, it is empty")
+       }
+
+       for i := 0; i < len(b.eip.Gateways); i++ {
+               fmt.Printf("\t%v\n", b.eip.Gateways[i])
+       }
+       return nil
+
+}
diff --git a/geo.go b/geo.go
new file mode 100644 (file)
index 0000000..e004fbb
--- /dev/null
+++ b/geo.go
@@ -0,0 +1,40 @@
+package main
+
+import (
+       "github.com/hongshibao/go-kdtree"
+)
+
+type EuclideanPoint struct {
+       kdtree.Point
+       Vec []float64
+}
+
+func (p EuclideanPoint) Dim() int {
+       return len(p.Vec)
+}
+
+func (p EuclideanPoint) GetValue(dim int) float64 {
+       return p.Vec[dim]
+}
+
+func (p EuclideanPoint) Distance(other kdtree.Point) float64 {
+       var ret float64
+       for i := 0; i < p.Dim(); i++ {
+               tmp := p.GetValue(i) - other.GetValue(i)
+               ret += tmp * tmp
+       }
+       return ret
+}
+
+func (p EuclideanPoint) PlaneDistance(val float64, dim int) float64 {
+       tmp := p.GetValue(dim) - val
+       return tmp * tmp
+}
+
+func NewEuclideanPoint(vals ...float64) *EuclideanPoint {
+       ret := &EuclideanPoint{}
+       for _, val := range vals {
+               ret.Vec = append(ret.Vec, val)
+       }
+       return ret
+}
diff --git a/main.go b/main.go
index 4b9b9cf..1767a7c 100644 (file)
--- a/main.go
+++ b/main.go
@@ -7,9 +7,14 @@ import (
        "log"
        "net"
        "net/http"
+       "regexp"
        "strconv"
+       "strings"
 
+       "github.com/StefanSchroeder/Golang-Ellipsoid/ellipsoid"
+       "github.com/hongshibao/go-kdtree"
        "github.com/oschwald/geoip2-golang"
+       "github.com/tidwall/cities"
 )
 
 func floatToString(num float64) string {
@@ -33,7 +38,55 @@ func getRemoteIP(req *http.Request) string {
 }
 
 type geodb struct {
-       db *geoip2.Reader
+       db          *geoip2.Reader
+       Gateways    []gateway
+       GatewayTree *kdtree.KDTree
+       GatewayMap  map[[3]float64]gateway
+       earth       *ellipsoid.Ellipsoid
+}
+
+func geolocateCity(city string) coordinates {
+       // because some cities apparently are not good enough for the top 10k
+       missingCities := make(map[string]coordinates)
+       missingCities["hongkong"] = coordinates{22.319201099, 114.1696121}
+
+       re := regexp.MustCompile("-| ")
+       for i := 0; i < len(cities.Cities); i++ {
+               c := cities.Cities[i]
+               canonical := strings.ToLower(city)
+               canonical = re.ReplaceAllString(canonical, "")
+               if strings.ToLower(c.City) == canonical {
+                       return coordinates{c.Latitude, c.Longitude}
+               }
+               v, ok := missingCities[canonical]
+               if ok == true {
+                       return v
+               }
+
+       }
+       return coordinates{0, 0}
+}
+
+func (g *geodb) geolocateGateways(b *bonafide) {
+       g.GatewayMap = make(map[[3]float64]gateway)
+       gatewayPoints := make([]kdtree.Point, 0)
+
+       for i := 0; i < len(b.eip.Gateways); i++ {
+               gw := b.eip.Gateways[i]
+               coord := geolocateCity(gw.Location)
+               gw.Coordinates = coord
+               b.eip.Gateways[i] = gw
+
+               x, y, z := g.earth.ToECEF(coord.Latitude, coord.Longitude, 0)
+
+               p := NewEuclideanPoint(x, y, z)
+               gatewayPoints = append(gatewayPoints, *p)
+               var i [3]float64
+               copy(i[:], p.Vec)
+               g.GatewayMap[i] = gw
+       }
+       g.Gateways = b.eip.Gateways
+       g.GatewayTree = kdtree.NewKDTree(gatewayPoints)
 }
 
 func (g *geodb) getRecordForIP(ipstr string) *geoip2.City {
@@ -52,13 +105,24 @@ type jsonHandler struct {
 func (jh *jsonHandler) ServeHTTP(w http.ResponseWriter, req *http.Request) {
        ipstr := getRemoteIP(req)
        record := jh.geoipdb.getRecordForIP(ipstr)
+
+       x, y, z := jh.geoipdb.earth.ToECEF(record.Location.Latitude, record.Location.Longitude, 0)
+
+       t := NewEuclideanPoint(x, y, z)
+       nn := jh.geoipdb.GatewayTree.KNN(t, 1)[0]
+       p := [3]float64{nn.GetValue(0), nn.GetValue(1), nn.GetValue(2)}
+       closestGateway := jh.geoipdb.GatewayMap[p]
+
        data := map[string]string{
                "ip":   ipstr,
                "cc":   record.Country.IsoCode,
                "city": record.City.Names["en"],
                "lat":  floatToString(record.Location.Latitude),
                "lon":  floatToString(record.Location.Longitude),
+               "gw":   closestGateway.Location,
+               "gwip": closestGateway.IPAddress,
        }
+
        dataJSON, _ := json.Marshal(data)
        fmt.Fprintf(w, string(dataJSON))
 }
@@ -90,7 +154,15 @@ func main() {
        }
        defer db.Close()
 
-       geoipdb := geodb{db}
+       earth := ellipsoid.Init("WGS84", ellipsoid.Degrees, ellipsoid.Meter, ellipsoid.LongitudeIsSymmetric, ellipsoid.BearingIsSymmetric)
+       geoipdb := geodb{db, nil, nil, nil, &earth}
+
+       log.Println("Seeding gateway list...")
+       bonafide := newBonafide()
+       bonafide.getGateways()
+
+       geoipdb.geolocateGateways(bonafide)
+       bonafide.listGateways()
 
        mux := http.NewServeMux()
        jh := &jsonHandler{&geoipdb}