Subject: High update rates and network delay

From: "John McGarvey" <[email-masked]>
Date: Mon, 5 Mar 2001 14:36:38 -0500

The current LDAP replication architecture draft states:

(Section 10) " ... The Consumer must not support multiple concurrent
replication sessions with more than one Supplier for the  same Replication
Context."

I suggest that this requirement may lead to suboptimal transmission of
updates.  Consider the following case: servers A, B, C on one network,
servers D, E, F on another, and the two networks connnected by a slow
network link L.

(A B C) <------- L ---------> (D E F)

"Slow" may mean limited bandwidth or high latency or both.  Assume all of
these servers hold the same replication context and that it is writable on
each of the servers.  To make efficient use of the network connection,
changes originating at any server should only traverse L once.  One way to
configure bandwidth efficient replication is as follows.

- Replicas B and C supply updates to, and consume updates from, A.
- Replicas A, E and F supply updates to, and consume updates from, D.

(Additional backup replication agreements may be added in case A or D are
down.)

Given this setup, suppose we want to support high rates of update with
continual replication.  In conformance with the current draft, A could
consume updates from B, C, and D via sequential sessions.  But while A is a
consumer in session with B or C, it can not receive updates over L, so the
constrained resource goes unused for that period.  Similarly, when D is a
consumer in session with E or F, it can not receive updates over L.  This
is suboptimal and significantly lowers the maximum update rate that the
configuration can support.  I have chosen a simple example, but the more
complicated the topology, the more the update rate is affected.

I suggest the following alternative.  For this alternative, the requirement
from section 10 would have to be loosened to say

" ... The Consumer must not support multiple concurrent replication
sessions with more than one Supplier for the  same set of updates."

Here is the configuration:

- Replica B supplies updates to A but only those that originate at B.  It
consumes updates from A that originate at A, C, D, E, or F.
- Replica C supplies updates to A but only those that originate at C.  It
consumes updates from A that originate at A, B, D, E, or F.
- Replica A supplies updates to D that originate at A, B, or C.  It
consumes updates from D that originate at D, E, or F.

and so on.  The picture looks like:

B <---> A <----L----> D <---> E
        ^             ^
        |             |
        |             |
        v             v
        C             F

(Additional backup replication agreements may also be added for
availability.)  This construction is similar to the "spanning tree" created
by ethernet bridges, in that an update originating at a given server
reaches a destination via a single optimized path.  We can permit A act as
a consumer for simultaneous replication sessions from B, C, and D, because
the updates transmitted within each session are disjoint.  How can A
request updates from D that originate on D, E, and F, but not on B or C?
One way is for A to transmit only part of its update vector when it begins
a session as a consumer of updates from D.  It would send the part
corresponding to D, E, and F, but not the part corresponding to A, B, or C.

-- John McGarvey

---

From: "Ryan Moats" <[email-masked]>
Date: Mon, 5 Mar 2001 14:53:33 -0600

Well first, I think that the phrase "same set of changes" needs
to be defined precisely.

The rest of the discussion is more germane to setting up replication
agreements and implementation and so I think is independent of the
wording of the requirement.

Ryan

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of John McGarvey
Sent: Monday, March 05, 2001 1:37 PM
To: [email-masked]
Subject: High update rates and network delay

-- John McGarvey

---

From: "Ryan Moats" <[email-masked]>
Date: Mon, 5 Mar 2001 16:03:21 -0600

Doh... My brain just turned on and I just realized that this
is talking about architecture.  Therefore, please disregard
what I'm saying below.

Ryan

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Ryan Moats
Sent: Monday, March 05, 2001 2:54 PM
To: John McGarvey; [email-masked]
Subject: RE: High update rates and network delay

Ryan

-----Original Message-----

-- John McGarvey

---

From: "Albert Langer" <[email-masked]>
Date: Tue, 6 Mar 2001 19:10:15 +1100

[John M]

[Albert]
My understanding is that above is the solution used in Active Directory,
- a "bridgehead server" for each relatively slow link between "sites" that
have multiple DSAs with high bandwidth connectivity. It requires
quite complex calculations to optimize the choice of links while meeting
other constraints to minimize the number of hops so as to minimize
the diameter of the replication network and hence the overall replication
delay, while taking into account the distinction between fast links
within a "site" and slow links between them. These calculations can
be done on a decentralized basis but are non-trivial to specify.
They need to be done quite freqently and using a uniform algorithm to
ensure convergence in the "sporadically connected" environment of
scalable directory replication.

Another approach (Novell?) could use algorithms that converge to a
Hamiltonian circuit which could be simpler but maximizes the
diameter of the replication network.

For example the circuit for above diagram could be:

A B C (L) D E F (L) A 

(with either orientation).

Traffic could pass over the slow link L from C to D in one direction
and from F to A in the other direction simultaneously (at IP network
layer), despite the restriction to only 1 consumer session at a time.
Trouble is that as well as maximizing the replication diameter (from A
to F via 5 hops), this also needs to ensure that each site has
additional links and schedules so that traffic from C to A or B does
not pass across the link at all while avoiding any traffic crossing
more than once.

I'm inclined to agree with the architecture drafts approach of just
deferring such issues until basic standards for interoperability
are in place, although it seems clear that "optimal" interoperability
will require full standardization of link and schedule selection
algorithms (and many other aspects not yet addressed at all).

It is certainly useful to discuss possible approaches now though,
and there is lots of research on "gossip networks" available
(also applicable to other standards track protocols such as news).

[JohnM]

[Albert]
Likewise A cannot receive updates from D at the same time it is sending
updates to D, so the slow link is effectively half duplex. That alone
halves the total traffic that could be pushed through it. I think that
is the key point to look at for more optimal propagation. The
constraint imposed by A and D being unable to use the slow link
while they are consuming updates from other DSAs within their
respective sites is likely to have less impact since:

a) all that traffic from within a single site has to pass
over the slow link (slowly ;-)

b) the same traffic over the high speed links within a
site can be received quickly.

Therefore the total loss of use of the constrained resource
due to A and D at each end of the link being unavailable
while consuming intra-site updates is not likely to exceed
the loss from half duplex.

I'm doubtful as to whether a solution to that bigger problem
is feasible as consuming updates from more than one source
simultaneously can get horrendously complex for implementation
even with Single Master.

Also, don't forget that there can be multiple replicated areas
even if the replication network between the DSAs holding them
is the same.

That allows for overlapping consumer sessions by just
partitioning the replicated area to enable it in any
situation where the performance issues really justify
the extra trouble - without imposing more complex
standards in situations where it isn't needed.

[JohnM]

[Albert]
I don't understand.

The other alternative was:

How does this picture illustrate a difference? It looks like exactly
the same set of symmetric links to me.

Seems to me you need a picture illustrating the selection of which
updates are supplied and consumed over each link. That is hard to
draw and could be hard to dynamically calculate for a robust
sporadically connected replication network with multiple sites.

[JohnM]

-- John McGarvey

[Albert]
I suspect this would be too brittle, though worth exploring if you want
to write up an I-D specifying how to calculate the overlayed spanning trees
dynamically in a sporadically connected network and at the same allow for
news about replicas (and sites) joining or leaving the network to pass
across such links.

Might be worth first just tackling the specification of a global
algorithm that ensures each replica has a common view about who else
is currently in the replication network when deciding which updates
to consume and which to reject. That seems to be necessary for eventual
convergence with the current architecture, as well as for your suggestion,
but missing from the current draft.

Also consider this requirement:

AM6.  The sequence of updates to access control information (ACI) and
the data controlled by that ACI MUST be maintained by replication.

While it might be *theoretically* possible to meet that requirement
without ordered propagation of updates, the architecture and URP
drafts have so far made no attempt to show how. I wouldn't like to
try implementing it with more than one consumer session affecting
the same replicated area.

Since the scope of an ACI attribute value can be an entire subtree
the most obvious (and possibly only) solution requires applying
change reports from each originator in the same sequence that
they were generated by that originator - for all changes, not
just ACI changes.

The natural way to do that is to deliver changes from each
originator to each supplier in their original sequence
within each replication session (although arbitrarily
interleaved with changes from other originators).

That requires separation of local sequence numbers from
originator sequence numbers.

(In order to sort out the interleaving it is necessary to
add version numbers and maintain a tree of all concurrent
changes, rather than pretending that unsynchronized and
non-monotonic clocks can impose a total ordering on a
tree that is only partially ordered, just as that is
necessary for "preserving atomic operations").

So if you are going to look at how to optimize update
rates and network delay I would recommend assuming
that the specifications finally adopted will at least
require delivery of changes from each originator in strict
sequence over each replication link. That, together with
update vectors and the use of a high water mark based
on local sequence numbers is sufficient to ensure that
no changes are passed over any link more than once,
and robust eventual convergence despite DSAs crashing
and being restored from backups.

I suspect optimization of schedules and link selection
in that context will both be easier than, and differ
significantly from, any attempt to optimize in the
context of propagating unordered changes. If weakening
the restriction to a single consumer session is possible
at all, I believe it would need to be in that context.

PS If anyone is responding to last part, please
change it to a separate thread such as "Delivery
Sequence". I only mention it here because it is
likely to also impact on how to optimize update
rates and network delay, and it would be a pity if
anyone working on that were to waste time based
on an assumption that the current approach of
unordered propagation of changes will remain.