Simpler Algorithms for Processing Alert-Info URNs
draft-worley-alert-info-fsm-01

SALUD                                                          D. Worley
Internet-Draft                                                   Ariadne
Intended status: Standards Track                            May 12, 2016
Expires: November 13, 2016

           Simpler Algorithms for Processing Alert-Info URNs
                     draft-worley-alert-info-fsm-01

Abstract

   The "alert" namespace of uniform resource names (URNs) can be used in
   the Alert-Info header field of Session Initiation Protocol (SIP)
   requests and responses to inform a VoIP telephone (user agent) of the
   characteristics of the call that the user agent has originated or
   terminated.  Based on the URNs in the Alert-Info header field, the
   user agent must select an the best available signal to present to its
   user to indicate the characteristics of the call.  This document
   describes a method by which a user agent's designer can, based on the
   user agent's signals and their meanings, constructing a finite state
   machine (FSM) to process the URNs to select a signal in a way that
   obeys the restrictions given in the definition of the "alert" URN
   namespace.  In many situations, the resulting FSM is simpler and
   faster than the previously described selection algorithm.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on November 13, 2016.

Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

Worley                  Expires November 13, 2016               [Page 1]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Other URIs in Alert-Info  . . . . . . . . . . . . . . . . . .   4
   3.  Constructing the Finite State Machine for a Very Simple
       Example . . . . . . . . . . . . . . . . . . . . . . . . . . .   4
     3.1.  Listing the Expressed URNs  . . . . . . . . . . . . . . .   4
     3.2.  Constructing the Alphabet . . . . . . . . . . . . . . . .   5
     3.3.  Constructing the States and Transitions . . . . . . . . .   6
     3.4.  Summary . . . . . . . . . . . . . . . . . . . . . . . . .   9
     3.5.  Examples of Processing Alert-Info URNs  . . . . . . . . .  11
   4.  Example with "source" and "priority" URNs . . . . . . . . . .  13
   5.  Example 1 of RFC 7462 . . . . . . . . . . . . . . . . . . . .  16
   6.  Examples 2, 3, and 4 of RFC 7462  . . . . . . . . . . . . . .  21
   7.  An Example that Subsets Internal Sources  . . . . . . . . . .  24
   8.  An Example of "service" URNs  . . . . . . . . . . . . . . . .  25
   9.  Prioritizing Signals  . . . . . . . . . . . . . . . . . . . .  25
   10. Dynamic Sets of Signals . . . . . . . . . . . . . . . . . . .  29
   11. Normative References  . . . . . . . . . . . . . . . . . . . .  30
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  30

1.  Introduction

   A SIP user agent server determines an alerting signal (the ring tone)
   to present to its user (the called user) by processing the Alert-Info
   header field(s) in the incoming INVITE request.  Similarly, a SIP
   user agent client determines an alerting signal (the ringback tone)
   to present to its user (the calling user) by processing the Alert-
   Info header field(s) in the incoming provisional response to its
   outgoing INVITE request.

   [RFC3261] envisioned that the Alert-Info header field value would be
   a URL that the user agent could use to retrieve a signal.  This usage
   has security problems and is inconvenient to implement in practice.
   [RFC7462] introduced an alternative practice: The values could be
   URNs in the "alert" URN namespace which specify features of the call
   or of the signal that should be signaled to the user.  [RFC7462]

Worley                  Expires November 13, 2016               [Page 2]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   defined a large set of "alert" URNs and procedures for extending the
   set.

   However, a user agent is unlikely to provide alerting signals that
   can render more than a small subset of the possible combinations of
   "alert" URNs, so the user agent is frequently required to select one
   alerting signal which renders only a subset of the information in the
   Alert-Info header field(s).  The requirements for the process of
   selecting an alerting signal based on "alert" URNs are given in
   section 11.1 of [RFC7462].

   Section 12 of [RFC7462] gives one possible algorithm for selecting a
   signal which satisfies section 11.1.  This algorithm can be used
   regardless of the set of alerting signals that the user agent
   provides and their specified meanings.  This demonstrates that the
   rules can always be satisfied.  However, the algorithm is complex and
   slow.

   The purpose of this document is to describe an easier method for user
   agent designers to construct an algorithm for selecting alerting
   signals based on the Alert-Info header fields in a SIP message.
   Based on the user agent's signals and their meanings, the designer
   constructs:

   o  an "alphabet" containing a finite number of symbols; each possible
      "alert" URN maps into exactly one symbol

   o  a finite state machine (FSM) whose input is the alphabet of
      symbols and whose states describe information extracted from the
      Alert-Info URNs

   o  a signal for each state of the FSM, which is the signal that that
      the user agent will present if processing the Alert-Info URNs
      leaves the FSM in that state

   Note that the user agent has two FSMs.  One FSM is used to select the
   ring tone to present for an incoming INVITE request.  The other FSM
   is used to select the ringback tone to present based on an incoming
   provisional response to an outgoing INVITE request.

   To select a ring tone or ringback tone based on a SIP message, the
   user agent processes the "alert" URNs in the Alert-Info header field
   from left to right.  Initially the FSM is in a designated initial
   state.  The user agent maps each successive URN into the
   corresponding symbol, and then executes the state transition of the
   FSM specified by the symbol.  The state of the FSM after processing
   the URNs determines which signal the user agent will present to the
   user.

Worley                  Expires November 13, 2016               [Page 3]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   If the FSM is correctly constructed by the designer, the constraints
   of section 11.1 will be satisfied.

2.  Other URIs in Alert-Info

   Note that the values in an Alert-Info header field are allowed to be
   URIs of any schema, and within the "urn" schema, are allowed to have
   any namespace.[RFC3261]  The processing of URIs that are not "alert"
   URNs is not considered by this document, nor is that processing
   specified by [RFC7462].  But the algorithm designer must consider
   what to do with such URIs if they are encountered.  The simplest
   choice is to ignore them.  Alternatively, the algorithm may examine
   the URI to determine if it names an alerting signal or describes how
   to retrieve an alerting signal, and if so, choose to render that
   signal, rather than processing the "alert" URNs to select a signal.
   In any case, the remainder of this document assumes that all Alert-
   Info URIs that are not "alert" URNs have been removed.

3.  Constructing the Finite State Machine for a Very Simple Example

   Constructing the FSM involves:

   1.  Listing the URNs which are expressed by the various signals of
       the user agent.

   2.  From the expressed URNs, constructing the finite alphabet of
       symbols into which input URNs are mapped and which drive the
       state transitions of the FSM.

   3.  Constructing the states of the FSM and the transitions between
       them.

   4.  Selecting a signal to be associated with each FSM state.

   We will explain the process using a very simple example in which
   there are two signals, one expressing "internal source" and one
   expressing "external source", along with a default signal (for when
   there is no source information to signal).  The "internal source"
   signal expresses urn:alert:source:internal, and the "external source"
   signal expresses urn:alert:source:external.

3.1.  Listing the Expressed URNs

   The first step is to establish for each of the user agent's signals
   what call characteristics it represents, which is to say, the set of
   "alert" URNs which are its information content.  From the totality of
   these expressed URNs, the designer can then determine which sets of

Worley                  Expires November 13, 2016               [Page 4]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   URNs must be distinguished from each other.  In our simple example,
   the expressed URNs are:

       urn:alert:source:external
       urn:alert:source:internal

3.2.  Constructing the Alphabet

   In order to reduce the infinite set of possible "alert" URNs to a
   finite alphabet of input symbols which cause the FSM's transitions,
   the designer must partition the "alert" URNs into a finite set of
   categories.

   Once we've listed all the expressed URNs, we can list all of the
   alert-categories that are relevant to the user agent's signaling;
   "alert" URNs in any other alert-category cannot affect the signaling
   and can be ignored.  (The easiest method to achieve is to skip over
   them during Alert-Info processing.  A more formal method is to map
   all of these URNs into one "Other" symbol, and then for each state of
   the FSM, have the Other symbol transition to that state.)

   Within each relevant alert-category, we now define a distinct symbol
   for every expressed URN and for all of their "ancestor" URNs (those
   that can be created by removing one or more trailing alert-ind-
   parts).  In order to name the symbols in a way that distinguishes
   them from the corresponding URNs, we remove the initial "urn:alert:"
   and capitalize each alert-ind-part.  Thus in our example, we get
   these symbols:

       Source
       Source:External
       Source:Internal

   Note that there is a "Source" symbol even though there is no
   corresponding URN.  (urn:alert:source is not a valid URN -- see
   [RFC7462] section 7.  Although the processing algorithm must be
   prepared to screen out such a purported URN if it appears in the
   Alert-Info header field.)  However, its existance as a symbol will be
   useful later when we construct the FSM.

   For each of these symbols, we add a symbol that classifies URNs that
   extend the symbol's corresponding URN with alert-ind-parts that
   cannot be expressed:

       Source:Other
       Source:External:Other
       Source:Internal:Other

Worley                  Expires November 13, 2016               [Page 5]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   The latter two classify URNs like
   urn:alert:source:external:foo@example, which extend URNs that we
   already have symbols for.  The first is for classifying URNs, such as
   urn:alert:source:bar@example, which have alert-ind-parts that
   contradict all the "source" URNs that the user agent can signal.

   We can then simplify the set of symbols by removing the ones like
   Source:External:Other and Source:Internal:Other that consist of
   adding "Other" to a symbol which corresponds to an expressed URN
   which is not ancestral to any other expressed URN.

   This leaves the following symbols for the "source" category:

       Source
       Source:External
       Source:Internal
       Source:Other

   These can be visually summarized by showing the infinite tree of
   possible source "alert" URNs and how the tree is partitioned into
   subtrees that map to each of these symbols.  We also mark with "*"
   the symbols that correspond to expressed URNs.

                               urn:alert
                                   |
                               {   |    }
                               { source } --> 1
                               {   |    }
                                   |
               +-------------------+-------------------+
               |                    |                  |
          {    |      }        {    |      }        {  |  }
          { external* } --> 2  { internal* } --> 3  { ... } --> 4
          {    |      }        {    |      }        {     }
          {   ...     }        {   ...     }
          {           }        {           }

       1 = Source
       2 = Source:External
       3 = Source:Internal
       4 = Source:Other

3.3.  Constructing the States and Transitions

   The user agent processes the Alert-Info URNs left-to-right using a
   finite state machine (FSM), with each successive URN causing the FSM
   to transition to a new state.  Each state of the FSM describes the
   information which has so far been extracted from the URNs.  The state

Worley                  Expires November 13, 2016               [Page 6]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   of the FSM after processing all the URNs determines which signal the
   user agent will present to the user.

   We label each state with a set of symbols, one from each relevant
   category, which describe the information that's been extracted from
   all of the URNs that have so far been processed.  The initial state
   is labeled with the "null" symbols that are just the category names,
   because no information has yet been recorded.  In our simple example,
   the initial state is labeled "Source", since that's the only relevant
   category.

       State: Source (initial state)

   Each state has a corresponding alerting signal, which is the signal
   that the user agent will produce when URN processing leaves the FSM
   in that state.  The signal is the one that best expresses the
   information that has been extracted from the URNs.  Usually the
   choice of signal is obvious to the designer, but there are certain
   constraints that the choice must satisfy.  The main constraint is
   that the signal's expressed URNs must be semantic supersets of (i.e.,
   identical to or a prefix of) the URNs corresponding to the symbols in
   the state's label.  In particular, if the expressed URN of the signal
   in a certain category is shorter than the state's label, we show that
   in the state's name by putting parentheses around the trailing part
   of the symbol that is not expressed by the signal.  For instance, if
   the symbol in the label is "Source:External" but the signal only
   expresses "Source" (i.e., no "source" URN at all), then the symbol in
   the label is modified to be "Source:(External)".  Note that the
   parentheses are part of the state name, so in some circumstances
   there may be two or more distinct states labeled with the same
   symbols, but with different placement of parentheses within the
   symbols.

   The initial state's label is the null symbols for the relevant
   categories, so the only allowed signal is the default signal, which
   expresses no URNs:

       State: Source (initial state)
       Signal: default (no URNs)

   From each state, we must construct the transition for each possible
   input symbol.  For a particular state and symbol, we construct the
   label of the destination state by combining the input symbol with the
   symbol in the start state's label for the same category.  If one of
   the symbols is a prefix of the other, we select the longer one; if
   not, we select the symbol in the start state's label.

Worley                  Expires November 13, 2016               [Page 7]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   Thus, in our simple example, the initial state has the following
   transitions:

       State: Source (initial state)
       Signal: default (no URNs)
       Transitions:
           Source:External -> Source:External
           Source:Internal -> Source:Internal
           Source:Other -> Source:Other

   In all of these transitions, the input symbol is compatible with the
   matching label of the state, "Source", so the destination state's
   label is the full input symbol.

   However, there is a further constraint on the destination state: Its
   signal must express URNs that at least contain the expressed URNs of
   the signal of the start state.  Within that constraint, and being
   compatible with the destination state's label, for the category of
   the input URN, the destination state's signal must express the
   longest URN that can be expressed by any signal.

   In our example, this means that the destination Source:External state
   has the "external source" signal, which expresses
   urn:alert:source:external.  Since that signal expresses all of the
   state's label, it is the chosen state.  Similarly, the destination
   Source:Internal state has the "internal source" signal.  But for the
   transition on input Source:Other, the "Source:Other" state must have
   the default signal, as there is no signal that expresses
   urn:alert:source:[some-unknown-alert-ind-part].  So the destination
   state is "Source:(Other)", where the parentheses record that the
   "Other" part of the label is not expressed by the state's signal.

   Thus, the initial state and the states it can transition to are:

Worley                  Expires November 13, 2016               [Page 8]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source (initial state)
       Signal: default (no URNs)
       Transitions:
           Source:External -> Source:External
           Source:Internal -> Source:Internal
           Source:Other -> Source:(Other)

       State: Source:External
       Signal: external source (urn:alert:source:external)

       State: Source:Internal
       Signal: internal source (urn:alert:source:internal)

       State: Source:(Other)
       Signal: default (no URNs)

   Looking at the state Source:External, we see that it is incompatible
   with all input symbols other than Source:External, and thus all of
   its transitions are to itself:

       State: Source:External
       Signal: external source (urn:alert:source:external)
       Transitions:
           Source:External -> Source:External
           Source:Internal -> Source:External
           Source:Other -> Source:External

   and similarly:

       State: Source:Internal
       Signal: internal source (urn:alert:source:internal)
       Transitions:
           Source:External -> Source:Internal
           Source:Internal -> Source:Internal
           Source:Other -> Source:Internal

       State: Source:(Other)
       Signal: default (no URNs)
       Transitions:
           Source:External -> Source:(Other)
           Source:Internal -> Source:(Other)
           Source:Other -> Source:(Other)

3.4.  Summary

   To summarize the steps of the method:

   1.  The signals have the meanings:

Worley                  Expires November 13, 2016               [Page 9]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       default
       internal source
       external source

   2.  The expressed URNs are:

       urn:alert:source:external
       urn:alert:source:internal

   3.  The relevant categories of "alert" URNs are only:

       source

   4.  Thus, the infinite universe of possible "alert" URNs can be
       reduced to these symbols, which are the categories of URNs that
       are different in ways that are significant to the resolution
       process:

       Source
       Source:External
       Source:Internal
       Source:Other

   5.  The FSM is:

       State: Source (initial state)
       Signal: default (no URNs)
       Transitions:
           Source:External -> Source:External
           Source:Internal -> Source:Internal
           Source:Other -> Source:(Other)

       State: Source:External
       Signal: external source (urn:alert:source:external)
       Transitions:
           Source:External -> Source:External
           Source:Internal -> Source:External
           Source:Other -> Source:External

       State: Source:Internal
       Signal: internal source (urn:alert:source:internal)
       Transitions:
           Source:External -> Source:Internal
           Source:Internal -> Source:Internal
           Source:Other -> Source:Internal

Worley                  Expires November 13, 2016              [Page 10]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source:(Other)
       Signal: default (no URNs)
       Transitions:
           Source:External -> Source:(Other)
           Source:Internal -> Source:(Other)
           Source:Other -> Source:(Other)

       *  Each state is labeled by a set of symbols which describe the
          information which has been extracted from the URNs so far.

       *  Each state has a signal which is a semantic superset of the
          state's label, i.e., the signal's expressed URNs match the
          initial portion of the label symbols.  If Alert-Info
          processing finishes with the FSM in a state, the user agent
          will present the state's signal to the user.

       *  The state's label is marked to show what subset of the symbols
          are expressed by the state's signal, and the marking is part
          of the state's name -- two states can have the same label but
          different signals.

       *  If a transition's input symbol is compatible with (is a
          semantic subset) of the start state's label, the destination
          state's label is the input symbol.  If not, the destination
          state is the start state.  This is how the state's label
          records what information has been accumulated while processing
          the Alert-Info URNs.

       *  A transition's destination state has a signal which
          semantically subsets the start state's signal as much as
          possible in the category of the input symbol.  (In most cases,
          the choice of signal is unique.  In rare cases there may be
          more than one signal that meets this criterion, so the
          designer may have some flexibility.)

3.5.  Examples of Processing Alert-Info URNs

   In the trivial case where the user agent receives no Alert-Info URNs,
   then processing begins and ends with the FSM in the initial state and
   selects the default signal.

   If the user agent receives

       Alert-Info: <urn:alert:source:internal>

   then processing progresses:

Worley                  Expires November 13, 2016              [Page 11]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal
       Signal: internal source

   If the user agent receives

       Alert-Info: <urn:alert:source:external>,
           <urn:alert:source:internal>

   then processing progresses:

       State: Source
           Process: Source:External (urn:alert:source:external)
       State: Source:External
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:External
       Signal: external source

   If the user agent receives

       Alert-Info: <urn:alert:source:unclassified>,
           <urn:alert:source:internal>

   then processing progresses:

       State: Source
           Process: Source:Other (urn:alert:source:unclassified)
       State: Source:(Other)
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:(Other)
       Signal: default

   If the user agent receives

       Alert-Info: <urn:alert:priority:high>,
           <urn:alert:source:internal>

   then processing progresses:

       State: Source
           Process: skip urn:alert:priority:high
       State: Source
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal
       Signal: internal source

Worley                  Expires November 13, 2016              [Page 12]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

4.  Example with "source" and "priority" URNs

   Now consider an example where the user agent can signal "external
   source", "internal source", "low priority", and "high priority"
   individually or in any combination of source and priority, along with
   a default signal.  This example is essentially the cartesian product
   of two copies of the example in Section 3, one dealing with the
   call's source and one dealing with the call's priority.  So there is
   a total of 9 signals:

       default
       external source
       internal source
       low priority
       low priority/external source
       low priority/internal source
       high priority
       high priority/external source
       high priority/internal source

   The expressed URNs are:

       urn:alert:source:external
       urn:alert:source:internal
       urn:alert:priority:low
       urn:alert:priority:high

   The relevant categories of "alert" URNs are only:

       source
       priority

   The alphabet of symbols is:

       Source
       Source:External
       Source:Internal
       Source:Other
       Priority
       Priority:Low
       Priority:High
       Priority:Other

   The 16 states are as follows, where 10 states have a simple structure
   because from them, no further information can be recorded.

Worley                  Expires November 13, 2016              [Page 13]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source/Priority
       Signal: default
       Transitions:
           Source:External -> Source:External/Priority
           Source:Internal -> Source:Internal/Priority
           Source:Other -> Source:(Other)/Priority
           Priority:High -> Source/Priority:High
           Priority:Low -> Source/Priority:Low
           Priority:Other -> Source/Priority:(Other)

       State: Source:External/Priority
       Signal: external source
       Transitions:
           Priority:High -> Source:External/Priority:High
           Priority:Low -> Source:External/Priority:Low
           Priority:Other -> Source:External/Priority:(Other)
           other -> Source:External/Priority

       State: Source:Internal/Priority
       Signal: internal source
       Transitions:
           Priority:High -> Source:Internal/Priority:High
           Priority:Low -> Source:Internal/Priority:Low
           Priority:Other -> Source:Internal/Priority:(Other)
           other -> Source:Internal/Priority

       State: Source:(Other)/Priority
       Signal: default
       Transitions:
           Priority:High -> Source:(Other)/Priority:High
           Priority:Low -> Source:(Other)/Priority:Low
           Priority:Other -> Source:(Other)/Priority:(Other)
           other -> Source:(Other)/Priority

       State: Source/Priority:High
       Signal: high priority
       Transitions:
           Source:External -> Source:External/Priority:High
           Source:Internal -> Source:Internal/Priority:High
           Source:Other -> Source:(Other)/Priority:High
           other -> Source/Priority:High

       State: Source:External/Priority:High
       Signal: external source/high priority
       Transitions:
           any -> Source:External/Priority:High

Worley                  Expires November 13, 2016              [Page 14]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source:Internal/Priority:High
       Signal: internal source/high priority
       Transitions:
           any -> Source:Internal/Priority:High

       State: Source:(Other)/Priority:High
       Signal: high priority
       Transitions:
           any -> Source:(Other)/Priority:High

       State: Source/Priority:Low
       Signal: low priority
       Transitions:
           Source:External -> Source:External/Priority:Low
           Source:Internal -> Source:Internal/Priority:Low
           Source:Other -> Source:(Other)/Priority:Low
           other -> Source/Priority:Low

       State: Source:External/Priority:Low
       Signal: external source/low priority
       Transitions:
           any -> Source:External/Priority:Low

       State: Source:Internal/Priority:Low
       Signal: internal source/low priority
       Transitions:
           any -> Source:Internal/Priority:Low

       State: Source:(Other)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(Other)/Priority:Low

       State: Source/Priority:(Other)
       Signal: default
       Transitions:
           Source:External -> Source:External/Priority:(Other)
           Source:Internal -> Source:Internal/Priority:(Other)
           Source:Other -> Source:(Other)/Priority:(Other)
           other -> Source/Priority:(Other)

       State: Source:External/Priority:(Other)
       Signal: external source
       Transitions:
           any -> Source:External/Priority:(Other)

Worley                  Expires November 13, 2016              [Page 15]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source:Internal/Priority:(Other)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(Other)

       State: Source:(Other)/Priority:(Other)
       Signal: default
       Transitions:
           any -> Source:(Other)/Priority:(Other)

   An example of processing that involves multiple "source" URNs and one
   "priority" URN:

       Alert-Info: <urn:alert:source:internal>,
           <urn:alert:source:unclassified>,
           <urn:alert:priority:high>

       State: Source/Priority
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal/Priority
           Process: Source:(Other) (urn:alert:source:unclassified)
       State: Source:Internal/Priority
           Process: Priority:High (urn:alert:priority:high)
       State: Source:Internal/Priority:High
       Signal: internal source/high priority

5.  Example 1 of RFC 7462

   A more complicated example is in section 12.2.1 of [RFC7462].  It is
   like the example in Section 4, except that the user agent can only
   signal "external source", "internal source", "low priority", and
   "high priority" individually but not in combination, as well as a
   default signal:

       default
       internal source
       external source
       high low
       high priority

   The signals can express the following URNs:

       urn:alert:source:external
       urn:alert:source:internal
       urn:alert:priority:low
       urn:alert:priority:high

   The relevant categories of "alert" URNs are:

Worley                  Expires November 13, 2016              [Page 16]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       source
       priority

   The alphabet of symbols is:

       Source
       Source:External
       Source:Internal
       Source:Other
       Priority
       Priority:Low
       Priority:High
       Priority:Other

   In this example, the FSM has 20 states because both "source" and
   "priority" URNs are recorded, but the order in which the two appear
   affects the signal:

       State: Source/Priority
       Signal: default
       Transitions:
           Source:External -> Source:External/Priority
           Source:Internal -> Source:Internal/Priority
           Source:Other -> Source:(Other)/Priority
           Priority:Low -> Source/Priority:Low
           Priority:High -> Source/Priority:High
           Priority:Other -> Source/Priority:Other

   Because there are no signals for combinations of "source" and
   "priority" URNs, processing a "priority" URN from the state
   Source:External/Priority leads to a state that records the priority
   information, but does not signal it:

       State: Source:External/Priority
       Signal: external source
       Transitions:
           Priority:High -> Source:External/Priority:(High)
           Priority:Low -> Source:External/Priority:(Low)
           Priority:Other -> Source:External/Priority:(Other)
           other -> Source:External/Priority

       State: Source:External/Priority:(High)
       Signal: external source
       Transitions:
           any -> Source:External/Priority:(High)

Worley                  Expires November 13, 2016              [Page 17]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source:External/Priority:(Low)
       Signal: external source
       Transitions:
           any -> Source:External/Priority:(Low)

       State: Source:External/Priority:(Other)
       Signal: external source
       Transitions:
           any -> Source:External/Priority:(Other)

   And similarly for Source:Internal/Priority:

       State: Source:Internal/Priority
       Signal: external source
       Transitions:
           Priority:High -> Source:Internal/Priority:(High)
           Priority:Low -> Source:Internal/Priority:(Low)
           Priority:Other -> Source:Internal/Priority:(Other)
           other -> Source:Internal/Priority

       State: Source:Internal/Priority:(High)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(High)

       State: Source:Internal/Priority:(Low)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(Low)

       State: Source:Internal/Priority:(Other)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(Other)

   On the other hand, state Source:(Other)/Priority can transition to
   states that can signal priority:

       State: Source:(Other)/Priority
       Signal: default
       Transitions:
           Priority:High -> Source:(Other)/Priority:High
           Priority:Low -> Source:(Other)/Priority:Low
           Priority:Other -> Source:(Other)/Priority:(Other)
           other -> Source:(Other)/Priority

Worley                  Expires November 13, 2016              [Page 18]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source:(Other)/Priority:High
       Signal: high priority
       Transitions:
           any -> Source:(Other)/Priority:High

       State: Source:(Other)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(Other)/Priority:Low

       State: Source:(Other)/Priority:(Other)
       Signal: default
       Transitions:
           any -> Source:(Other)/Priority:(Other)

   From the state Source/Priority:High, "source" URNs transition to
   states that record both source and priority but signal only priority.
   Thus, we can get two states, Source:(External)/Priority:High and
   Source:External/Priority:(High) that record the same information but
   have different signals -- one state is reached by processing a
   "priority" URN and then a "source" URN, whereas the other is reached
   by processing a "source" URN and then a "priority" URN.

       State: Source/Priority:High
       Signal: high priority
       Transitions:
           Source:External -> Source:(External)/Priority:High
           Source:Internal -> Source:(Internal)/Priority:High
           Source:Other -> Source:(Other)/Priority:High
           other -> Source/Priority:High

       State: Source:(External)/Priority:High
       Signal: high priority
       Transitions:
           any -> Source:(External)/Priority:High

       State: Source:(Internal)/Priority:High
       Signal: high priority
       Transitions:
           any -> Source:(Internal)/Priority:High

   Similarly for Source/Priority:Low:

Worley                  Expires November 13, 2016              [Page 19]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source/Priority:Low
       Signal: low priority
       Transitions:
           Source:External -> Source:(External)/Priority:Low
           Source:Internal -> Source:(Internal)/Priority:Low
           Source:Other -> Source:(Other)/Priority:Low
           other -> Source/Priority:Low

       State: Source:(External)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(External)/Priority:Low

       State: Source:(Internal)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(Internal)/Priority:Low

   However, the state Source/Priority:(Other) behaves as it does in
   Section 4:

       State: Source/Priority:(Other)
       Signal: default
       Transitions:
           Source:External -> Source:External/Priority:(Other)
           Source:Internal -> Source:Internal/Priority:(Other)
           Source:Other -> Source:(Other)/Priority:(Other)
           other -> Source/Priority:(Other)

   As an example of processing, if the user agent receives

       Alert-Info: <urn:alert:source:internal>

   then processing progresses:

       State: Source/Priority
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal/Priority
       Signal: internal source

   A more complicated example involves multiple "source" URNs which do
   not select a non-default signal and one "priority" URN which can be
   signaled:

Worley                  Expires November 13, 2016              [Page 20]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       Alert-Info: <urn:alert:source:unclassified>,
           <urn:alert:source:internal>,
           <urn:alert:priority:high>

       State: Source/Priority
           Process: Source:Other (urn:alert:source:unclassified)
       State: Source:(Other)/Priority
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:(Other)/Internal
           Process: Priority:High (urn:alert:priority:high)
       State: Source:(Other)/Priority:High
       Signal: high priority

   Since the only characteristic of a state that affects the output of
   the FSM is the state's signal, several groups of states in this FSM
   can be merged using standard FSM optimization algorithms:

       states with signal "external source":
           Source:External/Priority:(High)
           Source:External/Priority:(Low)
           Source:External/Priority:(Other)

       states with signal "internal source":
           Source:Internal/Priority:(High)
           Source:Internal/Priority:(Low)
           Source:Internal/Priority:(Other)

       states with signal "high priority":
           Source:(Other)/Priority:High
           Source:(External)/Priority:High
           Source:(Internal)/Priority:High

       states with signal "low priority":
           Source:(Other)/Priority:Low
           Source:(External)/Priority:Low
           Source:(Internal)/Priority:Low

   This reduces the FSM to 12 states.

6.  Examples 2, 3, and 4 of RFC 7462

   Example 2 of [RFC7462] is similar to the example in Section 4, but it
   does not include a signal for the combination "internal source, low
   priority" to make resolution examples work inconsistently.

   The FSM for this example has the same alphabet as the FSM of
   Section 4.  Most of the states of this FSM are the same as the states
   of the FSM of Section 4, but the state Source:Internal/Priority:Low

Worley                  Expires November 13, 2016              [Page 21]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   is missing because there is no signal for that combination.  It is
   replaced by two states: One state is Source:Internal/Priority:(Low);
   it records that Source:Internal was specified first (and is to be
   signaled) and that Priority:Low was specified later (and can not be
   signaled -- but it still prevents any further "priority" URN from
   having an effect).  The other state is
   Source:(Internal)/Priority:Low; it records the reverse sequence of
   events.

   The changes in the FSM are:

       State: Source:Internal/Priority
       Signal: internal source
       Transitions:
           Priority:Low -> Source:Internal/Priority:(Low)
           (other transitions unchanged)

       State: Source/Priority:Low
       Signal: low priority
       Transitions:
           Source:Internal -> Source:(Internal)/Priority:Low
           (other transitions unchanged)

       State: Source:Internal/Priority:(Low)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(Low)

       State: Source:(Internal)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(Internal)/Priority:Low

   An example of processing that involves multiple "source" URNs and one
   "priority" URN:

       Alert-Info: <urn:alert:source:internal>,
           <urn:alert:source:unclassified>,
           <urn:alert:priority:high>
       State: Source/Priority
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal/Priority
           Process: Source:Other (urn:alert:source:unclassified)
       State: Source:Internal/Priority
           Process: Priority:High (urn:alert:priority:high)
       State: Source:Internal/priority:high
       Signal: internal source/high priority

Worley                  Expires November 13, 2016              [Page 22]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   If the user agent receives

       Alert-Info: <urn:alert:source:internal>

       State: Source/Priority
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal/Priority
       Signal: internal source

   If the user agent receives

       Alert-Info: <urn:alert:source:external>,
           <urn:alert:priority:low>

       State: Source/Priority
           Process: Source:External (urn:alert:source:external)
       State: Source:External/Priority
           Process: Priority:Low (urn:alert:priority:low)
       State: Source:External/Priority:Low
       Signal: external source/low priority

   Suppose the same user agent receives

       Alert-Info: <urn:alert:source:internal>,
           <urn:alert:priority:low>

   Note that there is no signal that corresponds to this combination.
   In that case, the processing is:

       State: Source/Priority
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:Internal/Priority
           Process: Priority:Low (urn:alert:priority:low)
       State: Source:Internal/Priority:(Low)
       Signal: internal source

   If the order of the URNs is reversed, what is signaled is still the
   the meaning of now different first URN:

       Alert-Info: <urn:alert:priority:low>,
           <urn:alert:source:internal>

       State: Source/Priority
           Process: Priority:Low (urn:alert:priority:low)
       State: Source/Priority:Low
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:(Internal)/Priority:Low
       Signal: low priority

Worley                  Expires November 13, 2016              [Page 23]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   Notice that the existence of the new states prevents later URNs of a
   category from overriding earlier URNs of that category, even if the
   earlier one was not itself signalable:

       Alert-Info: <urn:alert:priority:low>,
           <urn:alert:source:internal>,
           <urn:alert:source:external>

       State: Source/Priority
           Process: Priority:Low (urn:alert:priority:low)
       State: Source/Priority:Low
           Process: Source:Internal (urn:alert:source:internal)
       State: Source:(Internal)/Priority:Low
           Process: Source:External (urn:alert:source:external)
       State: Source:(Internal)/Priority:Low
       Signal: low priority

   whereas if the second transition had been to the state Source/
   Priority:Low (on the basis that there is no proper state
   Source:Internal/Priority:Low), then the third transition would have
   been to the state Source:External/Priority:Low, and the signal would
   have been "external source/low priority".

7.  An Example that Subsets Internal Sources

   In the the example of Section 3, there are signals for "external
   source" and "internal source".  Let us add to that example a signal
   for "source internal from a VIP".  That last signal expresses the
   private extension URN urn:source:internal:vip@example, which is a
   subset of urn:source:internal, which is expressed by the "source
   internal" signal.  There is a total of 3 expressed URNs, one of which
   is a subset of another:

       urn:alert:source:internal
       urn:alert:source:internal:vip@example
       urn:alert:source:external

   This generates the following alphabet of symbols:

       Source
       Source:Internal
       Source:Internal:Vip@example
       Source:Internal:Other
       Source:Other

Worley                  Expires November 13, 2016              [Page 24]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

8.  An Example of "service" URNs

   In this example there are signals for "service forward" (the call has
   been forwarded) and "source recall callback" (a recall due to a
   callback).  This gives 2 expressed URNs:

       urn:alert:service:forward
       urn:alert:service:recall:callback

   This generates the following alphabet of symbols:

       Service
       Service:Forward
       Service:Recall
       Service:Recall:Callback
       Service:Recall:Other
       Service:Other

9.  Prioritizing Signals

   The specifications in [RFC7462] are oriented toward giving the sender
   of Alert-Info control over which of the "alert" URNs are most
   important.  But in some situations, the user may prefer to prioritize
   expressing one URN category over another regardless of the order the
   URNs appear in Alert-Info.  This section describes how that can be
   accommodated within the framework of [RFC7462], and presents the FSM
   that this method generates.

   This example uses the signals of Section 5, viz., "external source",
   "internal source", "low priority" and "high priority", but this time,
   we want to signal "high priority" in preference to any other signal
   that might be applicable.

   We accommodate this within the framework of [RFC7462] by assigning
   the signal "high priority" for each of these combinations of URNs:

       urn:alert:priority:high
       urn:alert:priority:high, urn:alert:source:internal
       urn:alert:priority:high, urn:alert:source:external

   The result is that the "high priority" signal is the optimal signal
   for any combination of urn:alert:priority:high with "source" URNs.

   The intermediate steps of the method produce the same results as
   before.  The signals can express the following URNs:

Worley                  Expires November 13, 2016              [Page 25]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       urn:alert:source:external
       urn:alert:source:internal
       urn:alert:priority:low
       urn:alert:priority:high

   The relevant categories of "alert" URNs are:

       source
       priority

   The alphabet of symbols is:

       Source
       Source:External
       Source:Internal
       Source:Other
       Priority
       Priority:Low
       Priority:High
       Priority:Other

   When the FSM is constructed, it is the same as the FSM for Section 5,
   except that certain states are effectively renamed and merged,
   because any "source" is defined to be expressed if high priority is
   expressed:

       Source:External/Priority:(High) and
       Source:(External)/Priority:High become:
           State: Source:External/Priority:High
           Signal: high priority

       Source:Internal/Priority:(High) and
       Source:(Internal)/Priority:High become:
           State: Source:Internal/Priority:High
           Signal: high priority

   This reduces the FSM to 18 states.  In addition, these two new
   states, along with the states Source/Priority:High and
   Source:(Other)/Priority:High, can be merged by FSM optimization,
   since all of them have the signal "high priority" and from them,
   there are no transitions to states outside this set.  We name this
   merged state Source:*/Priority:High.

   The final FSM has 15 states.  The changes from the FSM of Section 5
   are marked with change bars.

Worley                  Expires November 13, 2016              [Page 26]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source/Priority
       Signal: default
       Transitions:
           Source:External -> Source:External/Priority
           Source:Internal -> Source:Internal/Priority
           Source:Other -> Source:(Other)/Priority
           Priority:Low -> Source/Priority:Low
   |       Priority:High -> Source:*/Priority:High
           Priority:Other -> Source/Priority:Other

       State: Source:External/Priority
       Signal: external source
       Transitions:
   |       Priority:High -> Source:*/Priority:High
           Priority:Low -> Source:External/Priority:(Low)
           Priority:Other -> Source:External/Priority:(Other)
           other -> Source:External/Priority

   |   State: Source:*/Priority:High
   |   Signal: high priority
   |   Transitions:
   |       any -> Source:*/Priority:High

       State: Source:External/Priority:(Low)
       Signal: external source
       Transitions:
           any -> Source:External/Priority:(Low)

       State: Source:External/Priority:(Other)
       Signal: external source
       Transitions:
           any -> Source:External/Priority:(Other)

       State: Source:Internal/Priority
       Signal: external source
       Transitions:
   |       Priority:High -> Source:*/Priority:High
           Priority:Low -> Source:Internal/Priority:(Low)
           Priority:Other -> Source:Internal/Priority:(Other)
           other -> Source:Internal/Priority

       State: Source:Internal/Priority:(Low)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(Low)

Worley                  Expires November 13, 2016              [Page 27]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

       State: Source:Internal/Priority:(Other)
       Signal: internal source
       Transitions:
           any -> Source:Internal/Priority:(Other)

       State: Source:(Other)/Priority
       Signal: default
       Transitions:
   |       Priority:High -> Source:*/Priority:High
           Priority:Low -> Source:(Other)/Priority:Low
           Priority:Other -> Source:(Other)/Priority:(Other)
           other -> Source:(Other)/Priority

       State: Source:(Other)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(Other)/Priority:Low

       State: Source:(Other)/Priority:(Other)
       Signal: default
       Transitions:
           any -> Source:(Other)/Priority:(Other)

       State: Source/Priority:Low
       Signal: low priority
       Transitions:
           Source:External -> Source:(External)/Priority:Low
           Source:Internal -> Source:(Internal)/Priority:Low
           Source:Other -> Source:(Other)/Priority:Low
           other -> Source/Priority:Low

       State: Source:(External)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(External)/Priority:Low

       State: Source:(Internal)/Priority:Low
       Signal: low priority
       Transitions:
           any -> Source:(Internal)/Priority:Low

       State: Source/Priority:(Other)
       Signal: default
       Transitions:
           Source:External -> Source:External/Priority:(Other)
           Source:Internal -> Source:Internal/Priority:(Other)
           Source:Other -> Source:(Other)/Priority:(Other)
           other -> Source/Priority:(Other)

Worley                  Expires November 13, 2016              [Page 28]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

10.  Dynamic Sets of Signals

   This section discusses how to construct FSMs for user agent that
   allows the user to configure the use of ringtones.  Several
   approaches can be used:

   o  Whenever the set of ringtones is changed, re-execute the processes
      listed in Section 3.

   o  Whenever the set of ringtones is changed, rebuild the list of
      expressed URNs (Section 3.1) and reconstruct the alphabet of
      symbols(Section 3.2).  Then use an algorithm for dynamically
      constructing states of the FSM as they are needed in Alert-Info
      processing.

   o  If the set of possible URNs expressed by the ringtones is
      sufficiently limited, the steps of Section 3 can be carried
      generically, and the generic FSM can be specialized for the
      current ringtone configuration.

   The remainder of this section gives an example of the third approach.

   For the example, we will use a set of ringtones that express the
   identify of the caller.  To signal this information, a private
   extension "alert" URN category is used, "caller@example":

       urn:alert:caller@example:alice@example.com
       urn:alert:caller@example:bob@example.com
       etc.

   which we can express by the generic pattern

       urn:alert:caller@example:IDENTITY

   where "IDENTITY" is replaced in succession by the set of caller
   identities that have their own ringtones to generate the set of
   expressed URNs.

   The alphabet is then:

         Caller@example
         Caller@example:IDENTITY
         Caller@example:Other

   where "IDENTITY" is replaced in succession by the set of caller
   identities.  The "Caller@example:Other" symbol includes all URNs of
   the category "caller@example" that are not included in any of the
   other symbols.

Worley                  Expires November 13, 2016              [Page 29]
Internet-Draft   Simpler Algorithms for Alert-Info URNs         May 2016

   The states and transitions of the FSM are:

       State: Caller@example (initial state)
       Signal: default (no URNs)
       Transitions:
           Caller@example:IDENTITY -> Caller@example:IDENTITY
           Caller@example:Other -> Caller@example:(Other)

       State: Caller@example:IDENTITY
       Signal: signal for caller IDENTITY
       Transitions:
           any -> Caller@example:IDENTITY

       State: Caller@example:(Other)
       Signal: default (no URNs)
       Transitions:
           any -> Caller@example:(Other)

   where again, the second state is replicated once for each caller
   identity that has a ringtone, with "IDENTITY" replaced with the
   caller identity.

11.  Normative References

   [RFC3261]  Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston,
              A., Peterson, J., Sparks, R., Handley, M., and E.
              Schooler, "SIP: Session Initiation Protocol", RFC 3261,
              DOI 10.17487/RFC3261, June 2002,
              <http://www.rfc-editor.org/info/rfc3261>.

   [RFC7462]  Liess, L., Ed., Jesske, R., Johnston, A., Worley, D., and
              P. Kyzivat, "URNs for the Alert-Info Header Field of the
              Session Initiation Protocol (SIP)", RFC 7462,
              DOI 10.17487/RFC7462, March 2015,
              <http://www.rfc-editor.org/info/rfc7462>.

Author's Address

   Dale R. Worley
   Ariadne Internet Services
   738 Main St.
   Waltham, MA  02451
   US

   Email: worley@ariadne.com

Worley                  Expires November 13, 2016              [Page 30]