Subject: ldup arch draft - part 2 of 2

From: [email-masked] (John Merrells)
Date: Fri, 22 Oct 1999 11:02:27 -0700

INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    The DN and Replica Identifier allow the Responder to determine which
    Replication Agreement is being acted on.

    The Update Transfer Protocol OID identifies the Update Transfer
    Protocol that the Initiator wishes to be used. This document defines
    two Protocols,  one for full update and one for incremental update.

    The Replica Number Table provides a mapping from Replica Identifiers
    (the RDN of the Replica Sub-Entry) to Replica Numbers (a small
    integer). The Supplier sends Replica Numbers instead of Replica
    Identifiers to reduce network bandwidth requirements.

    The Supplier server uses the Ordering flag to inform the Consumer of
    the ordering of the Replication Update sequence transferred during the
    Replication Session. The Consumer can make use of this knowledge
    should the session be interrupted.

    7.2.2 Start Replication Response

    The LDUP Protocol document [LDUP Protocol] defines an LDAP Extended
    Response, Start Replication Response, that is sent in reply to a Start
    Replication Request, from the Responder to the Initiator. The
    parameters of the Start Replication Response include an response code,
    and an optional Update Vector.

    7.2.3 Consumer Initiated, Start Replication Session

    The Supplier Responder need not return its Update Vector to the
    Consumer Initiator, as it is not needed in this case.

    7.3 Update Transfer

    Each Update Transfer Protocol is identified by an OID. An LDUP
    conformant server implementation must support the two update protocols
    defined here, and may support many others. A server will advertise its
    protocols in the Root DSE multi-valued attribute
    'supportedReplicationProtocols'.

    The details of the two mandatory to implement protocols are defined by
    the LDUP Protocol Internet Draft [LDUP Protocol].  One protocol
    provides a Full Update for initialisation and re-initialisation of a
    replica, and the other protocol maintains that replica via an
    Incremental Update.

    Merrells, Reed, Srinivasan                                  [Page 23]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    7.4 End Replication Session

    A Replication Session is terminated by the Supplier by sending an End
    Replication LDAP extended request, see section 7.4.1. The purpose of
    the request and response operations is to carry the Update Vector from
    the Supplier to the Consumer in the Full Update case, and to convey
    the Update Vector from the Consumer to the Supplier in the Incremental
    Update case.

    7.4.1 End Replication Request

    The LDUP Protocol document [LDUP Protocol] defines an LDAP Extended
    Request, End Replication Request, that is sent from the Initiator to
    the Responder. The End Replication Request includes a flag for the
    Supplier to request the Consumers Update Vector.

    When the update has completed the Supplier sends this extended request
    to inform the Consumer that all updates have been sent, and to advise
    the Consumer if its Update Vector should be returned.

    7.4.2 End Replication Response

    The LDUP Protocol document [LDUP Protocol] defines an LDAP Extended
    Response, End Replication Response, that is sent in reply to an End
    Replication Request, from the Responder to the Supplier. The Response
    can optionally include an Update Vector.

    If the ‘return update vector’ flag in the request was set then the
    Consumer should return its Update Vector to the Supplier.

    7.5 Integrity & Confidentiality

    Data integrity (ie, protection from unintended changes) and
    confidentiality (ie, protection from unintended disclosure to
    eavesdroppers) SHOULD be provided by appropriate selection of
    underlying transports, for instance TLS, or IPSEC.  Replication MUST
    be supported across TLS LDAP connections.  Servers MAY be configured
    to refuse replication connections over unprotected TCP connections.

    8. LDUP Update Protocols

    This Internet-Draft defines two transfer protocols for the supplier to
    push changes to the consumer.   Other protocols could be defined to

    Merrells, Reed, Srinivasan                                  [Page 24]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    transfer changes, including those which pull changes from the supplier
    to the consumer, but those are left for future work.

    8.1 Replication Updates and Update Primitives

    Both LDUP Update Protocols define how Replication Updates are
    transferred from the Supplier to the Consumer. Each Replication Update
    consists of a set of Update Primitives that describe the state changes
    that have been made to a single entry. Each Replication Update
    contains a single Unique Identifier that addresses the entry to which
    the Update Primitives are to be applied.

    There are seven types of Update Primitive each of which codifies an
    assertion about the state of an entry. They assert the presence or
    absence of an entry, the name of the entry, the presence or absence of
    its attributes, and the presence or absence its attribute values.  An
    assertion based approach has been chosen so that the Primitives are
    idempotent. Meaning that re-application of a Primitive to an Entry
    will cause no change to the entry. This is desirable as it provides
    some resilience against some kinds of system failures.

    Each Update Primitive contains a CSN that denotes the unique point in
    the total ordering of primitives that this primitive appears. The
    Supplier maps the Replica Identifier component of the CSN onto a
    Replica Number before transmission. The Consumer uses the provided
    Replica Number Table to map this back onto the Replica Identifier.

    The Update Primitives are fully defined in the LDUP Update
    Reconciliation Procedures Internet Draft [LDUP URP].

    8.2 Fractional Updates

    When fully populating or incrementally bringing up to date a
    Fractional Replica each of the Replication Updates must only contain
    updates to the attributes in the Fractional Entry Specification.

    9. LDUP Full Update Transfer Protocol

    9.1 Supplier Initiated, Full Update, Start Replication Session

    The Consumer Responder need not return its Update Vector to the
    Supplier Initiator, as it is not needed in this case.

    Merrells, Reed, Srinivasan                                  [Page 25]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    9.2 Full Update Transfer

    This Full Update Protocol provides a bulk transfer of the replica
    contents for the initial population of new replicas, and the
    refreshing of existing replicas.

    The Consumer must replace its entire replica contents with that sent
    from the Supplier.

    The Consumer need not service any requests for this Naming Context
    whilst the full update is in progress. The Consumer could return a
    referral to another replica, possibly the supplier. [REF]

    9.3 Replication Update Generation

    The entire state of a Replicated Area can be mapped onto a sequence of
    Replication Updates, each of which contains a sequence of Update
    Primitives that describe the entire state of a single entry.

    The sequence of Replication Updates must be ordered such that no entry
    is created before its parent.

    9.4 Replication Update Consumption

    A Consumer will receive the Replication Updates, extract the sequence
    of Update Primitives, and must apply them to the DIB in the order
    provided.

    9.5 Full Update, End Replication Session

    Since the Full Update also replicates the sub-entry that represents
    the Supplier Replica the Consumer will have received the Update Vector
    that represents the update state of the Consumer.

    After a Full Update transfer the Supplier sends the Update Vector that
    reflects the update state of the full replica information sent.  The
    Consumer records this as its Update Vector.

    The Supplier could be accepting updates whilst the update is in
    progress.  Once the Full Update has completed, an Incremental Update
    should be performed to transfer these changes.

    Merrells, Reed, Srinivasan                                  [Page 26]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    9.6 Interrupted Transmission

    If the Replication Session terminates before the End Replication
    Request is sent, then the Replica is invalid and must be re-
    initialised. The Consumer must not permit LDAP Clients to access the
    incomplete replica. The Consumer could refer the Client to the
    Supplier Replica, or return an error result code.

    10. LDUP Incremental Update Transfer Protocol

    For efficiency, the Incremental Update Protocol transmits only those
    changes that have been made to the Supplier replica that the Consumer
    has not already received. In a replication topology with transitive
    redundant replication agreements, changes may propagate through the
    replica network via different routes.

    The Consumer must not support multiple concurrent replication sessions
    with more than one Supplier for the same Naming Context. A Supplier
    that attempts to initiate a Replication Session with a Consumer
    already participating as a Consumer in another Replication Session
    will receive the busy error code.

    10.1 Update Vector

    The Supplier uses the Consumer's Update Vector to determine the
    sequence of updates that should be sent to the Consumer.

    Each Replica entry includes an Update Vector to record the point to
    which the replica has been updated. The vector is a set of CSN values,
    one value for each known updateable Replica. Each CSN is the most
    recent change, made at that Replica, that has been replicated to this
    Replica.

    For example, consider two updatable replicas of a naming context, one
    is assigned replica identifier  ‘1’, the other replica identifier ‘2’.
    Each is responsible for maintaining its own update vector, which will
    contain two CSNs, one for each replica. So, if both replicas are
    identical they will have equivalent update vectors.

    Both Update Vectors =

    {1998081018:44:31z#0x000F#1#0x0000, 1998081018:51:20z#0x0001#2#0x0000}

    Subsequently, at 7pm, an update is applied to replica ‘2’, so its
    update vector is updated.

    Merrells, Reed, Srinivasan                                  [Page 27]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    Replica ‘1’ Update Vector =

    {1998081018:44:31z#0x000F#1#0x0000, 1998081018:51:20z#0x0001#2#0x0000}

    Replica ‘2’ Update Vector =

    {1998081018:44:31z#0x000F#1#0x0000, 1998081019:00:00z#0x0000#2#0x0000}

    Since the Update Vector records the state to which the replica has
    been updated, a supplier server, during Replication Session
    initiation, can determine the sequence of updates that should be sent
    to the consumer. From the example above no updates need to be sent
    from replica ‘1’ to replica ‘2’, but there is an update pending from
    replica ‘2’ to replica ‘1’.

    Because the Update Vector embodies knowledge of updates made at all
    known replicas it supports replication topologies that include
    transitive and redundant connections between replicas. It ensures that
    changes are not transferred to a consumer multiple times even though
    redundant replication agreements may exist. It also ensures that
    updates are passed across the replication network between replicas
    that are not directly linked to each other.

    It may be the case that a CSN for a given replica is absent, for one
    of two reasons.

    1. CSNs for Read-Only replicas might be absent because no changes will
      have ever been applied to that Replica, so there are no changes to
      replicate.

    2. CSNs for newly created replicas may be absent because no changes to
      that replica have yet been propagated.

    An Update Vector might also contain a CSN for a replica that no longer
    exists.  The replica may have been temporarily taken out of service,
    or may have been removed from the replication topology permanently. An
    implementation may choose to retire a CSN after some configurable time
    period.

    10.2 Supplier Initiated, Incremental Update, Start Replication Session

    The Consumer Responder must return its Update Vector to the Supplier
    Initiator. The Supplier uses this to determine the sequence of
    Replication Updates that need to be sent to the Consumer.

    Merrells, Reed, Srinivasan                                  [Page 28]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    10.3 Replication Update Generation

    The Supplier generates a sequence of Replication Updates to be sent to
    the consumer. To enforce LDAP Constraint 20.1.6, that the LDAP Modify
    must be applied atomically, each Replication Update must contain the
    entire sequence of Update Primitives for all the LDAP Operations for
    which the Replication Update contains Update Primitives. Stated less
    formally, for each primitive the update contains, it must also contain
    all the other primitives that came from the same operation.

    10.3.1 Replication Log Implementation

    A log-based implementation might take the approach of mapping LDAP
    Operations onto an equivalent  sequence of Update Primitives. A
    systematic procedure for achieving this is fully described in the LDUP
    Update Reconciliation Procedures Internet Draft [LDUP URP].

    The Consumer Update Vector is used to determine the sequence of LDAP
    Operations in the operation log that the Consumer has not yet seen.

    10.3.2 State-Based Implementation

    A state-based implementation might consider each entry of the replica
    in turn using the Update Vector of the consumer to find all the state
    changes that need to be transferred. Each state change (entry,
    attribute, or value - creation, deletion, or update) is mapped onto
    the equivalent Update Primitive. All the Update Primitives for a
    single entry might be collected into a single Replication Update.
    Consequently, it could contain the resultant primitives of many LDAP
    operations.

    10.4 Replication Update Consumption

    A Consumer will receive Replication Updates, extract the sequence of
    Update Primitives, and must apply them to the DIB in the order
    provided. LDAP Constraint 20.1.6 states that the modifications within
    an LDAP Modify operation must be applied in the sequence provided.

    Those Update Primitives must be reconciled with the current replica
    contents and any previously received updates.  In broad outline,
    updates are compared to the state information associated with the item
    being operated on. If the change has a more recent CSN, then it is
    applied to the directory contents. If the change has an older CSN it
    is no longer relevant and its change must not be effected.

    Merrells, Reed, Srinivasan                                  [Page 29]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    If the consumer acts as a supplier to other replicas then the updates
    are retained for forwarding.

    10.5 Update Resolution Procedures

    The LDAP Update Operations must abide by the constraints imposed by
    the LDAP Data Model and LDAP Operational Behaviour, Appendix B. An
    operation that would violate at least one of these constraints is
    rejected with an error result code.

    The loose consistency model of this replication architecture and its
    support for multiple updateable replicas of a naming context means
    that LDAP Update Operations may be accepted at one replica, which
    would not be at another. At the time of acceptance, the accepting
    replica may not have received other updates that would cause a
    constraint to be violated, and the operation to be rejected.

    Replication Updates must never be rejected because of a violation of
    an LDAP Constraint. If the result of applying the Replication Update
    causes a constraint violation to occur, then some remedial action must
    be taken to satisfy the constraint. These Update Resolution Procedures
    are introduced here, and fully described in the LDAP Update Resolution
    Procedures Internet-Draft [LDUP URP].

    10.5.1 URP: Distinguished Names

    LDAP Constraints 20.1.1 and 20.1.10 ensure that each entry in the
    replicated area has a unique DN. A Replication Update could violate
    this constraint producing two entries, with different unique
    identifiers, but with the same DN. The resolution procedure is to
    rename the most recently named entry so that its RDN includes its own
    unique identifier. This ensures that the new DN of the entry shall be
    unique.

    10.5.2 URP: Orphaned Entries

    LDAP Constraints 20.1.11 ensures that every entry must have a parent
    entry. A Replication Update could violate this constraint producing an
    entry with no parent entry. The resolution procedure is to create a
    Glue Entry to take the place of the absent parent. The Glue Entry’s
    superior will be the Lost and Found Entry. This well known place
    allows administrators and their tools to find and repair abandoned
    entries.

    Merrells, Reed, Srinivasan                                  [Page 30]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    10.5.3 URP: Distinguished Not Present

    LDAP Constraints 20.1.8 and 20.1.9 ensure that the components of an
    RDN appear as attribute values of the entry. A Replication Update
    could violate this constraint producing an entry without its
    distinguished values. The resolution procedure is to add the missing
    attribute values, and mark them as distinguished not present, so that
    they can be deleted when the attribute values are no longer
    distinguished.

    10.5.4 URP: Schema - Single Valued Attributes

    LDAP Constraint 20.1.7 enforces the single-valued attribute schema
    restriction. A Replication Update could violate this constraint
    creating a multi-value single-valued attribute. The resolution
    procedure is to consider the value of a single-valued attribute as
    always being equal. In this way the most recently added value will be
    retained, and the older one discarded.

    10.5.5 URP: Schema - Required Attributes

    LDAP Constraint 20.1.7 enforces the schema objectclass definitions on
    an entry. A Replication Update could violate this constraint creating
    an entry that does not have attribute values for required attributes.
    The resolution procedure is to ignore the schema violation and mark
    the entry for administrative repair.

    10.5.6 URP: Schema - Extra Attributes

    LDAP Constraint 20.1.3 and 20.1.7 enforces the schema objectclass
    definitions on an entry. A Replication Update could violate this
    constraint creating an entry that has attribute values not allowed by
    the objectclass values of the entry. The resolution procedure is to
    ignore the schema violation and mark the entry for administrative
    repair.

    10.5.7 URP: Duplicate Attribute Values

    LDAP Constraint 20.1.5 ensures that the values of an attribute
    constitute a set of unique values. A Replication Update could violate
    this constraint. The resolution procedure is to enforce this
    constraint, recording the most recently assigned CSN with the value.

    Merrells, Reed, Srinivasan                                  [Page 31]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    10.5.8 URP: Ancestry Graph Cycle

    LDAP Constraint 20.4.2.1 prevents against a cycle in the DIT. A
    Replication Update could violate this constraint causing an entry to
    become it’s own parent, or for it to appear even higher in it’s
    ancestry graph. The resolution procedure is to break the cycle by
    changing the parent of the entry closest to be the lost and found
    entry.

    10.6 Incremental Update, End Replication Session

    If the Supplier sent none of its own updates to the Consumer, then the
    Supplier's CSN within the Supplier's update vector should be updated
    with the earliest possible CSN that it could generate, to record the
    time of the last successful replication session. The Consumer will
    have received the Supplier's Update Vector in the replica sub-entry it
    holds for the Supplier replica.

    The Consumer's resultant Update Vector CSN values will be at least as
    great as the Supplier's Update Vector.

    The Supplier may request that the Consumer return its resultant Update
    Vector so that the Supplier can update its replica sub-entry for the
    Consumer Replica. The Supplier requests this by setting a flag in the
    End Replication Request. The default flag value is TRUE meaning the
    Consumer Update Vector must be returned.

    10.7 Interrupted Transmission

    If the Replication Session terminates before the End Replication
    Request is sent then the Consumer’s Update Vector may or may not be
    updated to reflect the updates received. The Start Replication request
    includes a Replication Update Ordering flag which states whether the
    updates were sent in CSN order per replica.

    If updates are sent in CSN order per replica then it is possible to
    update the Consumer Update Vector to reflect that some portion of the
    updates to have been sent have been received and successfully applied.
    The next Incremental Replication Session will pick up where the failed
    session left off.

    If updates are not sent in CSN order per replica then the Consumer
    Update can not be updated. The next Incremental Replication Session
    will begin where the failed session began. Some updates will be
    replayed, but because the application of Replication Updates is
    idempotent they will not cause any state changes.

    Merrells, Reed, Srinivasan                                  [Page 32]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    11. Purging State Information

    The state information stored with each entry need not be stored
    indefinitely. A server implementation may choose to periodically, or
    continuously, remove state information that is no longer required. The
    mechanism is implementation-dependent, but to ensure interoperability
    between implementations, the state information must not be purged
    until all known replicas have received and acknowledged the change
    associated with a CSN. This is determined from the Purge Vector
    [11.1].

    All the CSNs stored that are lower than the Purge Vector may be
    purged, because no changes with older CSNs can be replicated to this
    replica.

    11.1 Purge Vector

    The Purge Vector is an Update Vector constructed from the Update
    Vectors of all known replicas. Each replica has a sub-entry for each
    known replica stored below its naming context. Each of those entries
    contains the last known update vector for that replica. The lowest CSN
    for each replica are taken from these update vectors to form the Purge
    Vector. The Purge Vector is used to determine when state information
    and updates need no longer be stored.

    11.2 Purging Deleted Entries, Attributes, and Attribute Values

    The following conditions must hold before an item can be deleted from
    the Directory Information Base.

    1) The LDAP delete operation has been propagated to all replication
    agreement partners.

    2) All the updates from all the other replicas with CSNs less than the
    CSN on the deletion have been propagated to the server holding the
    deleted entry (similarly for deleted attributes and attribute values).

    3) The CSN generator of the other Replicas must have advanced beyond
    the deletion CSN of the deleted entry. Otherwise, it is possible for
    one of those Replicas to generate operations with CSNs earlier than
    the deleted entry.

    Merrells, Reed, Srinivasan                                  [Page 33]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    12. Replication Configuration and Management

    Replication management entries, such as replica or replication
    agreement entries, can be altered on any updateable replica. These
    entries are implicitly included in the directory entries governed by
    any agreement associated with this naming context.  As a result, all
    servers with a replica of a naming context will have access to
    information about all other replicas and associated agreements.

    The deployment and maintenance of a replicated directory network
    involves the creation and management of all the replicas of a naming
    context and replication agreements among these replicas.  This section
    outlines, through an example, the administrative actions necessary to
    create a new replica and establish replication agreements.  Typically,
    administrative tools will guide the administrator and facilitate these
    actions.  The objective of this example is to illustrate the
    architectural relationship among various replication related
    operational information.

    A copy of an agreement should exist on both the supplier and consumer
    side for the replication update transfer protocol to be able to start.
    For this purpose, the root of the naming context, replica objects and
    the replication agreement objects are created first on one of the
    servers.  A copy of these objects are then manually created on the
    second server associated with the agreement.

    The scenario below starts with a server (named DSA1) that holds an
    updateable replica of a naming context NC1.  Procedures to establish
    an updateable replica of the naming context on a second server (DSA2)
    are outlined.

    On DSA1:

    1) Add the context prefix for NC1 to the Root DSE attribute
      'replicaRoot' if it does not already exist.

    2) Alter the 'ObjectClass' attribute of the root entry of NC1 to
      include the "namingContext" auxiliary class.

    3) Create a replica object, NC1R1, (as a child of the root of NC1) to
      represent the replica on DSA1.  The attributes include replica type
      (updateable, read-only etc.) and DSA1 access point information.

    4) Create a copy of the replica object NC1R2 (after it is created on
      DSA2)

    5) Create a replication agreement, NC1R1-R2 to represent update
      transfer from NC1R1 to NC1R2.  This object is a child of NC1R1.

    Merrells, Reed, Srinivasan                                  [Page 34]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    On DSA2:

    1) Add NC1's context prefix to the Root DSE attribute 'replicaRoot'.

    2) Create a copy of the root entry of NC1 as a copy of the one in DSA1
      (including the namingContext auxiliary class)

    3) Create a copy of the replica object NC1R1

    4) Create a second replica object, NC1R2 (as a sibling of NC1R1) to
      represent the replica on DSA2.

    5) Create a copy of the replication agreement, NC1R1-R2

    6) Create a replication agreement, NC1R2-R1, to represent update
      transfer from NC1R2 to NC1R1.  This object is a sibling of NC1R1-
      R2.

    After these actions update transfer to satisfy either of the two
    agreements can commence.

    If data already existed in one of the replicas, the update transfer
    protocol should perform a complete update of the data associated with
    the agreement before normal replication begins.

    13. Time

    The server assigns a CSN for every LDAP update operation it receives.
    Since the CSN is principally based on time, the CSN is susceptible to
    the Replica clocks drifting in relation to each other (either forwards
    or backwards).

    The server must never assign a CSN older than or equal to the last CSN
    it assigned.

    The server must reject update operations, from any source, which would
    result in setting a CSN on an entry or a value which is earlier than
    the one that is there.  The error code serverClocksOutOfSync (72)
    should be returned.

    Merrells, Reed, Srinivasan                                  [Page 35]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    14. Security Considerations

    The preceding architecture discussion covers the server
    authentication, session confidentiality, and session integrity in
    sections 7.1.1 and 7.5

    The internet draft "Authentication Methods" for LDAP, provides a
    detailed LDAP security discussion.  Its introductory passage is
    paraphrased below. [AUTH]

    A Replication Session can be protected with the following security
    mechanisms.

    1) Authentication by means of the SASL mechanism set, possibly backed
      by the TLS credentials exchange mechanism,

    2) Authorization by means of access control based on the Initiators
      authenticated identity,

    3) Data integrity protection by means of the TLS protocol or data-
      integrity SASL mechanisms,

    4) Protection against snooping by means of the TLS protocol or data-
      encrypting SASL mechanisms,

    The configuration entries that represent Replication Agreements may
    contain authentication information. This information must never be
    replicated between replicas.

    Updates to a multi-mastered entry may collide causing the Update
    Resolution Procedures [10.5] to reject or reverse one of the changes
    to the entry. The URP algorithms resolve conflicts by using the total
    ordering of updates imposed by the assignment of CSNs for every
    operation. As a consequence updates originating from system
    administrators have no priority over updates originating from regular
    system users.

    15. Acknowledgements

    This document is a product of the LDUP Working Group of the IETF. The
    contributions of its members is greatly appreciated.

    Merrells, Reed, Srinivasan                                  [Page 36]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    16. References

    [AUTH] - M. Wahl, H. Alvestrand, J. Hodges, RL "Bob" Morgan,
    "Authentication Methods for LDAP", Internet Draft, draft-ietf-ldapext-
    authmeth-02.txt, June 1998.

    [BCP-11] - R. Hovey, S. Bradner, "The Organizations Involved in the
    IETF Standards Process", BCP 11, RFC 2028, October 1996.

    [LDAPv3] - M. Wahl, S. Kille, T. Howes, "Lightweight Directory Access
    Protocol (v3)", RFC 2251, December1997.

    [LDUP Info.] - E. Reed, "LDUP Replication Information Model", Internet
    Draft, draft-reed-ldup-infomod-00-1.txt, August 1998.

    [LDUP Protocol] - G. Good, E. Stokes 'The LDUP Replication Update
    Protocol' , Internet Draft, draft-ietf-ldup-protocol-00.txt, May 1999.

    [LDUP Requirements] - R. Weiser, E. Stokes 'LDAP Replication
    Requirements', Internet Draft, draft-weiser-replica-req-02.txt, April
    1998.

    [LDUP URP] -  S. Legg 'LDUP Update Reconciliation Procedures',
    Internet Draft, draft-legg-ldup-urp-00.txt, February 1999.

    [NTP] - D. L. Mills, "Network Time Protocol (Version 3)", RFC 1305,
    March, 1992.

    [REF] - T. Howes, Mark Wahl, "Referrals and Knowledge References in
    LDAP Directories", Internet draft, draft-ietf-ldapext-referral-00.txt,
    March 1998.

    [RFC2119] - S. Bradner, "Key words for use in RFCs to Indicate
    Requirement Levels", RFC 2119.

    [RFC2252] - M. Wahl, A. Coulbeck, T. Howes, S. Kille, 'Lightweight
    Directory Access Protocol (v3): Attribute Syntax Definitions', RFC
    2252, December 1997.

    [SNTP] - D. L. Mills, "Simple Network Time Protocol (SNTP) Version 4
    for IPv4, IPv6 and OSI", RFC 2030, University of Delaware, October
    1996.

    [TLS] -  J. Hodges, R. L. "Bob" Morgan, M. Wahl, "Lightweight
    Directory Access Protocol (v3):                Extension for Transport
    Layer Security", Internet draft, draft-ietf-ldapext-ldapv3-tls-01.txt,
    June 1998.

    Merrells, Reed, Srinivasan                                  [Page 37]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    [UUID] - P. Leach, R. Salz, "UUIDs and GUIDs", Internet draft, draft-
    leach-uuids-guids-01.txt, February 1998.

    [X501] - ITU-T Recommendation X.501 (1993), ) | ISO/IEC 9594-2:1993,
    Information Technology - Open Systems Interconnection - The Directory:
    Models

    [X680] - ITU-T Recommendation X.680 (1994) | ISO/IEC 8824-1:1995,
    Information technology - Abstract Syntax Notation One (ASN.1):
    Specification of Basic Notation

    [X525] - ITU-T Recommendation X.525 (1997) | ISO/IEC 9594-9:1997,
    Information Technology - Open Systems Interconnection - The Directory:
    Replication

    17. Intellectual Property Notice

    The IETF takes no position regarding the validity or scope of any
    intellectual property or other rights that might be claimed to
    pertain to the implementation or use of the technology described in
    this document or the extent to which any license under such rights
    might or might not be available; neither does it represent that it has
    made any effort to identify any such rights.  Information on the
    IETF's procedures with respect to rights in standards-track and
    standards-related documentation can be found in BCP-11. [BCP-11]
    Copies of claims of rights made available for publication and any
    assurances of licenses to be made available, or the result of an
    attempt made to obtain a general license or permission for the use of
    such proprietary rights by implementors or users of this specification
    can be obtained from the IETF Secretariat.

    The IETF invites any interested party to bring to its attention any
    copyrights, patents or patent applications, or other proprietary
    rights which may cover technology that may be required to practice
    this standard.  Please address the information to the IETF Executive
    Director.

    18. Copyright Notice

     Copyright (C) The Internet Society (1998,1999). All Rights Reserved.

    This document and translations of it may be copied and furnished to
    others, and derivative works that comment on or otherwise explain it
    or assist in its implementation may be prepared, copied, published and

    Merrells, Reed, Srinivasan                                  [Page 38]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    distributed, in whole or in part, without restriction of any kind,
    provided that the above copyright notice and this paragraph are
    included on all such copies and derivative works.  However, this
    document itself may not be modified in any way, such as by removing
    the copyright notice or references to the Internet Society or other
    Internet organizations, except as needed for the  purpose of
    developing Internet standards in which case the procedures for
    copyrights defined in the Internet Standards process must be followed,
    or as required to translate it into languages other than English.

    The limited permissions granted above are perpetual and will not be
    revoked by the Internet Society or its successors or assigns.

    This document and the information contained herein is provided on an
    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT
    NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN
    WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

    19. Authors' Address

         John Merrells
         Netscape Communications, Inc.
         501 East Middlefield Road
         Mountain View
         CA 94043

         E-mail: [email-masked]
         Phone: +1 650-937-5739

         Edwards E. Reed
         Reed-Matthews, Inc.

         E-mail: [email-masked]
         Phone: +1 801-785-0315

         Uppili Srinivasan
         Oracle, Inc.
         Redwood Shores

         E-mail: [email-masked]
         Phone: +1 650 506 3039

    Merrells, Reed, Srinivasan                                  [Page 39]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

         LDUP Engineering Mailing List: [email-masked]

         LDUP Working Group Mailing List: [email-masked]

    20. Appendix B - LDAP Constraints

    20.1 LDAP Constraints Clauses

    This is an enumeration of the Data Model and Operation Behaviour
    constraint clauses defined in RFC 2251. [LDAPv3]

    1) Data Model - Entries have names: one or more attribute values from
      the entry form its relative distinguished name (RDN), which MUST be
      unique among all its siblings. (p5)

    2) Data Model - Attributes of Entries - Each entry MUST have an
      objectClass attribute. (p6)

    3) Data Model - Attributes of Entries - Servers MUST NOT permit
      clients to add attributes to an entry unless those attributes are
      permitted by the object class definitions. (p6)

    4) Relationship to X.500 - This document defines LDAP in terms of
      X.500 as an X.500 access mechanism.  An LDAP server MUST act in
      accordance with the X.500 (1993) series of ITU recommendations when
      providing the service. However, it is not required that an LDAP
      server make use of any X.500 protocols in providing this service,
      e.g. LDAP can be mapped onto any other directory system so long as
      the X.500 data and service model as used in LDAP is not violated in
      the LDAP interface. (p8)

    5) Elements of Protocol - Common Elements - Attribute - Each attribute
      value is distinct in the set (no duplicates). (p14)

    6) Elements of Protocol - Modify Operation - The entire list of entry
      modifications MUST be performed in the order they are listed, as a
      single atomic operation. (p33)

    7) Elements of Protocol - Modify Operation - While individual
      modifications may violate the directory schema, the resulting entry
      after the entire list of modifications is performed MUST conform to
      the requirements of the directory schema. (p33)

    8) Elements of Protocol - Modify Operation - The Modify Operation
      cannot be used to remove from an entry any of its distinguished

    Merrells, Reed, Srinivasan                                  [Page 40]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

      values, those values which form the entry's relative distinguished
      name. (p34)

    9) Elements of Protocol - Add Operation - Clients MUST include
      distinguished values (those forming the entry's own RDN) in this
      list, the objectClass attribute, and values of any mandatory
      attributes of the listed object classes. (p35)

    10)  Elements of Protocol - Add Operation - The entry named in the
      entry field of the AddRequest MUST NOT exist for the AddRequest to
      succeed. (p35)

    11)  Elements of Protocol - Add Operation - The parent of the entry to
      be added MUST exist. (p35)

    12)  Elements of Protocol - Delete Operation - ... only leaf entries
      (those with no subordinate entries) can be deleted with this
      operation. (p35)

    13)  Elements of Protocol - Modify DN Operation - If there was already
      an entry with that name [the new DN], the operation would fail.
      (p36)

    14)  Elements of Protocol - Modify DN Operation - The server may not
      perform the operation and return an error code if the setting of
      the deleteoldrdn parameter would cause a schema inconsistency in
      the entry. (p36)

    20.2 LDAP Data Model Constraints

    The LDAP Data Model Constraint clauses as written in RFC 2251 [LDAPv3]
    may be summarised as follows.

    a) The parent of an entry must exist. (LDAP Constraint 11 & 12.)

    b) The RDN of an entry is unique among all its siblings. (LDAP
      Constraint 1.)

    c) The components of the RDN must appear as attribute values of the
      entry. (LDAP Constraint 8 & 9.)

    d) An entry must have an objectclass attribute. (LDAP Constraint 2 &
      9.)

    e) An entry must conform to the schema constraints.  (LDAP Constraint
      3 & 7.)

    Merrells, Reed, Srinivasan                                  [Page 41]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    f) Duplicate attribute values are not permitted. (LDAP Constraint 5.)

    20.3 LDAP Operation Behaviour Constraints

    The LDAP Operation Behaviour Constraint clauses as written in RFC 2251
    [LDAPv3] may be summarised as follows.

    A) The Add Operation will fail if an entry with the target DN already
    exists. (LDAP Constraint 10.)

    B) The Add Operation will fail if the entry violates data constraints:

         a - The parent of the entry does not exist. (LDAP Constraint 11.)

         b - The entry already exists. (LDAP Constraint 10.)

         c - The entry RDN components appear as attribute values on the
         entry. (LDAP Constraint 9.)

         d - The entry has an objectclass attribute. (LDAP Constraint 9.)

         e - The entry conforms to the schema constraints. (LDAP
         Constraint 9.)

         f - The entry has no duplicated attribute values. (LDAP
    Constraint 5.)

    C) The modifications of a Modify Operation are applied in the order
    presented. (LDAP Constraint 6.)

    D) The modifications of a Modify Operation are applied atomically.
    (LDAP Constraint 6.)

    E) A Modify Operation will fail if it results in an entry that
    violates data constraints:

         c - If it attempts to remove distinguished attribute values.
         (LDAP Constraint 8.)

         d - If it removes the objectclass attribute. (LDAP Constraint 2.)

         e - If it violates the schema constraints. (LDAP Constraint 7.)

         f - If it creates duplicate attribute values. (LDAP Constraint
         5.)

    Merrells, Reed, Srinivasan                                  [Page 42]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    F) The Delete Operation will fail if it would result in a DIT that
    violates data constraints:

         a - The deleted entry must not have any children. (LDAP
    Constraint 12.)

    G) The ModDN Operation will fail if it would result in a DIT or entry
    that violates data constraints:

         b - The new Superior entry must exist. (Derived LDAP Data Model
         Constraint A)

         c - An entry with the new DN must not already exist. (LDAP
         Constraint 13.)

         c - The new RDN components do not appear as attribute values on
         the entry. (LDAP Constraint 1.)

         d - If it removes the objectclass attribute. (LDAP Constraint 2.)

         e - It is permitted for the operation to result in an entry that
         violates the schema constraints. (LDAP Constraint 14.)

    20.4 New LDAP Constraints

    The introduction of support for multi-mastered entries, by the
    replication scheme presented in this document, necessitates the
    imposition of new constraints upon the Data Model and LDAP Operation
    Behaviour.

    20.4.1 New LDAP Data Model Constraints

    1) Each entry shall have a unique identifier generated by the UUID
    algorithm available through the ‘entryUUID’ operational attribute. The
    entryUUID attribute is single valued.

    20.4.2 New LDAP Operation Behaviour Constraints

    1) The LDAP Data Model Constraints do not prevent cycles in the
      ancestry graph. Existing constraints Data Model Constraint - 20.4.1
      - (a) and Operation Constraint - 20.4.2 - (B) would prevent this in
      the single master case, but not in the presence of multiple
      masters.

    Merrells, Reed, Srinivasan                                  [Page 43]
                            Expires 22 March 2000

    INTERNET-DRAFT      LDAP Replication Architecture   October 22, 1999

    2) The LDAP Data Model Constraints state that only the LDAP Modify
      Operation is atomic. All other LDAP Update Operations are also
      considered to be atomically applied to the DIB.

    Merrells, Reed, Srinivasan                                  [Page 44]
                            Expires 22 March 2000