SWORD on PlanetLab: Scalable Wide-Area Resource Discovery

Query Language

Note: Currently inter-node and per-group requirements are not supported because no latency or bandwidth sensors are available. We leave the following discussion here for illustrative purposes only.

SWORD takes as input an XML query. The query requests one or more groups of nodes. A group is an equivalence class of nodes with the same requirements. These requirements may be single-node requirements (load, free memory, etc.) or inter-node requirements. In addition to per-group requirements, the user may specify cross-group constraints.

The system is best illustrated with a sample query, which appears below. In the next few paragraphs we will explain what this query means.

     <request>
        <group>
           <name>Group1</name>
           <num_machines>10</num_machines>
           <oneminload>0.0,0.0,0.0,2.0,0.01</oneminload>
           <disk_free>0.1,0.2,max,max,0.005</disk_free>
           <latency>0.0,0.0,20.0,30.0,0.5</latency>
           <os_name>
              <value>Linux, 0.0</value>
           </os_name>
           <gnp>
              <value>0.0/0.0/0.0;50.0, 0.0</value>
           </gnp>
        </group>
        <group>
           <name>Group2</name>
           <num_machines>10</num_machines>
           <oneminload>0.0,0.0,0.0,2.0,0.01</oneminload>
           <disk_free>0.1,0.2,max,max,0.005</disk_free>
           <latency>0.0,0.0,20.0,30.0,0.5</latency>
           <os_name>
              <value>Linux, 0.0</value>
           </os_name>
           <gnp>
              <value>100.0/-100.0/100.0;50.0, 0.0</value>
           </gnp>
        </group>
        <constraint>
           <group_names>Group1 Group2</group_names>
           <latency>0.0,10.0,90.0,100.0,0.5</latency>
        </constraint>
     </request>
    

This query requests two groups. Each group is requested to have ten machines, with no more than two nodes in either group coming from the same PlanetLab site. Each group is to be composed of a disjoint set of nodes such that the nodes within a group meet the following requirements: oneminload is less than 2.0, disk_free is greater than 0.1 GB, os_name is Linux, and the latency from that node to every other node in the group is less than 30 ms.

Additionally, each node in Group 1 is required to be within a radius of 50.0 from the 3D network coordinate (0.0, 0.0, 0.0), and each node in Group 2 is required to be within a radius of 50.0 from the 3D network coordinate (100.0, -100.0, 100.0). What this means is that if there is a node A at (0.0, 0.0, 0.0) and a node B at (100.0, -100.0, 100.0), then every node in Group 1 is within 50 ms latency of node A and every node in Group 2 is within 50 ms latency of node B. Finally, there must be at least one pair of nodes such that the first node is in group Group1, the second node is in group Group2, and the latency between the nodes is between 0.0 and 100.0.

Although it may seem redundant to allow queries over latency as well as network coordinates, it is not. For example, a query might place each group near a different network coordinate that is at the centroid of a user base (e.g. users in North America, users in Europe, users in Asia, etc.), while constraining inter-node latency among nodes in a group to ensure that nodes running the service have high-quality connections to transfer data amongst each other.

The syntax of the <request>, <group>, <constraint>, <name>, <num_machines>, and <group_names> tags should be clear from the sample query and the explanation above. The remaining tags specify requirements on attributes which can be doubles, strings, booleans, or network coordinates. SWORD currently uses CoTop as its data source.

In the example query, oneminload, disk_free, and latency are double attributes, os_name is a string attribute, and gnp is a network coordinate attribute. The syntax for the requirements associated with attributes of each of these types is as follows: attr refers to the name of the attribute (e.g. load_one), and actual_value refers to the actual value of that attribute for the candidate node under consideration. Note that each request (XML query) must contain at least one <group>, and there may be zero or more <constraint>s.


Requirements for double attributes

    <attr>abs_min, ideal_min, ideal_max, abs_max, k</attr>
    

abs_min is the required lower bound on actual_value
abs_max is the required upper bound on actual_value
ideal_min is the preferred lower bound on actual_value
ideal_max is the preferred upper bound on actual_value
k is the number of abstract penalty units "charged" per unit deviation of attr if actual_value is between abs_min and ideal_min or between ideal_max and abs_max.

If actual_value is less than abs_min or greater than abs_max, the node will never be returned, and if actual_value is between ideal_min and ideal_max the amount charged will be 0.

Here the "deviation" is defined as: if actual_value is between abs_min and ideal_min, then ideal_min-abs_min; otherwise actual_value is between ideal_max and abs_max and the deviation is abs_max-ideal_max. Penalty charged is then penalty*deviation. Thus penalty is in the normalized units of "badness per unit deviation" where deviation is measured in the native units of the attribute (e.g. GB for disk space, milliseconds for latency, etc.) In the example query above, the user has instructed the system to penalize a candidate node the same amount for each 0.01 unit of load, 0.005 GB of free disk space, or 0.5ms of inter-node latency that it is below ideal_min or above ideal_max.

The figure below illustrates the regions of this "penalty function" (which can be thought of as the inverse of a utility function).


Requirements for string attributes


    <attr>
	<value>name1 name2 name3 ..., p1</value>
	<value>name4 name5 name6 ..., p2</value>
    </attr>
    

nameX are the permitted string values for actual_value
p1 is the number of penalty units that will be "charged" if actual_value matches one of the strings name1, name2, name3, ...
p2 is the number of penalty units that will be "charged" if actual_value matches one of the strings name4, name5, name6, ...

For example, if the attribute is machine_type, the user might specify a penalty of 0 for x86 and 1 for powerpc.

The penalty curve for strings (and, as we shall see, for network coordinates) can therefore be thought of as a step function, as illustrated below.


Requirements for network coordinates


    <gnp>
	<vaue>coord_1;coord_2;coord_3/radius1, penalty1</value>
	<vaue>coord_4;coord_5;coord_6/radius2, penalty2</value>
    </gnp>
      
    

penalty1 is the number of penalty units that will be "charged" if the network coordinate of the candidate node is within radius1 units of the three-dimensional network coordinate (coord_1, coord_2, coord_3), and
penalty2 is the number of penalty units that will be "charged" if the network coordinate of the candidate node is within radius2 units of the three-dimensional network coordinate (coord_4, coord_5, coord_6).


Putting it all together

The penalty values allow a total "penalty" to be computed for assigning a candidate node to a particular group. This total penalty is the sum over all requirements for the group (including cross-group constraints) of the penalties associated with each attribute that is a requirement for the group. SWORD's job is to return to the user a mapping of candidate nodes to groups that minimizes the total cost of the mapping (i.e. the sum over all nodes of the penalty associated with putting each node in the group into which it is placed). The "penalty" associated with a requirement maps the deviation of the actual value into abstract penalty units.

Thus in SWORD, each requirement specifies a restricted form of a utility function. This family of utility functions is presumed to correspond to the Quality of Service (performance, reliability, predictability, etc.) that the application derives from different values of the various node attributes that affect the application's QoS.


Queries without utility functions and inter-node requirements

If you merely want any set of nodes that meet absolute requirements, i.e. you are not interested in the utility/penalty features, you can set all costs to zero. In that case the ideal_min and ideal_max values will be ignored. As a further simplification, you can leave out any inter-node requirements (intra-group and inter-group latency requirements). These simplifications allows you to issue a query more akin to what you might issue to a standard query processor. For example, the following very simple query requests all nodes with loads less than 2, at least 200 MB of free disk space, and at least 100 MB of free memory, with at most two nodes from each PlanetLab site. Note that SWORD allows the special value "all" for <num_machines>. If "all" is used for <num_machines> in a query, then there must be only one group and no inter-node (latency) requirements.

     <request>
        <group>
           <name>Group1</name>
           <num_machines>all</num_machines>
           <load_one>0.0,0.0,2.0,2.0,0.0</load_one>
           <disk_free>0.2,0.2,max,max,0.0</disk_free>
           <mem_free>102400.0,102400.0,max,max,0.0</mem_free>
           <os_name>
              <value>Linux, 0.0</value>
           </os_name>
        </group>
     </request>