Pyxida: An Open Source Network Coordinate Library and Application

We have created an open source library and application that incorporates the ideas from our research on network coordinates. It is called Pyxida (pronounced "peeks-ee-da" which means "compass" in Greek). In the short term, the Pyxida project will provide the following pieces of functionality: (a) estimate the latencies between hosts in a distributed system with stable and accurate network coordinates, (b) route to the host whose coordinate is nearest to a point in the abstract coordinate space (useful for distributed gaming applications), and (c) provide a stand-alone application that constructs a network coordinate system.

We are open to new developers; if you are interested, please send us an email.

• The Azureus BitTorrent Client uses Pyxida for its decentralized tracker and to quickly and cheaply select between possible piece providers.
• A slice on PlanetLab uses Pyxida to dynamically track the coordinates of its hundreds of machines.
• Researchers at Boston University and Harvard are using Pyxida to study selfish neighbor selection in overlay and peer-to-peer networks.
• Tsinghua Network Coordinates Research Project uses Pyxida to analyze network coordinate systems under churn.
• PeerWise Overlay Network at the University of Maryland
• A Comparative Study of Network Coordinate System at UCSB.

Project Leaders

• Jonathan Ledlie (Harvard University)
• Peter Pietzuch (Imperial College London)

Developers

• Michael Parker (UCLA, Google)

Library Version

• pyxida-0.1.5.jar

Stand-alone Application

• pyxida-0.1.5.tar.gz

Pyxida can be used in three ways: as a "standalone" application, as a library that you build into your distributed application, and as a service you query. The standalone application and the library are independent software artifacts; the service is an instance of the library running on PlanetLab.

Our reasoning behind creating two artifacts instead of just one is that some users want to incorporate network coordinates directly into their application: they want to control the network, when messages are sent, the wire format, and have more control in general. These people will use the library. Other people want a distinct network measurement substrate, a tool that performs measurements of its own accord and simply provides quick estimates of network latencies. These people will use the standalone application. In addition, because the standalone application is one of the simplest uses of the library, its code provides library users with a starting point to help them incorporate the library into their application.

PlanetLab Service

Web Interface

XML/RPC Interface

The query tool can: (a) ask a node for its current coordinate, (b) ask a node for another node's coordinate, (c) ask for the estimated latency between two nodes. You can find specifics on running the tool by running it with no arguments (./query.pl). Support for proxy coordinates will be added to the tool in the future. In addition, we are creating a separate tool to support the creation and deletion of proxy coordinates.

Example of querying a node for its own coordinate:
query: query.pl -l http://planetlab-1.imperial.ac.uk
response: [-469.250 148.827 -718.443 -112.174 h0.357]

Example of estimating inter-node latency:
query: query.pl -a planetlab01.cs.washington.edu -b planetlab1.csail.mit.edu http:planetlab-1.imperial.ac.uk//
response: 357.550

Note that we will be changing the path used to access the service relatively soon.

Standalone Version

• Download and untar the tarball.
• Modify config/pyxida.cfg appropriately.
• List a set of nodes that will tend to be up that others can bootstrap from.
• Select ICMP or application-level measurements. ICMP is more accurate but requires the application be run as root. We use Keita Fujii's Jpcap library for ICMP measurements.
• run: ./runPyxida.sh on the nodes in your overlay.
• Observe the local coordinates change in the log files and use the (included) perl scripts to query the overlay.
• Or write your own tools that query via external API (see javadoc).

Library Version

• Download pyxida.jar
• Create an instance of NCClient on each node
• Piggyback the following information between neighbors: the coordinate, the local error, and the age; and determine a round-trip time estimate.
• Call ncClient.processSample() to refine each node's coordinate.
• The standalone application does all of this for you, so it provides a good starting point on using the library in your own application.

Videos

You can find a directory with videos that show the dynamic behaviour of network coordinates on PlanetLab.

Time-sliced Coordinates

You can find a directory with coordinates over time that show which nodes were running and what their coordinates were, sliced into ten-minute intervals. Data taken from PlanetLab.

Log Files

Logging levels for particular classes and subtrees can be set in the config/log.config file.
E.g. edu.harvard.syrah.pyxida.level = DEBUG Setting this to DEBUG will produce a lot of output. We suggest INFO, which will produce a periodic summary.

The basic format of the logs is:
DEBUG/INFO/WARNING/ERROR timestamp java-class : message
e.g. DE 1165381552727 NCManager : setting timer to 9477

Each network coordinate summarizes its behavior with lines of the form:
update: [sc=[11.498,-69.529,14.73,16.269,h19.323],
ac=[6.827,-41.283,8.746,9.66,h11.473],
er=0.675,sys_re50=0.454,sys_re95=1,app_re50=0.672,app_re95=1.93,
sys_dd=1.256,app_dd=5.455,ne=2.025,rd=0,
sf=5205.779,af=5205.779,rrl=0.278,narl=0.212,ralp=0.338,
age=3,vl=72,gr=0.007,nn=96.6]

The format of these update lines is:
sc: system-level coordinate
ac: app-level coordinate (see our ICDCS/WORLDS papers about this)
er: Vivaldi error/confidence (an EWMA)
sys_re50 = median (50th pctl) of the distribution of relative errors for the recent past
sys_re95 = 95th pctl of this distribution
app_* = same but for app-level coordinate (however, they are not fully functional in our current version)
sys_dd = sys-level coordinate change per update (distance delta)
sf = avg number of milliseconds between updates
nn = distance to nearest neighbor
rrl = Lua's relative rank loss
narl and ralp are two metrics from our ICDCS and WORLDS papers
gr = the pull of gravity

Typically the place to start is sys_re50. On the Internet, the median of the distribution of these values should range between 8-20% depending on the particular set of machines you are using.

Known bugs with 0.1.2

• XML/RPC interface is fragile (invalid ports may cause crashes).

Known bugs with 0.1.1

• XML/RPC interface (and query.pl) is broken.
• ICMP crashes.

Coming soon:

• web query and status tool
• proxy coordinates: create a coordinate for a non-overlay node.
• add application-level coordinates for improved stability
• version of the library written in Python.