Subject: [salud] Another algorithm for selecting a signal

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Thu, 29 Sep 2011 11:28:55 -0400

[as individual]

This is a rather rambling discussion of an algorithm for selecting
ringing signals.  The goal is to be a more formalized and generalized
version of what Laura described in
http://www.ietf.org/mail-archive/web/salud/current/msg00151.html, and
also include the multiple-stage selection I've described previously.

This is the idea:

For each feature, there is a tree of possible values.  For this
description, we will name each tree by the feature name, and name each
node by the trailing portion of the URN.  Each URN corresponds to a
node in a feature tree.  Thus, there is a tree named "source", whose
root node is also named "source", and which has the children
source:internal, source:external, source:friend, and source:family
(according to the -02 draft).

For example, the URN <urn:alert:source:external> is placed at the node
"source:external" in the "source" tree.

(Of course, there are an infinite number of potential additional nodes
in the tree for private values, but we don't have to represent those
nodes explicitly unless the device has a signal representing the
private value.)

We assign similar locations to signals, but each signal has a place in
*every* tree.  If a signal has a simple meaning, such as "external
source", its place in the "source" tree is source:external, but its
place in every other feature tree is at the root node, meaning that it
has no particular meaning for that feature.

A signal that has a complex meaning may have non-root positions in
more than one feature tree.  For example, an "external, high priority"
signal would be placed at source:external and priority:high, but be at
the root in all other feature trees.

In order to assure that the algorithm always selects at least one
signal, we assume that there is a "default" signal, whose position in
every feature tree is at the root.  The default signal is set up so
that it will never be excluded from the set of acceptable signals for
an indication, but will usually be the least-desirable signal for any
indication.

The algorithm proceeds by considering each URN in the indication from
left to right, while revising a set of signals.  The set of signals
starts as the entire set of signals available to the device.  Each URN
excludes some signals from the set, and *sorts* the signals that
remain in the set according to how well they represent the URN.  The
first URN is the "major sort", and has the most influence on the
position of a signal in the set.  The second URN is a "minor sort", in
that it arranges the orders of the signals that are tied within the
first sort, the third URN arranges the orders of the signals that are
tied within the first two sorts, etc.

At the end of the algorithm, a final, "most minor" sort is done, which
orders the signals which have been tied under all the sorts driven by
the URNs.  This sort places the least specific signal *first*.

Once all the URNs are processed and the sorting is done, the device
selects the first signal in the set.

Here is how a sort proceeds:

The URN is at a specific node in a specific feature tree.

All signals whose positions are ancestor nodes of the URN are kept;
all other signals are removed from the set.

Within any group of signals that are tied under previous sorts, place
first those which are at the node of the URN, place second those which
are at the parent node of the URN, etc., and place last those which
are at the root node of the feature tree.

Here are some examples of how the algorithm works:

Example 1 (from Laura)

> Take the following example:
>
> The device has a set of alerting signals consisting which are for
> <urn:alert:source:external>, <urn:alert:source:internal>,
> <urn:alert:priority:low>, <urn:alert:priority:high>. It receives
> <urn:alert:source:external>.  The device eliminates
> <urn:alert:source:internal> and keeps  <urn:alert:source:external>,
> <urn:alert:priority:low>, <urn:alert:priority:high>.  Could it happen
> that it chooses to render <urn:alert:priority:high> or did I miss
> something in the algorithm description?

There are 4 signals.  We list their primary meanings, and the
locations that they are placed in the feature trees:

Meaning: <urn:alert:source:external>
Locations:
	source:external
	priority (that is, the root node of the priority tree)

Meaning: <urn:alert:source:internal>
Locations:
	source:internal
	priority

Meaning: <urn:alert:priority:low>
Locations:
	source
	priority:low

Meaning: <urn:alert:priority:high>
Locations:
	source
	priority:high

To which we add:
Meaning: default
Locations:
	source
	priority

If the device receives <urn:alert:source:internal>, then the sort is:

Signals at source:internal:
	<urn:alert:source:internal>
Signals at source:
	<urn:alert:priority:low>
	<urn:alert:priority:high>
	default

And these signals are excluded from the set:
	<urn:alert:source:external>

So in this example, the sorting algorithm properly gives first place
to <urn:alert:source:internal>.

Example 2

Let us add to this set of signals ones that express combinations like
"internal, high priority", but let us specifically exclude the
combination "internal, low priority" so as to set up some tricky
examples.  This enlarges our set of signals:

Meaning: default
Locations:
	source
	priority

Meaning: external
Locations:
	source:external
	priority

Meaning: internal
Locations:
	source:internal
	priority

Meaning: low
Locations:
	source
	priority:low

Meaning: high
Locations:
	source
	priority:high

Meaning: external high
Locations:
	source:external
	priority:high

Meaning: external low
Locations:
	source:external
	priority:low

Meaning: internal high
Locations:
	source:internal
	priority:high

If the device receives <urn:alert:source:internal>, then the sort is:

Signals at source:internal: (that is, tied for first place)
	internal
	internal high
Signals at source: (tied for second place)
	low
	high
	default

Signals excluded from the set:
	external
	external low
	external high

Two signals are tied for the first place, but the final sort orders
them:
	internal
	internal high
because it puts the least-specific signal first.  So the signal
"internal" is chosen.

Example 2b

Suppose the same device receives <urn:alert:source:external>,
<urn:alert:priority:low>.  The first sort (due to
<urn:alert:source:external>) is:

Signals at source:external:
	external
	external low
	external high
Signals at source:
	low
	high
	default

Signals excluded:
	internal
	internal high

The second sort (due to <urn:alert:priority:low>) puts signals at
priority:low before signals at priority, and excludes signal at
priority:high:

	external low
	external
	low
	default

Excluded:
	external high
	high
	internal
	internal high

So, as you would expect, we choose "external low".

Example 2c

Suppose the same device receives <urn:alert:source:internal>,
<urn:alert:priority:low>.  Note that there is no signal that
corresponds to this combination.

The first sort is based on source:internal, and results in this order:

	(tied:)
	internal
	internal high

	(tied:)
	low
	high
	default

Excluded:
	external
	external low
	external high

The second sort is based on priority:low, and results in this order:

	internal
	low
	default

Excluded:
	internal high
	high
	external low
	external
	external high

So we choose the signal "internal".

Example 2d

Suppose the same device receives <urn:alert:priority:low>,
<urn:alert:source:internal>.  This is like example 2c, but the URNs
are in the opposite order.

The first sort is based on priority:low, and results in this order:

	(tied:)
	low
	external low

	(tied:)
	internal
	external
	default

Excluded:
	high
	external high
	internal high

The second sort is based on source:internal, and results in this order:

	low
	internal
	default

Excluded:
	internal high
	high
	external low
	external
	external high

So we choose the signal "low".

Example 3

Let us set up a simple set of signals, with three signals giving
priority:

Meaning: default
Locations:
	priority

Meaning: low
Locations:
	priority:low

Meaning: high
Locations:
	priority:high

Notice that we've used the "default" signal to cover "normal
priority".  That is so the signal will cover situations where no
priority URN is present, as well as the ones with
<urn:alert:priority:normal>.  So we're deliberately failing to
distinguish "priority:normal" from the default priority.

If the device receives <urn:alert:priority:low>, the sort is:

	low
	default

Excluded:
	high

and signal "low" is chosen.

Similarly, if the device receives <urn:alert:priority:high>, signal
"high" is chosen.

If the device receives <urn:alert:priority:normal>, the sort is:

	default

Excluded:
	low
	high

and signal "default" is chosen.

If no "priority" URN is received, "default" will be put before "low"
and "high" by the final sort, and so it will be chosen.

Dale

---

From: Laura Liess <[email-masked]>
Date: Fri, 30 Sep 2011 16:01:59 +0200

Dale,

I went through your description and examples and I think it works :-).

Thanks
Laura

2011/9/29 Worley, Dale R (Dale) <[email-masked]>:
> _______________________________________________
> salud mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/salud
>