Skip to Content.
Sympa Menu

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

Subject: perfsonar development work

List archive

nmwg: r281 - trunk/nmwg/doc/dLS


Chronological Thread 
  • From:
  • To: ,
  • Subject: nmwg: r281 - trunk/nmwg/doc/dLS
  • Date: Wed, 3 Oct 2007 09:22:12 -0400
Author: mac
Date: 2007-10-03 09:22:11 -0400 (Wed, 03 Oct 2007)
New Revision: 281

Modified:
trunk/nmwg/doc/dLS/dLS.html
trunk/nmwg/doc/dLS/dLS.pdf
trunk/nmwg/doc/dLS/dLS.xml
Log:
Some changes and comments in Token Passing, Summarization Notification,
Leader Election.



Modified: trunk/nmwg/doc/dLS/dLS.html
===================================================================
--- trunk/nmwg/doc/dLS/dLS.html 2007-10-02 14:35:02 UTC (rev 280)
+++ trunk/nmwg/doc/dLS/dLS.html 2007-10-03 13:22:11 UTC (rev 281)
@@ -372,14 +372,14 @@
</div>
<p>LS Operation</p>
<pre>
- _____ __________
-| | Register/De-register | Service |
+ _____ __________
+| | Register/De-register | Service |
| LS | &lt;------------------------&gt; | Service |
|_____| &lt;--------- |__________|
| _________________
| | |
----------------&gt; | Client/Service |
- Query for Services |_________________|
+ Query for Services |_________________|

</pre>
<p>Services interacting with an LS</p>
@@ -501,9 +501,41 @@
<a href="#rfc.section.2.2.2">2.2.2</a>&nbsp;<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&nbsp;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">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&nbsp;4.6</a>). The responses will be parsed to get any
useful updated information.</p>
-<p id="rfc.section.2.2.2.p.3">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.4">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.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&nbsp;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&nbsp;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>
+<h4 id="rfc.section.2.2.2.1">
+<a href="#rfc.section.2.2.2.1">2.2.2.1</a>&nbsp;<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>&nbsp;<a id="TTRT"
href="#TTRT">TTRT computing algorithm</a>
+</h4>
+<p id="rfc.section.2.2.2.2.p.1">TBD.</p>
<h3 id="rfc.section.2.2.3">
<a href="#rfc.section.2.2.3">2.2.3</a>&nbsp;<a id="summary-blast"
href="#summary-blast">Summarization Notification</a>
</h3>
@@ -515,22 +547,41 @@
<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.3">
<a href="#LSControl-Summary" title="LS Summary Message">Section&nbsp;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.p.5">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.p.6">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.p.7">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.p.8">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&nbsp;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>
-<p id="rfc.section.2.2.p.9">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&nbsp;2.2.4</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.p.10">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.3.p.4">
+<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>END_NOTE:<br>
+<br>
+<br>
+</p>
+<h3 id="rfc.section.2.2.4">
+<a href="#rfc.section.2.2.4">2.2.4</a>&nbsp;<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">
+<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>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&nbsp;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>&nbsp;<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>
<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>
<li>a zero-conf default name for the organization (internet2.edu)</li>
<li>A way to sub-divide the organization (everything after trailing / )</li>
</ol>
-<h3 id="rfc.section.2.2.4">
-<a href="#rfc.section.2.2.4">2.2.4</a>&nbsp;<a id="TTRT" href="#TTRT">TTRT
computing algorithm</a>
-</h3>
-<p id="rfc.section.2.2.4.p.1">TBD.</p>
<h2 id="rfc.section.2.3">
<a href="#rfc.section.2.3">2.3</a>&nbsp;<a id="search"
href="#search">Search</a>
</h2>

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-02 14:35:02 UTC (rev 280)
+++ trunk/nmwg/doc/dLS/dLS.xml 2007-10-03 13:22:11 UTC (rev 281)
@@ -62,14 +62,14 @@
<figure anchor="ls-op">
<preamble>LS Operation</preamble>
<artwork>
- _____ __________
-| | Register/De-register | Service |
+ _____ __________
+| | Register/De-register | Service |
| LS | &lt;------------------------&gt; | Service |
|_____| &lt;--------- |__________|
| _________________
| | |
----------------&gt; | Client/Service |
- Query for Services |_________________|
+ Query for Services |_________________|

</artwork>
<postamble>Services interacting with an LS</postamble>
@@ -356,6 +356,11 @@
instance will know where the next token message should go.
</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
holder to send it's summary information to all available LS
@@ -373,6 +378,13 @@
above and below this value.
</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
@@ -380,6 +392,25 @@
the previous token, any LS instance should see this dispose of
the
duplicate message.
</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>
+ <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>
+
</section>

<section anchor="summary-blast" title="Summarization Notification">
@@ -406,8 +437,12 @@
periodic event).
</t>

+<t><vspace blankLines="2" />START_NOTE (Maciej 10/3/07):<vspace
blankLines="1" />
+ 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).
+<vspace blankLines="1" />END_NOTE:<vspace blankLines="2" /></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
@@ -417,6 +452,10 @@
elements the LS is responsible for.
</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
@@ -445,13 +484,10 @@
will start to the upper level to keep the hierarchy complete.
</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>
+ </section>

+ <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
constructed to allow internal differentiation. In the future, we
may
@@ -474,14 +510,10 @@
</list>
</t>

- <section anchor="TTRT" title="TTRT computing algorithm">
- <t>TBD.</t>
- </section>
-
</section>

+ </section>

-
<!-- Search Section -->

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


  • nmwg: r281 - trunk/nmwg/doc/dLS, svnlog, 10/03/2007

Archive powered by MHonArc 2.6.16.

Top of Page