diff options
Diffstat (limited to 'ios/RelaySelector')
| -rw-r--r-- | ios/RelaySelector/Haversine.swift | 48 | ||||
| -rw-r--r-- | ios/RelaySelector/Midpoint.swift | 49 | ||||
| -rw-r--r-- | ios/RelaySelector/RelaySelector.swift | 77 |
3 files changed, 157 insertions, 17 deletions
diff --git a/ios/RelaySelector/Haversine.swift b/ios/RelaySelector/Haversine.swift new file mode 100644 index 0000000000..74fe3218c7 --- /dev/null +++ b/ios/RelaySelector/Haversine.swift @@ -0,0 +1,48 @@ +// +// Haversine.swift +// RelaySelector +// +// Created by Marco Nikic on 2023-06-29. +// Copyright © 2023 Mullvad VPN AB. All rights reserved. +// + +import Foundation +import MullvadTypes + +public enum Haversine { + /// Approximation of the radius of the average circumference, + /// where the boundaries are the meridian (6367.45 km) and the equator (6378.14 km). + static let earthRadiusInKm = 6372.8 + + /// Implemented as per https://rosettacode.org/wiki/Haversine_formula#Swift + /// Computes the great circle distance between two points on a sphere. + /// + /// The inputs are converted to radians, and the output is in kilometers. + /// - Parameters: + /// - lat1: The first point's latitude + /// - lon1: The first point's longitude + /// - lat2: The second point's latitude + /// - lon2: The second point's longitude + /// - Returns: The haversine distance between the two points. + static func distance( + _ latitude1: Double, + _ longitude1: Double, + _ latitude2: Double, + _ longitude2: Double + ) -> Double { + let dLat = latitude1.toRadians - latitude2.toRadians + let dLon = longitude1.toRadians - longitude2.toRadians + + let haversine = sin(dLat / 2).squared + sin(dLon / 2) + .squared * cos(latitude1.toRadians) * cos(latitude2.toRadians) + let c = 2 * asin(sqrt(haversine)) + + return Self.earthRadiusInKm * c + } +} + +extension Double { + var toRadians: Double { self * Double.pi / 180 } + var toDegrees: Double { self * 180.0 / Double.pi } + var squared: Double { pow(self, 2) } +} diff --git a/ios/RelaySelector/Midpoint.swift b/ios/RelaySelector/Midpoint.swift new file mode 100644 index 0000000000..d01983a96f --- /dev/null +++ b/ios/RelaySelector/Midpoint.swift @@ -0,0 +1,49 @@ +// +// Midpoint.swift +// RelaySelector +// +// Created by Marco Nikic on 2023-07-11. +// Copyright © 2023 Mullvad VPN AB. All rights reserved. +// + +import CoreLocation +import Foundation +import MullvadTypes + +public enum Midpoint { + /// Computes the approximate midpoint of a set of locations. + /// + /// This works by calculating the mean Cartesian coordinates, and converting them + /// back to spherical coordinates. This is approximate, because the semi-minor (polar) + /// axis is assumed to equal the semi-major (equatorial) axis. + /// + /// https://en.wikipedia.org/wiki/Spherical_coordinate_system#Cartesian_coordinates + static func location(in coordinates: [CLLocationCoordinate2D]) -> CLLocationCoordinate2D { + var x = 0.0, y = 0.0, z = 0.0 + var count = 0 + + coordinates.forEach { coordinate in + let cos_lat = cos(coordinate.latitude.toRadians) + let sin_lat = sin(coordinate.latitude.toRadians) + let cos_lon = cos(coordinate.longitude.toRadians) + let sin_lon = sin(coordinate.longitude.toRadians) + + x += cos_lat * cos_lon + y += cos_lat * sin_lon + z += sin_lat + + count += 1 + } + + let inv_total_weight = 1.0 / Double(count) + x *= inv_total_weight + y *= inv_total_weight + z *= inv_total_weight + + let longitude = atan2(y, x) + let hypotenuse = sqrt(x * x + y * y) + let latitude = atan2(z, hypotenuse) + + return CLLocationCoordinate2D(latitude: latitude.toDegrees, longitude: longitude.toDegrees) + } +} diff --git a/ios/RelaySelector/RelaySelector.swift b/ios/RelaySelector/RelaySelector.swift index 5643f5d73f..558c81452c 100644 --- a/ios/RelaySelector/RelaySelector.swift +++ b/ios/RelaySelector/RelaySelector.swift @@ -42,9 +42,43 @@ public enum RelaySelector { ) -> REST.BridgeRelay? { let mappedBridges = mapRelays(relays: relaysResponse.bridge.relays, locations: relaysResponse.locations) let filteredRelays = applyConstraints(constraints, relays: mappedBridges) - let randomBridgeRelay = pickRandomRelay(relays: filteredRelays) + guard filteredRelays.isEmpty == false else { return shadowsocksRelay(from: relaysResponse) } - return randomBridgeRelay?.relay ?? shadowsocksRelay(from: relaysResponse) + // Compute the midpoint location from all the filtered relays + // Take *either* the first five relays, OR the relays below maximum bridge distance + // sort all of them by Haversine distance from the computed midpoint location + // then use the roulette selection to pick a bridge + + let midpointDistance = Midpoint.location(in: filteredRelays.map { $0.serverLocation.geoCoordinate }) + let maximumBridgeDistance = 1500.0 + let relaysWithDistance = filteredRelays.map { + RelayWithDistance( + relay: $0.relay, + distance: Haversine.distance( + midpointDistance.latitude, + midpointDistance.longitude, + $0.serverLocation.latitude, + $0.serverLocation.longitude + ) + ) + }.sorted { + $0.distance < $1.distance + }.filter { + $0.distance <= maximumBridgeDistance + }.prefix(5) + + var greatestDistance = 0.0 + relaysWithDistance.forEach { + if $0.distance > greatestDistance { + greatestDistance = $0.distance + } + } + + let randomRelay = rouletteSelection(relays: Array(relaysWithDistance), weightFunction: { relay in + UInt64(1 + greatestDistance - relay.distance) + }) + + return randomRelay?.relay ?? filteredRelays.randomElement()?.relay } /** @@ -64,7 +98,7 @@ public enum RelaySelector { numberOfFailedAttempts: numberOfFailedAttempts ) - guard let relayWithLocation = pickRandomRelay(relays: filteredRelays), let port else { + guard let relayWithLocation = pickRandomRelayByWeight(relays: filteredRelays), let port else { throw NoRelaysSatisfyingConstraintsError() } @@ -82,7 +116,7 @@ public enum RelaySelector { return RelaySelectorResult( endpoint: endpoint, relay: relayWithLocation.relay, - location: relayWithLocation.location + location: relayWithLocation.serverLocation ) } @@ -98,16 +132,16 @@ public enum RelaySelector { case let .only(relayConstraint): switch relayConstraint { case let .country(countryCode): - return relayWithLocation.location.countryCode == countryCode && + return relayWithLocation.serverLocation.countryCode == countryCode && relayWithLocation.relay.includeInCountry case let .city(countryCode, cityCode): - return relayWithLocation.location.countryCode == countryCode && - relayWithLocation.location.cityCode == cityCode + return relayWithLocation.serverLocation.countryCode == countryCode && + relayWithLocation.serverLocation.cityCode == cityCode case let .hostname(countryCode, cityCode, hostname): - return relayWithLocation.location.countryCode == countryCode && - relayWithLocation.location.cityCode == cityCode && + return relayWithLocation.serverLocation.countryCode == countryCode && + relayWithLocation.serverLocation.cityCode == cityCode && relayWithLocation.relay.hostname == hostname } } @@ -136,11 +170,15 @@ public enum RelaySelector { } } - private static func pickRandomRelay<T: AnyRelay>(relays: [RelayWithLocation<T>]) -> RelayWithLocation<T>? { - let totalWeight = relays.reduce(0) { accummulatedWeight, relayWithLocation in - accummulatedWeight + relayWithLocation.relay.weight - } + private static func pickRandomRelayByWeight<T: AnyRelay>(relays: [RelayWithLocation<T>]) + -> RelayWithLocation<T>? { + rouletteSelection(relays: relays, weightFunction: { relayWithLocation in relayWithLocation.relay.weight }) + } + private static func rouletteSelection<T>(relays: [T], weightFunction: (T) -> UInt64) -> T? { + let totalWeight = relays.map { weightFunction($0) }.reduce(0) { accumulated, weight in + accumulated + weight + } // Return random relay when all relays within the list have zero weight. guard totalWeight > 0 else { return relays.randomElement() @@ -150,9 +188,9 @@ public enum RelaySelector { // non-zero weight. var i = (1 ... totalWeight).randomElement()! - let randomRelay = relays.first { relayWithLocation -> Bool in + let randomRelay = relays.first { relay -> Bool in let (result, isOverflow) = i - .subtractingReportingOverflow(relayWithLocation.relay.weight) + .subtractingReportingOverflow(weightFunction(relay)) i = isOverflow ? 0 : result @@ -228,7 +266,7 @@ public enum RelaySelector { longitude: serverLocation.longitude ) - return RelayWithLocation(relay: relay, location: location) + return RelayWithLocation(relay: relay, serverLocation: location) } } @@ -266,5 +304,10 @@ extension REST.BridgeRelay: AnyRelay {} fileprivate struct RelayWithLocation<T: AnyRelay> { let relay: T - let location: Location + let serverLocation: Location +} + +fileprivate struct RelayWithDistance<T: AnyRelay> { + let relay: T + let distance: Double } |