meridian title
A Lightweight Approach to Network Positioning

Meridian Query Language Specification

We developed a language for safely executing general-purpose localization queries on Meridian hosts. The language enables a user to implement different localization algorithms based on the rings-of-rings overlay maintained by Meridian, which in turn enables the system to support a much larger class of algorithms than the three we explored in our SIGCOMM paper. The language for expressing these algorithms is a safe, polymorphic, dynamically-typed variant of C with tight resource controls and an extended set of library calls. Every Meridian packet carries the full query specified by the user, similar to a capsule in an active network, and the query is executed on each Meridian node it is forwarded. Hence the language can be used to implement and experiment with queries that we, the system implementers, have not yet thought of.

Major differences between the Meridian Query Language and C

1) No pointers, no heap objects.
2) No global variables
3) No incrementers/decrementers
4) No +=, *=, etc operators
5) Compound statement (i.e. {...}) must follow if/else/else if
6) Dynamic type checking
7) Structs have implicit typedefs (i.e. don't need struct keyword when defining an instance of it)
8) Structs cannot have another struct as a field
9) Does not support array of arrays, although it does support array of structs that has an array field

Due to the dynamic type checking, a program may fail a type check at a remote host, which can be difficult to debug. Testing the query locally is currently the best solution.

Limitations

Currently, the entire program plus the marshalled parameters must fit inside one UDP packet. The UDP payload size is set at 1400 bytes as many nodes have IP fragmentation disabled. The program text itself is compressed before being inserted into the packet, so the maximum size of the program text is approximately 3 KB.

The entire query must be resolved within a 10 seconds timeout. Queries that take longer than the timeout will be automatically removed from the Meridian servers.

A query is limited to O(N) number of hops/RPCs.

Primitive types

int, double, string

Additional structures

struct Node {
     int addr;
     int port;
     int rendvAddr;
     int rendvPort;
};

The Node structure is used in many of the library calls, and is implicitly defined. The addr and port are the address and port of the node. The rendvAddr and rendvPort are the rendevous nodes that the packet will route through in order to reach the firewalled host, where a value of 0 for both rendvAddr and rendvPort indicates the node is not behind a firewall.

struct Measurement {
     int addr;
     int port;
     int rendvAddr;
     int rendvPort;
     double distance[];
};

A Measurement is returned from system calls that issue probes, and represents a source node's latency measurement to a set of targets. Each entry in distance represents the latency in milliseconds from the source node (as defined by the addr, port, rendvAddr and rendvPort fields) to a target. The ordering of the distance array is always the same as the target array used to generate the Measurement.

System and Library Calls

The Meridian framework exports a set of interfaces through which query code can acquire node handles and perform latency probes.

Nodes

Node get_self()

 -- Returns a Node with 0 for addr, 0 for port, and the actual value of rendvAddr and rendvPort of the current node

Node[] ring_lt(double latency_ms)

 -- Returns a Node array with all primary ring members that are less than latency_ms away

Node[] ring_le(double latency_ms)

 -- Returns a Node array with all primary ring members that are less than or equal to latency_ms away

Node[] ring_gt(double latency_ms)

 -- Returns a Node array with all primary ring members that are greater than latency_ms away

Node[] ring_ge(double latency_ms)

 -- Returns a Node array with all primary ring members that are greater than or equal to latency_ms away

Probes

Measurement[] get_distance_tcp(
      Node target[],
      int timeout_ms)
Measurement[] get_distance_tcp(
      Node source[],
      Node target[],
      int timeout_ms)

 -- Issues TCP probes from each of the Meridian nodes in source to each of the target nodes in target. If no source array is given, then the node array {get_self()} is implicitly defined as source. The system call returns after all probes results have been returned, or the timeout of timeout_ms has expired. The return value is a Measurement array of the same size as source. The distance field in each Measurement entry i is of the same size as target, with each entry j in the distance array representing the measured latency from the source[i] to target[j]. If the system call returns from an expired timeout, any entries in the distance array with a value bigger than the timeout_ms should be considered as an incomplete probe. A timeout_ms of -1 indicates a timeout equal to the duration of the query.

Measurement[] get_distance_dns(
      Node target[],
      int timeout_ms)
Measurement[] get_distance_dns(
      Node source[],
      Node target[],
      int timeout_ms)

 -- Issues DNS probes from each of the Meridian nodes in source to each of the target DNS servers in target. The system call is the same as get_distance_tcp in other details

Measurement[] get_distance_ping(
      Node target[],
      int timeout_ms)
Measurement[] get_distance_ping(
      Node source[],
      Node target[],
      int timeout_ms)

 -- Issues Meridian PING probes from each of the Meridian nodes in source to each of the target Meridian servers in target. Note that the probes are not ICMP packets, but are UDP packets carrying a Meridian header in the payload. The system call is the same as get_distance_tcp in other details.

Library functions

T rpc(Node target, func, ...)

 -- A blocking call that forwards the control flow to the Meridian node target and executes the function func on the target node. The parameters to the function follow func in the parameter list. The type T returned by the call is the same type that the function func returns. Asynchronous RPCs are planned and should be available in the next revision.

T print(T value)

 -- Outputs to the console the string representation of value, and returns value unchanged. The type T must be a primitive type (i.e. int, double, and string). Note that calling print on a remote node will not result in any output on the console of the local node

T println(T value)

 -- Same as print but outputs an additional linebreak at the end.

double dbl(int x)

 -- Returns the nearest double representation of integer x

int round(double x)

 -- Returns the nearest integer representation of double x

int ceil(double x)

 -- Returns the ceiling of x as an integer

int floor(double x)

 -- Returns the floor of x as an integer

double sin(double x)

 -- See manpage sin(3)

double cos(double x)

 -- See manpage cos(3)

double tan(double x)

 -- See manpage tan(3)

double asin(double x)

 -- See manpage asin(3)

double acos(double x)

 -- See manpage acos(3)

double atan(double x)

 -- See manpage atan(3)

double log(double x)

 -- See manpage log(3)

double exp(double x)

 -- See manpage exp(3)

double pow(double x, double y)

 -- See manpage pow(3)

int dns_lookup(string name)

 -- Returns the address in host byte order from the hostname given in name. No explicit byte order conversion to network byte order is needed as the built in marshalling in the rpc function will handle the necessary byte conversions on RPCs, and both Node and Measurement store all integer fields in host byte order.

string dns_addr(int addr)

 -- Returns the standard numbers-and-dots notation of addr. The parameter addr must be in host byte order.

void push_back(T array[], T value)

 -- Push value to the end of array.

void pop_back(T array[])

 -- Removes the last entry in array. No action is taken if array is empty.

int array_size(T array[])

 -- Returns the number of entries in array.

T[] array_intersect(T x[], T y[])

 -- Every entry that is in x and also in y are copied to the return array. The resulting array will only contain unique entries even if x and/or y have duplicate entries.

T[] array_union(T x[], T y[])

 -- Every entry in both x and y are in the return array. The resulting array will only contain unique entries.

T array_max(T x[])

 -- Returns the largest entry in array x. Type T must be either int or double.

int array_max_offset(T x[])

 -- Returns the array offset to largest entry in array x. Type T must be either int or double.

T array_min(T x[])

 -- Returns the smallest entry in array x. Type T must be either int or double.

int array_min_offset(T x[])

 -- Returns the array offset to smallest entry in array x. Type T must be either int or double.

double array_avg(T x[])

 -- Returns the average value of the entries in array x. Type T must be either int or double.

Demo

You experiment with the Meridian Query Language by issuing queries in real time to our sample Meridian network. The demo is accessible here. All queries are limited to a total of 10 CPU seconds, are capped in how many packets they can send, and are limited in how much memory they can allocate, so the impact of errant queries on the network is limited. We reserve the right to terminate this service at any time for any reason for any user.