rfc9034v4.xml   rfc9034.xml 
skipping to change at line 472 skipping to change at line 472
leads to a small Epoch_Range; if DTL = 0, there will only be 16 RTUs leads to a small Epoch_Range; if DTL = 0, there will only be 16 RTUs
within the Epoch_Range (i.e., Epoch_Range(DTL) = 16<sup>1</sup>) for any TU. The within the Epoch_Range (i.e., Epoch_Range(DTL) = 16<sup>1</sup>) for any TU. The
values that can be represented in the current epoch are in the range values that can be represented in the current epoch are in the range
[0, (Epoch_Range(DTL) - 1)].</t> [0, (Epoch_Range(DTL) - 1)].</t>
<t> <t>
Assuming wraparound does not occur, OT is represented by the value (OT m od Epoch_Range), Assuming wraparound does not occur, OT is represented by the value (OT m od Epoch_Range),
and DT is represented by the value (DT mod Epoch_Range). All arithmetic is and DT is represented by the value (DT mod Epoch_Range). All arithmetic is
to be performed modulo (Epoch_Range(DTL)), yielding only positive to be performed modulo (Epoch_Range(DTL)), yielding only positive
values for DT - OT. values for DT - OT.
</t> </t>
<t> <t>
In order to allow fine-grained control over the setting of the In order to allow fine-grained control over the setting of the
deadline time, it is required to allow fractional seconds to be deadline time, it is required to allow fractional seconds to be
used in the fields for DT and OTD. This is done by specifying used in the fields for DT and OTD. This is done by specifying
a binary point which allocates some of the bits for fractional times. a binary point, which allocates some of the bits for fractional times.
Thus, all such fractions are restricted to be negative powers of 2. Thus, all such fractions are restricted to be negative powers of 2.
Each point of time between OT and DT is then represented by a time Each point of time between OT and DT is then represented by a time
unit (either seconds or ASNs) and a fractional time unit. unit (either seconds or ASNs) and a fractional time unit.
</t> </t>
<t> <t>
Let OT_abs, DT_abs, and CT_abs denote the true (absolute) values (on the Let OT_abs, DT_abs, and CT_abs denote the true (absolute) values (on the
synchronized timelines) for Origination Time and Deadline Time, and synchronized timelines) for OT, DT, and
Current Time. Let N be the number of bits to be used to represent current time. Let N be the number of bits to be used to represent
the integer parts of OT_abs, DT_abs, and CT_abs; the integer parts of OT_abs, DT_abs, and CT_abs:
</t> </t>
<dl spacing="compact"> <t indent="6">N = {4*(DTL+1)/2} + BinaryPt </t>
<dt>N = </dt> <dd> {4*(DTL+1)/2} + BinaryPt </dd>
</dl>
<t> <t>
The originating node has to pick a segment size (2^N) so that The originating node has to pick a segment size (2^N) so that
DT_abs - OT_abs &lt; 2^N, and so that intermediate network nodes DT_abs - OT_abs &lt; 2^N, and so that intermediate network nodes
can detect whether or not CT_abs &gt; DT_abs. can detect whether or not CT_abs &gt; DT_abs.
</t> </t>
<t> <t>
Given a value for N, the value for DT is represented in the Given a value for N, the value for DT is represented in the
deadline-time format is by DT = (DT_abs mod 2^N). DT is typically deadline-time format by DT = (DT_abs mod 2^N). DT is typically
represented as a positive value (even though negative modular represented as a positive value (even though negative modular
values make sense). Also, let OT = OT_abs mod 2^N and values make sense). Also, let OT = OT_abs mod 2^N and
CT = CT_abs mod 2^N, both OT and CT also considered as CT = CT_abs mod 2^N, where both OT and CT are also considered as
non-negative values. non-negative values.
</t> </t>
<t> <t>
When the packet is launched by the originating node (Orig_Node), When the packet is launched by the originating node (Orig_Node),
CT_abs == OT_abs and CT == OT. Given a particular value for N, CT_abs == OT_abs and CT == OT. Given a particular value for N,
then in order for downstream nodes to detect whether or not the then in order for downstream nodes to detect whether or not the
deadline has expired (i.e., whether DT_abs > CT_abs), it is deadline has expired (i.e., whether DT_abs > CT_abs), the following is
required that (***) DT_abs - OT_abs &lt; 2^N. Otherwise the ambiguity required:
</t>
<t indent="6" anchor="assumption">Assumption 1: DT_abs - OT_abs &lt; 2^N.</t
>
<t>
Otherwise the ambiguity
inherent in the modulus arithmetic yielding OT and DT will cause inherent in the modulus arithmetic yielding OT and DT will cause
failure: one cannot measure time differences greater than 2^N using failure: one cannot measure time differences greater than 2^N using
numbers in a time segment of length less than 2^N. numbers in a time segment of length less than 2^N.
</t> </t>
<t> <t>
Under the assumption (***), downstream nodes must effectively check Under <xref target="assumption" format="none">Assumption 1</xref>, downst
whether or not their Current Time is later than the Deadline Time ream nodes must effectively check
-- but the value of the Deadline Time has to be inferred from the whether or not their current time is later than the DT -- but
the value of the DT has to be inferred from the
value of DT in the 6LoRHE, which is a number less than 2^N. This value of DT in the 6LoRHE, which is a number less than 2^N. This
inference cannot be expected to reliably succeed unless assumption (***) inference cannot be expected to reliably succeed unless <xref target="ass
is valid, which means that Orig_Node has to be careful to pick proper umption" format="none">Assumption 1</xref>
is valid, which means that the Orig_Node has to be careful to pick proper
values for DTL and for BinaryPt. values for DTL and for BinaryPt.
</t> </t>
<t> <t>
Since OT is not necessarily provided in the 6loRHE, there may be a Since OT is not necessarily provided in the 6loRHE, there may be a
danger of ambiguity. Surely, when DT = CT, the deadline time danger of ambiguity. Surely, when DT = CT, the deadline time
is expiring and the packet should be dropped. But what if an is expiring and the packet should be dropped. However, what if an
intermediate node measures that CT = DT+1? Was the packet intermediate node measures that CT = DT+1? Was the packet
launched a short time before arrival at the intermediate node, launched a short time before arrival at the intermediate node,
or has the current time wrapped around so that or has the current time wrapped around so that
CT_abs - OT_abs &gt; 2^N? CT_abs - OT_abs &gt; 2^N?
</t> </t>
<t> <t>
In order to solve this problem, a safety margin has to be provided, In order to solve this problem, a safety margin has to be provided,
in addition to requiring that DT_abs - OT_abs &lt; 2^N. The value in addition to requiring that DT_abs - OT_abs &lt; 2^N. The value
of this safety margin is proportional to 2^N and is determined by of this safety margin is proportional to 2^N and is determined by
skipping to change at line 607 skipping to change at line 608
o | | router | | router o | | router | | router
+-----+ +-----+ +-----+ +-----+
o o o o o o
o o o o o o o o o o o o o o o o o o
o LLN o o LLN o o o LLN o o LLN o o
o o o o o o o o o o o o o o o o o o
6LoWPAN Network (subnet N1) 6LoWPAN Network (subnet N2) 6LoWPAN Network (subnet N1) 6LoWPAN Network (subnet N2)
]]></artwork> ]]></artwork>
</figure> </figure>
<section numbered="true" toc="default"> <section numbered="true" toc="default">
<name>Scenario 1: Endpoints in the same DODAG (N1)</name> <name>Scenario 1: Endpoints in the Same DODAG (N1)</name>
<t> <t>
In Scenario 1, shown in <xref target="fig4" format="default"/>, the Sende r 'S' has an In Scenario 1, shown in <xref target="fig4" format="default"/>, the Sende r 'S' has an
IP datagram to be routed to a Receiver 'R' within IP datagram to be routed to a Receiver 'R' within
the same Destination-Oriented Directed Acyclic Graph (DODAG). the same Destination-Oriented Directed Acyclic Graph (DODAG).
For the route segment from the sender to the 6LBR, the sender For the route segment from the sender to the 6LBR, the sender
includes a Deadline-6LoRHE by encoding the deadline time includes a Deadline-6LoRHE by encoding the deadline time
contained in the packet. Subsequently, each 6LR will perform hop-by-hop contained in the packet. Subsequently, each 6LR will perform hop-by-hop
routing to forward the packet towards the 6LBR. Once the 6LBR receives routing to forward the packet towards the 6LBR. Once the 6LBR receives
the IP datagram, it sends the packet downstream towards 'R'. the IP datagram, it sends the packet downstream towards 'R'.
</t> </t>
skipping to change at line 1084 skipping to change at line 1085
<!-- [I-D.ietf-6lo-blemesh] IESG state Publication Requested as of 2020 Sept 1 --> <!-- [I-D.ietf-6lo-blemesh] IESG state Publication Requested as of 2020 Sept 1 -->
<xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D .ietf-6lo-blemesh-10.xml"/> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D .ietf-6lo-blemesh-10.xml"/>
</references> </references>
</references> </references>
<section anchor="modular" title="Modular Arithmetic Considerations"> <section anchor="modular" title="Modular Arithmetic Considerations">
<t> <t>
Graphically, one might visualize the timeline as follows: Graphically, one might visualize the timeline as follows:
</t> </t>
<figure anchor="fig7" title="Absolute time line representation"> <figure anchor="fig7" title="Absolute Timeline Representation">
<artwork><![CDATA[ <artwork><![CDATA[
OT_abs CT_abs DT_abs OT_abs CT_abs DT_abs
-------|-------------|-------------|------------------>]]> -------|-------------|-------------|------------------>]]>
</artwork> </artwork>
</figure> </figure>
<t> <t>
In <xref target="fig7"/>, the value of CT_abs is envisioned In <xref target="fig7"/>, the value of CT_abs is envisioned
as traveling to the right as time progresses, getting farther away as traveling to the right as time progresses, getting farther away
from OT_abs and getting closer to DT_abs. The timeline is considered from OT_abs and getting closer to DT_abs. The timeline is considered
to be subdivided into time subintervals [i,j] starting and ending at to be subdivided into time subintervals [i,j] starting and ending at
absolute times equal to k*(2^N), for integer values of k. Let absolute times equal to k*(2^N), for integer values of k. Let
I_k = k*(2^N) and I_(k+1) = (k+1)*2^N. Intervals starting at I_k I_k = k*(2^N) and I_(k+1) = (k+1)*2^N. Intervals starting at I_k
and I_(k+1) may occur at various placements in the above timeline. and I_(k+1) may occur at various placements in the above timeline.
Even though OT_abs is *always* less than DT_abs, it could be that Even though OT_abs is <em>always</em> less than DT_abs, it could be that
DT &lt; OT because of the way that DT and OT are represented within DT &lt; OT because of the way that DT and OT are represented within
the range [0, 2^N). Similarly for CT_abs and CT compared to OT and DT. the range [0, 2^N) and similarly for CT_abs and CT compared to OT and DT.
</t> </t>
<t> <t>
Representing the above situation in time segments of length 2^N Representing the above situation in time segments of length 2^N
(and values OT, CT, DT) results in several cases where the deadline (and values OT, CT, DT) results in several cases where the deadline
time has not elapsed: time has not elapsed:
</t> </t>
<dl> <dl>
<dt> 1) OT &lt; CT &lt; DT </dt> <dt> 1) OT &lt; CT &lt; DT </dt>
<dd> (e.g, I_k &lt; OT_abs &lt; CT_abs &lt; DT_abs &lt; I_(k+1) ) < /dd> <dd> (e.g., I_k &lt; OT_abs &lt; CT_abs &lt; DT_abs &lt; I_(k+1) ) </dd>
<dt> 2) DT &lt; OT &lt; CT </dt> <dd>(e.g, I_k &lt; OT_abs &lt; CT_abs <dt> 2) DT &lt; OT &lt; CT </dt> <dd>(e.g., I_k &lt; OT_abs &lt; CT_abs
&lt; I_(k+1) &lt; DT_abs ) </dd> &lt; I_(k+1) &lt; DT_abs ) </dd>
<dt> 3) CT &lt; DT &lt; OT </dt> <dd> (e.g, I_k &lt; OT_abs &lt; I_(k+1) <dt> 3) CT &lt; DT &lt; OT </dt> <dd> (e.g., I_k &lt; OT_abs &lt; I_(k+1
&lt; CT_abs &lt; DT_abs ) </dd> ) &lt; CT_abs &lt; DT_abs ) </dd>
</dl> </dl>
<t> <t>
In the following cases, the deadline time has elapsed and the In the following cases, the deadline time has elapsed and the
packet should be dropped. packet should be dropped.
</t> </t>
<dl> <dl>
<dt> 4) DT &lt; CT &lt; OT </dt> <dd></dd> <dt> 4) DT &lt; CT &lt; OT </dt> <dd></dd>
<dt> 5) OT &lt; DT &lt; CT </dt> <dd></dd> <dt> 5) OT &lt; DT &lt; CT </dt> <dd></dd>
<dt> 6) CT &lt; OT &lt; DT </dt> <dd></dd> <dt> 6) CT &lt; OT &lt; DT </dt> <dd></dd>
</dl> </dl>
skipping to change at line 1136 skipping to change at line 1137
moving away from OT_abs and towards DT_abs. moving away from OT_abs and towards DT_abs.
For times CT_abs before the expiration of the deadline time, we also For times CT_abs before the expiration of the deadline time, we also
have CT_abs - OT_abs == CT - OT mod 2^N and similarly for DT_abs - have CT_abs - OT_abs == CT - OT mod 2^N and similarly for DT_abs -
CT_abs. CT_abs.
</t> </t>
<t> <t>
As time proceeds, DT_abs - CT_abs gets smaller. When the deadline time As time proceeds, DT_abs - CT_abs gets smaller. When the deadline time
expires, DT_abs - CT_abs begins to grow negative. A proper selection expires, DT_abs - CT_abs begins to grow negative. A proper selection
for SAFETY_FACTOR allows it to go for SAFETY_FACTOR allows it to go
*slightly negative* but for an intermediate point to *detect* that it <em>slightly negative</em> but for an intermediate point to <em>detect</e m> that it
has gone negative. has gone negative.
Note that in modular arithmetic, "slightly negative" means *exactly* Note that in modular arithmetic, "slightly negative" means <em>exactly</e m>
the same as "almost as large as the modulus (i.e., 2^N)". the same as "almost as large as the modulus (i.e., 2^N)".
Now consider the test condition Now consider the test condition
((CT - DT) mod 2^N) > SAFETY_FACTOR*2^N. ((CT - DT) mod 2^N) > SAFETY_FACTOR*2^N.
</t> </t>
<t> <t>
(DT_abs - OT_abs) &lt; 2^N*(1-SAFETY_FACTOR) satifies the test (DT_abs - OT_abs) &lt; 2^N*(1-SAFETY_FACTOR) satifies the test
condition when CT_abs == OT_abs (i.e., when the packet it launched). condition when CT_abs == OT_abs (i.e., when the packet is launched).
In modular arithmetic, 2^N*(1-SAFETY_FACTOR) == In modular arithmetic, 2^N*(1-SAFETY_FACTOR) ==
2^N - 2^N*SAFETY_FACTOR == -2^N*(SAFETY_FACTOR). 2^N - 2^N*SAFETY_FACTOR == -2^N*(SAFETY_FACTOR).
Then DT_abs - OT_abs &lt; -2^N*(1-SAFETY_FACTOR). Then DT_abs - OT_abs &lt; -2^N*(1-SAFETY_FACTOR).
Inverting the inequality, Inverting the inequality,
OT_abs - DT_abs > 2^N*(1-SAFETY_FACTOR), and thus at OT_abs - DT_abs > 2^N*(1-SAFETY_FACTOR), and thus at
launch CT_abs - DT_abs > 2^N*(1-SAFETY_FACTOR). launch CT_abs - DT_abs > 2^N*(1-SAFETY_FACTOR).
</t> </t>
<t> <t>
As CT_abs grows larger, CT_abs - DT_abs gets LARGER in (non-negative) As CT_abs grows larger, CT_abs - DT_abs gets LARGER in (non-negative)
modular arithmetic until the time at which CT_ABS == DT_ABS, and modular arithmetic until the time at which CT_ABS == DT_ABS, and
suddenly CT_ABS - DT_abs becomes zero. And, suddenly, the test suddenly CT_ABS - DT_abs becomes zero. Also suddenly, the test
condition is no longer fulfilled. condition is no longer fulfilled.
</t> </t>
<t> <t>
As CT_abs grows still larger, CT_abs > DT_abs, and we need to detect As CT_abs grows still larger, CT_abs > DT_abs, and we need to detect
this condition as soon as possible. Requiring the SAFETY_FACTOR this condition as soon as possible. Requiring the SAFETY_FACTOR
enables this detection until CT_abs exceeds DT_abs enables this detection until CT_abs exceeds DT_abs
by an amount equal to SAFETY_FACTOR*2^N. by an amount equal to SAFETY_FACTOR*2^N.
</t> </t>
skipping to change at line 1180 skipping to change at line 1181
A note about "inverting the inequality". Observe that a &lt; b A note about "inverting the inequality". Observe that a &lt; b
implies that -a > -b on the real number line. Also, implies that -a > -b on the real number line. Also,
(a - b) == -(b - a). These facts hold also for modular arithmetic. (a - b) == -(b - a). These facts hold also for modular arithmetic.
</t> </t>
<t> <t>
During the times prior to the expiration of the deadline, for During the times prior to the expiration of the deadline, for
Safe = 2^N*SAFETY_FACTOR we have: Safe = 2^N*SAFETY_FACTOR we have:
</t> </t>
<t> <t indent="6">
(DT_abs - 2^N) &lt; OT_abs &lt; CT_abs &lt; DT_abs &lt; DT_abs+Safe (DT_abs - 2^N) &lt; OT_abs &lt; CT_abs &lt; DT_abs &lt; DT_abs+Safe
</t> </t>
<t> <t>
Naturally DT_abs - 2^N == DT_abs mod 2^N == DT. Naturally, DT_abs - 2^N == DT_abs mod 2^N == DT.
</t> </t>
<t> <t>
Again considering <xref target="fig7"/>, it is easy to see Again considering <xref target="fig7"/>, it is easy to see
that {CT_abs - (DT_abs - 2^N)} gets larger and larger until the time that {CT_abs - (DT_abs - 2^N)} gets larger and larger until the time
at which CT_abs = DT_abs, which is the first time at which at which CT_abs = DT_abs, which is the first time at which
CT - DT == 0 mod 2^N. As CT_abs increases past the deadline time, CT - DT == 0 mod 2^N. As CT_abs increases past the deadline time,
0 &lt; CT_abs - DT_abs &lt; Safe. In this range, any intermediate 0 &lt; CT_abs - DT_abs &lt; Safe. In this range, any intermediate
node can detect that the deadline has expired. As CT_abs increases node can detect that the deadline has expired. As CT_abs increases
past DT_abs+Safe, it is no longer possible for an intermediate node past DT_abs+Safe, it is no longer possible for an intermediate node
 End of changes. 22 change blocks. 
33 lines changed or deleted 37 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/