Subject: sub-tree filtering proposals

From: Andy Bierman <[email-masked]>
Date: Fri, 28 May 2004 14:56:05 -0700

A) Issue 14.1: Subset specification

A.1) Extensibility

The <get> and <get-config> operations should be modified to 
allow for the utilization of different types of standard, 
proprietary, and experimental filter mechanisms in an extensible 
way.  
  - An additional containment layer (called <filter>) is needed 
    above the user data model content in the get operation <rpc>
    message.
  - The <filter> element can appear zero or one times
  - There is one attribute defined, called 'filter-type', which 
    identifies the type of filter processing requested by the manager
  - The content type is 'any' (any element outside the netconf
    namespace)

In addition, some name clarifications to the get operations
are needed:
  - For <get>, change the name of the <state> parameter to <data>.
  - For the <rpc-reply> associated with <get> and <get-config> 
    operations, change the return parameter name to <data>

Old Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <state>
        <foo xmlns="http://example.com/schema-1"/>
      </state>
    </get>
  </rpc>

New Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <foo xmlns="http://example.com/schema-1"/>
        </filter>
      </data>
    </get>
  </rpc>

New Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <foo xmlns="http://example.com/schema-1">7</foo>
    </data>
  </rpc-reply>
      
B) Issue 14.1.2: Subtree Filtering
----------------------------------

B.1) Overview

XML sub-tree filtering is a mechanism that allows an application
to select particular XML sub-trees to include in the <rpc-reply>
for a <get> or <get-config> operation.  A small set of filters
for inclusion, simple content exact-match, and selection is provided,
which allows some useful, but also very limited selection mechanisms.
The agent does not need to utilize any data-model specific
semantics during processing, allowing for simple and centralized 
implementation strategies. 

A sub-tree filter is comprised of well-formed XML.  No special tags, 
content, or structure are imposed in any way.  It is possible that
a sub-tree filter expression may contain an empty leaf node, even
if the XSD for the particular data model indicates some content
is required (i.e., maxOccurs > 0).  For this reason, it may not
be possible to completely validate all filter expressions 
against an XSD which represents the fully populated data model.

Conceptually, a sub-tree filter is comprised of zero or more 
element sub-trees, which represent the filter selection criteria.
At each containment level within a sub-tree, the set of sibling
nodes is logically processed by the agent to determine if
its sub-tree (and path to the root) are included in the filter output.

Element nodes have different purposes, depending on their position in 
the sub-tree.  Most nodes in the sub-tree identify containment, in 
which the specified node name must exactly match a corresponding node 
in the agent's data model.  A leaf node in the filter with simple 
content is used to select matching data (i.e., some or all of
the set of sibling nodes which includes this leaf node).

XML attributes can be present in any node in the filter.
Each attribute acts as an additional term for the "AND"
expression for that particular node.  In addition to
matching the name and position of the element, only instances
matching all specified attribute values will be included in
the response.

XML namespaces may be specified (via 'xmlns' declarations)
within the filter data model.  If so, the declared namespace
must first exactly match a namespace supported by the agent.
Only data associated with a specified namespace will be 
considered in the filter operation.

Response messages contains only the sub-trees selected by
the filter.  Any selection criteria that was present in the
request, within a particular selected sub-tree, is also included 
in the response.  Specific data instances are not duplicated
in the response in the event the request contains multiple filter 
sub-tree expressions which select the same data.

B.2) Sub-tree Filter Components

A sub-tree filter is comprised of XML elements and their XML
attributes.  An attribute which appears in a sub-tree filter
is called an "attribute match expression".  All elements
present in a particular sub-tree within a filter must match 
associated nodes present in the agent's conceptual data model.

Nodes which contain only child elements are called "containment nodes".
Leaf nodes which contain simple content are called "content match 
nodes".  Empty leaf nodes are called "selection nodes".

B.2.1) Attribute Match Expressions

Any number of (unqualified or qualified) XML attributes may
be present in any type of filter node.  In addition to the
selection criteria normally applicable to that node, the
selected data must have matching values for every attribute
specified in the node.  If an element is not defined to include
a specified attribute, then it is not selected in the filter
output.

B.2.2) Containment Nodes

Each node specified in a sub-tree filter represents an
inclusive filter.  Only associated nodes in the specified
conceptual datastore on the agent are selected by the filter.
A node must exactly match the namespace and absolute path name
of the filter data, except the filter absolute path name is
adjusted to start from the layer below <filter>.
A containment node must have one or more child nodes.

B.2.3) Content Match Nodes

A leaf node with simple content represents an exact-match filter on 
the simple content, which is combined (as an "AND" expression")
with the criteria for a containment node, to select data model 
instances.  All sibling content match nodes combine to represent
a logical "AND" expression.  

If all specified sibling content match nodes in a sub-tree filter 
expression are 'true', then the agent determines the nodes to be 
selected in the following manner:

  - if the set of all sibling nodes (at a given processing level)
    includes only content match nodes, then all sibling sub-trees
    (including the content match nodes) are selected by the filter.

  - if the set of all sibling nodes (at a given processing level)
    includes any containment or selection nodes, then only the 
    content match nodes, plus any sibling sub-trees selected by 
    further processing, are selected by the filter.

  - if a containment node is present in the sibling set, then
    it is potentially selected.  If further recursive processing 
    of its child nodes produces any selected filter output,
    then the containment nodes the element hierarchy related to
    the particular sub-tree are included in the filter results.

  - if a selection node is present in the sibling set, then
    its sub-tree is selected in the filter output.  

If any of the sibling content match node tests are 'false', 
then no further filter processing is performed on that sibling 
set, and none of the sibling sub-trees are selected by the filter,
including the content match node(s). 

B.2.4) Selection Nodes

An empty leaf node represents an "explicit selection" filter.  
Presence of any selection nodes (within a set of sibling nodes)
will cause the filter to select the specified sub-tree(s).
If a particular sibling set contains content match nodes and selection
or containment nodes, then automatic selection of the entire sibling 
sub-tree is suppressed, and only the specified selection and/or 
containment nodes are selected by the filter.  Unless further 
restricted by the application of attribute match expressions or 
content match nodes in the entire element hierarchy containing
a particular node, the presence of a selection node will cause 
all instances of that node (and each node's sub-tree) to be selected 
by the filter output.

B.3 Sub-tree Filter Processing Algorithms

The filter output (i.e., set of selected nodes) is initially empty.

Each sub-tree filter can contain one or more data model fragments,
which represent portions of the data model which should be selected
(with all child nodes) in the filter output.

Each sub-tree data fragment is compared by the agent to the
internal data models supported by the agent.  If the entire
sub-tree data-fragment filter (starting from the root to the
innermost element specified in the filter) exactly matches a 
corresponding portion of the supported data model, then that
node and all its children are included in the result data.

The agent processes all nodes with the same parent node 
(sibling set) together, starting from the root to the leaf
nodes.  The root elements in the filter are considered to
be in the same sibling set (assuming they are in the same
namespace), even though they do not have a common parent.

For each sibling set, the agent determines which nodes are
included (or potentially included) in the filter output,
and which sibling sub-trees are excluded (pruned) from
the filter output.  The agent first determines which types
of nodes are present in the sibling set, and processes
the nodes according to the rules for their type.  If any
nodes in the sibling set are selected, then the process
is recursively applied to the sibling sets of each selected 
node.  The algorithm continues until all sibling sets in all
sub-trees specified in the filter have been processed.

C) Examples
-----------
 
C.1: No filter

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      ... entire set of data models returned ...
    </data>
  </rpc-reply>

Notes:

 - Since the sub-tree filter is inclusive, and the start state
   is the empty set, the best way to get everything on the
   agent is to leave out the filter.  Not sure the best way
   to fit this into <get> and <get-config> operations though.

C.2: Empty filter

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter type="subtree">
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
    </data>
  </rpc-reply>

Notes:

 - Nothing is selected because no content match or selection
   nodes are present.  This is not an error.

C.3) Select the entire <users> sub-tree

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <users xmlns="http://example.com/schema-1"/>
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <users xmlns="http://example.com/schema-1">
        <user>
          <name>root</name>
          <type>superuser</type>
          <full-name>Charlie Root</full-name>
          <company-info>
            <dept>1</dept>
            <id>1</id>
          </company-info>
        </user>
        <user>
          <name>fred</name>
          <type>admin</type>
          <full-name>Fred Flintstone</full-name>
          <company-info>
            <dept>2</dept>
            <id>2</id>
          </company-info>
        </user>
        <user>
          <name>barney</name>
          <type>admin</type>
          <full-name>Barney Rubble</full-name>
          <company-info>
            <dept>2</dept>
            <id>3</id>
          </company-info>
        </user>
      </users>
    </data>
  </rpc-reply>
      
Notes:

 - The filter contains one selection node (<users>), so just
   that sub-tree is selected by the filter
 - This example represents the fully-populated <users> data model 
   in most of the filter examples that follow.  In a real
   data model, the 'company-info' would not likely be returned
   with the list of users for a particular host or network.
 - The following filter request would have produced the same
   result, but only because the container <users> defines one
   child element (<user>)

    <rpc message-id="101" xmlns="netconf-uri">
      <get>
        <data>
          <filter filter-type="subtree">
            <users xmlns="http://example.com/schema-1">
              <user/>
            </users>
          </filter>
        </data>
      </get>
    </rpc>

C.4) Select all 'name' elements within the 'users' sub-tree

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <users xmlns="http://example.com/schema-1">
            <user>
              <name/>
            </user>
          </users>
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <users xmlns="http://example.com/schema-1">
        <user>
          <name>root</name>
        </user>
        <user>
          <name>fred</name>
        </user>
        <user>
          <name>barney</name>
        </user>
      </users>
    </data>
  </rpc-reply>

Notes:

 - This filter contains two containment nodes (users, user),
   and one selector node (name).
 - All instances of the 'name' element in the same sibling set 
   are selected in the filter output.
 - The manager may need to know that 'name' is used as an
   instance identifier in this particular data structure,
   but the agent does not need to know that meta-data in 
   order to process the request.

C.5) One specific <user> entry

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <users xmlns="http://example.com/schema-1">
            <user>
              <name>fred</name>
            </user>
          </users>
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <users xmlns="http://example.com/schema-1">
        <user>
          <name>fred</name>
          <type>admin</type>
          <full-name>Fred Flintstone</full-name>
          <company-info>
            <dept>2</dept>
            <id>2</id>
          </company-info>
        </user>
      </users>
    </data>
  </rpc-reply>
      
Notes:

 - This filter contains two containment nodes (users, user)
   and one content match node (name).  
 - All instances of the sibling set containing 'name',
   for which the value of 'name' equals "fred", are selected
   in the filter output.

C.6) Specific elements from a specific <user> entry

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <users xmlns="http://example.com/schema-1">
            <user>
              <name>fred</name>
              <type/>
              <full-name/>
            </user>
          </users>
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <users xmlns="http://example.com/schema-1">
        <user>
          <name>fred</name>
          <type>admin</type>
          <full-name>Fred Flintstone</full-name>
        </user>
      </users>
    </data>
  </rpc-reply>
      
Notes:

 - This filter contains two containment nodes (users, user),
   one content match node (name), and two selector nodes
   (type, full-name).
 - All instances of the 'type' and 'full-name' elements in
   the same siibling set containing 'name', for which the value 
   of 'name' equals "fred", are selected in the filter output.
   The 'company-info' element is not included because the
   sibling set contains selection nodes.

C.7) Multiple sub-trees

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <users xmlns="http://example.com/schema-1"/>
            <user>
              <name>root</name>
              <company-info/>
            </user>
            <user>
              <name>fred</name>
              <company-info>
                <id/>
              </company-info>
            </user>
            <user>
              <name>barney</name>
              <type>superuser</type>
              <company-info>
                <dept/>
              </company-info>
            </user>
          </users>
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <users xmlns="http://example.com/schema-1"/>
        <user>
          <name>root</name>
          <company-info>
            <dept>1</dept>
            <id>1</id>
          </company-info>
        </user>
        <user>
          <name>fred</name>
          <company-info>
            <id>2</id>
          </company-info>
        </user>
      </users>
    </data>
  </rpc-reply>

Notes:
 
 - This filter contains three sub-trees (name=root, fred, barney)
 - The "root" sub-tree filter contains two containment nodes (users, 
   user), one content match node (name), and one selector node 
   (company-info).  The sub-tree selection criteria is met, and just 
   the company-info sub-tree for "root" is selected in the filter 
   output.
 - The "fred" sub-tree filter contains three containment nodes 
   (users, user, company-info), one content match node (name), and 
   one selector node (id). The sub-tree selection criteria is met, 
   and just the 'id' element within the company-info sub-tree for 
   "fred" is selected in the filter output.
 - The "barney" sub-tree filter contains three containment nodes (users, 
   user, company-info), two content match nodes (name, type), and one 
   selector node (dept). The sub-tree selection criteria is not met
   because user "barney" is not a "superuser", and the entire sub-tree 
   for "barney" (including its parent 'user' entry) is excluded from
   the filter output.

C.8) Table with attribute naming

Request:

  <rpc message-id="101" xmlns="netconf-uri">
    <get>
      <data>
        <filter filter-type="subtree">
          <t:interfaces xmlns:t="http://example.com/schema-2"/>
            <t:interface t:ifName="eth0"/>
          </t:interfaces>
        </filter>
      </data>
    </get>
  </rpc>

Reply:

  <rpc-reply message-id="101" xmlns="netconf-uri">
    <data>
      <t:interfaces xmlns:t="http://example.com/schema-2">
        <t:interface t:ifName="eth0">
          <t:ifInOctets>45621</t:ifInOctets>
          <t:ifOutOctets>774344</t:ifOutOctets>
        </t:interface>
      </t:interfaces>
    </data>
  </rpc-reply>
      
Notes:

 - This filter contains one containment node (interfaces), one 
   attribute match expression (ifName), and one selector node
   (interface).
 - All instances of the 'interface' sub-tree which have an
   ifName attribute equal to "eth0" are selected in the
   filter output.
 - The filter data elements and attributes must be qualified 
   because the 'ifName' attribute will not be considered part 
   of the 'schema-2' namespace if it is unqualified.
 - If 'ifName' were a child node instead of an attribute, then
   the following request would produce the same results:

    <rpc message-id="101" xmlns="netconf-uri">
      <get>
        <data>
          <filter filter-type="subtree">
            <interfaces xmlns="http://example.com/schema-2">
              <interface>
                <ifName>eth0</ifName>
              </interface>
            </interfaces>
          </filter>
        </data>
      </get>
    </rpc>

D) Open Issues
--------------

D.1) "No Such Object/Instance"

Is it important that an NMS know if results are empty because
the filter will never match anything (noSuchObject) or
the results are empty because the well-specified dynamic table
is empty (noSuchInstance)?

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/netconf/>