perfsonar-dev - nmwg: r282 - trunk/nmwg/doc/dLS

Subject: perfsonar development work

List archive

nmwg: r282 - trunk/nmwg/doc/dLS

From:
To: ,
Subject: nmwg: r282 - trunk/nmwg/doc/dLS
Date: Thu, 4 Oct 2007 22:32:30 -0400

Author: zurawski
Date: 2007-10-04 22:32:28 -0400 (Thu, 04 Oct 2007)
New Revision: 282

Added:
trunk/nmwg/doc/dLS/LSControl-Join.xml
trunk/nmwg/doc/dLS/LSControl-Leader.xml
trunk/nmwg/doc/dLS/LSControl-Summary.xml
trunk/nmwg/doc/dLS/LSControl-Summary2.xml
trunk/nmwg/doc/dLS/LSControl-Token.xml
trunk/nmwg/doc/dLS/metadata.xml
trunk/nmwg/doc/dLS/service.xml
Removed:
trunk/nmwg/doc/dLS/LSToken-Join.xml
trunk/nmwg/doc/dLS/LSToken-Leader.xml
trunk/nmwg/doc/dLS/LSToken-Summary.xml
trunk/nmwg/doc/dLS/LSToken-Token.xml
trunk/nmwg/doc/dLS/ex1.xml
trunk/nmwg/doc/dLS/ex2.xml
Modified:
trunk/nmwg/doc/dLS/LSRing.xml
trunk/nmwg/doc/dLS/dLS.html
trunk/nmwg/doc/dLS/dLS.pdf
trunk/nmwg/doc/dLS/dLS.xml
trunk/nmwg/doc/dLS/rfc2629.xslt
Log:
Adding many new sections, and addressing some of the comments by others.
there are still several examples and sections that need work:

Sections that need additional content
2.1.2 Upper Scope Summarization
2.1.2.1 IP addesses summarization algorithm
2.2.1 Join Procedure/2.2.1.1 Join algorithm
2.2.2 Token Passing/2.2.4 Leader election
2.3 search (and all subsections and related examples)

Examples that need additional content
LSControl-Summary
LSControl-Leader
LSDiscovery

-jason

Added: trunk/nmwg/doc/dLS/LSControl-Join.xml

Added: trunk/nmwg/doc/dLS/LSControl-Leader.xml

Added: trunk/nmwg/doc/dLS/LSControl-Summary.xml

Added: trunk/nmwg/doc/dLS/LSControl-Summary2.xml

Added: trunk/nmwg/doc/dLS/LSControl-Token.xml

Modified: trunk/nmwg/doc/dLS/LSRing.xml
===================================================================
--- trunk/nmwg/doc/dLS/LSRing.xml 2007-10-03 13:22:11 UTC (rev 281)
+++ trunk/nmwg/doc/dLS/LSRing.xml 2007-10-05 02:32:28 UTC (rev 282)
@@ -1,17 +1,3 @@
-
-
<nmwg:store type="LSRing-lower">


@@ -40,7 +26,6 @@
<psservice:serviceDescription>...</psservice:serviceDescription>
</psservice:service>
</perfsonar:subject>
-
<nmwg:eventType>http://perfsonar.net/services/LS/join/success</nmwg:eventType>
<nmwg:parameters>
<nmwg:parameter name="active">1</nmwg:parameter>
<nmwg:parameter name="contentSize">50</nmwg:parameter>
@@ -83,8 +68,6 @@

-
-
<nmwg:store type="LSRing-upper">


@@ -120,4 +103,3 @@
</nmwg:metadata>

</nmwg:store>
-

Deleted: trunk/nmwg/doc/dLS/LSToken-Join.xml

Deleted: trunk/nmwg/doc/dLS/LSToken-Leader.xml

Deleted: trunk/nmwg/doc/dLS/LSToken-Summary.xml

Deleted: trunk/nmwg/doc/dLS/LSToken-Token.xml

Modified: trunk/nmwg/doc/dLS/dLS.html
===================================================================
--- trunk/nmwg/doc/dLS/dLS.html 2007-10-03 13:22:11 UTC (rev 281)
+++ trunk/nmwg/doc/dLS/dLS.html 2007-10-05 02:32:28 UTC (rev 282)
@@ -272,7 +272,7 @@
content: "Distributed Lookup Service (dLS) in the perfSONAR
Framework";
}
@bottom-left {
- content: "Swany, et al.";
+ content: "Boote, et al.";
}
@bottom-center {
content: "Informational";
@@ -297,58 +297,62 @@
<link rel="Author" href="#rfc.authors">
<link rel="Copyright" href="#rfc.copyright">
<link rel="Chapter" title="1 Introduction" href="#rfc.section.1">
-<link rel="Chapter" title="2 System Specific Operation"
href="#rfc.section.2">
+<link rel="Chapter" title="2 system Specific Operation"
href="#rfc.section.2">
<link rel="Chapter" title="3 Bootstrapping" href="#rfc.section.3">
-<link rel="Chapter" title="4 Structures and Messages" href="#rfc.section.4">
-<link rel="Chapter" title="5 Open Issues" href="#rfc.section.5">
-<link rel="Chapter" title="6 Appendices" href="#rfc.section.6">
-<link rel="Chapter" href="#rfc.section.7" title="7 References">
+<link rel="Chapter" title="4 structures and Messages" href="#rfc.section.4">
+<link rel="Chapter" title="5 Appendices" href="#rfc.section.5">
+<link rel="Chapter" href="#rfc.section.6" title="6 References">
<meta name="generator"
content="http://greenbytes.de/tech/webdav/rfc2629.xslt, Revision 1.291,
2006/10/29 09:03:19, XSLT vendor: SAXON 8.8 from Saxonica
http://www.saxonica.com/";>
<link rel="schema.DC" href="http://purl.org/dc/elements/1.1/";>
+<meta name="DC.Creator" content="Boote, J">
+<meta name="DC.Creator" content="Glowiak, M">
<meta name="DC.Creator" content="Swany, M">
-<meta name="DC.Creator" content="Boote, J">
<meta name="DC.Creator" content="Zurawski, J">
-<meta name="DC.Creator" content="Glowiak, M">
<meta name="DC.Date.Issued" scheme="ISO8601" content="2007-10">
</head>
<body>
<table summary="header information" class="header" border="0"
cellpadding="1" cellspacing="1">
<tr>
-<td class="front left">Network Measurement Working Group</td>
-<td class="front right">M Swany, Editor</td>
+<td class="front left">perfSONAR</td>
+<td class="front right">J Boote</td>
</tr>
<tr>
<td class="front left">
</td>
-<td class="front right">UDel</td>
+<td class="front right">Internet2</td>
</tr>
<tr>
<td class="front left">Intended status: Informational</td>
-<td class="front right">J Boote, Contributor</td>
+<td class="front right">M Glowiak</td>
</tr>
<tr>
<td class="front left">
</td>
-<td class="front right">J Zurawski, Contributor</td>
+<td class="front right">PSNC</td>
</tr>
<tr>
<td class="front left">
</td>
-<td class="front right">Internet2</td>
+<td class="front right">M Swany</td>
</tr>
<tr>
<td class="front left">
</td>
-<td class="front right">M Glowiak, Contributor</td>
+<td class="front right">UDel</td>
</tr>
<tr>
<td class="front left">
</td>
-<td class="front right">PSNC</td>
+<td class="front right">J Zurawski</td>
</tr>
<tr>
<td class="front left">
</td>
+<td class="front right">Internet2</td>
+</tr>
+<tr>
+<td class="front left">
+</td>
<td class="front right">October 2007</td>
</tr>
</table>
@@ -356,11 +360,11 @@
<h1>
<a id="rfc.status" href="#rfc.status">Status of this Memo</a>
</h1>
-<p>This memo provides information for the Grid community. It does not
specify any standards or technical recommendations. Distribution is
unlimited.</p>
+<p>This memo provides information for the perfSONAR community. It does not
specify any standards or technical recommendations. Distribution is
unlimited.</p>
<h1>
<a id="rfc.copyrightnotice" href="#rfc.copyrightnotice">Copyright Notice</a>
</h1>
-<p>Copyright � The Open Grid Forum (2007). All Rights Reserved.</p>
+<p>Copyright � The perfSONAR Consortium (2007). All Rights Reserved.</p>
<hr class="noprint">
<h1 id="rfc.section.1" class="np">
<a href="#rfc.section.1">1.</a> <a id="intro"
href="#intro">Introduction</a>
@@ -390,25 +394,30 @@
<li>Scope - to enable a hierarchy of systems, some form of scoping must
exist that forms logical communication and data exchange channels.</li>
<li>Search - information location is key and the way in which distributed
location and search is handled is the crux of this service.</li>
</ul>
-<p id="rfc.section.1.p.4">Additionally we present solutions to issues
related to the operation of this seemless service including bootstrapping and
domain specific concerns.</p>
+<p id="rfc.section.1.p.4">Additionally we present solutions to issues
related to allow seamless operation of this service including bootstrapping
and domain specific concerns.</p>
<hr class="noprint">
<h1 id="rfc.section.2" class="np">
-<a href="#rfc.section.2">2.</a> <a id="system" href="#system">System
Specific Operation</a>
+<a href="#rfc.section.2">2.</a> <a id="system" href="#system">system
Specific Operation</a>
</h1>
<h2 id="rfc.section.2.1">
<a href="#rfc.section.2.1">2.1</a> <a id="summary"
href="#summary">Summarization</a>
</h2>
-<p id="rfc.section.2.1.p.1">The first step of information flow is when a
service registers with an LS. The service may know the name of an LS via
static configuration, or other forms of bootstrapping may occur. A service
registers metadata record about itself and full metadata (i.e. containing all
information such as subject, eventType(s), and any parameters, see <a
href="#service-metadata" title="Service metadata
example">Section 4.1</a>) about stored (or gathered) data. Such a record
is called Lookup Information (see <a href="#lookup-info" title="Lookup
Information">Section 4.2</a>). The idea is to move the metadata from a
local XML data store to a specialized LS with additional searching
capabilities. While a service instance may support limited searching, this is
not required as they should be focused on storing or gathering data and leave
the lookup functionality to the LS. Possible exceptions are rapidly changing
Metadata like the most recent timestamp and fu
ll details of data stored in long-term archival MAs.</p>
-<p id="rfc.section.2.1.p.2">
-<br>
-<br>
-<br>START_NOTE (Jason 9/18/07):<br>
-<br> Question 1) In the first level of summarization (i.e. 'local' ring)
what is being exchanged between HLS instances? Are they exchanging full
information, or summaries? Where is this info stored (i.e. seperate
collection)? If we are exchanging summaries it is natural to use a different
collection, if we are exchanging full info it doesn't seem to be necessary.
<br>
-<br>END_NOTE:<br>
-<br>
-<br>
-</p>
-<p id="rfc.section.2.1.p.3">The LS that a service contacts to register
becomes the "Home LS" (HLS, see <a href="#glossary"
title="Glossary">Section 6.1</a>) of that particular service. It is the
responsibility of the HLS to make summary data about the all of the pS
services it knows of available to the larger enterprise and to draw relevant
queries to itself. In order to make information available to the LS cloud,
the HLS will advertise this summary information to other LS instances to
propagate the appropriate information.</p>
+<p id="rfc.section.2.1.p.1">The first step of information flow is when a
service registers with an LS. The service may know the name of an LS via
static configuration (the most common case for legacy deployments), or other
forms of bootstrapping such as multicast may occur. A service registers a
"service metadata" record about itself and full metadata (i.e. containing all
information such as subject, eventType(s), and any parameters, see <a
href="#service-metadata" title="service metadata
example">Section 4.1</a>) about stored data it has knowledge of. Such a
record is called Lookup Information (see <a href="#lookup-info" title="Lookup
Information">Section 4.2</a>).</p>
+<p id="rfc.section.2.1.p.2">The idea is to move the metadata from a local
XML data store to a specialized LS with additional searching capabilities.
While a service instance may support limited searching, this is not necessary
as they should be focused on storing or gathering data and leave the lookup
functionality to the LS. Possible exceptions are rapidly changing Metadata
like the most recent timestamp and full details of data stored in long-term
archival MAs.</p>
+<p id="rfc.section.2.1.p.3">The LS that a service contacts to register
becomes the "Home LS" (HLS, see <a href="#glossary"
title="Glossary">Section 5.1</a>) of that particular service. It is the
responsibility of the HLS to make summary data about the all of the pS
services it knows of available to the larger enterprise and to draw relevant
queries to itself.</p>
+<p id="rfc.section.2.1.p.4">The construction of such a summary is important
to the overall success of this service; summaries must be general enough to
allow for easy creation and exchange but also must retain enough information
to provide a rich query interface able to locate the distributed information.
We start by making an observation that summarization is best based on scope,
simply put this means that we should attempt to summarize the "most" the
"further" away from the source that we get. This creates a smaller data set
that travels the furthest away while keeping the larger and more informative
data sets closer to the source. We present the strategies as such: </p>
+<ul>
+<li>Summarization for the "lower scope" (formerly known as "local
scope")</li>
+<li>Summarization for the "upper scope" (formerly known as "global
scope")</li>
+</ul>
+<p> We limit the discussion in this case to these two scopes, although
extension to "n" scopes is possible. As the number of of scopes increases
additional "aggregation" will be necessary to combine information thus
reducing the size of the data sets further.</p>
+<h3 id="rfc.section.2.1.1">
+<a href="#rfc.section.2.1.1">2.1.1</a> <a
id="lower_scope_summarization" href="#lower_scope_summarization">Lower Scope
Summarization</a>
+</h3>
+<p id="rfc.section.2.1.1.p.1">This first level of summarization, between HLS
instances internal to a domain, consists of simply dropping superfluous
information from the metadata descriptions provided by registered services.
For now we define this to be simply removing additional "parameter" elements
from the metadata. Special consideration must be given to the
"supportedEventType" parameter by simply converting this to actual eventType
elements. This will ensure interoperability with legacy services.</p>
+<p id="rfc.section.2.1.1.p.2">Future iterations may choose to drop
additional pieces of information deemed unnecessary or private such as parts
of topological descriptions. This sort of modification is encouraged as long
as the data remains "symmetrical" and conforms to the schematic definitions
for a given metadata description. It should be noted that such modifications
will affect the searching procedure and could isolate the source services.</p>
+<p id="rfc.section.2.1.1.p.3">The mechanics for performing this level of
summarization can use any number of technologies. Either Extensible
Stylesheet Language Transformation (XSLT) documents or the XQuery language
(see <a href="#glossary" title="Glossary">Section 5.1</a>) may be used
to prepare the initial data for exchange in this first level. Since the
exchange of this local information will occur frequently, a simple operation
that is scheduled or on demand should be employed by the individual
implementations to ensure the regular LS functions are not impeded.</p>
+<p id="rfc.section.2.1.1.p.4">In order to make information available to the
LS cloud, the HLS will advertise this summary information to other LS
instances to propagate the appropriate information. Information exchange will
be handled using a "taking turns" protocol such as token ring (see <a
href="#glossary" title="Glossary">Section 5.1</a>). The holder of the
token will then perform the information exchange to other known instances.</p>
<div id="hls-cloud">
</div>
<div id="rfc.figure.2">
@@ -441,141 +450,173 @@
|____/T\ Token
\_/

- </pre>
-<p>HLS instances communicating via token (A). The holder of the token (LS3)
will inform everyone of summary information (B).</p>
+ </pre>
+<p>HLS instances communicating via a token message (A). The holder of the
token (LS3) will inform everyone of it's summary information (B).</p>
<p class="figure">Figure 2</p>
-<p id="rfc.section.2.1.p.5">The most natural summarization is based on the
topology of the network (like in network routing). Thus, a given HLS will
perform topology-based summarization and will include this information as
well as eventType information to other LSs in its "lower scope" (formerly
known as "local scope"). Likewise, more aggressive summarization can take
place when the "lower scope" registers into the "upper scope" (formerly known
as "global scope"). This is analogous to the aggregation that occurs in IGPs
(lower scope) and EGPs (upper scope).</p>
-<p id="rfc.section.2.1.p.6">Summarization will be performed using
specialized summary algorithm. Topology information such as IP addresses will
be summarized using algorithms basing on radix tree (the IP addresses
summarization algorithm is described in section <a href="#IP-summary"
title="IP addesses summarization algorithm">Section 2.1.1</a>) .</p>
-<p id="rfc.section.2.1.p.7">In addition to that either Extensible Stylesheet
Language Transformation (XSLT) documents or the XQuery language may be used
for transformation eventType elements.</p>
-<p id="rfc.section.2.1.p.8">
-<br>
-<br>
-<br>START_NOTE (Jason 9/18/07):<br>
-<br> Question 3) Are additional 'aggressive' summaries still needed? At the
upper levels it seems to be less of 'summarization' and more of an aggregate
of summaries (unless we are dropping things out). <br>
-<br>END_NOTE:<br>
-<br>
-<br>
-</p>
-<p id="rfc.section.2.1.p.9">These documents will take into account the XML
elements that represent the network topology currently used in metadata
subjects as well as additional items such as eventTypes. The output of this
process becomes a "service summary" that represents a breadth of the original
input. See <a href="#LSControl-Summary" title="LS Summary
Message">Section 4.6</a> for a mock-up of the summary output. Additional
transformations, while aggressive, will strive to preserve as much
information as possible to remain useful during the search procedures.</p>
-<p id="rfc.section.2.1.p.10">In early discussions, we left the possibility
open for multiple types of summarization for different types of services and
data. This is still possibility. There are arguments to simplify the types of
summarizations that can occur. The first is that arbitrary summarizations
will yield arbitrary XML data, making discovery queries more difficult to
construct. Thus it seems to be sufficient to summarize over the Topology
elements in a regular fashion and simply include the eventTypes and drop the
Parameters. This will ease query construction.</p>
-<p id="rfc.section.2.1.p.11">We may target cases where various
summarizations are possible, but for now summarization on the basis of
topology seems sufficient.</p>
-<p id="rfc.section.2.1.p.12">A related question is that of policy. In our
discussions, we had the intuition that some domains would want to register
less information than others. One example is whether the actual IP addresses
of MPs capable of launching active measurements. These hosts, if compromised,
can pose significant denial of service threat.</p>
-<h3 id="rfc.section.2.1.1">
-<a href="#rfc.section.2.1.1">2.1.1</a> <a id="IP-summary"
href="#IP-summary">IP addesses summarization algorithm</a>
+<p id="rfc.section.2.1.1.p.6">Once exchanged, the details regarding storage
in the XML database backend (see <a href="#glossary"
title="Glossary">Section 5.1</a>) are also left to individual
implementations. It is understood that this information, in the possession of
non HLS instances, is provided as a convenience and should be treated in the
same way that directly registered information is (i.e. purged on expiration).
When requested, credit must also be attributed to the HLS as being
(non)authoritative for each piece of information.</p>
+<h3 id="rfc.section.2.1.2">
+<a href="#rfc.section.2.1.2">2.1.2</a> <a
id="upper_scope_summarization" href="#upper_scope_summarization">Upper Scope
Summarization</a>
</h3>
-<p id="rfc.section.2.1.1.p.1">The IP addresses summarization algorithm is
based on radix tree. The idea of the algorithm is...</p>
-<p id="rfc.section.2.1.1.p.2">
-<br>
-<br>
-<br>START_NOTE (Maciej 10/2/07):<br>
-<br> To be done... I'd expect detailed recipe here. <br>
-<br>END_NOTE:<br>
-<br>
-<br>
-</p>
+<p id="rfc.section.2.1.2.p.1">A designated member of each lower ring will be
required to interact with the upper level. The mechanics of how we learn who
is the designated leader is discussed in <a href="#tokens" title="Token
Passing">Section 2.2.2</a>. The leader of each group (and the designated
backup) will be responsible for examining each member's summary information
and building a summarization/aggregation that best describes the contents of
the ring.</p>
+<p id="rfc.section.2.1.2.p.2">The most natural summarization is based on the
topology of the network (like in network routing). Thus, topology-based
summarization will include this information as well as eventType information
from the other LSs. Summarization will be performed using specialized summary
algorithm. Topology information such as IP addresses will be summarized using
algorithms basing on radix tree (see <a href="#IP-summary" title="IP
addresses summarization algorithm">Section 2.1.2.1</a>).</p>
+<p id="rfc.section.2.1.2.p.3">Other information can be summarized in a less
programmatic fashion through the use of either Extensible Stylesheet Language
Transformation (XSLT) documents or the XQuery language as discussed in the
previous section. These mechanisms will take into account the XML elements
that represent the network topology currently used in metadata subjects as
well as additional items such as eventTypes.</p>
+<p id="rfc.section.2.1.2.p.4">The output of this process becomes a "service
summary" that represents a breadth of the original input. See <a
href="#LSControl-Summary-lower" title="LS Summary Message
(Lower)">Section 4.6</a> or <a href="#LSControl-Summary-upper" title="LS
Summary Message (Upper)">Section 4.7</a> for a mock-up of the summary
output. Additional transformations, while aggressive, will strive to preserve
as much information as possible to remain useful during the search
procedures.</p>
+<h4 id="rfc.section.2.1.2.1">
+<a href="#rfc.section.2.1.2.1">2.1.2.1</a> <a id="IP-summary"
href="#IP-summary">IP addresses summarization algorithm</a>
+</h4>
+<p id="rfc.section.2.1.2.1.p.1">To properly summarize a list of strings such
as IP addresses we must rely on the help of special algorithms and data
structures. The <a href="http://en.wikipedia.org/wiki/Radix_tree";>Radix
Tree</a> algorithm is useful in creating "associative arrays" where the keys
are expressed as strings. Radix Tree implementations have been used in
practice to index things such as text documents as well as more menial tasks
such as dictionaries. We are most interested in indexing IP addresses with
their natural hierarchy, where it is necessary to describe a large ranges of
values and have few exceptions.</p>
+<p id="rfc.section.2.1.2.1.p.2">A detailed explanation of the nuances of the
Radix Tree is well beyond the scope of this document, but a brief overview is
presented for completeness. The structure itself is best described as a
binary tree where nodes contain whole values and the edges are the primary
source of navigation. The edges of the tree can be based on a single
character or perhaps on even longer strings (one of the features that leads
to efficiency for small data sets). The algorithm should support the
following basic operations: </p>
+<ul>
+<li>Lookup: Indicate that something is or is not contained in the tree.</li>
+<li>Insert: Like in most inserts we attempt to place something into the
structure. We first start by doing a Lookup to see if it exists already; the
point where we stop is where we will insert the object. We are careful to
utilize the longest matching prefix of any other nearby edge to our
advantage. This last part is normally referred to as "splitting" and ensures
that each node has no more than two children.</li>
+<li>Delete: Delete an object from the tree. This operation will be
complicated by "collapsing" parents that have a single child and merging the
edges.</li>
+</ul>
+<p id="rfc.section.2.1.2.1.p.3">Once constructed, it is possible to consult
the structure in creating IP summaries as well as constructing information
regarding netmasks.</p>
<h2 id="rfc.section.2.2">
-<a href="#rfc.section.2.2">2.2</a> <a id="scope" href="#scope">Scope</a>
+<a href="#rfc.section.2.2">2.2</a> <a id="scope" href="#scope">scope</a>
</h2>
<p id="rfc.section.2.2.p.1">The next question is how to form the lower and
upper scopes. The simplest answer is that the lower scope be formed based on
the domain name of the participating systems. That would allow e.g.
internet2.edu, geant2.net, and pionier.gov.pl to potentially operate more
than one LS instance inside their own domains (for performance and
scalability.) As LS instances come online they will invoke bootstrapping
procedures to find and join a lower scoped group first.</p>
<p id="rfc.section.2.2.p.2">The scopes should be named based on URIs. This
will allow a domain-level scope to take the form <a
href="http://internet2.edu";>http://internet2.edu</a>, with subdomain scopes
named <a href="http://internet2.edu/foo";>http://internet2.edu/foo</a>, etc.
The top-level scope can be called <a
href="http://perfsonar.net";>http://perfsonar.net</a> with potential for
geographic divisions later if necessary for performance (such as <a
href="http://eu.perfsonar.net";>http://eu.perfsonar.net</a>).</p>
-<p id="rfc.section.2.2.p.3">With the generalities of what a scope is taken
care of, we now turn our attention to central algorithms of the dLS: </p>
+<p id="rfc.section.2.2.p.3">The major algorithms used to form and maintain
the ring structure of the dLS, no matter which scope we are talking about,
are as follows: </p>
<ul>
<li>Join Procedure</li>
<li>Token Passing</li>
<li>Summarization Notification</li>
</ul>
-<p id="rfc.section.2.2.p.4">The algorithms will be presented in the light of
the lower scoping, but will be used in the same manner for the upper scope as
well.</p>
+<p> Each of these procedures is paramount to keeping members of the
distributed "service" functioning correctly. The algorithms will be presented
in the frame of the lower scope, but will be used in the same manner for the
upper scope as well.</p>
<h3 id="rfc.section.2.2.1">
<a href="#rfc.section.2.2.1">2.2.1</a> <a id="join" href="#join">Join
Procedure</a>
</h3>
<p id="rfc.section.2.2.1.p.1">When an LS instance comes online it will have
some bootstrapping knowledge of potential peers (both inter and intra
domain). The inter-domain knowledge is used first to establish a connection
to an already in progress ring, or perhaps to start a ring that may not exist
yet.</p>
-<p id="rfc.section.2.2.1.p.2">An LS will continuously search it's LSRing
information (see <a href="#LSRing" title="LS Ring File
Structure">Section 4.3</a>) until a successful response to an LSControl
message (with a 'join' eventType, see <a href="#LSControl-Join" title="LS
Joining Message for Joining a Ring">Section 4.4</a>) is seen. The LS
will search though the successful response to this message and update its
LSRing with the returned information. This can mean updating the
'contentSize' and 'active' parameters as well as adding new LS instances.
These parameters are indicative of the LS's size (i.e. how many services are
registering with it) and 'live-ness' (i.e. were we successful in contacting
it recently).</p>
-<p id="rfc.section.2.2.1.p.3">After updating the LS will broadcast another
LSControl message (with a 'summary' eventType, see <a
href="#LSControl-Summary" title="LS Summary Message">Section 4.6</a>) to
all of the 'active' LS instances from it's LSRing. Again the responses will
be parsed to get any useful updated information. Each of the recipient LS
instances will do the same, including adding this new member to their own
lists (as many of them will not know of it's existence yet).</p>
+<p id="rfc.section.2.2.1.p.2">An LS will continuously search it's LSRing
information (see <a href="#LSRing" title="LS Ring File
Structure">Section 4.3</a>) until a successful response to an LSControl
message (with a "join" eventType, see <a href="#LSControl-Join" title="LS
Joining Message for Joining a Ring">Section 4.4</a>) is seen. The LS
will search though the successful response to this message and update its
LSRing with the returned information. This can mean updating the
"contentSize" and "active" parameters as well as adding new LS instances.
These parameters are indicative of the size of each LS (i.e. how many
services are registering with it) and "live-ness" (i.e. were we successful in
contacting it recently). The contacted LS will also update the local copy of
LSRing to add the new member to its "available" list.</p>
+<p id="rfc.section.2.2.1.p.3">After updating, the LS will broadcast another
LSControl message (with a "summary" eventType, see <a
href="#LSControl-Summary-lower" title="LS Summary Message
(Lower)">Section 4.6</a>, or of we are dealing with the upper level see
<a href="#LSControl-Summary-upper" title="LS Summary Message
(Upper)">Section 4.7</a>) to all of the "active" LS instances from it's
LSRing. Again the responses will be parsed to get any useful updated
information. Each of the recipient LS instances will do the same, including
adding this new member to their own lists (as many of them will not know of
it's existence yet).</p>
<p id="rfc.section.2.2.1.p.4">After this initial warm-up the LS will observe
the rules of token etiquette and remain silent until it is contacted with a
token, or it has not seen one in a very long time.</p>
<h4 id="rfc.section.2.2.1.1">
-<a href="#rfc.section.2.2.1.1">2.2.1.1</a> <a id="join_algorithm"
href="#join_algorithm">Join algorithm</a>
+<a href="#rfc.section.2.2.1.1">2.2.1.1</a> <a id="join_algorithm"
href="#join_algorithm">Join Algorithm</a>
</h4>
-<p id="rfc.section.2.2.1.1.p.1">This paragraph describes the Join procedure
for LS1. <p id="rfc.section.2.2.1.1.p.1">1. LS1 - "candidate" sends
LSControlRequest message with the http://perfsonar.net/services/LS/join
eventType to selected LS2 which is already a member of the ring</p> <p
id="rfc.section.2.2.1.1.p.2">2. LS2 receives join message from L1 and decides
whether to accept it or not. A security policy may occur here</p> <p
id="rfc.section.2.2.1.1.p.3">3. LS1 gets the answer - success joining (result
code: http://perfsonar.net/result/success/LS/join) or failure (error
code)</p> <p id="rfc.section.2.2.1.1.p.4">4. If succcess LS1 will be waiting
for token and LS2 updates its local peer list</p> <p
id="rfc.section.2.2.1.1.p.5">5. In the meantime LS2 receives Token. Then it
synchronizes peer lists - the local one and the one in token. LS2 sends local
summary to all peers from list (due to summary broadcasting algotirhm -
see...). LS2 sends Token to next peer from the l
ist (not necessarily to LS1).</p> <p id="rfc.section.2.2.1.1.p.6">6. When
there is LS1 turn it will get the Token. Then it synchronizes peer lists -
local and the one in token, sends its local summary to all peers from list
and sends Token to next peer</p>
+<p id="rfc.section.2.2.1.1.p.1">
</p>
+<div id="join-example">
+</div>
+<div id="rfc.figure.3">
+</div>
+<p>Illustration of LS Join Algorithm</p>
+<pre>
+ (5,6)
+ ______________________________________________________
+ | |
+ | |
+ __V__ _____ _V___
+| | | | (1) | |
+| LS3 | <----------------- | LS2 | <----------------> | LS1 |
+|_____| |_____| (2,3) |_____|
+ | ^ ^ ^ ^
+ | | | | |
+ | _____ | | | |
+ | | | | |_______________________| |
+ |-------> | LS4 | ---------| (5,6) |
+ |_____| <____________________________________|
+ (5,6)
+
+
+ </pre>
+<p class="figure">Figure 3</p>
+<p> </p>
+<dl class="empty">
+<dd>1. LS1 - "candidate" sends LSControlRequest message with the
http://perfsonar.net/services/LS/join eventType to selected LS2 which is
already a member of the ring</dd>
+<dd>2. LS2 receives join message from L1 and decides whether to accept it or
not. A security policy may occur here</dd>
+<dd>3. LS1 gets the answer - success joining (result code:
http://perfsonar.net/result/success/LS/join) or failure (error code)</dd>
+<dd>4. After receiving the response from LS2, LS1 will parse the results to
discover all members of the ring.</dd>
+<dd>5. LS1 will "broadcast" its summary info (lower or upper) to all of the
LS instances it learns of. This is of course "out of turn" as LS1 doesn't
have the token yet but this reasoning is twofold: <dl class="empty">
+<dd>This expedites all ring members knowing the new LS, the ring will grow
instantly by inserting the new member into the correct position.</dd>
+<dd>This allows the information it provides to the leaders to become
available for the next upper ring summary as soon as possible. Worst case
scenarios would place this knowledge cycles away from being recognized.</dd>
+</dl>
+</dd>
+<dd>6. All members of the ring will process the summaries, save the
necessary information, and recognize the new peer. Responses will be prepared
for LS1.</dd>
+</dl>
<h3 id="rfc.section.2.2.2">
<a href="#rfc.section.2.2.2">2.2.2</a> <a id="tokens"
href="#tokens">Token Passing</a>
</h3>
-<p id="rfc.section.2.2.2.p.1">The 'token' is a message (see <a
href="#LSControl-Token" title="LS Token Message">Section 4.5</a>) meant
to be passed around an LSRing to the various members in some order. We will
pass from smallest 'contentSize' to largest (with appropriate wrap around),
and at any given time an LS instance will know where the next token message
should go.</p>
-<p id="rfc.section.2.2.2.p.2">
-<br>
-<br>
-<br>START_NOTE (Maciej 10/3/07):<br>
-<br> Question: I am not convinced 'contentSize' should be the only
criterion. When new LS joins the ring it may have empty database, but in some
time it'll get a lot of metadata. The mechanism of leader election bases on
that, so it's quite important. If such LS will 'update' its 'contentSize'
value not all other LS-es may know about it immediately (token passing cycle)
and they may not have the same knowledge about the leader. I'd prefer more
deterministic way of leader election. <br>
-<br>END_NOTE:<br>
-<br>
-<br>
-</p>
-<p id="rfc.section.2.2.2.p.3">The token can be viewed as 'permission to
talk' and permits the holder to send it's summary information to all
available LS instances (see <a href="#LSControl-Summary" title="LS Summary
Message">Section 4.6</a>). The responses will be parsed to get any
useful updated information.</p>
-<p id="rfc.section.2.2.2.p.4">The holder of the token, after completing
summarization, will wait some pre-determined amount of time before sending
the token to the next LS instance. LS instances should be sensitive (although
not overly sensitive) to the progression of the token through the ring. A
token should expect to arrive in some interval equal to the size of the ring
times the waiting interval, with tolerance above and below this value.</p>
-<p id="rfc.section.2.2.2.p.5">The timeout mechanism(s) will need to be
further specified. It can be computed as a function of the number of nodes in
the ring. This is the Target Token Rotation Time (TTRT), for details see
section: <a href="#TTRT" title="TTRT computing
algorithm">Section 2.2.2.2</a>TTRT computing. There may be a future
point at which we need to think about ring splitting, but we believe that
this can be managed by further scope levels.</p>
-<p id="rfc.section.2.2.2.p.6">If the token has been 'dropped' along its path
the next LS in line will detect this and re-send it to not break the
communication chain. If for some reason a second token appears too quickly
after the previous token, any LS instance should see this dispose of the
duplicate message.</p>
-<p id="rfc.section.2.2.2.p.7">
-<br>
-<br>
-<br>START_NOTE (Maciej 10/3/07):<br>
-<br> Question: I'd like to know a bit more when new token will be created
and how to prevent existing two or more tokens (removing tokens?) <br>
-<br>END_NOTE:<br>
-<br>
-<br>
-</p>
+<p id="rfc.section.2.2.2.p.1">The "token" is a message (see <a
href="#LSControl-Token" title="LS Token Message">Section 4.5</a>) meant
to be passed around an LSRing to the various members in some order. There are
various criterion that can be used in deciding how to order the ring so that
everyone can predict where the token is, when they might expect to get it,
and whom they should get it from/ pass it to next. It is important that we
choose a sound method that is simple to calculate, and should use as much
"knowledge" of the ring as possible without burdening the LS instances too
much with complex calculations.</p>
+<p id="rfc.section.2.2.2.p.2">A common method used in P2P (see <a
href="#glossary" title="Glossary">Section 5.1</a>) systems such as
Gnutella (see <a href="#glossary" title="Glossary">Section 5.1</a>) when
forming "ultrapeers" is to consider the size of the data that a node is
serving. The principle, as described <a
href="http://rakjar.de/gnufu/index.php/GnuFU_en#Network_model:_Change_who_calls_whom:_Ultrapeers_and_Leafs";>here</a>,
alludes to the fact that nodes with less content to look after (i.e. less
services, or services with a smaller amount of data) can spend more time and
effort helping the enterprise as a whole by taking on additional roles (such
as serving as leaders). As such we will record the number of metadata
elements that register with each LS and share this with our friends in the
form of the "contentSize" parameter.</p>
+<p id="rfc.section.2.2.2.p.3">Token passing is directly related to the
concept of leader election (see <a href="#Leader_Election" title="Leader
election">Section 2.2.4</a>), so more explanation of this approach will
follow. For now we are justified in saying that the "contentSize" forms a
good criterion for "ordering" the members of the ring. With all members of
the ring aware of everyone's data size, we can easily know who we should pass
the token to, and receive it from at any point in time.</p>
+<p id="rfc.section.2.2.2.p.4">The token can be viewed as "permission to
talk" and permits the holder to send it's summary information to all
available LS instances (see <a href="#LSControl-Summary-lower" title="LS
Summary Message (Lower)">Section 4.6</a> and <a
href="#LSControl-Summary-upper" title="LS Summary Message
(Upper)">Section 4.7</a>). The responses will be parsed to get any
useful updated information.</p>
+<p id="rfc.section.2.2.2.p.5">The holder of the token, after completing
summarization, will wait some pre-determined amount of time before sending
the token to the next LS instance. In general the LS instances should not be
overly sensitive to the progression of the token. If each LS instance is
monitoring the progress, and for some reason we have lost the token it may
start a flurry of retransmits and drops that will take cycles to calm down
again.</p>
+<p id="rfc.section.2.2.2.p.6">Thus we leave the decisions regarding tokens
up to a single node, namely the designated leader of a ring. We build
functionality into leader nodes to be the only "maker" and "executioner" of
tokens. Extra tokens are dropped/created only by a single node in the ring.
All strange thrashing behavior is avoided and if something bad happens it is
eliminated in a single passing. The leader node will have knowledge of the
size of the ring (even if the Ring has grown our Join algorithm will inform
all interested parties instantly) and the token "wait" period (should be a
standard value) thus calculating the expected time is not an issue.</p>
<h4 id="rfc.section.2.2.2.1">
<a href="#rfc.section.2.2.2.1">2.2.2.1</a> <a
id="token_passing_algorithm" href="#token_passing_algorithm">Token passing
algorithm</a>
</h4>
-<p id="rfc.section.2.2.2.1.p.1">When receives the token (LSControlRequest
message with the http://perfsonar.net/services/LS/token/... eventType.</p>
-<p id="rfc.section.2.2.2.1.p.2">1.Update local peer list (from token)</p>
-<p id="rfc.section.2.2.2.1.p.3">2.Update token peer list (add newly
registered LS-es)</p>
-<p id="rfc.section.2.2.2.1.p.4">3.Send summary to all peers in the lease
(excluding itself)</p>
-<p id="rfc.section.2.2.2.1.p.5">4.Wait</p>
-<p id="rfc.section.2.2.2.1.p.6">6.Send token to next peer from the list (if
it fails, try next one)</p>
-<h4 id="rfc.section.2.2.2.2">
-<a href="#rfc.section.2.2.2.2">2.2.2.2</a> <a id="TTRT"
href="#TTRT">TTRT computing algorithm</a>
-</h4>
-<p id="rfc.section.2.2.2.2.p.1">TBD.</p>
+<p id="rfc.section.2.2.2.1.p.1">
+</p>
+<div id="token-example">
+</div>
+<div id="rfc.figure.4">
+</div>
+<p>Illustration of LS Token Passing</p>
+<pre>
+
+ _____ _____
+| | | |
+| LS1 | <----------------- | LS2 |
+|_____| |_____|
+ | ^
+ | |
+ | _____ |
+ | | | |
+ |-------> | LS3 | ---------|
+ |_____|
+
+
+ </pre>
+<p class="figure">Figure 4</p>
+<p> </p>
+<dl class="empty">
+<dd>0. When any LS receives the token (LSControlRequest message with the
http://perfsonar.net/services/LS/token/... eventType, we will do the
following:</dd>
+<dd>1.Update local peer list (from token)</dd>
+<dd>2.Send summary to all peers in the lease (excluding itself)</dd>
+<dd>3.Wait for some amount of time</dd>
+<dd>4.Send token to next peer from the list (if it fails, try next one)</dd>
+</dl>
<h3 id="rfc.section.2.2.3">
-<a href="#rfc.section.2.2.3">2.2.3</a> <a id="summary-blast"
href="#summary-blast">Summarization Notification</a>
+<a href="#rfc.section.2.2.3">2.2.3</a> <a id="summary-blast"
href="#summary-blast">summarization Notification</a>
</h3>
<p id="rfc.section.2.2.3.p.1">As discussed in the prior two sections there
are two acceptable instances to send your summary to the LSRing: </p>
<ol>
<li>When first joining</li>
<li>When holding the token</li>
</ol>
-<p id="rfc.section.2.2.3.p.2">In the first case we are explicitly entering
ourselves into the ring when we get our first message from a peer. This
ensures we show up in the token rotation the next cycle. The second case is
the routine exchange started when a token arrives from a peer.</p>
+<p id="rfc.section.2.2.3.p.2">In the first case we are explicitly entering
ourselves into the ring when we get our first message from a peer. This
ensures we show up in the token rotation instantly. The second case is the
routine exchange started when a token arrives from a peer.</p>
<p id="rfc.section.2.2.3.p.3">
-<a href="#LSControl-Summary" title="LS Summary Message">Section 4.6</a>
contains examples of the message format for this exchange. It is left up to
the implementation when the summarization occurs (i.e. at message send time,
or also as a periodic event).</p>
-<p id="rfc.section.2.2.3.p.4">
+<a href="#LSControl-Summary-lower" title="LS Summary Message
(Lower)">Section 4.6</a> and <a href="#LSControl-Summary-upper"
title="LS Summary Message (Upper)">Section 4.7</a>contains examples of
the message format for this exchange. It is left up to the implementation
when the summarization occurs (i.e. at message send time, or also as a
periodic event).</p>
+<h3 id="rfc.section.2.2.4">
+<a href="#rfc.section.2.2.4">2.2.4</a> <a id="Leader_Election"
href="#Leader_Election">Leader election</a>
+</h3>
+<p id="rfc.section.2.2.4.p.1">The most important role of the lower ring
nodes is electing a leader to serve in the upper levels. This logical ring
should consist of one representative from each of the lower scopes. This
representative will be selected based on the "contentSize" parameter, which
as we have discussed previously is a count of the number of metadata elements
the LS is responsible for. We choose this parameter primarily because it
imposes a very simple ordering on the nodes, and allows us to choose the
"least busy" node for performing more important work.</p>
+<p id="rfc.section.2.2.4.p.2">The theory behind this choice of leader is
that unladen LS instances will not be as loaded processing requests and
responses from clients and other services, thus the choice to name them as
leaders is natural. An added feature of this criteria is that it becomes very
simple to designate a leader LS for a domain; simply deploy an LS instance
that does not accept registrations. This service will only serve in the role
of liaison to the upper level.</p>
+<p id="rfc.section.2.2.4.p.3">All LS instances will have a complete view at
any given time (and updated over time) of the values of the "contentSize"
parameter for all peer LS instances in an LSRing. This ensures that the
"Leader" and "Vice-Leader" are always known. Explicit election is therefore
not required, and succession can pass between the two executives quickly.</p>
+<p id="rfc.section.2.2.4.p.4">The Leader and Vice-Leader LS instances should
exchange messages periodically to ensure that in the event of a failure the
lower level will still have a link to the upper level (see <a
href="#LSControl-Leader" title="LS Leader Message">Section 4.8</a>). A
Vice-Leader will be monitoring the time between successive communications
from the Leader to be sure it has not failed. In the event that it has, the
"Join" procedure will start to the upper level to keep the hierarchy
complete.</p>
+<p id="rfc.section.2.2.4.p.5">
<br>
<br>
<br>START_NOTE (Maciej 10/3/07):<br>
-<br> making summarization at the message send time may increase token
holding time and cause time-out in next peer in the list (and re-sending
token by it). <br>
+<br> Question: I am not convinced "contentSize" should be the only
criterion. When new LS joins the ring it may have empty database, but in some
time it'll get a lot of metadata. The mechanism of leader election bases on
that, so its quite important. If such LS will "update" its "contentSize"
value not all other LS-es may know about it immediately (token passing cycle)
and they may not have the same knowledge about the leader. I"d prefer more
deterministic way of leader election. <br>
<br>END_NOTE:<br>
<br>
<br>
</p>
-<h3 id="rfc.section.2.2.4">
-<a href="#rfc.section.2.2.4">2.2.4</a> <a id="Leader_Election"
href="#Leader_Election">Leader election</a>
-</h3>
-<p id="rfc.section.2.2.4.p.1">Building on the previous algorithms, we turn
our attention to the upper scope. This logical ring should consist of one
representative from each of the lower scopes. This representative will be
selected based on the 'contentSize' parameter, which as we have discussed
previously is a count of the number of metadata elements the LS is
responsible for.</p>
-<p id="rfc.section.2.2.4.p.2">
+<p id="rfc.section.2.2.4.p.6">
<br>
<br>
-<br>START_NOTE (Maciej 10/3/07):<br>
-<br> Basing on contentSize may be not reliable. See one of previous
comments. <br>
+<br>START_NOTE (Jason 10/4/07):<br>
+<br> I have added some more reasoning behind this, as well as a pointer to
some literature from the Gnutella folks as to why this is a good method. I am
not in favor of something complex when calculating a leader; we must choose
something that everyone can figure out [instantly] so that the ring continues
to function even during times when bad things are happening. Everyone will be
able to see (at any given time) how much information someone has, and the
notion that an unburdened system should be given more work (as opposed to a
system that may be very busy with local queries yet chosen anyway based on
separate criteria) is very appealing. <br>
<br>END_NOTE:<br>
<br>
<br>
</p>
-<p id="rfc.section.2.2.4.p.3">The theory behind this choice of leader is
that unladen LS instances will not be as loaded processing requests and
responses from clients and other services, thus the choice to name them as
leaders is natural. This also allows a domain to impose leadership on a
specific LS by having it not accept registrations for example, and only
serving in the leader role.</p>
-<p id="rfc.section.2.2.4.p.4">All LS instances will have a complete view at
any given time (and updated over time) of the values of the 'contentSize'
parameter for all peer LS instances in an LSRing. This ensures that the
'Leader' and 'Vice-Leader' are always known. Explicit election is therefore
not required, and succession can pass between the two executives quickly.</p>
-<p id="rfc.section.2.2.4.p.5">The Leader and Vice-Leader LS instances should
exchange messages periodically to ensure that in the event of a failure the
lower level will still have a link to the upper level (see <a
href="#LSControl-Leader" title="LS Leader Message">Section 4.7</a>). A
Vice-Leader will be monitoring the time between successive communications
from the Leader to be sure it has not failed. In the event that it has, the
'Join' procedure will start to the upper level to keep the hierarchy
complete.</p>
<h3 id="rfc.section.2.2.5">
-<a href="#rfc.section.2.2.5">2.2.5</a> <a id="scopes"
href="#scopes">Scopes</a>
+<a href="#rfc.section.2.2.5">2.2.5</a> <a id="scopes"
href="#scopes">scopes</a>
</h3>
-<p id="rfc.section.2.2.5.p.1">Scopes are named based on URIs. The top-level
domain provides a natural basis for the formation of these URIs. These URIs
may be constructed to allow internal differentiation. In the future, we may
need a mechanism to provide another level of hierarchy above the domain level
and below the root, but that is left for future work. Note: I would like to
see this be something like: <a
href="http://lsls.perfsonar.net/master/internet2.edu/";>http://lsls.perfsonar.net/master/internet2.edu/</a>.
Actual syntax doesn't matter that much but I would like the following
components: </p>
+<p id="rfc.section.2.2.5.p.1">Scopes are named based on URIs. The top-level
domain provides a natural basis for the formation of these URIs. These URIs
may be constructed to allow internal differentiation. In the future, we may
need a mechanism to provide another level of hierarchy above the domain level
and below the root, but that is left for future work. Note: I would like to
see this be something like: <a
href="http://lsls.perfsonar.net/master/internet2.edu/";>http://lsls.perfsonar.net/master/internet2.edu/</a>.
Actual syntax doesn"t matter that much but I would like the following
components: </p>
<ol>
<li>well-known hostname to get the current root.hints from (lsls)</li>
<li>a place holder for where we can break the scope between organization and
upper levels (master)</li>
@@ -585,21 +626,12 @@
<h2 id="rfc.section.2.3">
<a href="#rfc.section.2.3">2.3</a> <a id="search"
href="#search">Search</a>
</h2>
-<p id="rfc.section.2.3.p.1">
-<br>
-<br>
-<br>START_NOTE (Jason 9/18/07):<br>
-<br> Question 4) I think we should go with one algorithm here, and
'improvements' to the protocol in the future can give us two. Can we just
pick iterative and only explain that? <br>
-<br>END_NOTE:<br>
-<br>
-<br>
-</p>
-<p id="rfc.section.2.3.p.2">The search operation is obviously critical to
the Lookup Service's function. It is envisioned that searching could take one
of two major forms, iterative and recursive, analogous to those used in DNS.
This design will focus exclusively on iterative initially as the only method
in the first versions of the dLS. The key act when searching is to find what
eventTypes exist for a particular topology element or set of topology
elements.</p>
-<p id="rfc.section.2.3.p.3">As outlined above, the full data that services
register to an LS is not expected to leave the scope of that LS. The
information is summarized before wider distribution. Therefore, a client
needs to find an LS in the scope of the HLS to make queries about the
complete metadata. Specifically, a client wishing to locate information might
specify a topology element in a query to locate the LS instance (or
instances) that contain the relevant details. This separation of full data
and summary data means the overall act of searching is broken down into two
distinct phases -- Discovery and Metadata Query.</p>
+<p id="rfc.section.2.3.p.1">The search operation is obviously critical to
the Lookup Service's function. It is envisioned that searching could take one
of two major forms, iterative and recursive, analogous to those used in DNS.
This design will focus exclusively on iterative initially as the only method
in the first versions of the dLS. The key act when searching is to find what
eventTypes exist for a particular topology element or set of topology
elements.</p>
+<p id="rfc.section.2.3.p.2">As outlined above, the full data that services
register to an LS is not expected to leave the scope of that LS. The
information is summarized before wider distribution. Therefore, a client
needs to find an LS in the scope of the HLS to make queries about the
complete metadata. Specifically, a client wishing to locate information might
specify a topology element in a query to locate the LS instance (or
instances) that contain the relevant details. This separation of full data
and summary data means the overall act of searching is broken down into two
distinct phases -- Discovery and Metadata Query.</p>
<h3 id="rfc.section.2.3.1">
<a href="#rfc.section.2.3.1">2.3.1</a> <a id="discovery"
href="#discovery">Discovery Phase</a>
</h3>
-<p id="rfc.section.2.3.1.p.1">The Discovery Phase is used to locate the set
of Authoritative LS (or LSes) for a given Subject/eventType tuple. This
requires a query to be constructed over the Discovery information set (which
is not described yet, but which must consist of the 3-tuple of Subject
Summary, eventType and Authoritative LS.) Either a specific API call and a
pre-prepared query, or some automatic mechanism, must map the desired query
into a query of the Discovery infoset (see <a href="#LSControl-Discovery"
title="LS Discovery Message">Section 4.8</a>).</p>
+<p id="rfc.section.2.3.1.p.1">The Discovery Phase is used to locate the set
of Authoritative LS (or LSes) for a given Subject/eventType tuple. This
requires a query to be constructed over the Discovery information set (which
is not described yet, but which must consist of the 3-tuple of Subject
Summary, eventType and Authoritative LS.) Either a specific API call and a
pre-prepared query, or some automatic mechanism, must map the desired query
into a query of the Discovery infoset (see <a href="#LSControl-Discovery"
title="LS Discovery Message">Section 4.9</a>).</p>
<h4 id="rfc.section.2.3.1.1">
<a href="#rfc.section.2.3.1.1">2.3.1.1</a> <a id="discovery-alg"
href="#discovery-alg">Discovery Algorithm</a>
</h4>
@@ -609,7 +641,7 @@
<li>The client should start by making a discovery query (possibly using an
API call) to locate an LS that contains the data it is interested in. The
results of this query will be: <ol style="list-style-type: lower-alpha">
<li>Failure: Returned if there is no LS at a higher scope than the current
one, and nothing was found in the summary infoset that matches the query.</li>
<li>Referral: This is returned when there is no match other than a "global
wildcard" <ol style="list-style-type: lower-alpha">
-<li>If this LS is not participating in the highest (upper) scope, then it
returns the leader of its current scope (or a direct referral to an instance
of the next-higher scope.) This is effectively a wildcard match saying "I
don't know the answer, but I know who might." This is how the Metadata
registered to an LS in another scope (domain) is found.</li>
+<li>If this LS is not participating in the highest (upper) scope, then it
returns the leader of its current scope (or a direct referral to an instance
of the next-higher scope.) This is effectively a wildcard match saying "I
don"t know the answer, but I know who might." This is how the Metadata
registered to an LS in another scope (domain) is found.</li>
</ol>
</li>
<li>Success: We define success to mean at least one matching LS has been
returned. The LS must return the following: <ol style="list-style-type:
lower-alpha">
@@ -637,103 +669,74 @@
<p id="rfc.section.3.p.4">The above discovery algorithm is used to find an
LS within a given scope. Therefore, the only piece of information an LS
should need to be pre-configured with is the scope it belongs to. And as
stated above, that can be assumed to be "global:organization-dns-name". Note:
Need to define the specific syntax above.</p>
<hr class="noprint">
<h1 id="rfc.section.4" class="np">
-<a href="#rfc.section.4">4.</a> <a id="structures-and-messages"
href="#structures-and-messages">Structures and Messages</a>
+<a href="#rfc.section.4">4.</a> <a id="structures-and-messages"
href="#structures-and-messages">structures and Messages</a>
</h1>
<h2 id="rfc.section.4.1">
-<a href="#rfc.section.4.1">4.1</a> <a id="service-metadata"
href="#service-metadata">Service metadata example</a>
+<a href="#rfc.section.4.1">4.1</a> <a id="service-metadata"
href="#service-metadata">service metadata example</a>
</h2>
<p id="rfc.section.4.1.p.1">Example of metadata describing information
collected and stored in Measurement Archive service</p>
<p id="rfc.section.4.1.p.2">
<pre>

-<nmwg:metadata id="metadata.17155427"
- xmlns:nmwg="http://ggf.org/ns/nmwg/base/2.0/">
- <netutil:subject id="subject.17062918"
-
xmlns:netutil="http://ggf.org/ns/nmwg/characteristic/utilization/2.0/">
- <nmwgt:interface
xmlns:nmwgt="http://ggf.org/ns/nmwg/topology/2.0/">
- <nmwgt:hostName>Gallup's.fr</nmwgt:hostName>
- <nmwgt:ifName>ge-1/1/0</nmwgt:ifName>
- <nmwgt:ifDescription>Gallup's description:
ge-1/1/0</nmwgt:ifDescription>
- <nmwgt:ifAddress
type="ipv4">229.148.7.224</nmwgt:ifAddress>
- <nmwgt:direction>in</nmwgt:direction>
- <nmwgt:capacity>250000000</nmwgt:capacity>
- </nmwgt:interface>
- </netutil:subject>
-
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
-</nmwg:metadata>
-
-<nmwg:metadata id="metadata.171558"
- xmlns:nmwg="http://ggf.org/ns/nmwg/base/2.0/">
- <netutil:subject id="subject.17062919"
-
xmlns:netutil="http://ggf.org/ns/nmwg/characteristic/utilization/2.0/">
- <nmwgt:interface
xmlns:nmwgt="http://ggf.org/ns/nmwg/topology/2.0/">
- <nmwgt:hostName>Gallup's.fr</nmwgt:hostName>
- <nmwgt:ifName>ge-1/1/0</nmwgt:ifName>
- <nmwgt:ifDescription>Gallup's description:
ge-1/1/0</nmwgt:ifDescription>
- <nmwgt:ifAddress
type="ipv4">229.148.7.224</nmwgt:ifAddress>
- <nmwgt:direction>out</nmwgt:direction>
- <nmwgt:capacity>250000000</nmwgt:capacity>
- </nmwgt:interface>
- </netutil:subject>
-
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
-</nmwg:metadata>
+ <nmwg:metadata xmlns:nmwg="http://ggf.org/ns/nmwg/base/2.0/";
id="m_ale-netutil-1">
+ <netutil:subject
xmlns:netutil="http://ggf.org/ns/nmwg/characteristic/utilization/2.0/";
id="s_ale-netutil-1">
+ <nmwgt:interface
xmlns:nmwgt="http://ggf.org/ns/nmwg/topology/2.0/">
+ <nmwgt:ifAddress
type="ipv4">128.4.133.165</nmwgt:ifAddress>
+ <nmwgt:hostName>ale.pc.cis.udel.edu</nmwgt:hostName>
+ <nmwgt:ifName>eth0</nmwgt:ifName>
+ <nmwgt:ifIndex>2</nmwgt:ifIndex>
+ <nmwgt:direction>in</nmwgt:direction>
+ <nmwgt:capacity>1000000000</nmwgt:capacity>
+ </nmwgt:interface>
+ </netutil:subject>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
+ <nmwg:parameters id="p_ale-netutil-1">
+ <nmwg:parameter
name="supportedEventType">http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:parameter>
+ <nmwg:parameter
name="supportedEventType">http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>

</pre>
</p>
<h2 id="rfc.section.4.2">
<a href="#rfc.section.4.2">4.2</a> <a id="lookup-info"
href="#lookup-info">Lookup Information</a>
</h2>
-<p id="rfc.section.4.2.p.1">Example Lookup Information of Measurement
Archive. Metadata block contains basic service information and data elements
containing the metadata from the MA.</p>
+<p id="rfc.section.4.2.p.1">Example Lookup Information of Measurement
Archive. The metadata block contains basic service information and data
elements containing the metadata from the MA.</p>
<p id="rfc.section.4.2.p.2">
<pre>

-<nmwg:metadata
id="http://shower.fr:8080/axis/services/MeasurementArchiveService">
+<nmwg:metadata
id="http://newcastle.pc.cis.udel.edu:6767/perfSONAR_PS/services/snmpMA">
<perfsonar:subject id="subject.15977808">
- <psservice:service id="229.148.249.60.16283379">
- <psservice:serviceName>Java RRD MA</psservice:serviceName>
-
<psservice:accessPoint>http://shower.fr:8080/axis/services/MeasurementArchiveService</psservice:accessPoint>
+ <psservice:service id="service.16283379">
+ <psservice:serviceName>UDel perfSONAR-PS SNMP
MA</psservice:serviceName>
+
<psservice:accessPoint>http://newcastle.pc.cis.udel.edu:6767/perfSONAR_PS/services/snmpMA</psservice:accessPoint>
<psservice:serviceType>MA</psservice:serviceType>
- <psservice:serviceDescription>Java RRD MA, perfSONAR project,
229.148.249.60</psservice:serviceDescription>
+ <psservice:serviceDescription>perfSPNAR-PS SNMP MA deployed at
UDel, Newark DE, USA</psservice:serviceDescription>
</psservice:service>
</perfsonar:subject>
</nmwg:metadata>

-<nmwg:data
id="http://shower.fr:8080/axis/services/MeasurementArchiveService/1177595435/0";

-
metadataIdRef="http://shower.fr:8080/axis/services/MeasurementArchiveService">
- <nmwg:metadata id="metadata.17155427"
- xmlns:nmwg="http://ggf.org/ns/nmwg/base/2.0/">
- <netutil:subject id="subject.17062918"
-
xmlns:netutil="http://ggf.org/ns/nmwg/characteristic/utilization/2.0/">
+<nmwg:data
id="http://newcastle.pc.cis.udel.edu:6666/perfSONAR_PS/services/LS/1177595435/1";

+
metadataIdRef="http://newcastle.pc.cis.udel.edu:6767/perfSONAR_PS/services/snmpMA">
+ <nmwg:metadata xmlns:nmwg="http://ggf.org/ns/nmwg/base/2.0/";
id="m_ale-netutil-1">
+ <netutil:subject
xmlns:netutil="http://ggf.org/ns/nmwg/characteristic/utilization/2.0/";
id="s_ale-netutil-1">
<nmwgt:interface
xmlns:nmwgt="http://ggf.org/ns/nmwg/topology/2.0/">
- <nmwgt:hostName>Gallup's.fr</nmwgt:hostName>
- <nmwgt:ifName>ge-1/1/0</nmwgt:ifName>
- <nmwgt:ifDescription>Gallup's description:
ge-1/1/0</nmwgt:ifDescription>
- <nmwgt:ifAddress
type="ipv4">229.148.7.224</nmwgt:ifAddress>
+ <nmwgt:ifAddress
type="ipv4">128.4.133.165</nmwgt:ifAddress>
+ <nmwgt:hostName>ale.pc.cis.udel.edu</nmwgt:hostName>
+ <nmwgt:ifName>eth0</nmwgt:ifName>
+ <nmwgt:ifIndex>2</nmwgt:ifIndex>
<nmwgt:direction>in</nmwgt:direction>
- <nmwgt:capacity>250000000</nmwgt:capacity>
+ <nmwgt:capacity>1000000000</nmwgt:capacity>
</nmwgt:interface>
</netutil:subject>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:eventType>

<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
+ <nmwg:parameters id="p_ale-netutil-1">
+ <nmwg:parameter
name="supportedEventType">http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:parameter>
+ <nmwg:parameter
name="supportedEventType">http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:parameter>
+ </nmwg:parameters>
</nmwg:metadata>
-</nmwg:data>
-
-<nmwg:data
id="http://shower.fr:8080/axis/services/MeasurementArchiveService/1177595435/1";

-
metadataIdRef="http://shower.fr:8080/axis/services/MeasurementArchiveService">
- <nmwg:metadata id="metadata.171558"
- xmlns:nmwg="http://ggf.org/ns/nmwg/base/2.0/">
- <netutil:subject id="subject.17062919"
-
xmlns:netutil="http://ggf.org/ns/nmwg/characteristic/utilization/2.0/">
- <nmwgt:interface
xmlns:nmwgt="http://ggf.org/ns/nmwg/topology/2.0/">
- <nmwgt:hostName>Gallup's.fr</nmwgt:hostName>
- <nmwgt:ifName>ge-1/1/0</nmwgt:ifName>
- <nmwgt:ifDescription>Gallup's description:
ge-1/1/0</nmwgt:ifDescription>
- <nmwgt:ifAddress
type="ipv4">229.148.7.224</nmwgt:ifAddress>
- <nmwgt:direction>out</nmwgt:direction>
- <nmwgt:capacity>250000000</nmwgt:capacity>
- </nmwgt:interface>
- </netutil:subject>
-
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
- </nmwg:metadata>
</nmwg:data>

@@ -742,24 +745,11 @@
<h2 id="rfc.section.4.3">
<a href="#rfc.section.4.3">4.3</a> <a id="LSRing" href="#LSRing">LS
Ring File Structure</a>
</h2>
-<p id="rfc.section.4.3.p.1">Structure of the 'lower' and 'upper' LSRing
files.</p>
-<p id="rfc.section.4.3.p.2">
+<p id="rfc.section.4.3.p.1">The LSRing file represents the "state" of the LS
cloud at either level of hierarchy (we avoid using the terms "global" and
"local" here since the hierarchy may be much larger). This file must start
with some static values, and will be added to/deleted from as time goes on.
As such implementations must ensure that this file is under database control
of some sort.</p>
+<p id="rfc.section.4.3.p.2">Each metadata description contains the usual
service level info, as well as a "voting" parameter (labeled as
"contentSize") used to decide who the leader is, and a flag indicating if the
current service thinks the remote service is active. Both of these should be
updated frequently as reality changes.</p>
+<p id="rfc.section.4.3.p.3">
<pre>

-
-
<nmwg:store type="LSRing-lower">


@@ -788,7 +778,6 @@

<psservice:serviceDescription>...</psservice:serviceDescription>
</psservice:service>
</perfsonar:subject>
-
<nmwg:eventType>http://perfsonar.net/services/LS/join/success</nmwg:eventType>
<nmwg:parameters>
<nmwg:parameter name="active">1</nmwg:parameter>
<nmwg:parameter name="contentSize">50</nmwg:parameter>
@@ -831,8 +820,6 @@

-
-
<nmwg:store type="LSRing-upper">


@@ -868,114 +855,505 @@
</nmwg:metadata>

</nmwg:store>
-

</pre>
</p>
<h2 id="rfc.section.4.4">
<a href="#rfc.section.4.4">4.4</a> <a id="LSControl-Join"
href="#LSControl-Join">LS Joining Message for Joining a Ring</a>
</h2>
-<p id="rfc.section.4.4.p.1">Structure of the LSControl messages focused on
joining a ring.</p>
-<p id="rfc.section.4.4.p.2">
+<p id="rfc.section.4.4.p.1">This message exchange represents when a "new" LS
instance comes online. The LS will send these messages to its "list" of known
LS instances until it gets a hit. The message consists of metadata/data
pair(s) that contain service information and a parameter indicating "size" of
the data set the LS manages. This will be used for leader voting purposes
later.</p>
+<p id="rfc.section.4.4.p.2">The response message should indicate success or
failure via the eventType, and will contain metadata/data pair(s). The
metadata should indicate who the service is, and its "size" for voting
purposes. The data section is an enumeration of all of the current members of
the ring and their votes. This information gives the new member a snapshot of
the ring.</p>
+<p id="rfc.section.4.4.p.3">
<pre>

+<nmwg:message type="LSControlRequest">
+
+ <nmwg:metadata id="metadata.2">
+ <perfsonar:subject id="subject.2">
+ <psservice:service id="service.2">
+ <psservice:serviceName>Internet2 LS
#2</psservice:serviceName>
+
<psservice:accessPoint>http://packrat.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/join</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">100</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.2" metadataIdRef="metadata.2" />
+
+</nmwg:message>
+
+
+
+
+
+<nmwg:message type="LSControlResponse">
+
+ <nmwg:metadata id="metadata.6">
+ <perfsonar:subject id="subject.6">
+ <psservice:service id="service.6">
+ <psservice:serviceName>Internet2 LS
#6</psservice:serviceName>
+
<psservice:accessPoint>http://mead.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/join/success</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">50</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.6" metadataIdRef="metadata.6">
+ <nmwg:metadata id="metadata.1">
+ <perfsonar:subject id="subject.1">
+ <psservice:service id="service.1">
+ <psservice:serviceName>Internet2 LS
#1</psservice:serviceName>
+
<psservice:accessPoint>http://patdev0.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">0</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:metadata id="metadata.9">
+ <perfsonar:subject id="subject.9">
+ <psservice:service id="service.9">
+ <psservice:serviceName>Internet2 LS
#9</psservice:serviceName>
+
<psservice:accessPoint>http://thunderbird.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">200</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+ </nmwg:data>
+
+</nmwg:message>

</pre>
</p>
<h2 id="rfc.section.4.5">
<a href="#rfc.section.4.5">4.5</a> <a id="LSControl-Token"
href="#LSControl-Token">LS Token Message</a>
</h2>
-<p id="rfc.section.4.5.p.1">Structure of the LSControl messages serving as
the passable 'token'.</p>
-<p id="rfc.section.4.5.p.2">
+<p id="rfc.section.4.5.p.1">This message exchange represents the token that
is passed between LS instances in a cloud. The message contains metadata/data
pair(s) wherein the Metadata is the sending LS's info, and the data contains
the contents of the LSRing file (lower or upper depending on the token we are
exchanging).</p>
+<p id="rfc.section.4.5.p.2">The response to this message should indicate
success or failure. Failure and timeouts should trigger a resend.</p>
+<p id="rfc.section.4.5.p.3">
<pre>

+<nmwg:message type="LSControlRequest">
+
+ <nmwg:metadata id="metadata.6">
+ <perfsonar:subject id="subject.6">
+ <psservice:service id="service.6">
+ <psservice:serviceName>Internet2 LS
#6</psservice:serviceName>
+
<psservice:accessPoint>http://mead.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/token/lower</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">50</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.6" metadataIdRef="metadata.6">
+
+ <nmwg:metadata id="metadata.2">
+ <perfsonar:subject id="subject.2">
+ <psservice:service id="service.2">
+ <psservice:serviceName>Internet2 LS
#2</psservice:serviceName>
+
<psservice:accessPoint>http://packrat.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+ <nmwg:parameters>
+ <nmwg:parameter name="active">1</nmwg:parameter>
+ <nmwg:parameter name="contentSize">100</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:metadata id="metadata.1">
+ 
+ </nmwg:metadata>
+
+ <nmwg:metadata id="metadata.9">
+ 
+ </nmwg:metadata>
+
+ </nmwg:data>
+
+</nmwg:message>
+
+
+
+
+
+<nmwg:message type="LSControlResponse">
+
+ <nmwg:metadata id="metadata.2">
+ <perfsonar:subject id="subject.2">
+ <psservice:service id="service.2">
+ <psservice:serviceName>Internet2 LS
#2</psservice:serviceName>
+
<psservice:accessPoint>http://packrat.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/token/lower/success</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="active">1</nmwg:parameter>
+ <nmwg:parameter name="contentSize">100</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.2" metadataIdRef="metadata.2">
+ <nmwgr:datum value="some sort of message?">
+ </nmwg:data>
+
+</nmwg:message>

</pre>
</p>
<h2 id="rfc.section.4.6">
-<a href="#rfc.section.4.6">4.6</a> <a id="LSControl-Summary"
href="#LSControl-Summary">LS Summary Message</a>
+<a href="#rfc.section.4.6">4.6</a> <a id="LSControl-Summary-lower"
href="#LSControl-Summary-lower">LS Summary Message (Lower)</a>
</h2>
-<p id="rfc.section.4.6.p.1">Structure of the LSControl messages focused on
exchanging summary information.</p>
-<p id="rfc.section.4.6.p.2">
+<p id="rfc.section.4.6.p.1">This message exchange represents when an LS
instance is holding the token and sharing summary information (lower scope).
The message consists of metadata/data pair(s) that contain service
information and a parameter indicating "size" of the data set the LS manages
as well as the minimal (without parameters) summary.</p>
+<p id="rfc.section.4.6.p.2">The response message should indicate success or
failure via the eventType, and will contain metadata/data pair(s). The
metadata should indicate who the service is, and its "size" for leader voting
purposes. The data section is message that can be used for logging.</p>
+<p id="rfc.section.4.6.p.3">Caveots: </p>
+<dl class="empty">
+<dd>These messages are sent to everyone when you get a token.</dd>
+<dd>These messages are sent to everyone when you come online (and do not
necessarily have the token).</dd>
+</dl>
+<p id="rfc.section.4.6.p.4">When receiving the message, check your local
list and update it as needed for: </p>
+<dl class="empty">
+<dd>Do you know of this service? If so make sure the vote and other info is
ok.</dd>
+<dd>Update the summary info in your collection</dd>
+<dd>If you don"t know of them, add them!</dd>
+</dl>
+<p id="rfc.section.4.6.p.5">
<pre>

+<nmwg:message type="LSControlRequest">
+
+ <nmwg:metadata id="metadata.2">
+ <perfsonar:subject id="subject.2">
+ <psservice:service id="service.2">
+ <psservice:serviceName>Internet2 LS
#2</psservice:serviceName>
+
<psservice:accessPoint>http://packrat.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/summary/lower</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">100</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.2" metadataIdRef="metadata.2">
+
+ <nmwg:metadata>
+ 
+ </nmwg:metadata>
+
+ <nmwg:metadata>
+ 
+ </nmwg:metadata>
+
+ </nmwg:data>
+
+</nmwg:message>
+
+
+
+
+
+<nmwg:message type="LSControlResponse">
+
+ 
+ <nmwg:metadata id="metadata.6">
+ <perfsonar:subject id="subject.6">
+ <psservice:service id="service.6">
+ <psservice:serviceName>Internet2 LS
#6</psservice:serviceName>
+
<psservice:accessPoint>http://mead.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/summary/lower/success</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">50</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.6" metadataIdRef="metadata.6">
+ <nmwgr:datum value="some sort of message?">
+ </nmwg:data>
+
+</nmwg:message>

</pre>
</p>
<h2 id="rfc.section.4.7">
-<a href="#rfc.section.4.7">4.7</a> <a id="LSControl-Leader"
href="#LSControl-Leader">LS Leader Message</a>
+<a href="#rfc.section.4.7">4.7</a> <a id="LSControl-Summary-upper"
href="#LSControl-Summary-upper">LS Summary Message (Upper)</a>
</h2>
-<p id="rfc.section.4.7.p.1">Structure of the LSControl messages dealing with
when a Leader needs to inform the Vice-Leader of the summaries from above.</p>
-<p id="rfc.section.4.7.p.2">
+<p id="rfc.section.4.7.p.1">This message exchange represents when an LS
instance is holding the token and sharing summary information. The message
consists of metadata/data pair(s) that contain service information and a
parameter indicating "size" of the data set the LS manages. The "data"
portion is the summary info (FORMAT TBD!!!)</p>
+<p id="rfc.section.4.7.p.2">The response message should indicate success or
failure via the eventType, and will contain metadata/data pair(s). The
metadata should indicate who the service is, and its "size" for leader voting
purposes. The data section is message that can be used for logging.</p>
+<p id="rfc.section.4.7.p.3">Caveots: </p>
+<dl class="empty">
+<dd>These messages are sent to everyone when you get a token.</dd>
+<dd>These messages are sent to everyone when you come online (and do not
necessarily have the token).</dd>
+</dl>
+<p id="rfc.section.4.7.p.4">When receiving the message, check your local
list and update it as needed for: </p>
+<dl class="empty">
+<dd>Do you know of this service? If so make sure the vote and other info is
ok.</dd>
+<dd>Update the summary info in your collection</dd>
+<dd>If you don"t know of them, add them!</dd>
+</dl>
+<p id="rfc.section.4.7.p.5">
<pre>

+<nmwg:message type="LSControlRequest">
+
+ <nmwg:metadata id="metadata.2">
+ <perfsonar:subject id="subject.2">
+ <psservice:service id="service.2">
+ <psservice:serviceName>Internet2 LS
#2</psservice:serviceName>
+
<psservice:accessPoint>http://packrat.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/summary/upper</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">100</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.2" metadataIdRef="metadata.2">
+ <nmwg:metadata>
+ <summary:subject
xmlns:summary="http://ggf.org/ns/nmwg/summary/2.0/">
+ <nmtl3:network>
+ <nmtl3:subnet>128.4.10.0</nmtl3:subnet>
+ <nmtl3:netmask>255.255.255.0</nmtl3:netmask>
+ <nmtl3:asn>666</nmtl3:asn>
+ </nmtl3:network>
+ </summary:subject>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/errors/2.0</nmwg:eventType>
+ </nmwg:metadata>
+
+ <nmwg:metadata>
+ <nmtopo:subject>
+ <nmtopo:node>
+ <nmtopo:location>
+ <nmtopo:country>USA</nmtopo:country>
+ </nmtopo:location>
+ </nmtopo:node>
+ </nmtopo:subject>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/errors/2.0</nmwg:eventType>
+ </nmwg:metadata>
+ </nmwg:data>
+
+</nmwg:message>
+
+
+
+
+
+<nmwg:message type="LSControlResponse">
+
+ 
+ <nmwg:metadata id="metadata.6">
+ <perfsonar:subject id="subject.6">
+ <psservice:service id="service.6">
+ <psservice:serviceName>Internet2 LS
#6</psservice:serviceName>
+
<psservice:accessPoint>http://mead.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/summary/upper/success</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">50</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.6" metadataIdRef="metadata.6">
+ <nmwgr:datum value="some sort of message?">
+ </nmwg:data>
+
+</nmwg:message>

</pre>
</p>
<h2 id="rfc.section.4.8">
-<a href="#rfc.section.4.8">4.8</a> <a id="LSControl-Discovery"
href="#LSControl-Discovery">LS Discovery Message</a>
+<a href="#rfc.section.4.8">4.8</a> <a id="LSControl-Leader"
href="#LSControl-Leader">LS Leader Message</a>
</h2>
-<p id="rfc.section.4.8.p.1">Structure of the LSDiscovery Message used to
locate info-sets.</p>
-<p id="rfc.section.4.8.p.2">
+<p id="rfc.section.4.8.p.1">This message exchange will be conducted between
the Leader and Vice-Leader on some (frequent) interval. It may even become a
part of the Leader's token exchange with the Upper Level.</p>
+<p id="rfc.section.4.8.p.2">The leader identifies itself, and sends down the
summaries from the upper level for the Vice-Leader to store. If the leader
should die, the vice leader will have a summary of the upper level and be
able to continue answering lower level queries and obtaining information from
the higher levels.</p>
+<p id="rfc.section.4.8.p.3">
<pre>

+<nmwg:message type="LSControlRequest">
+
+ <nmwg:metadata id="metadata.6">
+ <perfsonar:subject id="subject.6">
+ <psservice:service id="service.6">
+ <psservice:serviceName>Internet2 LS
#6</psservice:serviceName>
+
<psservice:accessPoint>http://mead.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/leader</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">50</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.6" metadataIdRef="metadata.6">
+
+ 
+
+ <nmwg:metadata id="metadata.2">
+ <perfsonar:subject id="subject.2">
+ <psservice:service id="service.2">
+ <psservice:serviceName>ESnet LS
#2</psservice:serviceName>
+
<psservice:accessPoint>http://mea1.es.net:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+
<nmwg:eventType>http://perfsonar.net/services/LS/summary</nmwg:eventType>
+ <nmwg:parameters>
+ <nmwg:parameter name="contentSize">100</nmwg:parameter>
+ </nmwg:parameters>
+ </nmwg:metadata>
+
+ 
+
+ <nmwg:data id="data.2" metadataIdRef="metadata.2">
+ <nmwg:metadata>
+ <summary:subject
xmlns:summary="http://ggf.org/ns/nmwg/summary/2.0/">
+ <nmtl3:network>
+ <nmtl3:subnet>128.4.10.0</nmtl3:subnet>
+ <nmtl3:netmask>255.255.255.0</nmtl3:netmask>
+ <nmtl3:asn>666</nmtl3:asn>
+ </nmtl3:network>
+ </summary:subject>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/errors/2.0</nmwg:eventType>
+ </nmwg:metadata>
+
+ <nmwg:metadata>
+ <nmtopo:subject>
+ <nmtopo:node>
+ <nmtopo:location>
+ <nmtopo:country>USA</nmtopo:country>
+ </nmtopo:location>
+ </nmtopo:node>
+ </nmtopo:subject>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/tools/snmp/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/utilization/2.0</nmwg:eventType>
+
<nmwg:eventType>http://ggf.org/ns/nmwg/characteristic/errors/2.0</nmwg:eventType>
+ </nmwg:metadata>
+ </nmwg:data>
+
+ 
+
+ </nmwg:data>
+
+</nmwg:message>

</pre>
</p>
<h2 id="rfc.section.4.9">
-<a href="#rfc.section.4.9">4.9</a> <a id="Message Types" href="#Message
Types">Message Types</a>
+<a href="#rfc.section.4.9">4.9</a> <a id="LSControl-Discovery"
href="#LSControl-Discovery">LS Discovery Message</a>
</h2>
-<ol>
-<li>Discovery - The Discovery request will contain a subject of the relevant
type. This will essentially be either an ipAddress or a Network (for the
query by IP case) or an abstract node with a location element expressing the
location requirements of interest. <ol style="list-style-type: lower-alpha">
-<li>LSDiscoveryRequest</li>
-<li>LSDiscoveryResponse <ol style="list-style-type: lower-alpha">
-<li>Success</li>
-<li>Refer</li>
-<li>Failure</li>
-</ol>
-</li>
-</ol>
-</li>
-<li>Token - Token messages will be used to exchange information between LS
instances. The can be specialized (by eventType) to handle different tasks
such as Joining, exchanging summary information, or used for leader
communication. <ol style="list-style-type: lower-alpha">
-<li>LSControlRequest</li>
-<li>LSControlResponse <ol style="list-style-type: lower-alpha">
-<li>Success</li>
-<li>Refer</li>
-<li>Failure</li>
-</ol>
-</li>
-</ol>
-</li>
-<li>Other... <ol style="list-style-type: lower-alpha">
-<li>LS...Request</li>
-<li>LS...Response <ol style="list-style-type: lower-alpha">
-<li>Success</li>
-<li>Refer</li>
-<li>Failure</li>
-</ol>
-</li>
-</ol>
-</li>
-</ol>
+<p id="rfc.section.4.9.p.1">Structure of the LSDiscovery Message used to
locate info-sets. (FORMAT TBD!!!)</p>
+<p id="rfc.section.4.9.p.2">
+<pre>
+
+
+
+<nmwg:message type="LSDiscoveryRequest">
+
+ <nmwg:metadata id="metadata.1">
+
+ 
+
+ </nmwg:metadata>
+
+ <nmwg:data id="data.1" metadataIdRef="metadata.1" />
+
+</nmwg:message>
+
+
+
+<nmwg:message type="LSDiscoveryResponse">
+
+ <nmwg:metadata id="metadata.1.r">
+ 
+ <nmwg:eventType>success</nmwg:eventType>
+
+ <nmwg:eventType>failure</nmwg:eventType>
+
+ <nmwg:eventType>referral</nmwg:eventType>
+ </nmwg:metadata>
+
+ <nmwg:data id="data.1.r" metadataIdRef="metadata.1.r">
+
+ 
+ <nmwgr:datum value="some message" />
+
+ 
+ <nmwg:metadata id="metadata.6">
+ <perfsonar:subject id="subject.6">
+ <psservice:service id="service.6">
+ <psservice:serviceName>Internet2 LS
#6</psservice:serviceName>
+
<psservice:accessPoint>http://mead.internet2.edu:8080/perfSONAR_PS/services/LS</psservice:accessPoint>
+ <psservice:serviceType>LS</psservice:serviceType>
+
<psservice:serviceDescription>...</psservice:serviceDescription>
+ </psservice:service>
+ </perfsonar:subject>
+ </nmwg:metadata>
+
+ </nmwg:data>
+
+</nmwg:message>
+
+ </pre>
+</p>
<hr class="noprint">
<h1 id="rfc.section.5" class="np">
-<a href="#rfc.section.5">5.</a> <a id="issues" href="#issues">Open
Issues</a>
+<a href="#rfc.section.5">5.</a> <a id="apdx" href="#apdx">Appendices</a>
</h1>
-<ol>
-<li>Computing the TTRT</li>
-<li>One LS in multiple domains</li>
-<li>Schema for the token message</li>
-<li>LS to LS registration (describe the message type)</li>
-</ol>
-<hr class="noprint">
-<h1 id="rfc.section.6" class="np">
-<a href="#rfc.section.6">6.</a> <a id="apdx" href="#apdx">Appendices</a>
-</h1>
-<h2 id="rfc.section.6.1">
-<a href="#rfc.section.6.1">6.1</a> <a id="glossary"
href="#glossary">Glossary</a>
+<h2 id="rfc.section.5.1">
+<a href="#rfc.section.5.1">5.1</a> <a id="glossary"
href="#glossary">Glossary</a>
</h2>
<ul>
-<li>Service - A Service is an application that communicates with other
perfSONAR Services via standarized protocol set (SOAP+XML+NMWGv2)</li>
+<li>Service - A Service is an application that communicates with other
perfSONAR Services via standardized protocol set (SOAP+XML+NMWGv2)</li>
<li>Lookup Service (LS) - The Lookup Service is a key element of the
perfSONAR framework because it allows every independent service to be a
visible part of the system. New services may identify themselves to the
community and provide their detailed capabilities description. Other services
are able to communicate to the LS in order to get this data called Lookup
Information. Basic Lookup Service supports registration, query, keepalives
and de-registration actions (additionally updates?).</li>
<li>Lookup Information - information registered by a Service in the Lookup
Service</li>
<li>Summary Information - aggregated information from Lookup Information
that is sent by one LS to another</li>
@@ -983,9 +1361,14 @@
<li>Home LS (HLS) - The Home LS of a Service is the LS where the Service
registers its Lookup Information</li>
<li>Upper (Global) Scope - The scoping paradigm meant to indicate
intra-domain relationships.</li>
<li>Lower (Local) Scope - The scoping paradigm meant to indicate
inter-domain relationships.</li>
+<li>XSLT - Extensible Stylesheet Language Transformations is an XML-based
language used for the transformation of XML documents into other XML or
"human-readable" documents. The original document is not changed; rather, a
new document is created based on the content of an existing one.</li>
+<li>XQuery - A query language (with some programming language features) that
is designed to query collections of XML data. It is semantically similar to
SQL.</li>
+<li>Token Ring - A ring network in which the network topology features nodes
connected to exactly two other nodes, forming a circular pathway for signals:
a ring. Data travels from node to node, with each node handling every packet.
We use a logical ring in which a "token" message is used to synchronize the
communication among the nodes.</li>
+<li>Berkeley DB XML - Oracle Berkeley DB XML is an open source, embeddable
XML database with XQuery-based access to documents stored in containers and
indexed based on their content.</li>
+<li>eXist XML DB - eXist is an Open Source native XML database featuring
efficient, index-based XQuery processing, automatic indexing, extensions for
full-text search, XUpdate support, XQuery update extensions and tight
integration with existing XML development tools.</li>
</ul>
<h1 class="np" id="rfc.references">
-<a href="#rfc.section.7">7.</a> References</h1>
+<a href="#rfc.section.6">6.</a> References</h1>
<table summary="References" border="0" cellpadding="2">
<tr>
<td class="topnowrap">
@@ -1001,22 +1384,8 @@
<h1 id="rfc.authors" class="np">Authors' Addresses</h1>
<address class="vcard">
<span class="vcardline">
-<span class="fn">D. Martin Swany</span>
- (Editor)
- <span class="n hidden">
-<span class="family-name">Swany</span>
-<span class="given-name">D. Martin</span>
-</span>
-</span>
-<span class="org vcardline">University of Delaware
- Department of Computer and
Information Sciences
- Newark, DE 19716</span>
-</address>
-<address class="vcard">
-<span class="vcardline">
<span class="fn">Jeff Boote</span>
- (Contributor)
- <span class="n hidden">
+<span class="n hidden">
<span class="family-name">Boote</span>
<span class="given-name">Jeff</span>
</span>
@@ -1027,22 +1396,8 @@
</address>
<address class="vcard">
<span class="vcardline">
-<span class="fn">Jason Zurawski</span>
- (Contributor)
- <span class="n hidden">
-<span class="family-name">Zurawski</span>
-<span class="given-name">Jason</span>
-</span>
-</span>
-<span class="org vcardline">Internet2
- 1000 Oakbrook Drive Suite 300
- Ann Arbor MI 48104 </span>
-</address>
-<address class="vcard">
-<span class="vcardline">
<span class="fn">Maciej Glowiak</span>
- (Contributor)
- <span class="n hidden">
+<span class="n hidden">
<span class="family-name">Glowiak</span>
<span class="given-name">Maciej</span>
</span>
@@ -1052,5 +1407,29 @@
61-704 Poznan
Poland</span>
</address>
+<address class="vcard">
+<span class="vcardline">
+<span class="fn">D. Martin Swany</span>
+<span class="n hidden">
+<span class="family-name">Swany</span>
+<span class="given-name">D. Martin</span>
+</span>
+</span>
+<span class="org vcardline">University of Delaware
+ Department of Computer and
Information Sciences
+ Newark, DE 19716</span>
+</address>
+<address class="vcard">
+<span class="vcardline">
+<span class="fn">Jason Zurawski</span>
+<span class="n hidden">
+<span class="family-name">Zurawski</span>
+<span class="given-name">Jason</span>
+</span>
+</span>
+<span class="org vcardline">Internet2
+ 1000 Oakbrook Drive Suite 300
+ Ann Arbor MI 48104 </span>
+</address>
</body>
</html

Modified: trunk/nmwg/doc/dLS/dLS.pdf
===================================================================
(Binary files differ)

Modified: trunk/nmwg/doc/dLS/dLS.xml
===================================================================
--- trunk/nmwg/doc/dLS/dLS.xml 2007-10-03 13:22:11 UTC (rev 281)
+++ trunk/nmwg/doc/dLS/dLS.xml 2007-10-05 02:32:28 UTC (rev 282)
@@ -1,9 +1,9 @@
-<?xml version='1.0'?>
+<?xml version="1.0"?>
<!DOCTYPE rfc SYSTEM "rfc2629.dtd">

<rfc>

-<?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?>
+<?xml-stylesheet type="text/xsl" href="rfc2629.xslt" ?>
<?rfc toc="yes" ?>
<?rfc symrefs="yes" ?>
<?rfc sortrefs="yes"?>
@@ -15,31 +15,28 @@

<front>
<title>Distributed Lookup Service (dLS) in the perfSONAR
Framework</title>
- <author initials='M' surname='Swany' fullname='D. Martin Swany'
- role='Editor'>
- <organization abbrev='UDel'>University of Delaware
- Department of Computer and
Information Sciences
- Newark, DE 19716</organization>
- </author>
- <author initials='J' surname='Boote' fullname='Jeff Boote'
- role='Contributor'>
- <organization abbrev='Internet2'>Internet2
+
+ <author initials="J" surname="Boote" fullname="Jeff Boote">
+ <organization abbrev="Internet2">Internet2
1000 Oakbrook Drive Suite 300
Ann Arbor MI 48104 </organization>
</author>
- <author initials='J' surname='Zurawski' fullname='Jason Zurawski'
- role='Contributor'>
- <organization abbrev='Internet2'>Internet2
- 1000 Oakbrook Drive Suite 300
- Ann Arbor MI 48104 </organization>
- </author>
- <author initials='M' surname='Glowiak' fullname='Maciej Glowiak'
- role='Contributor'>
- <organization abbrev='PSNC'>Poznan Supercomputing and Networking
Center
+ <author initials="M" surname="Glowiak" fullname="Maciej Glowiak">
+ <organization abbrev="PSNC">Poznan Supercomputing and Networking
Center
ul. Noskowskiego 10
61-704 Poznan
Poland</organization>
</author>
+ <author initials="M" surname="Swany" fullname="D. Martin Swany">
+ <organization abbrev="UDel">University of Delaware
+ Department of Computer and
Information Sciences
+ Newark, DE 19716</organization>
+ </author>
+ <author initials="J" surname="Zurawski" fullname="Jason Zurawski">
+ <organization abbrev="Internet2">Internet2
+ 1000 Oakbrook Drive Suite 300
+ Ann Arbor MI 48104 </organization>
+ </author>
<date month="October" year="2007"/>
</front>

@@ -97,58 +94,121 @@
</list>

<t>
- Additionally we present solutions to issues related to the operation
- of this seemless service including bootstrapping and domain specific
+ Additionally we present solutions to issues related to allow
seamless
+ operation of this service including bootstrapping and domain specific
concerns.
</t>
</section>

- <section anchor="system" title="System Specific Operation">
+ <section anchor="system" title="system Specific Operation">



<section anchor="summary" title="Summarization">
<t>The first step of information flow is when a service registers
with
an LS. The service may know the name of an LS via static
- configuration, or other forms of bootstrapping may occur. A
service
- registers metadata record about itself and full metadata (i.e.
- containing all information such as subject, eventType(s), and any
- parameters, see <xref target="service-metadata" />) about stored
- (or gathered) data. Such a record is called Lookup Information
- (see <xref target="lookup-info" />). The idea is to move the
- metadata from a local XML data store to a specialized LS with
- additional searching capabilities. While a service instance
- may support limited searching, this is not required as they
- should be focused on storing or gathering data and leave the
- lookup functionality to the LS. Possible exceptions are rapidly
- changing Metadata like the most recent timestamp and full details
- of data stored in long-term archival MAs.
+ configuration (the most common case for legacy deployments), or
+ other forms of bootstrapping such as multicast may occur. A
service
+ registers a "service metadata" record about itself and full
+ metadata (i.e. containing all information such as subject,
+ eventType(s), and any parameters, see
+ <xref target="service-metadata" />) about stored data it has
+ knowledge of. Such a record is called Lookup Information (see
+ <xref target="lookup-info" />).
+ </t>
+
+ <t>
+ The idea is to move the metadata from a local XML data store to a
+ specialized LS with additional searching capabilities. While a
+ service instance may support limited searching, this is not
+ necessary as they should be focused on storing or gathering data
+ and leave the lookup functionality to the LS. Possible exceptions
+ are rapidly changing Metadata like the most recent timestamp and
+ full details of data stored in long-term archival MAs.
</t>

-
-<t><vspace blankLines="2" />START_NOTE (Jason 9/18/07):<vspace
blankLines="1" />
-Question 1) In the first level of summarization (i.e. 'local' ring) what is
being
-exchanged between HLS instances? Are they exchanging full information, or
-summaries? Where is this info stored (i.e. seperate collection)? If we are
exchanging
-summaries it is natural to use a different collection, if we are exchanging
-full info it doesn't seem to be necessary.
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
-
-
- <t>The LS that a service contacts to register becomes the "Home LS"
+ <t>
+ The LS that a service contacts to register becomes the "Home LS"
(HLS, see <xref target="glossary" />) of that particular service.
It is the responsibility of the HLS to make summary data about the
- all of the pS services it knows of available to the larger
- enterprise and to draw relevant queries to itself. In order to
- make information available to the LS cloud,
- the HLS will advertise this summary information to other LS
- instances to propagate the appropriate information.
- </t>
+ all of the pS services it knows of available to the larger
+ enterprise and to draw relevant queries to itself.
+ </t>
+
+ <t>
+ The construction of such a summary is important to the overall
+ success of this service; summaries must be general enough to
allow
+ for easy creation and exchange but also must retain enough
+ information to provide a rich query interface able to locate the
+ distributed information. We start by making an observation that
+ summarization is best based on scope, simply put this means that
we
+ should attempt to summarize the "most" the "further" away from
the
+ source that we get. This creates a smaller data set that travels
+ the furthest away while keeping the larger and more informative
data
+ sets closer to the source. We present the strategies as such:
+
+ <list style="symbols">
+ <t>Summarization for the "lower scope" (formerly known as
+ "local scope")</t>
+ <t>Summarization for the "upper scope" (formerly known as
+ "global scope")</t>
+ </list>
+
+ We limit the discussion in this case to these two scopes,
although
+ extension to "n" scopes is possible. As the number of of scopes
+ increases additional "aggregation" will be necessary to combine
+ information thus reducing the size of the data sets further.
+ </t>
+
+
+
+ <section anchor="lower_scope_summarization" title="Lower Scope
Summarization">
+ <t>
+ This first level of summarization, between HLS instances
internal
+ to a domain, consists of simply dropping superfluous information
+ from the metadata descriptions provided by registered services.

+ For now we define this to be simply removing additional
"parameter"
+ elements from the metadata. Special consideration must be
given to
+ the "supportedEventType" parameter by simply converting this to
+ actual eventType elements. This will ensure interoperability
with
+ legacy services.
+ </t>
+
+ <t>
+ Future iterations may choose to drop additional pieces of
+ information deemed unnecessary or private such as parts of
+ topological descriptions. This sort of modification is
encouraged
+ as long as the data remains "symmetrical" and conforms to the
+ schematic definitions for a given metadata description. It
should
+ be noted that such modifications will affect the searching
+ procedure and could isolate the source services.
+ </t>
+
+ <t>
+ The mechanics for performing this level of summarization can
use
+ any number of technologies. Either Extensible Stylesheet
+ Language Transformation (XSLT) documents or the XQuery language
+ (see <xref target="glossary" />) may be used to prepare the
+ initial data for exchange in this first level. Since the
+ exchange of this local information will occur frequently, a
+ simple operation that is scheduled or on demand should be
+ employed by the individual implementations to ensure the
+ regular LS functions are not impeded.
+ </t>
+
+ <t>In order to make information available to the LS cloud, the HLS
+ will advertise this summary information to other LS instances
to
+ propagate the appropriate information. Information exchange
+ will be handled using a "taking turns" protocol such as token
+ ring (see <xref target="glossary" />). The holder of the
+ token will then perform the information exchange to other
+ known instances.
+ </t>

- <figure anchor="hls-cloud">
- <preamble>HLS Cloud</preamble>
- <artwork>
+ <figure anchor="hls-cloud">
+ <preamble>HLS Cloud</preamble>
+ <artwork>

A) Token passing
_____ _____
@@ -175,87 +235,122 @@
|____/T\ Token
\_/

- </artwork>
- <postamble>HLS instances communicating via token (A). The holder
- of the token (LS3) will inform everyone of summary
- information (B).</postamble>
- </figure>
-
- <t>
- The most natural summarization is based on the topology of the
network
- (like in network routing). Thus, a given HLS will perform
topology-based
- summarization and will include this information as well as
eventType
- information to other LSs in its "lower scope" (formerly known as
- "local scope"). Likewise, more aggressive summarization can take
- place when the "lower scope" registers into the "upper scope"
- (formerly known as "global scope"). This is analogous to the
- aggregation that occurs in IGPs (lower scope) and EGPs (upper
- scope).
- </t>
-
- <t>
- Summarization will be performed using specialized summary
algorithm. Topology information such as IP addresses will be summarized using
algorithms basing on radix tree (the IP addresses summarization algorithm is
described in section <xref target="IP-summary" />) .</t>
+ </artwork>
+ <postamble>HLS instances communicating via a token message (A).
The
+ holder of the token (LS3) will inform everyone of
it's
+ summary information (B).</postamble>
+ </figure>
+
+ <t>Once exchanged, the details regarding storage in the XML
database
+ backend (see <xref target="glossary" />) are also left to
+ individual implementations. It is understood that this
+ information, in the possession of non HLS instances, is
provided
+ as a convenience and should be treated in the same way that
+ directly registered information is (i.e. purged on
expiration).
+ When requested, credit must also be attributed to the HLS as
being
+ (non)authoritative for each piece of information.
+ </t>
+ </section>

- <t>In addition to that either Extensible Stylesheet Language
Transformation (XSLT) documents or the XQuery language may be used for
transformation eventType elements.
- </t>
+ <section anchor="upper_scope_summarization" title="Upper Scope
Summarization">
+ <t>
+ A designated member of each lower ring will be required to
interact
+ with the upper level. The mechanics of how we learn who is the
+ designated leader is discussed in <xref target="tokens" />. The
+ leader of each group (and the designated backup) will be
responsible
+ for examining each member's summary information and building a
+ summarization/aggregation that best describes the contents of the
+ ring.
+ </t>
+
+ <t>
+ The most natural summarization is based on the topology of the
+ network (like in network routing). Thus, topology-based
+ summarization will include this information as well as eventType
+ information from the other LSs. Summarization will be performed
+ using specialized summary algorithm. Topology information such
+ as IP addresses will be summarized using algorithms basing on
+ radix tree (see <xref target="IP-summary" />).
+ </t>

-
-<t><vspace blankLines="2" />START_NOTE (Jason 9/18/07):<vspace
blankLines="1" />
- Question 3) Are additional 'aggressive' summaries still needed? At the
upper levels
- it seems to be less of 'summarization' and more of an aggregate of
summaries
- (unless we are dropping things out).
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
+ <t>
+ Other information can be summarized in a less programmatic
fashion
+ through the use of either Extensible Stylesheet Language
+ Transformation (XSLT) documents or the XQuery language as
discussed
+ in the previous section. These mechanisms will take into
account
+ the XML elements that represent the network topology currently
used
+ in metadata subjects as well as additional items such as
+ eventTypes.
+ </t>
+
+ <t>
+ The output of this process becomes a "service summary" that
+ represents a breadth of the original input. See
+ <xref target="LSControl-Summary-lower" /> or
+ <xref target="LSControl-Summary-upper" /> for a mock-up of the
+ summary output. Additional transformations, while aggressive,
will
+ strive to preserve as much information as possible to remain
+ useful during the search procedures.
+ </t>
+
+ <section anchor="IP-summary" title="IP addresses summarization
algorithm">
+ <t>
+ To properly summarize a list of strings such as IP addresses we
+ must rely on the help of special algorithms and data
structures.
+ The <eref
target="http://en.wikipedia.org/wiki/Radix_tree";>Radix Tree</eref>
+ algorithm is useful in creating "associative arrays" where the
+ keys are expressed as strings. Radix Tree implementations have
+ been used in practice to index things such as text documents as
+ well as more menial tasks such as dictionaries. We are most
+ interested in indexing IP addresses with their natural
hierarchy,
+ where it is necessary to describe a large ranges of values and
+ have few exceptions.
+ </t>
+
+ <t>
+ A detailed explanation of the nuances of the Radix Tree is well
+ beyond the scope of this document, but a brief overview is
+ presented for completeness. The structure itself is best
+ described as a binary tree where nodes contain whole values
and
+ the edges are the primary source of navigation. The edges of
the
+ tree can be based on a single character or perhaps on even
longer
+ strings (one of the features that leads to efficiency for
small
+ data sets). The algorithm should support the following basic
+ operations:

-
- <t>These documents will take into account the XML elements that
represent
- the network topology currently used in metadata subjects as well
as
- additional items such as eventTypes. The output of this process
- becomes a "service summary" that represents a breadth of the
original
- input. See <xref target="LSControl-Summary" /> for a mock-up of
the
- summary output. Additional transformations, while aggressive, will
- strive to preserve as much information as possible to remain
useful
- during the search procedures.
- </t>
+ <list style="symbols">
+ <t>Lookup: Indicate that something is or is not contained in
+ the tree.</t>
+ <t>Insert: Like in most inserts we attempt to place something
+ into the structure. We first start by doing a Lookup to
+ see if it exists already; the point where we stop is
where
+ we will insert the object. We are careful to utilize
+ the longest matching prefix of any other nearby edge to
our
+ advantage. This last part is normally referred to as
+ "splitting" and ensures that each node has no more than
+ two children.</t>
+ <t>Delete: Delete an object from the tree. This operation
will
+ be complicated by "collapsing" parents that have a single
+ child and merging the edges.</t>
+ </list>
+ </t>

- <t>In early discussions, we left the possibility open for multiple
types
- of summarization for different types of services and data. This
is
- still possibility. There are arguments to simplify the types of
- summarizations that can occur. The first is that arbitrary
- summarizations will yield arbitrary XML data, making discovery
- queries more difficult to construct. Thus it seems to be
sufficient
- to summarize over the Topology elements in a regular fashion and
- simply include the eventTypes and drop the Parameters. This will
ease
- query construction.
- </t>
+ <t>
+ Once constructed, it is possible to consult the structure in
+ creating IP summaries as well as constructing information
+ regarding netmasks.
+ </t>
+ </section>
+
+ </section>
+
+ </section>

- <t>We may target cases where various summarizations are possible, but
- for now summarization on the basis of topology seems sufficient.
- </t>
-
- <t>A related question is that of policy. In our discussions, we had
the
- intuition that some domains would want to register less
information
- than others. One example is whether the actual IP addresses of
MPs
- capable of launching active measurements. These hosts, if
- compromised, can pose significant denial of service threat.
- </t>
-
- <section anchor="IP-summary" title="IP addesses summarization
algorithm">
- <t>The IP addresses summarization algorithm is based on radix
tree. The idea of the algorithm is...</t>
-
-<t><vspace blankLines="2" />START_NOTE (Maciej 10/2/07):<vspace
blankLines="1" />
-To be done... I'd expect detailed recipe here.
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
-
- </section>
-
-
- </section>
-
-
-
+
+


- <section anchor="scope" title="Scope">
+ <section anchor="scope" title="scope">

<t>The next question is how to form the lower and upper scopes. The
simplest answer is that the lower scope be formed based on the
domain
@@ -280,19 +375,18 @@
</t>

<t>
- With the generalities of what a scope is taken care of, we now turn
- our attention to central algorithms of the dLS:
+ The major algorithms used to form and maintain the ring structure
of
+ the dLS, no matter which scope we are talking about, are as
follows:
<list style="symbols">
<t>Join Procedure</t>
<t>Token Passing</t>
<t>Summarization Notification</t>
</list>
+ Each of these procedures is paramount to keeping members of the
+ distributed "service" functioning correctly. The algorithms will
be
+ presented in the frame of the lower scope, but will be used in the
+ same manner for the upper scope as well.
</t>
-
- <t>
- The algorithms will be presented in the light of the lower
scoping,
- but will be used in the same manner for the upper scope as well.
- </t>

<section anchor="join" title="Join Procedure">
<t>
@@ -306,24 +400,28 @@
<t>
An LS will continuously search it's LSRing information (see
<xref target="LSRing" />) until a successful response to an
LSControl
- message (with a 'join' eventType, see
+ message (with a "join" eventType, see
<xref target="LSControl-Join" />) is seen. The LS will search
though
the successful response to this message and update its LSRing
with
- the returned information. This can mean updating the
'contentSize'
- and 'active' parameters as well as adding new LS instances.
These
- parameters are indicative of the LS's size (i.e. how many
services
- are registering with it) and 'live-ness' (i.e. were we
successful in
- contacting it recently).
+ the returned information. This can mean updating the
"contentSize"
+ and "active" parameters as well as adding new LS instances.
These
+ parameters are indicative of the size of each LS (i.e. how many
+ services are registering with it) and "live-ness" (i.e. were we
+ successful in contacting it recently). The contacted LS will
also
+ update the local copy of LSRing to add the new member to its
+ "available" list.
</t>

<t>
- After updating the LS will broadcast another LSControl message
(with
- a 'summary' eventType, see <xref target="LSControl-Summary" />)
to all
- of the 'active' LS instances from it's LSRing. Again the
responses
- will be parsed to get any useful updated information. Each of
the
- recipient LS instances will do the same, including adding this
new
- member to their own lists (as many of them will not know of it's
- existence yet).
+ After updating, the LS will broadcast another LSControl message
(with
+ a "summary" eventType, see <xref
target="LSControl-Summary-lower" />,
+ or of we are dealing with the upper level see
+ <xref target="LSControl-Summary-upper" />) to all of the
"active"
+ LS instances from it's LSRing. Again the responses will be
parsed
+ to get any useful updated information. Each of the recipient LS
+ instances will do the same, including adding this new member to
+ their own lists (as many of them will not know of it's existence
+ yet).
</t>

<t>
@@ -332,88 +430,191 @@
it has not seen one in a very long time.
</t>

- <section anchor="join_algorithm" title="Join algorithm">
+ <section anchor="join_algorithm" title="Join Algorithm">
+
<t>
- This paragraph describes the Join procedure for LS1.
- <t>1. LS1 - "candidate" sends LSControlRequest message with
the http://perfsonar.net/services/LS/join eventType to selected LS2 which is
already a member of the ring</t>
- <t>2. LS2 receives join message from L1 and decides whether
to accept it or not. A security policy may occur here</t>
- <t>3. LS1 gets the answer - success joining (result code:
http://perfsonar.net/result/success/LS/join) or failure (error code)</t>
- <t>4. If succcess LS1 will be waiting for token and LS2
updates its local peer list</t>
- <t>5. In the meantime LS2 receives Token. Then it
synchronizes peer lists - the local one and the one in token. LS2 sends local
summary to all peers from list (due to summary broadcasting algotirhm -
see...). LS2 sends Token to next peer from the list (not necessarily to
LS1).</t>
- <t>6. When there is LS1 turn it will get the Token. Then it
synchronizes peer lists - local and the one in token, sends its local summary
to all peers from list and sends Token to next peer</t>
-
- </t>
+ <figure anchor="join-example">
+ <preamble>Illustration of LS Join Algorithm</preamble>
+ <artwork>
+ (5,6)
+ ______________________________________________________
+ | |
+ | |
+ __V__ _____ _V___
+| | | | (1) | |
+| LS3 | <----------------- | LS2 | <----------------> | LS1 |
+|_____| |_____| (2,3) |_____|
+ | ^ ^ ^ ^
+ | | | | |
+ | _____ | | | |
+ | | | | |_______________________| |
+ |-------> | LS4 | ---------| (5,6) |
+ |_____| <____________________________________|
+ (5,6)
+
+
+ </artwork>
+ </figure>
+
+ <list type="symbols">
+ <t>1. LS1 - "candidate" sends LSControlRequest message with
+ the http://perfsonar.net/services/LS/join eventType to
+ selected LS2 which is already a member of the ring</t>
+ <t>2. LS2 receives join message from L1 and decides whether
+ to accept it or not. A security policy may occur
here</t>
+ <t>3. LS1 gets the answer - success joining (result code:
+ http://perfsonar.net/result/success/LS/join) or
failure
+ (error code)</t>
+ <t>4. After receiving the response from LS2, LS1 will parse
+ the results to discover all members of the ring.</t>
+ <t>5. LS1 will "broadcast" its summary info (lower or upper)
to
+ all of the LS instances it learns of. This is of
course
+ "out of turn" as LS1 doesn't have the token yet but
this
+ reasoning is twofold:
+ <list type="symbols">
+ <t>This expedites all ring members knowing the new LS,
+ the ring will grow instantly by inserting the new
+ member into the correct position.</t>
+ <t>This allows the information it provides to the
leaders
+ to become available for the next upper ring summary
as
+ soon as possible. Worst case scenarios would place
+ this knowledge cycles away from being recognized.</t>
+ </list>
+ </t>
+ <t>6. All members of the ring will process the summaries,
save
+ the necessary information, and recognize the new peer.

+ Responses will be prepared for LS1.</t>
+
+ 
+ </list>
+ </t>
</section>

</section>

<section anchor="tokens" title="Token Passing">
<t>
- The 'token' is a message (see <xref target="LSControl-Token" />)
+ The "token" is a message (see <xref target="LSControl-Token" />)
meant to be passed around an LSRing to the various members in
some
- order. We will pass from smallest 'contentSize' to largest
- (with appropriate wrap around), and at any given time an LS
- instance will know where the next token message should go.
+ order. There are various criterion that can be used in deciding
how
+ to order the ring so that everyone can predict where the token
is,
+ when they might expect to get it, and whom they should get it
from/
+ pass it to next. It is important that we choose a sound method
that
+ is simple to calculate, and should use as much "knowledge" of
the
+ ring as possible without burdening the LS instances too much with
+ complex calculations.
</t>
+
+ <t>
+ A common method used in P2P (see <xref target="glossary" />)
systems
+ such as Gnutella (see <xref target="glossary" />) when forming
+ "ultrapeers" is to consider the size of the data that a node is
+ serving. The principle, as described
+ <eref
target="http://rakjar.de/gnufu/index.php/GnuFU_en#Network_model:_Change_who_calls_whom:_Ultrapeers_and_Leafs";>here</eref>,

+ alludes to the fact that nodes with less content to look after
(i.e. less
+ services, or services with a smaller amount of data) can spend
more
+ time and effort helping the enterprise as a whole by taking on
+ additional roles (such as serving as leaders). As such we will
+ record the number of metadata elements that register with each LS
+ and share this with our friends in the form of the "contentSize"
+ parameter.
+ </t>

-<t><vspace blankLines="2" />START_NOTE (Maciej 10/3/07):<vspace
blankLines="1" />
- Question: I am not convinced 'contentSize' should be the only criterion.
When new LS joins the ring it may have empty database, but in some time it'll
get a lot of metadata. The mechanism of leader election bases on that, so
it's quite important. If such LS will 'update' its 'contentSize' value not
all other LS-es may know about it immediately (token passing cycle) and they
may not have the same knowledge about the leader. I'd prefer more
deterministic way of leader election.
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
-
-
<t>
- The token can be viewed as 'permission to talk' and permits the
+ Token passing is directly related to the concept of leader
+ election (see <xref target="Leader_Election" />), so more
+ explanation of this approach will follow. For now we are
justified
+ in saying that the "contentSize" forms a good criterion for
+ "ordering" the members of the ring. With all members of the ring
+ aware of everyone's data size, we can easily know who we should
+ pass the token to, and receive it from at any point in time.
+ </t>
+
+ <t>
+ The token can be viewed as "permission to talk" and permits the
holder to send it's summary information to all available LS
- instances (see <xref target="LSControl-Summary" />). The
responses
+ instances (see <xref target="LSControl-Summary-lower" /> and
+ <xref target="LSControl-Summary-upper" />). The responses
will be parsed to get any useful updated information.
</t>

<t>
The holder of the token, after completing summarization, will
wait
some pre-determined amount of time before sending the token to
the
- next LS instance. LS instances should be sensitive (although
not
- overly sensitive) to the progression of the token through the
- ring. A token should expect to arrive in some interval equal to
- the size of the ring times the waiting interval, with tolerance
- above and below this value.
+ next LS instance. In general the LS instances should not be
overly
+ sensitive to the progression of the token. If each LS instance
is
+ monitoring the progress, and for some reason we have lost the
+ token it may start a flurry of retransmits and drops that will
take
+ cycles to calm down again.
</t>

- <t>The timeout mechanism(s) will need to be further specified. It
can
- be computed as a function of the number of nodes in the ring.
This
- is the Target Token Rotation Time (TTRT), for details see
section: <xref target="TTRT" />TTRT computing. There may be a future
- point at which we need to think about ring splitting, but we
- believe that this can be managed by further scope levels.
- </t>
-
<t>
- If the token has been 'dropped' along its path the next LS in
line
- will detect this and re-send it to not break the communication
- chain. If for some reason a second token appears too quickly
after
- the previous token, any LS instance should see this dispose of
the
- duplicate message.
- </t>
+ Thus we leave the decisions regarding tokens up to a single
node,
+ namely the designated leader of a ring. We build functionality
+ into leader nodes to be the only "maker" and "executioner" of
+ tokens. Extra tokens are dropped/created only by a single node
in
+ the ring. All strange thrashing behavior is avoided and if
+ something bad happens it is eliminated in a single passing. The
+ leader node will have knowledge of the size of the ring (even if
+ the Ring has grown our Join algorithm will inform all interested
+ parties instantly) and the token "wait" period (should be a
+ standard value) thus calculating the expected time is not an
issue.
+ </t>

-<t><vspace blankLines="2" />START_NOTE (Maciej 10/3/07):<vspace
blankLines="1" />
- Question: I'd like to know a bit more when new token will be created and
how to prevent existing two or more tokens (removing tokens?)
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
-
- <section anchor="token_passing_algorithm" title="Token passing
algorithm">
- <t>When receives the token (LSControlRequest message with the
http://perfsonar.net/services/LS/token/... eventType.
- </t>
+
+ <section anchor="token_passing_algorithm" title="Token passing
algorithm">
+
+ <t>
+ <figure anchor="token-example">
+ <preamble>Illustration of LS Token Passing</preamble>
+ <artwork>
+
+ _____ _____
+| | | |
+| LS1 | <----------------- | LS2 |
+|_____| |_____|
+ | ^
+ | |
+ | _____ |
+ | | | |
+ |-------> | LS3 | ---------|
+ |_____|
+
+
+ </artwork>
+ </figure>
+
+ <list type="symbols">
+ <t>0. When any LS receives the token (LSControlRequest message
+ with the http://perfsonar.net/services/LS/token/...
+ eventType, we will do the following: </t>
<t>1.Update local peer list (from token)</t>
- <t>2.Update token peer list (add newly registered LS-es)</t>
- <t>3.Send summary to all peers in the lease (excluding
itself)</t>
- <t>4.Wait</t>
- <t>6.Send token to next peer from the list (if it fails, try
next one)</t>
- </section>
-
- <section anchor="TTRT" title="TTRT computing algorithm">
- <t>TBD.</t>
- </section>
-
+ <t>2.Send summary to all peers in the lease (excluding
itself)</t>
+ <t>3.Wait for some amount of time</t>
+ <t>4.Send token to next peer from the list (if it fails, try
next one)</t>
+ </list>
+ </t>
+ </section>
+
</section>

- <section anchor="summary-blast" title="Summarization Notification">
+
+
+
+ <section anchor="summary-blast" title="summarization Notification">
<t>
As discussed in the prior two sections there are two acceptable
instances to send your summary to the LSRing:
@@ -426,50 +627,62 @@
<t>
In the first case we are explicitly entering ourselves into the
ring when we get our first message from a peer. This ensures we
- show up in the token rotation the next cycle. The second case is
+ show up in the token rotation instantly. The second case is
the routine exchange started when a token arrives from a peer.
</t>

<t>
- <xref target="LSControl-Summary" /> contains examples of the
message
- format for this exchange. It is left up to the implementation
when
- the summarization occurs (i.e. at message send time, or also as a
- periodic event).
+ <xref target="LSControl-Summary-lower" /> and
+ <xref target="LSControl-Summary-upper" />contains examples of
the
+ message format for this exchange. It is left up to the
+ implementation when the summarization occurs (i.e. at message
+ send time, or also as a periodic event).
</t>
-
+
+
+
</section>

<section anchor="Leader_Election" title="Leader election">
+
<t>
- Building on the previous algorithms, we turn our attention to the
- upper scope. This logical ring should consist of one
- representative from each of the lower scopes. This representative
- will be selected based on the 'contentSize' parameter, which as we
- have discussed previously is a count of the number of metadata
- elements the LS is responsible for.
+ The most important role of the lower ring nodes is electing a
leader
+ to serve in the upper levels. This logical ring should consist
of
+ one representative from each of the lower scopes. This
+ representative will be selected based on the "contentSize"
+ parameter, which as we have discussed previously is a count of
the
+ number of metadata elements the LS is responsible for. We choose
+ this parameter primarily because it imposes a very simple
ordering
+ on the nodes, and allows us to choose the "least busy" node for
+ performing more important work.
</t>

-<t><vspace blankLines="2" />START_NOTE (Maciej 10/3/07):<vspace
blankLines="1" />
-Basing on contentSize may be not reliable. See one of previous comments.
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
-
<t>
The theory behind this choice of leader is that unladen LS
instances
will not be as loaded processing requests and responses from
clients
and other services, thus the choice to name them as leaders is
- natural. This also allows a domain to impose leadership on a
- specific LS by having it not accept registrations for example, and
- only serving in the leader role.
+ natural. An added feature of this criteria is that it becomes
very
+ simple to designate a leader LS for a domain; simply deploy an LS
+ instance that does not accept registrations. This service will
only
+ serve in the role of liaison to the upper level.
</t>
-
+
<t>
All LS instances will have a complete view at any given time (and
- updated over time) of the values of the 'contentSize' parameter for
- all peer LS instances in an LSRing. This ensures that the 'Leader'
- and 'Vice-Leader' are always known. Explicit election is therefore
+ updated over time) of the values of the "contentSize" parameter for
+ all peer LS instances in an LSRing. This ensures that the "Leader"
+ and "Vice-Leader" are always known. Explicit election is therefore
not required, and succession can pass between the two executives
quickly.
</t>
@@ -480,13 +693,34 @@
level will still have a link to the upper level (see
<xref target="LSControl-Leader" />). A Vice-Leader will be
monitoring
the time between successive communications from the Leader to be
sure
- it has not failed. In the event that it has, the 'Join' procedure
+ it has not failed. In the event that it has, the "Join" procedure
will start to the upper level to keep the hierarchy complete.
</t>
-
- </section>
+
+<t><vspace blankLines="2" />START_NOTE (Maciej 10/3/07):<vspace
blankLines="1" />
+ Question: I am not convinced "contentSize" should be the only criterion.
+ When new LS joins the ring it may have empty database, but in some time
+ it'll get a lot of metadata. The mechanism of leader election bases on
that, so
+ its quite important. If such LS will "update" its "contentSize" value not
all
+ other LS-es may know about it immediately (token passing cycle) and they
may
+ not have the same knowledge about the leader. I"d prefer more
deterministic
+ way of leader election.
+<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
+
+<t><vspace blankLines="2" />START_NOTE (Jason 10/4/07):<vspace
blankLines="1" />
+I have added some more reasoning behind this, as well as a pointer to some
+literature from the Gnutella folks as to why this is a good method. I am
not in
+favor of something complex when calculating a leader; we must choose
something
+that everyone can figure out [instantly] so that the ring continues to
function
+even during times when bad things are happening. Everyone will be able to
see (at
+any given time) how much information someone has, and the notion that an
unburdened
+system should be given more work (as opposed to a system that may be very
busy with
+local queries yet chosen anyway based on separate criteria) is very
appealing.
+<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
+
+ </section>

- <section anchor="scopes" title="Scopes">
+ <section anchor="scopes" title="scopes">

<t>Scopes are named based on URIs. The top-level domain provides a
natural basis for the formation of these URIs. These URIs may be
@@ -495,7 +729,7 @@
domain level and below the root, but that is left for future work.
Note: I would like to see this be something like:
<eref
target="http://lsls.perfsonar.net/master/internet2.edu/";>http://lsls.perfsonar.net/master/internet2.edu/</eref>.

- Actual syntax doesn't matter that much but I would like the
+ Actual syntax doesn"t matter that much but I would like the
following components:

<list style="numbers">
@@ -514,17 +748,13 @@

</section>

+
+
+


<section anchor="search" title="Search">

-
-<t><vspace blankLines="2" />START_NOTE (Jason 9/18/07):<vspace
blankLines="1" />
- Question 4) I think we should go with one algorithm here, and
'improvements' to the
- protocol in the future can give us two. Can we just pick iterative and
- only explain that?
-<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></t>
-
<t>The search operation is obviously critical to the Lookup Service's
function. It is envisioned that searching could take one of two
major forms, iterative and recursive, analogous to those used in
@@ -582,7 +812,7 @@
(upper) scope, then it returns the leader of
its
current scope (or a direct referral to an
instance
of the next-higher scope.) This is
effectively a
- wildcard match saying "I don't know the
answer, but
+ wildcard match saying "I don"t know the
answer, but
I know who might." This is how the Metadata
registered to an LS in another scope
(domain) is
found.
@@ -683,36 +913,52 @@



- <section anchor="structures-and-messages" title="Structures and
Messages">
+ <section anchor="structures-and-messages" title="structures and
Messages">

- <section anchor="service-metadata" title="Service metadata
example">
+ <section anchor="service-metadata" title="service metadata
example">
<t>Example of metadata describing information collected and
stored in
Measurement Archive service</t>
<t>
<artwork>
<![CDATA[
- <inline file="ex1.xml"/>
+ <inline file="metadata.xml"/>
]]>
</artwork>
</t>
</section>

<section anchor="lookup-info" title="Lookup Information">
- <t>Example Lookup Information of Measurement Archive. Metadata
block
+ <t>Example Lookup Information of Measurement Archive. The
metadata block
contains basic service information and data elements
containing
the metadata from the MA.</t>
<t>
<artwork>
<![CDATA[
- <inline file="ex2.xml"/>
+ <inline file="service.xml"/>
]]>
</artwork>
</t>
</section>

<section anchor="LSRing" title="LS Ring File Structure">
- <t>Structure of the 'lower' and 'upper' LSRing files.</t>
+
<t>
+ The LSRing file represents the "state" of the LS cloud at
either
+ level of hierarchy (we avoid using the terms "global" and
"local"
+ here since the hierarchy may be much larger). This file must
start
+ with some static values, and will be added to/deleted from as
time
+ goes on. As such implementations must ensure that this file
is under
+ database control of some sort.
+ </t>
+ <t>
+ Each metadata description contains the usual service level info,
as
+ well as a "voting" parameter (labeled as "contentSize") used to
+ decide who the leader is, and a flag indicating if the current
+ service thinks the remote service is active. Both of these should
+ be updated frequently as reality changes.
+ </t>
+
+ <t>
<artwork>
<![CDATA[
<inline file="LSRing.xml"/>
@@ -722,8 +968,24 @@
</section>

<section anchor="LSControl-Join" title="LS Joining Message for
Joining a Ring">
- <t>Structure of the LSControl messages focused on joining a
ring.</t>
<t>
+ This message exchange represents when a "new" LS instance
+ comes online. The LS will send these messages to its "list" of
+ known LS instances until it gets a hit. The message consists
+ of metadata/data pair(s) that contain service information
+ and a parameter indicating "size" of the data set the LS
+ manages. This will be used for leader voting purposes later.
+ </t>
+ <t>
+ The response message should indicate success or failure via
+ the eventType, and will contain metadata/data pair(s). The
metadata
+ should indicate who the service is, and its "size" for voting
+ purposes. The data section is an enumeration of all of the
current
+ members of the ring and their votes. This information gives the
+ new member a snapshot of the ring.
+ </t>
+
+ <t>
<artwork>
<![CDATA[
<inline file="LSControl-Join.xml"/>
@@ -733,8 +995,19 @@
</section>

<section anchor="LSControl-Token" title="LS Token Message">
- <t>Structure of the LSControl messages serving as the passable
'token'.</t>
<t>
+ This message exchange represents the token that is passed between
+ LS instances in a cloud. The message contains metadata/data
pair(s)
+ wherein the Metadata is the sending LS's info, and the data
contains
+ the contents of the LSRing file (lower or upper depending on the
+ token we are exchanging).
+ </t>
+ <t>
+ The response to this message should indicate success or failure.
+ Failure and timeouts should trigger a resend.
+ </t>
+
+ <t>
<artwork>
<![CDATA[
<inline file="LSControl-Token.xml"/>
@@ -742,12 +1015,89 @@
</artwork>
</t>
</section>
+
+ <section anchor="LSControl-Summary-lower" title="LS Summary
Message (Lower)">

- <section anchor="LSControl-Summary" title="LS Summary Message">
- <t>Structure of the LSControl messages focused on exchanging
summary information.</t>
<t>
+ This message exchange represents when an LS instance is holding
+ the token and sharing summary information (lower scope). The
message
+ consists of metadata/data pair(s) that contain service information
+ and a parameter indicating "size" of the data set the LS
+ manages as well as the minimal (without parameters) summary.
+ </t>
+ <t>
+ The response message should indicate success or failure via
+ the eventType, and will contain metadata/data pair(s). The
metadata
+ should indicate who the service is, and its "size" for leader
voting
+ purposes. The data section is message that can be used for
logging.
+ </t>
+ <t>
+ Caveots:
+ <list type="symbols">
+ <t>These messages are sent to everyone when you get a token.</t>
+
+ <t>These messages are sent to everyone when you come online (and
+ do not necessarily have the token).</t>
+ </list>
+ </t>
+ <t>
+ When receiving the message, check your local list and update it as
+ needed for:
+ <list type="symbols">
+ <t>Do you know of this service? If so make sure the vote and
other
+ info is ok.</t>
+ <t>Update the summary info in your collection</t>
+ <t>If you don"t know of them, add them!</t>
+ </list>
+ </t>
+
+ <t>
<artwork>
<![CDATA[
+ <inline file="LSControl-Summary2.xml"/>
+ ]]>
+ </artwork>
+ </t>
+ </section>
+
+ <section anchor="LSControl-Summary-upper" title="LS Summary
Message (Upper)">
+
+ <t>
+ This message exchange represents when an LS instance is holding
+ the token and sharing summary information. The message
+ consists of metadata/data pair(s) that contain service information
+ and a parameter indicating "size" of the data set the LS
+ manages. The "data" portion is the summary info (FORMAT TBD!!!)
+ </t>
+ <t>
+ The response message should indicate success or failure via
+ the eventType, and will contain metadata/data pair(s). The
metadata
+ should indicate who the service is, and its "size" for leader
voting
+ purposes. The data section is message that can be used for
logging.
+ </t>
+ <t>
+ Caveots:
+ <list type="symbols">
+ <t>These messages are sent to everyone when you get a token.</t>
+
+ <t>These messages are sent to everyone when you come online (and
+ do not necessarily have the token).</t>
+ </list>
+ </t>
+ <t>
+ When receiving the message, check your local list and update it as
+ needed for:
+ <list type="symbols">
+ <t>Do you know of this service? If so make sure the vote and
other
+ info is ok.</t>
+ <t>Update the summary info in your collection</t>
+ <t>If you don"t know of them, add them!</t>
+ </list>
+ </t>
+
+ <t>
+ <artwork>
+ <![CDATA[
<inline file="LSControl-Summary.xml"/>
]]>
</artwork>
@@ -755,9 +1105,21 @@
</section>

<section anchor="LSControl-Leader" title="LS Leader Message">
- <t>Structure of the LSControl messages dealing with when a
Leader needs to inform the Vice-Leader
- of the summaries from above.</t>
+
<t>
+ This message exchange will be conducted between the Leader and
+ Vice-Leader on some (frequent) interval. It may even become a
part
+ of the Leader's token exchange with the Upper Level.
+ </t>
+ <t>
+ The leader identifies itself, and sends down the summaries from the
+ upper level for the Vice-Leader to store. If the leader should
die,
+ the vice leader will have a summary of the upper level and be able
to
+ continue answering lower level queries and obtaining information
from
+ the higher levels.
+ </t>
+
+ <t>
<artwork>
<![CDATA[
<inline file="LSControl-Leader.xml"/>
@@ -767,80 +1129,20 @@
</section>

<section anchor="LSControl-Discovery" title="LS Discovery
Message">
- <t>Structure of the LSDiscovery Message used to locate
info-sets.</t>
+ <t>Structure of the LSDiscovery Message used to locate
info-sets.
+ (FORMAT TBD!!!)</t>
<t>
<artwork>
<![CDATA[
- <inline file="LSControl-Discovery.xml"/>
+ <inline file="LSDiscovery.xml"/>
]]>
</artwork>
</t>
</section>
-
- <section anchor="Message Types" title="Message Types">
- <list style="numbers">
- <t>Discovery - The Discovery request will contain a subject of the
- relevant type. This will essentially be either an ipAddress or
a
- Network (for the query by IP case) or an abstract node with a
- location element expressing the location requirements of
- interest.
- <list style="numbers">
- <t>LSDiscoveryRequest</t>
- <t>LSDiscoveryResponse
- <list style="numbers">
- <t>Success</t>
- <t>Refer</t>
- <t>Failure</t>
- </list>
- </t>
- </list>
- </t>
-
- <t>Token - Token messages will be used to exchange information
- between LS instances. The can be specialized (by eventType)
- to handle different tasks such as Joining, exchanging summary
- information, or used for leader communication.
- <list style="numbers">
- <t>LSControlRequest</t>
- <t>LSControlResponse
- <list style="numbers">
- <t>Success</t>
- <t>Refer</t>
- <t>Failure</t>
- </list>
- </t>
- </list>
- </t>
-
- <t>Other...
- <list style="numbers">
- <t>LS...Request</t>
- <t>LS...Response
- <list style="numbers">
- <t>Success</t>
- <t>Refer</t>
- <t>Failure</t>
- </list>
- </t>
- </list>
- </t>
-
- </list>
- </section>

</section>

- <section anchor="issues" title="Open Issues">
- <list style="numbers">
- <t>Computing the TTRT </t>
- <t>One LS in multiple domains</t>
- <t>Schema for the token message</t>
- <t>LS to LS registration (describe the message type)</t>

- </list>
- </section>
-
-
<section anchor="apdx" title="Appendices">

@@ -848,7 +1150,7 @@
<list style="symbols">

<t>Service - A Service is an application that communicates with
- other perfSONAR Services via standarized protocol set
+ other perfSONAR Services via standardized protocol set
(SOAP+XML+NMWGv2)</t>

<t>Lookup Service (LS) - The Lookup Service is a key element of the
@@ -879,6 +1181,32 @@
<t>Lower (Local) Scope - The scoping paradigm meant to indicate
inter-domain relationships.</t>

+ <t>XSLT - Extensible Stylesheet Language Transformations is an
+ XML-based language used for the transformation of XML documents
+ into other XML or "human-readable" documents. The original
+ document is not changed; rather, a new document is created
based
+ on the content of an existing one.</t>
+
+ <t>XQuery - A query language (with some programming language
+ features) that is designed to query collections of XML data. It
+ is semantically similar to SQL.</t>
+
+ <t>Token Ring - A ring network in which the network topology
features
+ nodes connected to exactly two other nodes, forming a circular
+ pathway for signals: a ring. Data travels from node to node,
+ with each node handling every packet. We use a logical ring in
+ which a "token" message is used to synchronize the
communication
+ among the nodes.</t>
+
+ <t>Berkeley DB XML - Oracle Berkeley DB XML is an open source,
+ embeddable XML database with XQuery-based access to documents
+ stored in containers and indexed based on their content.</t>
+
+ <t>eXist XML DB - eXist is an Open Source native XML database
+ featuring efficient, index-based XQuery processing, automatic
+ indexing, extensions for full-text search, XUpdate support,
+ XQuery update extensions and tight integration with existing
+ XML development tools.</t>
</list>
</section>

Deleted: trunk/nmwg/doc/dLS/ex1.xml

Deleted: trunk/nmwg/doc/dLS/ex2.xml

Added: trunk/nmwg/doc/dLS/metadata.xml

Modified: trunk/nmwg/doc/dLS/rfc2629.xslt
===================================================================
--- trunk/nmwg/doc/dLS/rfc2629.xslt 2007-10-03 13:22:11 UTC (rev 281)
+++ trunk/nmwg/doc/dLS/rfc2629.xslt 2007-10-05 02:32:28 UTC (rev 282)
@@ -1682,10 +1682,10 @@
<xsl:param name="mode" />

<xsl:if test="not($xml2rfc-private)">
- <myns:item>Network Measurement Working Group</myns:item>
+ <myns:item>perfSONAR</myns:item>
<myns:item>
<xsl:choose>
- <xsl:when test="/rfc/@ipr">Internet Draft</xsl:when>
+ <xsl:when test="/rfc/@ipr">Protocol Draft</xsl:when>

</xsl:choose>
</myns:item>
@@ -2880,7 +2880,7 @@
</xsl:when>
<xsl:when test="/rfc/@category='info' or not(/rfc/@category)">
<t>
- This memo provides information for the Grid community.
+ This memo provides information for the perfSONAR community.
It does not specify any standards or technical recommendations.
Distribution is unlimited.
</t>
@@ -2908,7 +2908,7 @@
Copyright © The IETF Trust (<xsl:value-of
select="/rfc/front/date/@year" />). All Rights Reserved.
</xsl:when>
<xsl:otherwise>
- Copyright © The Open Grid Forum (<xsl:value-of
select="/rfc/front/date/@year" />). All Rights Reserved.
+ Copyright © The perfSONAR Consortium (<xsl:value-of
select="/rfc/front/date/@year" />). All Rights Reserved.
</xsl:otherwise>
</xsl:choose>
</t>

Copied: trunk/nmwg/doc/dLS/service.xml (from rev 281,
trunk/nmwg/doc/dLS/ex2.xml)

nmwg: r282 - trunk/nmwg/doc/dLS, svnlog, 10/04/2007

List archive

nmwg: r282 - trunk/nmwg/doc/dLS