Hi,

Here is an advance copy of the Grid Notification Document.
Suggestions, corrections, improvements and discussion requested.
Please send grammatical corrections directly to me, topics of general
interest could be copied to people in this e-mail. I hope to send this
to the general MDS list in a couple of days.

thanks
sridhar

****

Notification Framework (version b0.1)


USC/Information Sciences Institute		Sridhar Gullapalli
Globus ISI Group				Karl Czajkowski
						Carl Kesselman

California State University, Northridge		Steven Fitzgerald


		The Grid Notification Framework



Status of this Memo:

This document specifies the Grid Notification Framework developed for
the Grid community, and requests discussion and suggestions for
improvements.



Abstract:

This document describes a generic notification framework through which
information about the existence and state information of a grid entity
can be propagated to other grid entities.  Grid entities include
machines, hardware devices, instruments, people such as users or
system administrators.  The framework is based on periodic messages
being dispatched by a declaring entity to one or more receiving
entities.  Upon receipt of these messages, receiving entities can
interpret the contents of the message to generate or update their
belief of entity being described.



This Document Specifies:

    i) The structure of the message that asserts the existence and
       includes state information about a particular entity.  In
       addition, part of the message delimits the time interval during
       which the state information contained within the message may be
       expected to be valid.

   ii) The interaction between the entities to aggregate information
       for use in a distributed environment such as the Grid.
       Applications built on top of this framework can use the
       information within the messages to keep track of the existence
       and the state of entities.

  iii) The application specific transport mechanism to carry out
       underlying communications. SOAP is offered as a candidate
       transport protocol.

   iv) Example uses of this framework to develop services such as
       registrations and invitations for Virtual Organizations (VOs).



Limitation of the Framework:

Entities in this framework make assertions about the existence and
state information of other entities in a distributed environment.
These assertions are actually beliefs based on information from
received messages and cannot be guaranteed to be accurate.
Network delays, partitioning and the potential for unpredicted state
change (failure of machines) could render some of these beliefs to be
incorrect and consequently notification events cannot be construed as
representing absolute truth.



Approach taken by the Framework:


Two levels of information are conveyed by each message: 1) the
existence and 2) state information of an entity, with separate
intervals of time associated with the validity of each piece of
information.  These intervals can be adjusted to balance between the
(validity) currency of information versus the cost of generating,
propagating, and processing each message.



Key Aspects of the Framework Include:

  - Soft-state model that provide a robust notification mechanism
    coupled with graceful deprecation of stale information and
    services associated with the Grid

  - Application selectable time intervals that determine the longevity
    of each datum within the system.

  - This framework is intended for use in an environment that provides
    authentication and integrity of information -- over connections
    authenticated using GSI, or within messages signed using GSI
    credentials.

  - Generic framework that can be used to implement a variety of
    services including, but not limited to registrations, invitations,
    secure job monitoring and submissions.


1. Model of Notification Framework

The model adopted by this framework is that of peers communicating
with one another within a distributed environment.  This assumption
implies that messages might not be received by an entity due to many
reason, such as network congestion or partitioning.  Additionally,
entities might not be capable of sending messages, due to planned or
unplanned interruptions of service.  Thus, entities must not assume
that they will receive a message from a peer.

The framework relies on periodic assertions (or positive messages)
that confirm the existence of and provide information about an entity.
When faced with the absence of messages, the framework cannot provide
insight pertaining to either the failure or non-failure of entities.

A soft-state model is developed and maintained at each receiving
entity as part of this framework.  This state is developed from
information contained within messages pertaining to the existence of
and associated state information about entities.  Each message
contains a time interval to indicate the longevity of the message
within the system.

This framework does not define how to interpret the state information
contained within the message, nor does it specify what processing must
be performed by the entity receiving the message.  Receivers can
simply note the existence of the message, perform some additional
interactions with the described entity, or log the information to
stable storage.  For example, an entity can recover its beliefs of a
remote entity after a system failure or restart by consulting logged
information.  The obvious exception are those messages that may have
been lost during downtime.

This framework can be used to map relatively steady state conditions
with the Grid, where a majority of messages get delivered in a timely
manner.  It fails to provide reliable information when rapid changes
occur to an entity, to the network topology, or to network congestion.



1.1 Definitions:


Message (MSG):
	MSG is a message that transmitted between entities within the
	Grid for the purpose of notification.

Auxiliary Data (AUX):
	AUX is a single datum associated with a notification message
	that provides state information about an described entity.

Described Entity (DES):
	DES is the entity whose existence is being asserted and whose
        state is being described by auxiliary data (AUX), included
        within the framework message (MSG).

Declaring Entity (DCL):
	DCL is the entity that asserts the validity of the
	information contained within the MSG.

Sending Entity (SND):
	SND is the entity that initiates the propagation of the
        MSG.

Receiving Entity (RCV):
	RCV is the entity that receives and interprets the MSG.  RCV
	is also the entity that can provide the information within the
	MSG to other external services (such as search engines).



1.2 Timestamps:

Each framework message includes three timestamp values TS1, TS2 and
TS3.  Timestamps are relative to the global time as perceived by DCL.
The values of the three timestamps are related via the constraint:

      TS1 <= TS2 <= TS3


Here we define the operator "<=" to define the relationship between
two timestamps.  TS1 <= TS2 is defined to be true if and only if the
time specified by TS2 occurs after the time specified by T1.  We also
use the operator "<", to denote that the time specified by TS1 occurs
before the time specified by T2.



2. The General Notification Exchange:


2.1  Entity Relationship Diagram:

     _______         ______         ______
    |       |       |      |  MSG   |      |
    | DCL   |------>| SND  |------->| RCV  |
    |_______|       |______|        |______|
        ^
        :
        :
        :
    ____:________
    |           |
    | DES (AUX) |
    |___________|




2.2 Description of a Notification Event:

A notification event within this framework is defined as a message (MSG)
generated by DCL, based on knowledge about DES, transported by SND and
received by RCV.  The framework does not specify how DCL obtains
information about DES.

The RCV entity accepts the message from SND.  The message asserts the
existence of DES with the state property AUX at time TS1.

Note that by the time the message reaches RCV, there is no guarantee
that DCL's assertion is still valid.  Independent verification of the
information could be performed using a variety of methods, one method
is to utilize the enquiry operation associated with the Grid
Information Service (GIS).  The enquiry can be directed towards either
DES or DCL.

Each message contains the required information to locate (name),
contact (protocol) and securely communicate (credentials) with the DES
or DCL entities to obtain additional information.



2.3  Message Semantics

Each notification message within this framework is interpreted to
represent the following statement:

    "DCL asserts that at time TS1,
       DES exists and AUX is valid until time TS2 and
       DES is expected to exist until time TS3."

The notion of existence indicates that a valid name is associated
with an entity.  The entity may or may not be "alive" or functioning.



2.4  Some Special Cases of the Notification Exchange:

In the general case, DCL, DES and SND may be different entities.
Notably, DCL could be a system administrator, SND and DES could be
Grid services, and RCV could process a message to provide information
to other applications.

In some implementations, however,  three of the above four entities can
identify a single entity leading to a special case of the framework, as
described below.

SND (sending entity), DCL (declaring entity) and DES (described
entity) may identify a single entity.  In this case, SND informs RCV
that it is alive and has state information (AUX) that is valid from
time TS1 until time TS2.  RCV may assume that SND exists between time
TS1 and TS3.



3. Finite State Automata (FA) at the Receiving Entity:

RCV's belief of a described entity can be modeled via a three-state
FA.  The meaning associated with three states are:

   S1: There are no applicable assertions from DCL about DES.
   S2: DCL asserts that DES exists and AUX is valid.
   S3: DCL asserts that DES exists and AUX is uncertain


                                        __________
                                       |          |
                                       |          |iii(MSG)
                                       v          |
      ----------     i(MSG)      ------------     |
     |          |-------------->|            |    |
  -->|    S1    |               |     S2     |----
     |__________|<--------------|____________|
         |   ^       ii(MSG)         |  ^
         |   |                       |  |
         |   |                       |  | v(MSG)
         |   |                    iv |  |
         |   |                       |  |
         |   |    vi(TS3)       _____v__|____
         |   |---------------- |             |
         |                     |     S3      |
         |-------------------> |_____________|
                 vii(MSG)



A state transition occurs when there is a change in RCV's beliefs
about a DES entity.  RCV's belief changes either through the
expiration of time or by the receipt of a valid message (MSG).

This framework performs two types of time comparisions i) between a
message timestamp and the current time as known at RVC, and ii) between
timestamps in two messages from the same DCL about the same DES.
In both cases, the application of this framework defines a comparision
function to determine which value is more recent.

We define Current_TS to be the global time as perceived by the RCV.
The use of Current_TS is then used to determine whether or not a
message is relevant.  Messages are considered to be relevant, if:


          Current_TS <= TS3

where the definition of '<=' is defined by the application of the
framework.

If RCV receives multiple relevant messages about a particular DES from
a particular DCL, only the message with most recent TS1 is considered.
The other messages are discarded.  Consider the case where two
messages, A and B, arrive at RCV with the timestamp TS1 set to TS1a
and TS1b, respectively.  If TS1a is more recent than TS1b (i.e.,
TS1b < TS1a), message B is discarded.  Notice that message ordering does
not determine which message is discarded.



Transitions within the State Diagram:

In this section, we describe the transitions that are made within the
given FA.  Each state transition is labeled as a Roman numeral.
Additionally, either the string MSG or TSn is provided within a set of
parentheses.  These strings indicate that the transition may occur
when a relevant message (MSG) arrives or when a constraint on
timestamps changes, respectively.

Note that the the timestamps from the previous relevant message is
retained.  We denote these timestamps as TS1', TS2', and TS3'.


The initial state is S1.  The conditions for each transition are as follows:

   (i) RCV receives a new message that obeys the constraint:

           TS1' < TS1  AND  Current_TS <= TS2 <= TS3

       The new message provides relevant information about DES.
       Hence, RCV's beliefs about DES moves from state S1 to state S2.


  (ii) RCV receives a new message that maintains the constraint:

           TS1' < TS1  AND  TS2 <= TS3 <= Current_TS

       The new message invalidates the previous received message.
       Hence, RCV's belief about DES moves from state S2 to state S1



 (iii) RCV receives a new message that maintains the constraint:

           TS1' < TS1  AND  Current_TS <= TS2 <= TS3

       (Recall that TS1' refer to the TS1 timestamp of the previously
       received message.)

       The new message provides updated information about DES.
       RCV's belief of DES remains in state S2, with updated times.


  (iv) Either:

         - RCV receives a new message that maintains the constraint:

               TS1' < TS1  AND  TS2 < TS2'  AND  TS3' <= TS3

         - sufficient time passes, which validates the constraint:

               TS2' < Current_TS <= TS3'

       The AUX value is no longer current.  Hence, RCV's belief about
       DES moves to state S3.


  (v)  RCV receives a new message that maintains the constraint:

            TS1' < TS1  AND  Current_TS <= TS2 <= TS3

       The new message is more current than the previous message.
       Hence, RCV's belief about DES moves from state S3 to S2.


  (vi) Sufficient time passes, which validates the constraint:

            TS3' < Current_TS

       The stored message is no longer relevant.  Hence, RCV's beliefs
       about DES is obsolete, and it transitions to S1.


 (vii) RCV receives a new message that maintains the constraint:

            TS1' < TS1  AND  TS2 <= Current_TS <= TS3


       The new message indicate that DES exists but the AUX value is
       not current.  Hence, RCV's beliefs about DES moves from state
       S1 to S3.




4. Framework Message Format

To develop a protocol based on the above framework all operations are
encapsulated in a common envelope, called the MSG.


         MSG::=    SEQUENCE {
                       version          Integer,
                       dcl_name         SubjectName,
                       dcl_location     Location,
                       des_name         SubjectName,
                       des_location     Location,
                       ts1              Timestamp,
                       ts2              Timestamp,
                       ts3              Timestamp,
                       auxiliary_state  BIT STRING
                       }

         Location ::= IA5String
	     -- a URL as defined in RFC2396

         SubjectName ::= UTF8String
             -- a representation a DN as defined in RFC 2253

  	 Timestamp ::= Grid Forum Representation



The MSG is either sent via an authenticated connection using GSI or
within messages signed using GSI credentials.

  Note: The specification of the above message content (auxiliary
    state) will be translated into a SOAP(/XML) description of the
    fixed metadata content and the potentially nested AUX data field.
    This translation will be appended to this document in the near
    future.  An appropriate standard variation including XML signature
    syntax will also be specified to support optional DCL-signed
    messages.



4.1 Description of the elements:

  Version: The version number associated with the implementation of
      this framework.

  dcl_name: The name of the declaring entity, in UTF8String format---a
      representation a DN as defined in RFC 2253.

  dcl_location: The location of declaring entity.  It is a URL (DNS
      Name, protocol and the port number) in IA5String---a URL as
      defined in RFC2396.

  dcl_name: The name of the described entity, in UTF8String format---a
      representation a DN as defined in RFC 2253.

  des_location: The location of described entity.  It is a URL (DNS
      Name, protocol and the port number) in IA5String---a URL as
      defined in RFC2396.

  ts1: The time at which the declaring entity asserts information
      about the described entity.  It is in the ascii Grid Forum
      representation of time (Appendix A).

  ts2: The time past which a declarer no longer has confidence in the
      information about the described entity.  It is in the ascii
      Grid Forum representation of time (appendix A).

  ts3: The time past which a declarer suggests that all information
      about the described entity may be purged.  It is in the ascii
      Grid Forum representation of time (appendix A).

  Auxiliary Data: Information about the properties (state) of the
      described entity.  This is in XML format.


5. Mapping onto Transport Services

This framework is designed to run at the applications level over a
transport layer.  For example, SOAP over HTTP/HTTPS can be used as
the underlying transport layer.



6. Developing An Information System for the Grid

A specific instantiation of the above protocol can be used to develop
an information system for the Grid environment.

We introduce two types of notification services
   o registration
   o invitation

The use of these services facilitate the aggregation of information
from grid entities, which can then be queried by external applications
and services.



6.1 Registration:

Registration is the mechanism by which an entity (SND) provides
information to another entity (RCV).  This information can describe
the status of SND or provide information about a third party (DES).
The information is carried within the auxiliary (AUX) part of the
message.



6.2 Invitation:

Invitation is the mechanism by which a grid entity (RCV) acting as an
aggregator solicits information from other entities (SND).  This
aggregator can then be queried by external services and entities for
this collated information.




Appendix A: Use of Grid Forum Timestamp Notation (ASCII representation):

  Editors note: I have just been informed, that the format of the Grid
      Forum Timestamp Notation has changed.  The appendix below is yet
      to be revised to reflect this change.


Some of the entities in this framework could be human beings.  For
instance, the DCL (declaring entity) could be a system administrator.
Thus having information in a format that emphaseses readability in
preference to compactness of representation and ease of computer
manipulation is preferred.  Therefore, we propose to specify timestamp
values in an ASCII format as opposed to a binary format.

There are three components within a timestamp,

    i) the time value
   ii) the precision by which it is measured, and
  iii) the accuracy


We propose following the Grid Forum (draft) "A Standard Timestamp for
Grid Computing" for determining the representation.  The proposed
value is represented using a variation on ISO8601 time standard in a
calendar-style.  For example

    2001-02-28-08:34:26.3032Zp.0005a.001

is a timestamp expressed within this notation.  The first component,
the value, extends until the symbol "Z", which indicates that UTC time
is specified.  The subcomponents of the time value are:

  Year: 2001
  Month: 02 (February)
  Day: 28
  Hour: 8 AM
  Minutes  34 minutes
  Seconds: 26.303  (26 seconds and 303 milliseconds)


The second component, the precision, is optional and is preceded by a
"p" whenever present.  Within the given example, .0005 specifies a 0.5
millisecond precision.  The third component, the accuracy, is optional
and is preceded by an "a" whenever present.  An accuracy of 0.001 is
specified within the given example.