Description of the LQN XML Schema

                                                    Peter Maly

                                                  March 2004


Introduction

    The definition of LQN models using XML is an evolution of the original SRVN
file format [2].  The new XML format is based on the work done in [4], with
further refinement for general usage.  There are new features in the XML format
to support new concepts for building and assembling models using components.
The normal LQN tool suite (like LQNS, ParaSRVN) do not support these new
features, however other tools outside the suite are being written to utilize
the new parts of the XML format.

   It is assumed that the reader of this document has a working understanding
of Layered Queuing Network models [3], and is somewhat familiar with the
various parameters that go into the model [2].  This document does not go into
the details of the new extensions introduced in [4] such as components, slot,
interface, sub-models, etc...


Basic XML terminology

    Anyone who is familiar with basic XML terminology can skip this section.  In
order to use the XML format version of the LQN input file, one does not have to
be an expert in XML.  There are three pieces of terminology which are used
throughout this document and are described here for convenience.  For further
information about XML, please consult the wealth of book and web sites
pertaining to the topic.

Element	Also known as a "tag", which is anything inside a XML file encapsulated by < and > characters.  For example a processor element in XML would appear as <processor>.  Whatever data is contained within the processor element would be encapsulated by the start tag <processor> and end tag </processor>.  Elements that contain no data can be written as <processor></processor> or in short hand <processor/>.
Attribute	Defines the property of an element.  Continuing with the example of the processor element, a processor could have a name of "p1" and a multiplicity of 3.  This would be shown in XML by: <processor name="p1" multiplicity="3"> where name and multiplicity are attributes of the element processor.
XML schema	Is a standard which defines rules by which an XML file must follow in order to be VALID.  When a XML parser reads in a XML file, it may have the ability to validate the XML file against the XML schema. More information about XML schemas can be found in [1] or other books and/or sources on the WWW.
Constraint checking	Part of the XML schema standard to allow powerful error checking on a XML file.  The two constraints defined in the XML schema standard are to ensure uniqueness across a specified element and/or attributes, and ensure references made to other parts of an XML file exist.

How to use the XML Schema

The three schema files which comprise the XML definition for layered models are:

lqn.xsd
lqn-sub.xsd
lqn-core.xsd

The first line of any XML LQN model will look like this:

<lqn-model xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:noNamespaceSchemaLocation="lqn.xsd">

    Notice that the root element of the XML specification is lqn-model, and
through the xsi:noNamespaceSchemaLocation attribute, it specifies that
this XML file conforms to the lqn.xsd schema.  The bulk of the specification
that pertains to defining a LQN model is in the lqn-core.xsd file, and is
included by lqn.xsd.  From a user's perspective, ensure that all three
.xsd files exist have the same path, i.e. exist in the same location.  For more
information about the schema, see http://lqn.html and [4].


Basic structure of the XML file

    Given the tree/hierarchical nature of XML, layered models are specified in a
bottom-up order, which is the reverse of how layered models are typically
presented.  A simplified layout of an incomplete LQN model written in XML
is shown below:

<lqn-model>
   <solver-params>
      <pragma/>
   </solver-params>
   <processor>
      <task>
     <entry>
        <entry-phase-activities>
           <activity>
          <synch-call/>
          <asynch-call/>
           </activity>
           <activity> ... </activity>
         </entry-phase-activities>
            <entry-activity-graph>
               <activity/>
               <precedence/>
            </entry-activity-graph>
     </entry>
         <entry> ... </entry>
         <task-activities>
            <activity/>
            <precedence/>
         </task-activities>
      </task>
      <task> ... </task>
   </processor>
   <processor> ... </processor>
</lqn-model>

    Notice how a processor is defined first, then within the processor block
all the tasks associated with it, then within the task block all the entries
associated with, etc...

    Activity graphs (specified by task-activities) belong to a task, and hence
are siblings to entry elements.  The element entry-activity-graph specifies
an activity graph contained within one entry, but is not supported by
any of the LQN tools.  The concept of phases still exists, but now
each phase is an activity, and is defined in the entry-phase-activities
element.

   The link core XML LQN schema contains all the required details for
defining LQNs using the new XML format.

    For completeness, the detailed description of the lqn-submodel schema has
also been included with the documentation, but is not expanded on. Refer to
[4] for more details.


List of constraints that the XML schema enforces for validity

• All processor have a unique name
• All tasks have a unique name
• All entries have a unique name
• All activities have a unique name within a given task
• All synchronous calls must have a valid destination
• All asynchronous calls must have a valid destination
• All forwarding calls must have a valid destination
• All activity connections (in precedence blocks) refer to valid activities
• All activity replies must refer to a valid entry
• All activity loops must refer to a valid activities
• Each entry has only one activity bound to it
  
• Phases restricted to values 1-3 (mainly for legacy purposes)
• All phase attributes within an entry must be unique

Tips on debugging an XML file

    The entire LQN tool set uses the Xerces XML parser library.  From personal
experience it does not appear to be the most rigorous when validating XML files
against schemas, and also tends to give rather cryptic error messages as opposed
to other tools.

    If an XML file fails to pass the validation phase, and the error looks cryptic,
chances are very good that there is a genuine problem with the XML file.  Xerces
has a bad habit of coming back with cryptic errors when constraint checking
fails, and only gives you the general area in the file where the actual problem
is.

    One easy and convenient solution around this problem is to validate the XML file
using another XML tool.  Tools that have been found to give more user friendly
feedback are XMLSpy (any edition), and XSDvalid (Java based, freely available).
Another solution is to check if a particular tool can de-activate schema
validation and rely on the actual tool to do its own internal error checking.
Currently this is no supported in any of the LQN tools which are XML enabled,
but it maybe implemented later on.

    If the XML file validates using other tools, but fails validation with Xerces,
or if the XML file fails validation on other tools, but passes with Xerces then
please report the problem.  The likelihood of validation passing with Xerces and
not other tools will be much higher then the reverse scenario, because Xerces
does not rigorously apply the XML Schema standard as other tools.  Other sources
of problems could be errors in the XML schema itself, or some unknown bug in the
Xerces library.



Tips on interpreting error messages from the Xerces XML parser

As mentioned in the previous section, Xerces reports cryptic error messages when
constraint checking fails.  If another XML tool is not readily available
then below are some guidelines to assist in finding the error in an XML file.

Possible error messages when constraint checking fails:

Message: Duplicate unique value declared for identity constraint of element 'task'.

This means one or more activities are being bound to the same entry.  This is not
allowed, as an entry is only allowed to be bound to one activity.  Check all
bound-to-entry attributes for all activities to ensure this constraint is being met.


Message: Duplicate unique value declared for identity constraint of element 'lqn-model'.

This means an element has a duplicate name, and the parser gives the line number
to the start of the second instance of duplicate element.  The first instance
exists somewhere above the the second instance in the XML file.  The following
elements must have unique name attributes, but the uniqueness does not span
elements.  Therefore a processor and task element can have the same name
attribute, but two processor elements cannot have the same name attribute.

The following elements must have a unique name attribute:

• processor
• task
• entry

Message: The key for identity constraint of element 'lqn-model' is not found.

When this error appears, Xerces does not give too many hints on where the error
actually occurs because it will always give a line number which points to the
end of the file (i.e. where the terminating tag </lqn-model> is).

In this case, the following three points should be inspected to ensure validity
of the model:

• All synchronous calls have a dest attribute which refers to a valid entry.

• All asynchronous calls have a dest attribute which refers to a valid entry.

• All forwarding calls have a dest attribute which refers to a valid entry.

If it is not practical to manually inspect the model, run the XML file through
another tool like XMLSpy or XSDvalid which will report more descriptive errors.


Message: The key for identity constraint of element 'task' is not found.

When this error appears, it means there is something wrong within the task element
indicated by the line number.
Check to make sure that:

• The name attribute of all reply-entry elements refers to a valid entry name,
  which exists within the same task as the task activity graph.

• All activities which contain the attribute bound-to-entry have a valid entry
  name that exists within the same task as the task activity graph.
  

Message: Duplicate unique value declared for identity constraint of element 'task'

When this error appears, it means an activity does not have a unique name within
the task element specified by the XML parser error output.


Message: The key for identity constraint of element 'task-activities' is not found.

When this error appears, it means there is something wrong within the
task-activities element indicated by the line number.

Check to make sure that:

• All activities referenced within the precedence elements refer to
  activities which are defined for that particular task activity graph.
  

• The name attribute of all reply-activity elements refers to an activity
  defined within the mentioned task-activities element.

• The head attribute of all post-LOOP elements refers to an activity defined
  within the mentioned task-activities element.

• All post-LOOP elements which contain the optional attribute end, refers to
  an activity defined within the mentioned task-activities element.
  

References

1. R. Allen Wyke, A. Watt, XML Schema Essentials, John Wiley & Sons Inc,
   2002.
   
   
2. D. C. Petriu, R. G. Franks, A. Hubbard, "SRVN Input File Format", RADS Lab
   internal report - Carleton University, November 1998.
   
   
3. C.M. Woodside, J.E. Neilson, D.C. Petriu and S. Majumdar, "The Stochastic
   Rendezvous Network Model for Performance of Synchronous Client-Server-Like
   Distributed Software", IEEE Transactions on Computers, Vol. 44, No. 1,
   January 1995, pp. 20-34.
   
   
4. Xiuping Wu, "An Approach to Predicting Peformance for Component Based
   Systems", M. Eng thesis, Carleton University, August 2003