![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to q-design.tex CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / doc / manual|
Return to q-design.tex CVS log | Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / doc / manual |
1.1 root 1: \chapter {Overview}
2:
3: \section {Introduction}
4:
5:
6:
7: This part of the manual describes aspects of the design of QUIPU which are not
8: needed to be known by the administrator or user of QUIPU.
9: However, it documents important design decisions and protocol, which are of
10: interest to understand how QUIPU works, and in some specific circumstances
11: (e.g., solving interoperability problems). A summary of the main features
12: of QUIPU is also given.
13:
14:
15: QUIPU fully implements both of the OSI Directory Protocols, and a number of
16: extensions.
17: The highlights of the QUIPU Directory Service
18: Implementation are:
19:
20: \begin{itemize}
21: \item
22: Use of memory structures to provide fast access, without use of
23: complex keying techniques.
24: \item
25: Activity scheduling within the DSA to allow for multiple accesses.
26: \item
27: General and flexible searching capabilities.
28: \item
29: A mechanism to provide non-local access control.
30: \item
31: A mechanism to provide external schema management.
32: \item
33: A sophisticated approach for management of distributed operations and
34: replication.
35: \end{itemize}
36:
37: The current implementation provides a DSA, and a procedural interface to the
38: Directory Abstract Service and the associated Directory Access Protocol
39: (DAP), which will enable other applications to use the Directory.
40:
41: \section {General Aims}
42:
43: To understand the rationale behind some of the decisions, it is
44: useful to consider the original aims of the QUIPU project.
45: These
46: can then be mapped onto a number
47: of more technical considerations:
48:
49: \begin{itemize}
50: \item To produce an implementation which followed the
51: emerging standards. This is an aim in itself.
52:
53: \item Flexibility, to enable the system to be used
54: for experimentation and research into problems relating to directory
55: services.
56:
57: \item To provide a vehicle for experimentation in the area of
58: distribution and replication.
59:
60: \item To provide some level of real usage.
61: This sort of work is useless if entirely confined to the laboratory.
62: It is important that it is capable of use for some level of experimental
63: service. However, it is not consciously designed to evolve into a full
64: fledged product.
65: \end{itemize}
66:
67: As the work has evolved, the following goals have emerged as
68: additional to the original ones listed above:
69:
70: \begin{itemize}
71: \item To provide a public domain the OSI Directory implementation as a part of
72: the ISODE package.
73:
74: \item To provide integrated support for the ISODE Applications.
75:
76: \item To be used as a part of the initial pilot Directory Service in
77: the UK Academic Community and in other pilots.
78: \end{itemize}
79:
80:
81: \section {Technical Goals}
82:
83: The major goals of the QUIPU Directory Service are:
84:
85: \begin{itemize}
86: \item Full support of the Directory Access Protocol and Directory System
87: Protocols \cite{CCITT.Directory}.
88: \item
89: Support of the majority of the service elements specified in the OSI Directory.
90: \item
91: Full interworking with other OSI Directory implementations.
92: \item
93: Very full searching and matching capabilities, beyond the minimum
94: required by the OSI Directory.
95: \item
96: Provision of a system which has potential for very high distribution.
97:
98: \item Support of distributed operations in a manner which is full
99: conformant with respect to non-QUIPU systems, and provides additional
100: functionality for QUIPU systems.
101:
102: \end{itemize}
103:
104: The following areas were not intended as goals in the initial system.
105: Some discussion is given as to how these areas might be tackled in
106: future versions.
107:
108: \begin{itemize}
109: \item
110: The QUIPU Directory is not intended for very large scale
111: systems (i.e., Millions and tens of Millions of entries per DSA or hundreds
112: of megabytes of data per DSA).
113:
114: \item
115: Substantial data robustness is not required: there is no need to employ
116: complex data backup techniques, such as replicated hardware.
117: \item
118: The security aspects of the OSI Directory were initially omitted, as not
119: required by the general aims.
120: At this point, there is no reason why this aspect should not be
121: integrated.
122:
123: \end{itemize}
124:
125: \section {Further QUIPU documents}
126:
127:
128: The following documents are available, in addition to this manual:
129:
130: \begin{itemize}
131: \item A paper on the original design, which is mainly of historical interest
132: \cite{inca-paper}.
133:
134: \item A paper presented at the 1988 IFIP 6.5 conference, which gives a
135: general overview \cite{QUIPU.IFIP}.
136:
137: \item A paper presented at Esprit Conference Week 1988, which describes the
138: distributed operations \cite{QUIPU.Distributed}.
139:
140: \item A paper presented to the Dutch \unix/ User Group in November 1989, which
141: describes how Quipu DSAs navigate the DIT \cite{QUIPU.Navigate}.
142:
143: \end{itemize}
144:
145: These papers, except the first, are distributed online with QUIPU.
146:
147: \chapter {General Design}
148:
149: \section {Overview}
150:
151: This chapter describes general decisions.
152: In particular, issues relating to use of
153: the OSI Directory are covered,
154: rather than
155: system implementation decisions.
156: However, the two are somewhat bound up.
157: Attention is drawn to the protocol extensions defined in section
158: \ref{edb-ros}. Note that this does {\em not} affect interactions with
159: non-QUIPU DSAs (or DUAs).
160: The following aspects of the OSI Directory are not handled in QUIPU 6.0.
161:
162: \begin{itemize}
163: \item The protocol elements for support of directory use of authentication
164: are handled in a conformant manner, but the associated services are not
165: available to the end user.
166:
167: \item
168: Search is always supported by multicasting. This does
169: {\em not} affect the basic service offered to the user, but means that
170: prohibition of chaining is not possible in all cases.
171:
172: \item Partial Outcome Qualifier is not supported for List.
173:
174: \item There are some aspects of distributed operation, where interaction
175: with another conforming system would not be fully general. In particular,
176: QUIPU might not be able to be configured with references to point at a
177: complex configuration where not all sibling entries are held.
178: \end{itemize}
179:
180: Otherwise, QUIPU 6.0 is believed to conform to the standard.
181:
182: \section {Service Controls}
183:
184: QUIPU use of service controls conforms to the OSI Directory.
185: Comments are made on those
186: controls where QUIPU makes a choice with respect to some option
187: given by the OSI Directory.
188:
189: \begin{description}
190: \item [preferChaining]
191: Chaining will be done.
192:
193: \item [chainingProhibited]
194: Chaining will not be done.
195: For some cases of the search operation, this means that the QUIPU Directory
196: Service will not be able to provide the service, and will return a
197: ``chaining required'' error.
198:
199:
200: \item [localScope]
201: The scope will be restricted to the DSA concerned (i.e., no chaining will be
202: done).
203:
204: \item [dontUseCopy] If this is set, the master data will be used. This may
205: have a significant impact on performance for operations on entries which are
206: high up the tree and for the DSAs which master this information. These issues
207: need study.
208:
209:
210: \item [dontDereferenceAliases]
211: Followed as per the OSI Directory.
212:
213: \item [priority]
214: This is used to help control scheduling within the DSA. High priority
215: tasks are dealt with before low priority tasks (Note: there are no checks
216: here, so this is open to mis-use !)
217:
218: \item [timeLimit]
219: Followed as per the OSI Directory.
220:
221: \item [sizeLimit]
222: Followed as per the OSI Directory.
223:
224: \item [scopeOfReferral]
225: The OSI Directory is followed, although QUIPU does not make use of this control.
226: \end{description}
227:
228:
229: \chapter {Distributed Operation}
230: \label {dist-op}
231:
232: \section {Overview}
233:
234:
235: Distributed Operation is a major aspect of the QUIPU
236: Directory Service
237: Sadly, the OSI Directory specifications in this area are, in the author's
238: opinion, rather unsatisfactory.
239: Therefore, the QUIPU distributed operations are described in a slightly
240: different manner. The concept of ``Naming Context'' is not used, and the
241: significance of ``Knowledge'' is de-emphasised. The external view of this
242: functionality is fully in line with the standard.
243:
244: Some of the concepts
245: defined in this chapter do {\em not} correspond to the
246: ISO/CCITT terms, and so new terminology is introduced.
247: Standard terminology is used in the standard way.
248:
249:
250: \section {DSA/DUA Interaction Model}
251:
252: There are some interesting choices to be made between DSA Referral and
253: Chaining. A DUA will start by contacting a local DSA, specifying that
254: chaining is preferred (i.e., DSA referrals should not be passed back to the
255: DUA). After that, the first DSA will proceed by use of DSA Referral, except
256: for operations where this is not possible in the QUIPU framework (some cases
257: of search). The advantages of this approach are:
258:
259: \begin{itemize}
260: \item
261: The DUA code can be kept to a minimum, as there is no need to handle
262: referrals.
263: This does mean that the DUA must always interact with the Directory
264: Service through a DSA which supports chaining (which might exclude
265: some implementations).
266: \item
267: Always going thorough a local DSA allows a ``per system'' cache to
268: be maintained in a coherent manner.
269: \item
270: The overhead of maintaining chained connections is not passed
271: on too far.
272: \end{itemize}
273:
274: Note that whilst the DUA procedural does not handle referrals transparently,
275: they are defined in the service interface, so that an application can
276: choose to handle the referrals directly if it wishes to do so.
277:
278: \section {Model of Data Distribution}
279: \label {model-dist}
280:
281: This is a critical section of the design. It is essential to understand it
282: before studying distributed operation.
283:
284: \subsection {Entry Data Blocks}
285:
286: For the root and every non-leaf vertex, there will be an
287: {\em Entry Data Block} (EDB)
288: which contains
289: {\em all}
290: information pertaining
291: to the next level down in the DIT.
292: Figure~\ref{edbf} gives and ASN.1 description of
293: the Entry Data Block format.
294:
295: \tagrind [htbp] {edb}{Entry Data Block Format}{edbf}
296:
297:
298: It should be noted and remembered that
299: the Entry Data Block associated with an entry and described as ``the Entry
300: Data Block of the entry'' contains the entries children (i.e., their
301: attributes and RDNs)
302: and not the attributes of the entry itself.
303: This is {\em not} necessarily intuitive.
304:
305:
306:
307: \subsection {Masters and Slaves}
308:
309: Every Entry Data Block has {\em Master} and {\em Slave} copies.
310: There will typically be only one master (although there may be
311: multiple master copies, where data is maintained ``out of band'').
312: Slave copies are automatically replicated from a Master EDB.
313: This may be direct or indirect. The full propagation path must be acyclic
314: (loop free).
315:
316: A DSA has either all or none of an Entry Data Block
317: as a Master or Slave
318: (viz: Entry Data Blocks are atomic).
319: Any other DIT information it contains is treated as cached
320: data.
321: A DSA does not need to have any Master or Slave data.
322:
323:
324: DSAs are named, and represented in the DIT.
325: One of the reasons for this, is to enable use of the
326: Directory to identify the OSI location of DSAs.
327: This OSI location can then be adjusted transparent to the
328: logical mapping of the DIT onto DSAs.
329: This can be seen as treating a DSA in the same manner as any other
330: Application Entity.
331: This simplifies the implementation, as there does not need to be
332: specific storage of additional configuration information (knowledge).
333:
334: An important piece of information stored in the entry of each DSA is the
335: list of EDBs and how they are replicated. This information is the basis for
336: automatic replication.
337:
338: \subsection {QUIPU Subordinate References}
339:
340: An entry has associated with it, attributes which indicate the
341: DSAs which have Master or Slave Entry Data Blocks for the entry
342: in question.
343: These pointers are known as {\em Quipu Subordinate References} (QSR).
344: For every QSR, the DSA must have a Master or Slave copy of the EDB, as
345: implied by the QSR.
346: The converse it not true: DSAs may have copies of EDBs without there being
347: QSRs.
348: The DSAs with QSRs have the information {\em and} are
349: prepared to answer public queries about the Entry Data Block in
350: question.
351: DSAs with EDBs (typically slave copies) and no QSRs usually have copies for
352: performance or robustness reasons.
353:
354: Quipu Subordinate References are similar to the standardised Non-Specific
355: Subordinate References (NSSR). There are the following differences:
356:
357: \begin{itemize}
358: \item QSRs admit to replication, and therefore there are Master QSRs and
359: Slave QSRs.
360:
361: \item A QSR always points to all of the relevant information, whereas an NSSR
362: may only point to a part of it and must be used in ``and'' conjunction with
363: other NSSRs.
364: \end{itemize}
365:
366:
367: \subsection {Access to the root EDB}
368:
369: There is no requirement for a given DSA to hold a copy of the
370: root Entry Data Block.
371: However, to be able to systematically process all queries, there
372: must be direct or indirect access to the root Entry Data Block.
373: Therefore, every DSA which does not have a copy of the root
374: Entry Data Block must know the name and address of one or more
375: DSA which either has a copy of the root Entry Data Block, or is
376: closer (in terms of these references) to a DSA which has a
377: copy. This approach is similar to, but not the same as, use of superior
378: references defined in the standard.
379:
380: \section {Standard Knowledge References}
381:
382:
383: In addition, to the QUIPU specific QSRs, an entry might also contain
384: standard Knowledge References, as defined in the OSI Directory. This is
385: used to point to data not contained in a QUIPU DSA. There are three types
386: of reference defined in the standard:
387:
388: \begin{description}
389: \item[Subordinate Reference] Pointer to an Entry
390:
391: \item[Cross Reference] From the QUIPU standpoint, the same as a subordinate
392: reference
393:
394: \item[Non Specific Subordinate Reference] Pointer to multiple subordinates
395: which must be queried for the next level down. QSRs are similar to this
396: (see previous section).
397:
398: \end{description}
399:
400: In the first two cases, the entry in the Entry Data
401: Block is considered to be ``Knowledge only'' (although other entry
402: information may be cached).
403: In the third case the entry will also have full information on itself.
404: If any of these are present, there will be no QUIPU master or slave pointers.
405: These three types of pointer are mutually exclusive\footnote{Thought(SEK) ---
406: does the standard let you have a subordinate reference plus a cached NSSR?}.
407:
408: These attributes are not supported in QUIPU 6.0.
409:
410: \section {Navigation}
411:
412: Given this data model, a straightforward navigation algorithm
413: can now be specified.
414: The requirement is to locate the entry associated with a
415: specified Distinguished Name.
416: When the entry is arrived at, the operations will behave
417: as proscribed.
418:
419: The basis of the navigation strategy is that the first DSA (i.e., the one
420: accessed by the DAP) does all of the hard work. Other DSAs, accessed by DSA
421: Referral, either answer the question or return an error. This is important,
422: as it is the basic strategy by which the system ensures completion of
423: queries.
424: There are times when the DSA may depart from this model, these are discussed
425: in Section~\ref{DSA:select} and \cite{QUIPU.Navigate}.
426:
427: First consider the behaviour of a DSA accessed by the Directory
428: System Protocol (DSP):
429:
430: \begin{enumerate}
431: \item
432: Look up the Distinguished Name.
433: \item
434: If the Distinguished Name is found, go to step 6.
435: \item
436: If there is a local copy of
437: the Entry Data Block of the parent,
438: return a nameError.
439: The ``matched'' parameter should be set to the Distinguished Name
440: of the Entry Data Block (i.e., the level above the offered name).
441: This is an authoritative NO.
442: \item
443: Strip the lowest component off the Distinguished Name, and go
444: to step 1.
445: If there are no more components, go to step 5.
446: This process checks for authoritative NO.
447: \item
448: At this point, the name has not been found, and no relevant
449: Entry Data Block has been found.
450: This implies that the DSA does not hold the root Entry Data
451: Block.
452: Therefore the DSA should return a DSA Referral.
453: The DSA Referral should be the list of DSAs (names and
454: addresses) which are known
455: to be closer to the root.
456: \item
457: We now have an entry which matches some or all of the original
458: Distinguished Name.
459: Consider this entry.
460: \item
461: If the entry contains an Alias attribute, dereference, and goto step 1.
462: Note that if a referral is returned, that the appropriate parameters should
463: be set to indicate all dereferences.
464: \item
465: If the entry is the one specified in the query, return the
466: answer to the query, or the appropriate (authoritative) error.
467: \item
468: If the entry is of object class ``QuipuNonLeafObject'', return a Referral.
469: This is simply a redirect to a DSA which can take the query at least one
470: step further. The names for the DSA Referral should be taken from the
471: master and slave Quipu Subordinate References. Where the calling DSA is a
472: non-QUIPU DSA, the Presentation address of the Master DSA must be looked up,
473: and only this one returned.
474: \item
475: If the entry contains a reference, the appropriate referral should be
476: returned.
477: \item
478: The query refers to an entry below the bottom of the DIT.
479: An authoritative nameError can be returned.
480: \end{enumerate}
481:
482: Now consider the slightly more complex case of the initial
483: DSA (doing the DSA Referral).
484: Steps 1-4 are followed as above
485: as above, to determine authoritative NO.
486:
487: \begin{enumerate}
488: \setcounter{enumi}{4}
489: \item
490: At this point, the name has not been found, and no relevant
491: Entry Data Block has been found.
492: This implies that the DSA does not hold the root Entry Data
493: Block.
494: The list of DSAs which are known
495: to be closer to the root, are the starting point for the
496: iterative query.
497: Go to step \ref{step-iter}.
498: \item
499: We now have an entry which matches some or all of the original
500: Distinguished Name.
501: Consider this entry.
502: \item
503: If the entry contains an Alias attribute, apply the relevant
504: dereference to the original query, and go back to the start.
505: \item
506: If the entry is the one specified in the query, return the
507: answer to the query, or the appropriate (authoritative) error.
508: \item
509: If the entry is of object class ``QuipuNonLeafObject'',
510: this gives a list of QSRs to start the iterative query.
511: Go to step \ref{step-iter}.
512: \item
513: If the entry contains a standard knowledge reference, then
514: go to step \ref{step-iter}. Note that for non-specific subordinate
515: references, {\em all} of the references must
516: be followed before giving up.
517: \item
518: The query refers to an entry below the bottom of the DIT.
519: An authoritative nameError can be returned,
520: \item
521: \label{step-iter}
522: Select one of the DSAs from the referral list.
523: The order to try the DSAs is arbitrary.
524: However, it is attempted to select ones with the
525: topologically closest name first (e.g., a UK DSA will prefer to
526: query another UK DSA before asking a French one).
527: Try DSAs in turn until one gives an answer or you get bored.
528: Consider the answer.
529: Authoritative answers (yes or no) should be passed back to the
530: DUA.
531: If a Referral is received, recurse to step, watching
532: carefully for loops.
533: \end{enumerate}
534:
535: It can be seen that this navigation is relying on data being
536: distributed correctly, and DSAs other than the one doing the
537: work behaving in a correct manner.
538: Information provided in the referral should be used to ensure that the
539: iteration is progressing, and thus detect livelock situations.
540:
541:
542:
543: \section {List}
544:
545: The Entry Data Block concept allows the list operation to fall out in a
546: straightforward manner.
547: Navigation to the Entry Data Block belonging to the name provided, will
548: give access to the full result for the list operation.
549:
550: Note that where cross/subordinate references are involved, it will be
551: assumed that these are not alias entries (reasonable in practice).
552: This will allow list to be performed in a single DSA in all cases.
553:
554: \section {Search}
555:
556: This section describes how the OSI Directory search is supported. This is
557: one of the hardest parts of the implementation, and care must be taken.
558: Note that the DAP argument in DSP is always that provided by the
559: DUA\footnote {Whilst this is in principle one of the key aspects of the way
560: the DSP works, the recommendations for distributed operations violate this
561: principle when dealing with aliases during search.}. This means that the
562: work done by a given DSA must be in relation to the target object. With
563: other operations, this is (fairly) straightforward, as the target object
564: always references the base object of the operation. For searching, care
565: must be taken to correctly verify whether the base object has been reached.
566: This is done by use of the operation progress information, setting the name
567: resolution phase to completed.
568:
569: The search operation functions by searching the part of the tree implied
570: by the ``subset'' specification.
571: Rather than returning all of the information, the queried DSA will apply
572: the associated filter to the entries in question, and return the
573: filtered result, along with appropriate continuation pointers.
574: This should minimise network traffic.
575:
576:
577: The case of ``subset = baseObject'' is handled by navigating to the Entry
578: Data Block of the object's parent, and applying the given filter.
579: If the entry is a cross reference or subordinate reference, the reference
580: should be followed (using the same query).
581:
582: The case of ``subset = oneLevel'' is handled by navigating to the object's
583: own Entry Data Block.
584: There the filter is applied to each of its children.
585: If any of the children are alias entries, the alias should be
586: de-referenced, and a baseObject search applied to the new entry.
587: For each child which is a cross references or subordinate references,
588: the references should be followed, setting the target object to be the child.
589:
590: The case of ``subset = wholeSubtree'' is handled by navigating to the
591: object's own Entry Data Block.
592: There, the filter is applied to the object and to each of its
593: children.
594: If any of the children are alias entries, the alias should be
595: de-referenced, and a wholeSubtree search applied to the new entry.
596: For each child which has QUIPU children (determined
597: by the prescence of a masterDSA attribute), the search should be applied to
598: the master or one of the slave DSAs, with target object set to the child.
599: For each child which is a cross reference or subordinate reference,
600: the references should be followed, setting the target object to the child.
601: For each child which has non-specific subordinate references, the search
602: should be applied to {\em all} of the referenced DSAs, with the target
603: object set to the child.
604:
605: There are three procedures for operating:
606:
607: \begin{enumerate}
608: \item Everything handled by the first DSA, with other DSAs returning a
609: mixture of results and partial outcome qualifiers.
610:
611:
612: \item Proceed by referral until a DSA is reached which has a copy of the
613: base object. Then this DSA proceeds by referral, and returns the full
614: result to the first DSA. This is how QUIPU 6.0 works. It has the advantage
615: of often accumulating search results in a local environment, and so is
616: selectable (possibly in a complex manner).
617:
618: \item Proceed by referral until a DSA is reached which has a copy of the
619: base object. Then proceed entirely by chaining. This is not done.
620:
621: \end{enumerate}
622:
623:
624: There is potential for looping in this procedure.
625: This will be detected and broken by noting loops in the DSA trace
626: information.
627: This takes account of the fact that some distribution will allow
628: for a query to re-enter the same DSA a number of times.
629:
630:
631: The Search and list operations make use of the ``partial results''
632: functionality to return information if a time or size limit is reached.
633: Thus, setting a low size limit will allow a user to easily examine
634: sample information (either by list or search).
635:
636: \section {Selecting a DSA}
637: \label{DSA:select}
638:
639: In Quipu-5.0 the
640: chain/refer choice was very ad hoc. For a DSA, the best
641: choice is usually to give a referral, except where this will not work.
642: To make this calculation, it is necessary to determine if two DSAs can
643: communicate directly. This is done by deriving from
644: the presentation address of a DSA, a list of connected networks. This can
645: then be used to determine if a pair of DSAs can communicate directly, and is
646: the basis for the chaining/referral choice. This will need the extension
647: of the network address, to allow encoding of private networks other than the
648: three well known ones.
649:
650: There is an analogous problem when a DSA needs to access a DSA which cannot
651: be accessed directly. Each DSA which does not have full connectivity, will
652: have an attribute which indicates network/DSA pairs. This indicates a DSA
653: which may be used (bilateral agreement) to access a given network by
654: application relay.
655:
656: The following Sections discuss briefly how these choices are made,
657: \cite{QUIPU.Navigate} describes the process more fully.
658:
659: \subsection {DSA Quality}
660:
661: Replication gives a choice of DSA to ask a given query to. The following
662: criteria are relevant:
663:
664: \begin{itemize}
665: \item Use an existing association if possible
666: \item Prefer a QUIPU DSA
667: \item Prefer a reliable DSA
668: \item Prefer a ``local'' DSA
669: \end{itemize}
670:
671: The first two are straightforward.
672: A local DSA can be selected using the following\ldots
673:
674: \begin{enumerate}
675: \item
676: Prefer to use networks in the order
677: specified by ts\_communities. This will encourage access over a local
678: ether/preferred net.
679:
680: \item Pick a DSA with a close name (e.g., prefer one in the same country)
681:
682: \item Pick a DSA in the same DMD. This would need to add a DMD attribute to
683: the DSA entry (encoded as DN) [Not yet implemented].
684: \end{enumerate}
685:
686: Picking a reliable DSA is achieved using the following information
687: \begin{verbatim}
688: DSAInfo ::= SEQUENCE {
689: dsa DistinguishedName,
690: lastAttempt UTCTime,
691: lastSuccess UTCTime OPTIONAL,
692: failures-since-last-success INTEGER }
693: \end{verbatim}
694: Thus a DSA will be able to check if it knows about the DSAs in question, and
695: can make a choice based on past results. This should operate dynamically,
696: without operator interference. Info on DSAs not contacted for a given period
697: should be expunged.
698: It is hoped to store this as an attribute of a DSA in future versions of
699: Quipu.
700:
701:
702: \subsection {Unavailable DSAs}
703:
704: In the case where a DSA is unavailable, and chaining is preferred, a reference
705: will be returned by a QUIPU DSA.
706: A QUIPU DUA, which knows it is talking to a QUIPU DSA
707: can rely on this behaviour, and simply use the referral as a diagnostic to
708: the user. It is hoped that the next version of the standard will add an
709: obvious extra parameter.
710:
711:
712: \subsection {Operating When DSAs are not Fully Interconnected}
713: \label {tcp-only}
714:
715: Whilst global interconnection of all application entities is an OSI ideal,
716: it will not be achievable in the short or medium term. Application relaying
717: by DSAs will be needed to achieve full directory connectivity.
718:
719:
720: In general, it is not desirable for DSAs to proceed by chaining - it wastes
721: unnecessary application level resources. Later, there may be policy reasons
722: to prefer chaining, but these are ignored for now. The internal structure
723: of network addresses allows a DSA to determine if two DSAs can communicate
724: directly.
725:
726:
727:
728: \section {The External View of QUIPU}
729:
730: To a non-QUIPU system, QUIPU will appear to work exactly according to the
731: standard.
732:
733: When a QUIPU DSA interacts with another DSA, it will look up its object
734: classes (and probably other information). This will allow it to determine if
735: the other DSA is a QUIPU DSA. When interacting with another QUIPU DSA, the
736: following deviations from the standard are possible. These are primarily
737: concerned with the introduction of replication:
738:
739: \begin{itemize}
740: \item Presentation Address might be omitted from Access Point (always
741: present in QUIPU 6.0, for consideration in QUIPU 7.0).
742: \item Cross References and Subordinate References have multiple values
743: (although QUIPU will probably never send these to itself).
744: \item Multiple values of Non Specific Subordinate Reference are assumed to
745: have OR conjunction (i.e., they are really QSRs).
746: \item Use of QUIPU Access control as described in Section~\ref{dsp-acl}
747: \end{itemize}
748:
749: When a QUIPU DSA returns references which are derived from reference
750: attributes, it will return them as specified. If it returns information
751: derived from QUIPU internal pointers, it will return a non-specific
752: subordinate reference. If the DSA being communicated with is not a QUIPU
753: DSA, it will return only a reference to the a selected DSA (as replication is
754: not admitted within the protocol).
755:
756: \section {Cached Data}
757: \label {cache-all}
758:
759: Cached data is not mentioned in the basic algorithm.
760: However, the algorithm can utilise cached
761: data in some circumstances.
762: This is because of the manner in which identification of copy data has been
763: introduced in the final stage of the OSI Directory specification.
764: Cached data may be used whenever this is not prohibited by the service
765: controls.
766: The standard does not clearly define what ``copy'' data is. In general,
767: QUIPU treats master and slave data as authoritative.
768: Both slave and cached data are returned to the user as
769: ``copy'' data. For this reason, the distinction between slave and copy data
770: can only be internal to QUIPU.
771:
772: There is no time to live or age information in the OSI Directory Protocols.
773: Care must be taken when caching, that spurious information is not passed
774: around indefinitely between DSAs.
775:
776: When QUIPU holds cached data, it will notes how long it has had it, and will
777: ``time out'' the data after a tailorable period.
778:
779: This section is open ended.
780: The exact approaches to caching, and determining suitable timeout values
781: will be the subject of experiment.
782:
783:
784: The important thing about managing cached data is to handle timeouts
785: sensibly.
786: Data cached from a cache may have an indeterminate age.
787: It is important that this data is given a relatively short timeout, to
788: prevent it being circulated indefinitely amongst a set of DSAs.
789: However, {\em if} the data can be verified by usage (e.g., correctly
790: connecting to a DSA verifies a presentation address), it should then be
791: treated as if cached from a master/slave.
792: Non-verified data should be treated in the same manner as user data, which
793: is described in the next section.
794: Data cached from master/slave information should be given a longer timeout.
795: Data is discarded, rather than refreshed automatically. A timeout of some
796: number of days seems appropriate for most data.
797:
798: \section {Configuration and Slave Update}
799:
800: A given DSA will have copies of zero or more Entry Data Blocks.
801: A DSA may either be a master for a given Entry Data Block, or a
802: slave.
803: If there are multiple master copies, it is assumed that these
804: are kept coherent by some out of band mechanism.
805: For example, one of them is the ``real'' master, and the others
806: are updated by file transfer when modifications occur.
807: This discussion will proceed for the single master case.
808:
809: There are three distinct types of DSA:
810:
811: \begin{enumerate}
812: \item
813: A DSA with a master copy of the root Entry Data Block.
814: \item
815: A DSA with a slave copy of the root Entry Data Block.
816: \item
817: A DSA with no copy of the root Entry Data Block.
818: \end{enumerate}
819:
820: As noted in Section~\ref{model-dist}, DSAs of type 2 and 3 will have pointer(s) to
821: a DSA which is ``closer'' to the master copy of the root Entry
822: Data Block.
823: Specifying this hierarchical distribution, as opposed to requiring
824: direct access to the master (as in earlier versions of the OSI Directory)
825: means that there can be many copies of information which needs to be highly
826: replicated, without excessive
827: redundant copying across the Wide Area Network.
828: This will be particularly important for the root Entry Data Block.
829:
830: DSAs of type 2 will only need the pointer information for initial
831: startup or recovery after catastrophic corruption.
832: When the slave copy of the root Entry Data Block has been
833: obtained for the first time, this will supercede the pointers.
834: DSAs of type 3 will usually use cached information in preference to
835: these pointers, and will only need the pointers if cached information is
836: (or appears to be) invalid.
837:
838: The only information which a DSA has to obtain locally at initial boot time,
839: other than the DSA pointers, is its own name. All other information may be
840: obtained from the Directory.
841: Beyond this, the Directory Service manages its own
842: configuration.
843: There is little point in having a Directory Service providing
844: general high speed access to global information, and then
845: requiring an additional system (knowledge) to deal with its own
846: configuration.
847:
848: Associated with the DSA's entry in the DIT is a specification of
849: the entries for which the DSA is a master, and for which it is
850: a slave.
851: A DSA will be able to derive the location of an Entry Data
852: Block for which it is master from this information.
853: Thus at initial boot, a DSA will utilise its initial DSA pointers
854: to read its own entry.
855: The location of master Entry Data Blocks will be derivable from
856: their name, and so their existence can then be verified by the
857: DSA in question.
858: A DSA which is a master for the root Entry Data Block will have
859: no pointers.
860: However, it can go straight to the master root Entry Data
861: Block, read the information about itself, and proceed as for
862: other DSAs.
863:
864:
865: It is believed that for early pilots, a high level of copying configuration
866: data will be desirable to achieve robustness. The root and national EDBs
867: will be very highly replicated, even though QUIPU can operate with a rather
868: low level of replication.
869:
870: \section {DSA Naming}
871: \label {dsa-naming}
872:
873: \subsection {Choice of Names to Prevent Loops}
874:
875: Care must be taken to prevent the situation where the location
876: of a DSA is only known through itself (and other more complex
877: variants).
878: A simple rule for naming DSAs will ensure that this cannot
879: happen.
880: The master DSA for a given entry (i.e., the DSA controlling the Entry Data Block of
881: containing
882: the entry's children) should have its
883: name in the Entry Data Block of the entry's parent or at a
884: level higher in the DIT.
885: For example, the master DSA of
886: \begin{quote}\small\begin{verbatim}
887: Country=UK, Org=University College London, OU=Computer Science
888: \end{verbatim}\end{quote}
889: which contains information on entries below Computer Science, may be labelled
890: \begin{quote}\small\begin{verbatim}
891: Country=UK, Org=University College London, DSA=Three Toed Sloth
892: \end{verbatim}\end{quote}
893: or
894: \begin{quote}\small\begin{verbatim}
895: Country=France, DSA=Capybara
896: \end{verbatim}\end{quote}
897: It may not be labelled
898: \begin{quote}\small\begin{verbatim}
899: Country=UK, Org=University College London, OU=Computer Science,
900: DSA=Alpaca
901: \end{verbatim}\end{quote}
902: or
903: \begin{quote}\small\begin{verbatim}
904: Country=France, Org=Inria, DSA=Llama
905: \end{verbatim}\end{quote}
906:
907:
908: A little more flexibility could be allowed;
909: However, this rule is simple, it prevents deadlock, and allows
910: for reasonable labelling practices.
911: The restriction may be relaxed somewhat, when the concept of Directory
912: Management Domains is introduced more formally.
913:
914: \chapter{Access Control and Authentication}
915:
916: \input{q-secdes}
917:
918: \chapter {Replicating Updates}
919: \label {des-first}
920: \label {dist-update}
921:
922:
923: \section {Basic Update Approach}
924: \label {edb-ros}
925:
926: QUIPU supports a simple automatic update
927: mechanism.
928: This allows for copying of Entry Data Blocks,
929: but with a simple check to ensure that only new information is copied.
930: Slave copies are obtained by use of a new remote operation.
931: The argument to the operation is the name of the Entry, and the
932: version number of the copy of the Entry Data Block held
933: locally.
934: A FULL copy of the Entry Data Block is returned if this version
935: is out of date.
936: In the DSA's entry, there is a list of Entry Data Blocks for which the DSA
937: has master or slave copies, and the DSA which it gets updates from.
938: For each Entry Data Block, there is the list of DSAs which pull the Entry
939: Data Block, and for slave copies, which DSA the update should come from.
940: It is assumed that this operation will be invoked sufficiently
941: often for it to be acceptable to consider the slave data as
942: ``official''.
943: For the type of usage being considered, this probably means several
944: times per day.
945: Within QUIPU, this operation is in a new protocol (QUIPU DSP), which will
946: also contains the DSP ASEs.
947: The operation is specified in Figure~\ref{getedb-py}.
948:
949: \tagrind {getedb}{EDB Access Operation}{getedb-py}
950: \clearpage
951:
952: Note that a DSA receiving a GetEDB operation, should check the associated
953: EDBInfo, to ensure that the DSA in question is allowed to pull a copy of
954: this EDB.
955:
956: The operation may be used to determine which version of the EDB is currently
957: master. This might be used when a query with dontUseCopy arrives, in order
958: to determine whether slave information is accurate. This would be a big
959: performance win for search and list operations, due to potnetila reduction
960: in information transferred.
961:
962: \chapter {Implementation Choices}
963:
964: \section {DSA Structure}
965:
966: Whilst the operation of a QUIPU DSA is fast, its
967: startup procedure is not, due to reading all of its data from a text file on
968: disk.
969: This long startup means that applications must be able to use
970: multiple DSAs, to prevent lockout whilst the local DSA starts up.
971: Also, the process structure of DSAs must be static.
972: To provide a system with reasonable availability, particularly in view of
973: the system's ability to perform extravagant searching, the basic
974: DSA must be able to handle multiple calls.
975: For this reason, apart from conformance issues, the DSA will be inherently
976: asynchronous, and will need to have its own internal scheduling.
977: Initially, this can be simple minded.
978: However, we are providing a framework for a system which is very
979: sophisticated in this area.
980:
981: The basic approach of the DSA is to have two (conceptually) co-routined modules, which are
982: interfaced by in-core C structures.
983: The first module is the DSA engine, which resolves inbound queries either
984: by looking them up in its in-core data structures or by generating further
985: queries.
986: The second module is the protocol engine.
987: This is responsible for opening and closing calls, and for mapping between
988: OPDUs on the network and C structures to be handled by the DSA engine.
989: The interface provided to the DSA is largely independent of DAP vs DSP.
990:
991: \subsection {Memory Structures}
992:
993: There are a number of structures which are of particular importance.
994: They are summarised here:
995:
996: \begin{itemize}
997: \item
998: The Entry is as the basic component of the in-core tree, which is linked
999: upwards and downwards between parents and children.
1000: The tree always starts at the root, even if there is no information beyond
1001: the RDN present.
1002: Where an entry corresponds to the base of an Entry Data Block, the parameters
1003: of the Entry Data Block are present.
1004: Siblings are linked in a chain.
1005: Each entry is represented by a `C' structure, which contains:
1006:
1007: \begin{itemize}
1008: \item
1009: Information on the linkage (hierarchical, and between siblings).
1010:
1011: \item
1012: How Entry Data Blocks are managed.
1013:
1014: \item
1015: How the ``special'' attributes (ACL, Schema, Alias, Password, DSA location
1016: info) are held.
1017: \end{itemize}
1018:
1019: \item
1020: There is a structure associated with each connection.
1021: This is used to represent actual and desired connections.
1022: These structures are linked into a list, and are the key point for the
1023: protocol module.
1024: They indicate a list of operations and tasks associated with each connection.
1025: When the DSA engine needs a connection, it will see if one is already
1026: open to the DSA in question. If it is not, a connection structure will be
1027: created, which the protocol engine will act on in due course.
1028: Similarly, the protocol engine will close down unneeded connections, possibly
1029: after some (intentional) delay.
1030:
1031: \item
1032: There is a Task structure associated with each query which arrives.
1033: This holds the {\em full} state of the task, so the the DSA can switch between
1034: tasks at intervals (typically when a network connection blocks).
1035: This points to the list of operations which have been generated by the task.
1036: This is the key structure for the DSA Engine.
1037:
1038: \item
1039: There is an Operation structure, associated with each pending operation.
1040: These structures are in mesh structure, arranged both by Task and Connection.
1041: \end{itemize}
1042:
1043: Multi-level priorities are associated with tasks and operations, which are
1044: used by both engines to control scheduling.
1045: This will be done in QUIPU 6.0 on two bases:
1046:
1047: \begin{itemize}
1048: \item The user specified priority
1049:
1050: \item The progress of the operation (long searches are downgraded in
1051: priority).
1052: \end{itemize}
1053:
1054: \subsection {Malloc}
1055:
1056: The above is optimised by careful use of malloc. \index{malloc}
1057: A purpose built malloc is used, this knows about the memory intensive DSA,
1058: and tries to ensure that data accessed at similar times during the DSA
1059: operation, will be stored in the same page of core memory.
1060: This has the effect that the number of page faults generated is
1061: significantly reduced (early results indicate a twenty percent improvement
1062: over the standard malloc supplied with SunOS4).
1063:
1064: \subsection {Disk Structures}
1065:
1066: All of
1067: the data for a given QUIPU DSA
1068: will be
1069: contained under a single (UNIX) directory. There will be a directory for
1070: each RDN, where the DSA in question has an Entry Data Block (which may be
1071: master, slave, or cached).
1072: The name of directory being that of the QUIPU text encoded RDN.
1073: Thus there will be a UNIX directory structure which corresponds to the
1074: portion of the DIT held in the DSA.
1075: There will be file in each RDN directory called ``EDB'', which has the
1076: authoritative version of the data, and one called ``EDB.bak'', which has the
1077: previous version.
1078: This might be extended to provide more comprehensive backup.
1079:
1080:
1081: When the system is booted, the following will occur:
1082:
1083: \begin{enumerate}
1084: \item
1085: Read tailoring information.
1086: \item
1087: Look for sequence of Entry Data Blocks implied by the DSAs name.
1088: These will usually be cached. for later reuse.
1089: If not, the default addresses must be used.
1090: \item
1091: With the DSA's own info available, read in the other master and slave Entry
1092: Data Blocks.
1093: \item
1094: Read in other Entry Data Blocks, checking for consistency.
1095: \end{enumerate}
1096:
1097: \section {OSI Choices}
1098:
1099: ROS (1988) and the implied protocols (ACSE and Presentation) will be used.
1100: Other combinations (e.g., TP0 over TCP or TP4 over CLNS may be used by
1101: bilateral agreement between DUA and DSA or DSA and DSA).
1102:
1103: To ensure full connectivity of the QUIPU Directory Service, one of the
1104: following conditions must be met:
1105:
1106: \begin{enumerate}
1107: \item Support of transport class 0 over international X.25(80) (This condition
1108: will be changed to support of CONS with access to the international X.25
1109: subnetwork, when such a statement is realistic).
1110:
1111: \item Access to a DSA which will perform application relaying in line with
1112: the procedures of Section~\ref {tcp-only}.
1113: This will need a bilateral agreement. It is hoped to establish ``well
1114: known'' DSAs which can serve this function for the following well known
1115: networks:
1116: \begin{itemize}
1117: \item Janet
1118: \item The DARPA/NSF Internet
1119: \end{itemize}
1120: \end{enumerate}
1121:
1122:
1123:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.