Subject: Re: [salud] Another algorithm for selecting a signal

From: Paul Kyzivat <[email-masked]>
Date: Sun, 02 Oct 2011 17:22:54 -0400

Dale,

This sounds pretty good. Just to be clear, I assume this is just an 
example of how to do this - presumably its not normative. Right?

A complication we may, or may not, want to explore is when the signals 
could represent different "media". For instance there may be separate 
audio and visual (not necessarily video) signals, and there might be 
combined audio/video signals.

When selecting signals, its probably necessary to do so independently 
for each medium. So for example there might be a complete set of audio 
signals, in the structure you describe, and just a single visual signal 
(e.g. blinking light) assigned to "default". Then the appropriate audio 
alert would be chosen and the light would blink for all cases.

Conversely, there might be a unique visual signal for every known 
feature (perhaps a text rendering of that signal), plus audio signals 
arranged as you show. In that case you would get a suitable audio alert 
plus a text display of the particular chosen text.

	Thanks,
	Paul

On 9/29/11 11:28 AM, Worley, Dale R (Dale) wrote:
> [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
> _______________________________________________
> salud mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/salud
>

---

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Mon, 3 Oct 2011 15:52:45 -0400

[as individual]

> From: Paul Kyzivat [[email-masked]]
> 

At this point, I've been looking at it largely as a proof-of-concept.
I only have a vague idea of what the desired properties are (what the
normative text would be).  That is why it was so important when Laura
provided an example where the previous algorithm did not provide the
desired results.

> combined audio/video signals.

Yeah, it's probably useful to mention possibilities like this.

Dale

---

From: Laura Liess <[email-masked]>
Date: Fri, 14 Oct 2011 15:33:13 +0200

Hi,

2011/10/3 Worley, Dale R (Dale) <[email-masked]>:
> normative text would be).

Looking at the requirements Dale already sent to the list
http://www.ietf.org/mail-archive/web/salud/current/msg00152.html, I
think we just need one more rule, which covers the case when the UA
did not receive any indication for a given signal propriety. This is a
first text proposal:  "In case the UA has more than one signals left
and those signals correspond to different value a propriety for which
no Alert-Info URN was received, the UA must choose the signal (s)
corresponding to the  value which is UA's "default" value for this
propriety."

Maybe you see a better way to describe this requirement?

Thanks a lot
Laura

> That is why it was so important when Laura

---

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Thu, 27 Oct 2011 17:07:50 -0400

[as individual]

Rewriting and expanding my message of 19 Aug (msg00152):

This version integrates Laura's suggestion (14 Oct, msg00170) of a
third requirement to prefer signals that mean the default value of a
property if the URNs specify no value for that property.  I've
generalized this to "if you can, select a signal that is no more
specific in any way than was required by the URNs".

This third requirement seems to me to be desirable, and the example
algorithm follows this third requirement.

This version follows this approach:

- Normatively, state a few requirements that the process of interpreting URNs
  must follow.  I believe that we can keep these principles to a small number,
  probably five or fewer.

- Non-normatively, provide an algorithm whose results satisfy the
  requirements.  This algorithm would be similar to the one I stated
  previously, with additions to handle situations like the one you
  proposed.  An example algorithm (1) proves that the normative
  requirements can be met, and (2) provides an initial implementation
  for manufacturers.

The proposed requirements are:

- Each alert-info URN has precedence over all URNs that follow it, and
  its interpretation is subordinate to all URNs that precede it.

- If the UA cannot implement the effect of a URN (because it does not
  recognize the URN or the URN's effect is precluded by
  higher-precedence, preceding URNs), the UA removes the final
  "name" of the URN repeatedly until either (1) the resulting URN is
  recognized and can be given effect by some signal (without reducing
  the degree of expression of any preceding URN), or (2) the resulting
  URN is reduced to having no "names".  In case (2), that URN in the
  series cannot be given effect, so it is ignored.

- In case that after processing all the URNs, the UA can generate more
  than one signal that are equally effective at expressing the URNs
  (under the preceding rules), one of those signals is selected.  When
  selecting from the set of equally effective signals, any particular
  signal is preferred over all signals that are more specific (in
  regard to the defined meaning of the signal to the user) than that
  particular signal.  (E.g., if each signal expresses a set of
  alert-indications (values) for a set of alert-categories (per the
  BNF), then a first signal is more specific than a second signal if
  the second signal's alert-indications are (partial or complete)
  initial portions of the first signal's corresponding
  alert-indications.)

The proposed non-normative example implementation is:  (This is copied
with small changes from my message of 29 Sep (msg00164).  The examples
in that message are omitted here.)

  node by the trailing portion of the URN.  Each URN thus corresponds to a

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

  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 in those trees, but be at the root in all other
  feature trees.

  Here is how a single sort step proceeds, examining a single URN to
  modify the set of signals (by excluding some signals and further
  sorting the signals that remain):

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

(The terminology is not consistent.  E.g., I've used "feature",
"property", and "alert-category" for the same thing.)

Dale

---

From: Paul Kyzivat <[email-masked]>
Date: Thu, 27 Oct 2011 18:14:02 -0400

> specific in any way than was required by the URNs".

I think this strategy will work.

>    requirements can be met, and (2) provides an initial implementation

This seems good.

>    initial portions of the first signal's corresponding

I think what is missing from here is the possibility that more than one 
signal can be selected. E.g. there may be a set of audio signals, and a 
set of graphic (I hesitate to say video) signals. It could be possible 
to render one of each without conflict. For that matter, it may be 
possible to render more than one of the same type, or not.

(Audio signals that are intended to be played repeatedly are probably 
mutually exclusive. Audio signals that are played once could conceivably 
be rendered in sequence. "Graphic" signals may be mutually exclusive if 
they are rendered to a fixed position and remain displayed. If they are 
sequential data that can be rendered in a larger field they might also 
be rendered in sequence. An audio+video signal may be mutually exclusive 
with other audio signals and graphic signals that render into the same 
space as the video.)

For instance, this would allow having one or a few general purpose audio 
signals together with a much more specific set of graphic (e.g. text) 
signals. Then the audio signal will get your attention, and you can look 
at the graphic for more detail.

>      URN are kept; all other signals are removed from the set.

All signals in the set positioned at that node, or an ancestor node of 
the URN are kept; ...

>      Within any group of signals that are tied under previous sorts, place

I don't understand the initial sort state. Are all signals initially 
tied? (Except perhaps for the default signal.)

>      are at the root node of the feature tree.

This doesn't handle non-conflicting signals. How about the following to 
extend it:

After applying this algorithm and selecting a signal, go back to the 
original tree, and remove all signals that conflict with this one. Then 
repeat the algorithm. If it yields another signal, select that one also, 
and repeat again.

(Obviously this is an inefficient algorithm, but it may be enough as a 
proof of concept. Certainly implementers can find a more optimal one. 
And if they only have audio alerts they don't need to bother.)

	Thanks,
	Paul

---

From: Laura Liess <[email-masked]>
Date: Fri, 28 Oct 2011 15:16:49 +0200

2011/10/27 Worley, Dale R (Dale) <[email-masked]>

> specific in any way than was required by the URNs".

Yes, this seems  much better to me.

Laura

---

From: "Worley, Dale R (Dale)" <[email-masked]>
Date: Fri, 28 Oct 2011 15:18:52 -0400

> at the graphic for more detail.

This is a good point.  But within the terminology we've been using, if
several different signals can be rendered at once, it isn't a set of
signals, but one signal which has a set of sensory components.

E.g., if the device generates audio signals and visual signals at the
same time, each "signal" (in the sense we've been using the term) is a
combination of one audio and one visual component.

The algorithms as we have been discussing them would work correctly,
within the context that the input set of signals is a set of *pairs*,
each pair containing an audio component and a visual component, and
the input set of pairs contains all possible pairs of audio and visual
components.

Once you trace through an ocean of details, any of the algorithms we
have discussed has this interesting property:  Running the algorithm
on the set of "paired" signals gives the same results as running the
algorithm twice, once on the audio signals and once on the visual
signals.

> > [...]

Yes, that corrects it.

> tied?

Yes, because they haven't yet been put into an order by a key.

The concept I am assuming is the idea of sorting by multiple keys, a
major key, a second-major key, etc.,... down to a minor key.  Compare
to several -k options given to the Unix 'sort' program.

Each URN provides one "key" for sorting.  In the result of the overall
sort, the relative order of two items is determined by the first (most
major) of the keys that does not consider the items tied.

In practice, if the sorting algorithm we use is stable (does not
change the ordering of tied items from input to output; see
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability), then one
can implement in this way:

Starting from the *last* sort (the final tie-breaker) and going to the
*first* sort, first execute the selection implied by the URN and then
sort the remaining items as implied by the URN.

(One can also separate the selection and sort steps, as the ordering
of the selection steps does not matter.)

> This doesn't handle non-conflicting signals. How about the following to

I'm not sure what you're getting at here.  The algorithm as presented
can handle signals that are non-conflicting in various ways, but the
requirement is to select *one* signal.  I think what you're concerned
about is discussed above regarding combination-signals.

Dale

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 28 Oct 2011 18:34:45 -0400

> algorithm twice, once on the audio signals and once on the visual

Yes, what I am talking about can be handled that way.
It may be convenient to do that, or not. (There is some benefit to 
treating them separately, since the total number that need to be defined 
can be a lot less.

But ultimately it is implementers choice how to do this.
I'm happy if you simply make what you said above (one signal with a set 
of sensory components) explicit.

	Thanks,
	Paul