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

Subject: perfsonar development work

List archive

nmwg: r287 - trunk/nmwg/doc/dLS

From:
To: ,
Subject: nmwg: r287 - trunk/nmwg/doc/dLS
Date: Wed, 10 Oct 2007 09:14:31 -0400

Author: szymon
Date: 2007-10-10 09:14:31 -0400 (Wed, 10 Oct 2007)
New Revision: 287

Modified:
trunk/nmwg/doc/dLS/dLS.xml
Log:
Second pass with more changes

Modified: trunk/nmwg/doc/dLS/dLS.xml
===================================================================
--- trunk/nmwg/doc/dLS/dLS.xml 2007-10-09 10:20:58 UTC (rev 286)
+++ trunk/nmwg/doc/dLS/dLS.xml 2007-10-10 13:14:31 UTC (rev 287)
@@ -111,9 +111,9 @@

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

- 
-
- <section anchor="summary" title="Summarization">
+ 
+
+ <section anchor="overview" title="Overview">
<t>The first step of information flow is when a pS 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
@@ -132,10 +132,21 @@
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
+ are rapidly changing metadata like the most recent timestamp and
full details of data stored in long-term archival MAs.
</t>
+
+ <t>The architecture of the dLS protocol assumes the existence of
logical
+ rings of LS instances. The current proposal involves two
levels of rings:
+ lower scope and upper scope. Lower scope hides
inter-domain relationships
+ between LS instances while upper scope hides intra-domain
relationships.
+ </t>
+
+ </section>
+
+ 

+ <section anchor="summary" title="Summarization">
<t>
The LS that a service contacts to register becomes the "Home LS"
(HLS, see <xref target="glossary" />) of that particular service.
@@ -212,9 +223,8 @@
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.
+ ring. The holder of the token will then perform the
information
+ exchange to other known instances (see <xref target="glossary"
/>).
</t>

<figure anchor="hls-cloud">
@@ -265,7 +275,7 @@

<section anchor="upper_scope_summarization" title="Upper Scope
Summarization">
<t>
- A designated member of each lower ring will be required to
interact
+ A designated member of each lower scope will be required to
interact
with the upper scope. The mechanics of how we learn who is the
designated leader is discussed in <xref target="tokens" />. The
leader of each lower scope (and the designated backup) will be
responsible
@@ -281,7 +291,7 @@
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" />).
+ Radix Tree (see <xref target="IP-summary" />).
</t>

<t>
@@ -361,11 +371,7 @@



- <section anchor="scope" title="Scope">
- <t>The architecture of the dLS protocol assumes the existence
of logical
- rings of LS instances. The current proposal involves two
levels of rings:
- lower scope and upper scope.
- </t>
+ <section anchor="scope" title="Scope Forming">

<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
@@ -406,18 +412,19 @@
<section anchor="join" title="Join Procedure">
<t>
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.
+ knowledge of potential peers (both inter and intra domain). This
+ information is contained in LSRing file (see
+ <xref target="LSRing" />). 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.
</t>

<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
- <xref target="LSControl-Join" />) is seen. The LS will search
though
- the successful response to this message and update its LSRing
with
+ A candidate LS will continuously search it's LSRing information
and
+ send an LSControl mesage to its know LS instances with a "join"
eventType
+ (see <xref target="LSControl-Join" />) until a successful
response
+ is seen. The LS candidate will then search through
+ the successful LSControlResponse 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
@@ -428,21 +435,23 @@
</t>

<t>
- 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
+ After updating, the newly joined LS will broadcast another
LSControl message with
+ a "summary" eventType (see <xref
target="LSControl-Summary-lower" />,
+ or if 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).
+ LS instances from its LSRing. Again the responses will be
parsed
+ to get any useful updated information. At the end of this
process
+ joining LS will possess an LSRing file reflecting the state of
the
+ dLS cloud. Each of the recipient LS instances which hasn't
heard
+ anything from this joining LS previously will do the same,
+ including adding this new member to their own lists (as they
+ didn't know of it's existence yet).
</t>

<t>
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.
+ it has not seen one in a very long time (see <xref
target="tokens" />).
</t>

<section anchor="join_algorithm" title="Join Algorithm">
@@ -456,9 +465,9 @@
| |
| |
__V__ _____ _V___
-| | | | (1) | |
-| LS3 | <----------------- | LS2 | <________________> | LS1 |
-|_____| |_____| (2,3) |_____|
+| | | | <_______(1)_______ | |
+| LS3 | <----------------- | LS2 | | LS1 |
+|_____| |_____| _______(3)_______> |_____|
| ^ ^ ^ ^
| | | | |
| _____ | | | |
@@ -476,20 +485,24 @@
</t>

<list type="symbols">
- <t>1. LS1 - "candidate" sends LSControlRequest message with
+ <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>
+ selected LS2 which is already a member of the ring.
+ LS2 was found in LSRing initial file during
bootstrapping
+ process.</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:
+ to accept it or not. A security policy may occur
here.</t>
+ <t>3. LS2 sends the LSControlResponse answer indicating
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 parses
+ the results of LSControlResponse to discover all
members
+ of its scope.</t>
+ <t>5. LS1 broadcast its summary info (lower or upper) with
+ LSControl message with
http://perfsonar.net/services/LS/summary
+ eventType 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
@@ -500,9 +513,9 @@
this knowledge cycles away from being recognized.</t>
</list>
</t>
- <t>6. All members of the ring will process the summaries,
save
+ <t>6. All members of the ring process the summaries, save
the necessary information, and recognize the new peer.

- Responses will be prepared for LS1.</t>
+ Responses are sent to LS1.</t>

 | LS3 | --------| |
+ |_____| <___(3)___|
+
+
+
+ </artwork>
+ </figure>
+
+ <t>Let's assume LS1, LS2 and LS3 are in the ring. LS1 receives a
token.
+ </t>
+
<t>The algorithm for token passing works as follows.

- <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. 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 type="numbers">
+ <t>LS1 receives the token i.e. LSControlRequest message
+ with the http://perfsonar.net/services/LS/token/
+ eventType from its predecessor L3.</t>
+ <t>LS1 updates its local peer list based on token content.</t>
+ <t>LS1 sends LSControlRequest message with the
+ http://perfsonar.net/services/LS/summary/ eventType
+ to all peers in the lease (excluding itself).</t>
+ <t>LS2 receiving this message checks its collection and
updates it
+ if necessary with service info including "contentSize".</t>
+ <t>LS1 waits for some amount of time.</t>
+ <t>LS1 sends token to next LS (LS2) from the LSRing lower
scope
+ (if it fails, try next one).</t>
</list>

</t>
@@ -616,7 +661,7 @@

- <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:
@@ -659,9 +704,9 @@
<section anchor="Leader_Election" title="Leader election">

<t>
- The most important role of the lower ring nodes is electing a
leader
+ The most important role of the lower scope 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
+ one representative LS 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
@@ -690,13 +735,14 @@
</t>

<t>
- The Leader and Vice-Leader LS instances should exchange messages
+ The Leader and Vice-Leader LS instances should exchange messages
+ (see <xref target="LSControl-Leader" />)
periodically to ensure that in the event of a failure the lower
- 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
- will start to the upper level to keep the hierarchy complete.
+ level will still have a link to the upper level. 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.
</t>

<t><vspace blankLines="2" />START_NOTE (Maciej 10/3/07):<vspace
blankLines="1" />
@@ -722,7 +768,7 @@

</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
@@ -731,15 +777,15 @@
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">
- <t>well-known hostname to get the current root.hints from
+ <t>Well-known hostname to get the current root.hints from
(lsls)</t>
- <t>a place holder for where we can break the scope between
+ <t>A place holder for where we can break the scope between
organization and upper levels (master)</t>
- <t>a zero-conf default name for the organization
+ <t>A zero-conf default name for the organization
(internet2.edu)</t>
<t>A way to sub-divide the organization (everything after
trailing / )</t>
@@ -774,11 +820,11 @@
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.

+ down into two distinct phases - Discovery and Metadata Query.

</t>

<section anchor="discovery" title="Discovery Phase">
- <t>The Discovery Phase is used to locate the set of
Authoritative LS
+ <t>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
@@ -814,7 +860,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.
@@ -862,7 +908,7 @@
the query mechanism that is in place with the current LS
implementations.
</t>
- <t>Once we have found the Home LS (or Home LSes) that contain data
+ <t>Once we have found the HLS (or Home LSes) that contain data
in the range of our discovery query, we can pose Metadata
Queries
to each of them. The results will be failure or success.
</t>
@@ -1033,15 +1079,6 @@
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:
@@ -1077,15 +1114,6 @@
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:
@@ -1093,7 +1121,7 @@
<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>
+ <t>If you don't know of them, add them!</t>
</list>
</t>

@@ -1144,6 +1172,16 @@

</section>

+
+ 
+
+ <section anchor="codes" title="Result codes">
+ <list style="symbols">
+ <t>error.ls.foo - </t>
+ <t>success.ls.foo - </t>
+ </list>
+
+ </section>

<section anchor="apdx" title="Appendices">

@@ -1151,13 +1189,17 @@
<section anchor="glossary" title="Glossary">
<list style="symbols">

- <t>AuthotitativeLS - </t>
+ <t>AuthoritativeLS - LS that is an authority for the perfSONAR
+ services in question. AuthoritativeLS is a result of
+ discovery phase and can be used in the metadata query
phase.</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>Bootstraping - </t>
+ <t>Bootstraping - It refers to the process of automatically
finding
+ at service startup other LS instances of the scope utilizing
+ a previously configured registry.</t>

<t>eXist XML DB - eXist is an Open Source native XML database
featuring efficient, index-based XQuery processing, automatic
@@ -1183,13 +1225,17 @@
<t>Lower Scope - The scoping paradigm meant to indicate
inter-domain relationships.</t>

- <t>LSRing - </t>
+ <t>LSRing - Represents the state of the LS cloud listing available
+ LS instances</t>

<t>Multidomain / Distributed Lookup Information (mLS) - Lookup
Service which supports summarization and communication with
other
Lookup Services (which might be in the same domain...)</t>

- <t>P2P - </t>
+ <t>P2P - network infrastucture that does not have fixed clients
and servers,
+ but a number of peer nodes that function as both clients and
servers
+ to the other nodes on the network. This model is contrasted
with the
+ client-server model.</t>

<t>Service - A Service is an application that communicates with
other perfSONAR Services via standardized protocol set

nmwg: r287 - trunk/nmwg/doc/dLS, svnlog, 10/10/2007

List archive

nmwg: r287 - trunk/nmwg/doc/dLS