# ----------------------------------------------------------------------------
#  $RCSfile: xbone-control-protocol.txt,v $
#
# $Revision: 1.8 $
#   $Author: yushunwa $
#     $Date: 2003/10/13 21:09:56 $
#    $State: Exp $
# ----------------------------------------------------------------------------
#
# Primary Author: Yu-Shun Wang
# First Version:  2002/4/11
#
# ----------------------------------------------------------------------------

                          X-Bone Control Protocol
                              Yu-Shun Wang

>>> Introduction

    Note: This protocol should be as generic as possible so that if the term
          "XBone" in this document is replaced with "Virtual Network", it is
          still a valid protocol to be deployed in the Internet.

    This document describes the XBone Control Protocol, a protocol for
    controling and managing nodes in a virtual network. The primary purpose of
    this protocol is to discover, select, configure, and monitor nodes of a
    virtual network. It is a one-to-many communication protocol and can be used
    recursively to support large scale divide-and-conquer type of deployments
    and recursive virtual networks.

    - Initiator: GUI, OM, applications
    - Responder: OMs, RDs.

    The following describes the message exchange part of the protocol.


>>> Create - Four-Phase Create

    Notations:
      *   Multicast message (SMIME-signed UDP)
      ^   Unicast SMIME-signed UDP
      ->  Unicast message, TCP/SSL unless noted otherwise
      =>  Multiple unicast messages


       [Level N] ................ [Level N+1] ................ [Level N+2]

       Req-<OVL>                       <Idle>
         [1]                              .
           .\                             .
           . \ INVITE-<OVL>*              .
           .  ------------------->        .
           .                      \       .
         <Phase I: Invite>         \      .
           .                        [2]-------
           .                       /      .
           .   ACK-INVITE-<OVL>^  /       .
           .  <===================        .
           . /                            .
           ./                         <Reserve>
         [3]                              .
           .\                             .
           . \ SELECT-<OVL>               .
           .  ===================>        .
           .                      \       .
         <Phase II: Select>        \      .
           .                        [4]-------
           .                       /      .
           .    ACK-SELECT-<OVL>  /       .
           .  <===================        .
           . /                            .
           ./                         <Select>
         [5]                              .
           .\   RELEASE-<OVL>* &          .
           . \  DISPATCH-<OVL>            .
           .  ===================>        .
           .                      \       .
           .                       \      .
           .                        [6]------- <<= Point of Recursion
           .                        | [1']
           .                        |    \
           .                        |     \   INVITE-<OVL>*
           .                        |      ------------------->
           .                        |                          \
           .                        | <Phase I: Invite>         \
           .                        |                            [2']
           .                        |                           /
           .                        |        ACK-INVITE-<OVL>  /
           .                        |      <===================
           .                        |     /
           .                        |    /
           .                        v [3']
           .                             \
           .                        R     \    SELECT-<OVL>
           .                        E      ===================>
         <Phase III:                C                          \
                                    U <Phase II: Select>        \
           Commit/Release>          R                            [4']
           .                        S                           /
           .                        E        ACK-SELECT-<OVL>  /
           .                               <===================
           .                              /
           .                        ^    /
           .                        | [5']
           .                        |    \   RELEASE-<OVL>* &
           .                        |     \   COMMIT-<OVL>
           .                        |      ===================>
           .                        |                          \
           .                        | <Phase III:               \
           .                        |   Commit/Release>          [6']
           .                        |                           /
           .                        |        ACK-COMMIT-<OVL>  /
           .                        |      <===================
           .                        |     /
           .                        |    /
           .                        | [7']
           .                        [6] <- End of Recursion
           .    ACK-COMMIT-<OVL>   /
           .  <===================/
           . /
           ./
         [7]
           .\
           . \    CONFIG-<OVL>
           .  ===================>
           .                      \
           .                       \
           .                        [8] <- Point of Recursion
           .                        | [7']
           .                        |    \
           .                        v     \    CONFIG-<OVL>
           .                        R      ===================>
           .                        E                          \
           .                        C                           \
         <Phase IV: Config>         U <Phase IV: Config>         [8']
           .                        R                           /
           .                        S         ACK-CONFIG-<OVL> /
           .                        E      <===================
           .                        ^     /
           .                        |    /
           .                        | [9']
           .                        [8] <- End of Recursion
           .                       /
           .     ACK-CONFIG-<OVL> /
           .  <===================
           . /
           ./
         [9]

>>> Level N [Left Hand Side or OM]

    <Phase I: Invite>

    [1] - Receive API request to create an overlay, API-Req-<OVL>.
        - Parse API command & generate corresponding data structure for the
          overlay.
        - Generate INVITE command & sign it with SMIME.
        - Send out multicast INVITE-<OVL> message.
        - Start timer and collect ACK-INVITE-<OVL>.
        - Timeout: Do we have enough ACKs?
          [Y] Done. Return a list of nodes.
          [N] Should we retry?
              [Y] Loop back to multicast INVITE-<OVL>.
              [N] Fail. Send multicast RELEASE-<OVL> and die.
                  Caller should send an API-Error back.
        * State: Overlay object hash & a list of nodes that replied.

    <Phase II: Select>

    [3] - Given a list of nodes, apply whatever criteria or optimization
          to select a set of nodes.
        - Send unicast TCP/SSL SELECT-<OVL> to the selected nodes.
        - Start timer and collect ACK-SELECT-<OVL>.
        - Receive all ACKs?
          [Y] Done. Return a list of selected nodes.
          [N] Timeout or NACKs:
              - Send DELETE-<OVL> to all selected nodes.
              - Send multicast RELEASE-<OVL>.
              - Die.
              - Caller should send API-Error back.

        - Caller should map the physical
    <Phase III: Commit|Propose/Release>

    [5] - Send multicast Release-<OLV> to release non-selected RDs in [2].
        - Assign sub-overlays to chosen OMs and form the invitation or cmds
          (XOL of the sub-overlays & total number of sub-OMs at this level)
          to send with COMMIT-<OVL>.
        - Send TCP/SSL COMMIT-<OVL> to selected nodes. This will trigger
          recursive <Invite>, <Select>, and <Commit> of the next layer.
        - Start timer and wait for ACKs.
        - Receive all ACKs: Done. Return a completely pinned down OVL spec.
          [OR] Timeout or NACKs: Failed.
               - Send DELETE-<OVL> to all selected nodes.
               - Die.
               - Caller should send API-Error back.

    <Phase IV: Config>

    [7] - Form the configuration commands to each node.
        - Send TCP/SSL config commands to all nodes.
        - Start timer and wait for ACKs.
        - Received all ACKs: Succeed. Return completed overlay data structure.
          [OR] Timeout or NACKs: Failed.
               - Send DELETE-<OVL> to all selected nodes.
               - Clean up local state. Delete overlay.
               - Caller should send API-Error back.

    [9] - Succeed. Commit overlay state, send API-Reply back.


>>> Level N+1 [Right Hand Side, RD or Sub-OM]

    [2] - RDs: Receive Discover-<OVL>, 
               Reserve resource (state: Reserve),
               Reply.
        - OMs: Receive Discover-<OVL>,
               (Nothing to reserve),
               Reply.

    * If <OVL> has NO non-recursive nodes (RDs), skip Phase II.


    [4] - Selected RDs: Receive Select-RD, 
                        Commit reserved resources (state: Commit),
                        Send Ack-Select-RD back.

    * If <OVL> has NO recursive nodes (OMs), send multicast Release-<OVL>,
      and skip Phase III.

    [6] - Non-selected RDs receive Release-<OVL>, release resources.
        - Selected OMs receive Req-<sub-OVL>, the specifications of the
          sub-overlays, start their own Discover & Select process (Phases I,
          II, & III). 
          => POINT OF RECURSION!
        - Once selected OMs finished their Phase I to III, send Ack-<sub-OVL>
	  back.
        * The Select-OM part might need to be serialized among multiple OMs
	  if we want to ensure
          (1) node exclusiveness among overlays,
          (2) no starvation among several competing OMs.

    [8] - RDs: Receive config commands, 
               start configuring nodes,
               send Ack-Config.
        - OMs: Receive config commands, 
               send out config commands recursively to their RDs,
               => POINT OF RECURSION!
               gather all (sub)Ack-Config's,
               send Ack-Config.

    [9] - Receive all Ack-Config. Send success, done!

  > State transition diagrams

    * Note that the following state transition diagrams assume that OM and
      RD are separate entities/processes.

    - Notations:

        - T/O = Timeout
        - OVL = Overlay Specification
        - SND = Send
        - RCV = Receive
        - IF  = Condition on
        - ACT = Internal actions
        - NOP = No Operation
        - *   = Multicast message
        - ^   = Message send to the user 
        - @   = Message received from the user


    1. For GUI/OM:
                               +----+  +----+
                  RCV: Discover|    |  |    |RCV: Discover
                  IF:  ACL Ok  |    |  |    |IF:  ACL not ok
                  SND: Reply   |    |  |    |ACT: NOP
                               +->+------+<-+
 +------------------------------->| IDLE |<----------------------------------+
 |                                +------+                                   |
 |                                  |  ^                                     |
 |                   RCV: Req-<OVL>@|  | T/O: Not Enough                     |
 |                   SND: Discover* |  | SND: Fail^                          |
 |                                  |  | SND: Release-<OVL>*                 |
 |                                  v  |                                     |
 |                             +-------------+                               |
 |                             |  DISCOVERY  |                               |
 |                             +-------------+                               |
 |            T/O: Enough Reps  |           |T/O: Enough Reps                |
 |            IF:  NO RD req'd  |           |IF:  Req RDs                    |
 |            ACT: Pick OMs &   |           |ACT: Pick RDs                   |
 |                 <sub-OVL>    |           |SND: Select-RD                  |
 |            SND: Req-<sub-OVL>|           |                                |
 |                             /             \                               |
 |                            /               \                              |
 |  T/O: Not all ACKs        /                 \          T/O: Not all ACKs  |
 |  SND: Delete-<OVL>       v   RCV:All ACKs    v         SND: Release-<OVL>*|
 |  SND: Fail-<OVL>^+---------+ IF: Req OMs   +---------+ SND: Fail-<OVL>^   |
 +<-----------------| WAIT-OM |<--------------| WAIT-RD |------------------->+
 |                  +---------+ SND:Release-  +---------+                    |
 |                        |         <OVL>*        |                          |
 |                        |     ACT:Pick OMs &    |                          |
 |                        |         <sub-OVL>     | RCV: All ACKs            |
 |         RCV: All ACKs  |     SND:Req-<sub-OVL> | IF:  No OM req'd         |
 |         SND: Ack-<OVL>^ \                     /  SND: Ack-<OVL>^          |
 |                          \       +-----+     /   SND: Release-<OVL>*      |
 |                           \----->| ACK |<---/                             |
 |                                  +-----+                                  |
 |                  RCV: Cancel@     |   | RCV: Config@                      |
 |                  SND: Delete-<OVL>|   | SND: Config-<OVL>                 |
 +<----------------------------------+   v                                   |
 |                                +--------+                                 |
 +--------------------------------| CONFIG |---------------------------------+
                   RCV: All ACKs  +--------+  T/O or NACKs
                   SND: Succeed-<OVL>^        SND: Delete-<OVL>
                                              SND: Fail-<OVL>^
      Notes:
      (1) At Wait-OM and Wait-RD, we could add another state (T/O) to timeout
          processing to do some fancy stuff like resending Select-RDs or even
          change (re-select) other RDs. The diagram above showed the simplest
          way, i.e., just fail! :-)
      (2) After the GUI or OM picks which OMs to send <sub-OVL>'s to, the
          corresponding requests might need to be sent in sequence instead of
          in parallel for 2 reasons:
            - to ensure exclusiveness among (sub-) overlays; i.e., each node
              can only be in one of the sub-overlays,
            - to avoid starvation among competing OMs.
      (3) The top transition caused by "RCV: Discover" is for OMs acting as
          RDs to construct recursive overlays.

    2. For RD:
                            +--+ RCV: DISCOVERY
                            |  | ACL OK
                            v  | SND: ACK-DISCOVERY
                          +--------+
              +--+------->|  IDLE  |<----------------------+
              |  |        +--------+                       |
              |  |Failed       |                           |
              |  |(not enough  |RCV: INVITE                |
              |  | replies)    |SND: INVITE(D)             |
              |  |SND:RELEASE  V                           |
              |  | (D)   +----------+                      |
              |  +-------|   ACL &  |                      |
              |          | Resource |                      |
              |          |  Timeout |                      |
              |          +----------+                      |
              |                |Succeed (rcv'd             |
              |T/O; or         |  enough replies)          |
              |RCV:RELEASE     |SND: ACK-INVITE+           |
              |SND:RELEASE(D)  |     Guest List            |
              |                V                           |
              |          +----------+                      |
              +----------| RESERVE  |                      |
                         +----------+                      |
                               |RCV: SELECT                |
                               |SND: SELECT(D)             |
                               V                           |
                        +------------+                     |
                        | COMMITTING |                     |
             +----------|   Timeout  |                     |
             |Fail      +------------+                     |
             | missing            |Succeed (rcv'd          |
             | ACK-SEL or         |  all ACK-SEL)          |
             | NACK-SEL           |SND: ACK-SELECT         |
             |or                  V                        |
             |RCV:DELETE       +-----------+               |
             |         +-------| COMMITTED |               |
             |         |       +-----------+               |
             |         |T/O; or      |RCV: CONFIG          |
             |         |RCV:DELETE   |SND: CONFIG(D)       |
             V         V             V                     |
          +-------------+          +-----------+           |
          |SND:DELETE(D)|<---------| CONFIGURE |-----------+
          |Delete ovl   | Fail     +-----------+ Succeed
          |Cleanup      |  (NACK-CONF or         (rcv'd all
          +-------------+   Timeout or            ACK-CONF)
                            just fail)           SND: ACK-CONF
                          or
                          RCV:DELETE



>>> XBone Control Message Format Examples

  * Detailed grammar is specified in lib/XB_CTL.pm.

  > Invite: Invite message from Layer N to Layer N+1
    [*] denotes optional, one or many

    (xbonecontrol protocol_version release_version seq_no
      (credential (user_name  'Yu-Shun Wang')
                  (user_email yushunwa@isi.edu)
                  (auth_type  x509) )
      (invite     # common fields
                  (application $app_type)
                  (name        $app_name)
                  (version     $app_vers)
                  (level       $level)
                  (host        $host_count   $host_os)
                  (router      $router_count $router_os)
                  (meta        $meta_count)
                  # common/application-specific options
                  (routing     dynamic|static)
                  (IPsec       yes|no
                    (authentication none|md5|sha1)*
                    (encryption     none|des|3des)*)
                  (QoS         yes|no)
                  (application (name abone)
                               (script    $script_url
                                 (freebsd $fbsd_script_url)*
                                 (linux   $linux_script_url)*))*
      )
    ) XBoneEOC

    #TODO: more capabilities (such as?)
    #TODO: application scripts

  > Ack-Invite:

    (xbonecontrol protocol_version release_version sequence_no
      (ack-invite
        (application $app_type)
        (name        $app_name)
        (version     $app_vers)
        (level       $level)
        (type        host|router|both|meta)
        (hostname    add.isi.edu)
        (ipaddr      128.9.160.213))
    )

  > Select:

    (xbonecontrol protocol_version release_version
      (credential (user_name  'Yu-Shun Wang')
                  (user_email yushunwa@isi.edu)
                  (auth_type  x509) )
      (select     (application $app_type)
                  (name        $app_name)
                  (level       $level)
                  (type        host|router|meta))
    )

  > Ack-Select:

    (xbonecontrol protocol_version release_version
      (ack-select (application $app_type)
                  (name        $app_name)
                  (level       $level)
                  (type        host|router|both|meta))
    )

  > Release:

    (xbonecontrol protocol_version release_version sequence
      (credential (user_name  'Yu-Shun Wang')
                  (user_email yushunwa@isi.edu)
                  (auth_type  x509))
      (release    (application $app_type)
                  (name        $app_name)
                  (level       $level))
    )

  > Delete:

    (xbonecontrol protocol_version release_version
      (credential (user_name  'Yu-Shun Wang')
                  (user_email yushunwa@isi.edu)
                  (auth_type  x509))
      (stop       (application $app_type)
                  (name        $app_name)
                  (level       $level))
    )

  > Ack-Delete:

    (xbonecontrol protocol_version release_version
      (ack-stop   (application $app_type)
                  (name        $app_name)
                  (level       $level)
      )
    )

  > Dispatch:

    - TODO how to distinguish between real vs. control recursion?

    (xbonecontrol protocol_version release_version
      (credential
        (user_name  'Yu-Shun Wang')
        (user_email yushunwa@isi.edu)
        (auth_type  x509)
      )
      (dispatch   # common fields
                  (application $app_type)
                  (name        $app_name)
                  (version     $app_vers)
                  (level       $level)
                  (retry       $retry)
                  # application-specific fields
                  (create_overlay ... )
      )
    )

  > Ack-Dispatch:

    - TODO should we list all selected nodes in Ack-Dispatch?

    (xbonecontrol protocol_version release_version
      (ack-dispatch (application $app_type)
                    (name        $app_name)
                    (level       $level)
    )