Discussion:
WIDEn-N implementation rules
(too old to reply)
James Ewen
2009-08-16 18:19:56 UTC
Permalink
Scott,

Here's a little something that I've been meaning to discuss for a few
years now... (yeah, I'm a procrastinator).

First thing, we need to discuss how a UIFLOOD or UITRACE algorithm is
supposed to work, ignoring the callsign insertion portion for the
moment.

Let's just use the usual base alias of WIDE, where the path used by
the user would be in the form of WIDEn-N.

The general concept was for people to set both "n" and "N" to the same
value, where "n" would indicate the number of hops desired when
initiated, and "N" would keep track of the number of hops to go.

AX.25 packet rules limit the value of "N" to a maximum of 7.

So, one would be able to use an outgoing path of anything between
WIDE1-1 and WIDE7-7, and expect it to be acted upon by a digipeater
that supports UIFLOOD or UITRACE.
From there, it was decided by consensus that it would be good to be
able to limit the number of hops supported by a digipeater to keep
users from abusing the network by using excessive "N" hop values. With
a majority of digipeater running on the Kantronics hardware, a
pseudo-trap concept was designed and implemented. Setting UIDIGI
WIDE3-3,WIDE4-4,WIDE5-5,WIDE6-6,WIDE7-7 in the KPC-3 and KPC-3+
hardware captures any of those paths, and does a simple callsign
substitution digipeat. This has the effect of giving a single hop,
overwriting WIDEn-N aliase with the callsign of the digipeater.

The flaw in this design is that Kantronics will digipeat any other
combinations of n-N that do not match exactly with the UIDIGI
settings. If a user sends a packet with an outgoing path of WIDE7-7,
and a single digipeater acts upon the packet, that packet will bypass
the traps, since the packet would be WIDE7-6 or less. Using non
standard n-N values also bypass the traps. Using a path such as
WIDE1-7 will be acted upon by Kantronics TNCs with traps enabled.

The OT2 digipeater rules allow us to setup WIDEn-N digipeating rules,
with hop limits. Setting a hop limit of 3 restricts the action of the
digipeater to packets that have an "N" value of 3 or less. However,
there is no check done on the"n" value, which means that packets with
a higher or lower "n" value will get acted upon. This can cause some
undesirable digipeater action such as when a digipeater is set up to
act as a fill-in digipeater.

Setting ALIAS to WIDE, and HOPLIMIT to 1 should only act upon a packet
with a path of WIDE1-1, however, because the "n" value is not checked,
any packet with an "N" value of 1 is acted upon. This is undesirable
since all packets travelling through the APRS-RF network will end up
with an "N" value of 1 on their last hop. A workaround of setting the
ALIAS of WIDE1 and HOPLIMIT of 1 works to create a digipeater that
only acts upon WIDE1-1, and no other values of "n" when "N" equals 1.

To further expand upon this, one would need to set an ALIAS of WIDE2
and HOPLIMIT of 2 to act upon only WIDE2-2 and WIDE2-1 packet paths.
Setting another ALIAS of WIDE3 and HOPLIMIT of 3 would act upon only
WIDE3-3, WIDE3-2, and WIDE3-1 packet paths.

If however a line of code was added to the firmware that checked to
make sure that the value of "n" was less than or equal to the hop
limit for that alias, we would ensure that the users only used proper
outgoing paths. One would not be able to use a malformed path such as
WIDE1-7, but a path such as WIDE2-1 would still be viable. This would
require that "N" would always have to be less than "n", and that "n"
was less than HOPLIMIT.

Here's a small portion of the code.

// Get value of N in alias
n = packet_data[a-6+c] >> 1;
// Must be a number
if (!isdigit(n)) continue;

You check the"n" character to ensure that it is a number.

// Get SSID, skip if it's already 0 (so why isn't H set?)
c = (packet_data[a] & 0x1e) >> 1;

// Check against max N limit and cap it
if (c > globalcfg.digi[d].n) c = globalcfg.digi[d].n;

Then you check to ensure that "N" is less than the hop limit.

What needs to be done, is to not only ensure that "n" is less than or
equal to the hoplimit, and that "N" is less than "n".

//Check to ensure that "n" is greater than "N"
if (n > c c = n) continue;

I'm no C coder, but if you understand the concept, it should only be
one more line of code to ensure that the OT2 implements proper hop
limiting.

James
VE6SRV
Scott Miller
2009-08-16 18:38:13 UTC
Permalink
You're right, it shouldn't be a big code change. I've been holding off
on it because there seems to be some disagreement on how hop limiting in
particular should work - dropping excessive paths completely, counting
already-used hops against the limit, or (like it does now) just capping
the remaining hops. And then there's the exception of the WIDE1-1 behavior.

What I'd really like to see is a flowchart, or maybe even just a matrix,
showing what the behavior should be. Something that everyone can look
at and see what the implications are for each case, and that can serve
as an implementation guide when everyone's had a chance to look at it.

Scott
Post by James Ewen
Scott,
Here's a little something that I've been meaning to discuss for a few
years now... (yeah, I'm a procrastinator).
First thing, we need to discuss how a UIFLOOD or UITRACE algorithm is
supposed to work, ignoring the callsign insertion portion for the
moment.
Let's just use the usual base alias of WIDE, where the path used by
the user would be in the form of WIDEn-N.
The general concept was for people to set both "n" and "N" to the same
value, where "n" would indicate the number of hops desired when
initiated, and "N" would keep track of the number of hops to go.
AX.25 packet rules limit the value of "N" to a maximum of 7.
So, one would be able to use an outgoing path of anything between
WIDE1-1 and WIDE7-7, and expect it to be acted upon by a digipeater
that supports UIFLOOD or UITRACE.
From there, it was decided by consensus that it would be good to be
able to limit the number of hops supported by a digipeater to keep
users from abusing the network by using excessive "N" hop values. With
a majority of digipeater running on the Kantronics hardware, a
pseudo-trap concept was designed and implemented. Setting UIDIGI
WIDE3-3,WIDE4-4,WIDE5-5,WIDE6-6,WIDE7-7 in the KPC-3 and KPC-3+
hardware captures any of those paths, and does a simple callsign
substitution digipeat. This has the effect of giving a single hop,
overwriting WIDEn-N aliase with the callsign of the digipeater.
The flaw in this design is that Kantronics will digipeat any other
combinations of n-N that do not match exactly with the UIDIGI
settings. If a user sends a packet with an outgoing path of WIDE7-7,
and a single digipeater acts upon the packet, that packet will bypass
the traps, since the packet would be WIDE7-6 or less. Using non
standard n-N values also bypass the traps. Using a path such as
WIDE1-7 will be acted upon by Kantronics TNCs with traps enabled.
The OT2 digipeater rules allow us to setup WIDEn-N digipeating rules,
with hop limits. Setting a hop limit of 3 restricts the action of the
digipeater to packets that have an "N" value of 3 or less. However,
there is no check done on the"n" value, which means that packets with
a higher or lower "n" value will get acted upon. This can cause some
undesirable digipeater action such as when a digipeater is set up to
act as a fill-in digipeater.
Setting ALIAS to WIDE, and HOPLIMIT to 1 should only act upon a packet
with a path of WIDE1-1, however, because the "n" value is not checked,
any packet with an "N" value of 1 is acted upon. This is undesirable
since all packets travelling through the APRS-RF network will end up
with an "N" value of 1 on their last hop. A workaround of setting the
ALIAS of WIDE1 and HOPLIMIT of 1 works to create a digipeater that
only acts upon WIDE1-1, and no other values of "n" when "N" equals 1.
To further expand upon this, one would need to set an ALIAS of WIDE2
and HOPLIMIT of 2 to act upon only WIDE2-2 and WIDE2-1 packet paths.
Setting another ALIAS of WIDE3 and HOPLIMIT of 3 would act upon only
WIDE3-3, WIDE3-2, and WIDE3-1 packet paths.
If however a line of code was added to the firmware that checked to
make sure that the value of "n" was less than or equal to the hop
limit for that alias, we would ensure that the users only used proper
outgoing paths. One would not be able to use a malformed path such as
WIDE1-7, but a path such as WIDE2-1 would still be viable. This would
require that "N" would always have to be less than "n", and that "n"
was less than HOPLIMIT.
Here's a small portion of the code.
// Get value of N in alias
n = packet_data[a-6+c] >> 1;
// Must be a number
if (!isdigit(n)) continue;
You check the"n" character to ensure that it is a number.
// Get SSID, skip if it's already 0 (so why isn't H set?)
c = (packet_data[a] & 0x1e) >> 1;
// Check against max N limit and cap it
if (c > globalcfg.digi[d].n) c = globalcfg.digi[d].n;
Then you check to ensure that "N" is less than the hop limit.
What needs to be done, is to not only ensure that "n" is less than or
equal to the hoplimit, and that "N" is less than "n".
//Check to ensure that "n" is greater than "N"
if (n > c c = n) continue;
I'm no C coder, but if you understand the concept, it should only be
one more line of code to ensure that the OT2 implements proper hop
limiting.
James
VE6SRV
James Ewen
2009-08-16 19:31:55 UTC
Permalink
You're right, it shouldn't be a big code change.  I've been holding off
on it because there seems to be some disagreement on how hop limiting in
particular should work - dropping excessive paths completely, counting
already-used hops against the limit, or (like it does now) just capping
the remaining hops.  And then there's the exception of the WIDE1-1 behavior.
I know my opinion on the matter. If it doesn't fit in the rules, dump
it. If you have a HOPLIMIT of 3, there are only 6 valid paths that
should be acted upon. Anything other than that should be ignored.

Counting hops used in malformed paths only encourages the continued
use of malformed paths, and acting upon N values below the limit even
when the packet was started with a higher limit allows abusive paths.

You have to make people do it right, or they don't learn. I used to be
on the other side of the fence, but after nearly 5 years of people not
making the change, I'm at my limit.
What I'd really like to see is a flowchart, or maybe even just a matrix,
showing what the behavior should be.  Something that everyone can look
at and see what the implications are for each case, and that can serve
as an implementation guide when everyone's had a chance to look at it.
That could be done, and the wiki would be a place to post it... Now I
have to figure how to flowchart or matrix it to make sense.

That's one of the big problems in APRS, is that the digipeating rules
have never been laid out properly. People discuss the rules, yet they
implement them differently across the continent. Actually now with the
New n-N paradigm, I think it's a little more homogenous.

James
VE6SRV
Bob Poortinga
2009-08-17 14:56:52 UTC
Permalink
Post by Scott Miller
You're right, it shouldn't be a big code change. I've been holding off
on it because there seems to be some disagreement on how hop limiting in
particular should work - dropping excessive paths completely, counting
already-used hops against the limit, or (like it does now) just capping
the remaining hops. And then there's the exception of the WIDE1-1 behavior.
Instead of changing the way HOPLIMIT works, why not just add a new command
such as HOPMAX? Shouldn't take much memory.
--
Bob Poortinga K9SQL <http://www.linkedin.com/in/bobpoortinga>
Bloomington, Indiana US
James Ewen
2009-08-17 15:25:50 UTC
Permalink
On Mon, Aug 17, 2009 at 8:56 AM, Bob Poortinga
Post by Bob Poortinga
Instead of changing the way HOPLIMIT works, why not just add a new command
such as HOPMAX?  Shouldn't take much memory.
Please describe what HOPMAX would do?

James
VE6SRV
Lynn W. Deffenbaugh (Mr)
2009-08-16 19:13:35 UTC
Permalink
Post by James Ewen
AX.25 packet rules limit the value of "N" to a maximum of 7.
Just for clarity to those learning AX.25 by osmosis, the AX.25 packet
rules (http://www.tapr.org/pub_ax25.html) do NOT directly limit the
value of N to 7, but to 15 (4 bits as shown in 2.2.13.1.1 (A7) and
2.2.13.2 (A21)). This is where the SSID limits of -0 (normally
suppressed) to -15 comes from.

What AX.25 DOES directly limit is the number of elements in the PATH of
a packet. This is limited to 8 per 2.2.13.3 in the AX.25 spec. This
limit does not include the source and destination callsigns (the
Address-Field 2.2.13.1).

With callsign substitution occurring, a WIDE7-7 packet could become:

DIGI-1,DIGI-2,DIGI-3,DIGI-4,DIGI-5,DIGI-6,DIGI-7,WIDE7*

This consumes all 8 available path slots according to AX.25. By
extension, a WIDE8-8 or WIDE9-9 would run out of substitution spots in
the path before exhausting the path, thereby blaming the WIDE7-7 limit
on AX.25, but only because of the callsign substitution and traceability
of the WIDEn-N paradigm.

Lynn (D) - KJ4ERJ - Testing my understanding of the actual limits
James Ewen
2009-08-16 19:25:41 UTC
Permalink
On Sun, Aug 16, 2009 at 1:13 PM, Lynn W. Deffenbaugh
Post by Lynn W. Deffenbaugh (Mr)
Post by James Ewen
AX.25 packet rules limit the value of "N" to a maximum of 7.
Just for clarity to those learning AX.25 by osmosis, the AX.25 packet
rules (http://www.tapr.org/pub_ax25.html) do NOT directly limit the
value of N to 7, but to 15 (4 bits as shown in 2.2.13.1.1 (A7) and
2.2.13.2 (A21)).  This is where the SSID limits of -0 (normally
suppressed) to -15 comes from.
My suggestion that N be limited to a numeric value of 7 was not based
on the SSID limit, but rather by the element limit you list below.
Post by Lynn W. Deffenbaugh (Mr)
What AX.25 DOES directly limit is the number of elements in the PATH of
a packet.  This is limited to 8 per 2.2.13.3 in the AX.25 spec.  This
limit does not include the source and destination callsigns (the
Address-Field 2.2.13.1).
This limit is indeed an AX.25 limit as you point out.
Post by Lynn W. Deffenbaugh (Mr)
DIGI-1,DIGI-2,DIGI-3,DIGI-4,DIGI-5,DIGI-6,DIGI-7,WIDE7*
This consumes all 8 available path slots according to AX.25.  By
extension, a WIDE8-8 or WIDE9-9 would run out of substitution spots in
the path before exhausting the path, thereby blaming the WIDE7-7 limit
on AX.25, but only because of the callsign substitution and traceability
of the WIDEn-N paradigm.
While it is true that you could use an outgoing path of WIDE9-15 which
is a perfectly acceptable path alias format according to one part of
the AX.25 spec, it would not be acted upon by the Kantronics line, nor
any other digipeater that I know of.

I tried higher values of N when playing with the Kantronics line a
number of years ago, and it limited the value it acted upon to ensure
that the substitution spots weren't over run.

One thing that I didn't try was to use something like WIDE7-7,WIDE7-7
to see what would happen if the substitution spots were full, yet the
TNC was asked to insert yet another callsign. Would it overwrite the
last callsign, not insert a callsign, or bomb out?

This of course is getting a little deep, and a little off topic for
the T2 reflector.

James
VE6SRV
Bill V WA7NWP
2009-08-17 18:31:29 UTC
Permalink
t for clarity to those learning AX.25 by osmosis, the AX.25 packet
Post by James Ewen
Post by Lynn W. Deffenbaugh (Mr)
rules (http://www.tapr.org/pub_ax25.html) do NOT directly limit the
value of N to 7, but to 15 (4 bits as shown in 2.2.13.1.1 (A7) and
2.2.13.2 (A21)).  This is where the SSID limits of -0 (normally
suppressed) to -15 comes from.
My suggestion that N be limited to a numeric value of 7 was not based
on the SSID limit, but rather by the element limit you list below.
APRS (ala Bob B.) has other definitions for the 8..15 SSID's which are
essentially unused in our current implementations.

Bill WA7NWP

Continue reading on narkive:
Loading...