![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to duug.ms 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 / duug|
Return to duug.ms CVS log | Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / doc / duug |
1.1 root 1: .\" pic |troff -ms
2: .nr PS 12
3: .nr VS 14
4: .ND
5: .sp 2
6: .TL
7: Directory navigation in the Quipu X.500 system
8: .sp 4
9: .AU
10: Paul Barker
11: Colin J. Robbins
12: .sp 4
13: .AI
14: 12th October 1989
15: .AB
16: .nh
17: OSI Directory Services have recently been standardised according to the
18: X.500 / IS 9594 standard. This first part of this paper gives a
19: brief overview of the Directory Services model.
20: .PP
21: Quipu [1][2] is one of the first implementations of the X.500 standard and
22: has been developed at UCL. \(dg
23: .FS
24: \(dg The work was originally funded by under the European Strategic
25: Program for Research
26: into Information Technology (ESPRIT). Quipu was developed as a deliverable
27: for INCA, project 395. Quipu is currently funded by the U.K. Joint Network
28: Team.
29: .FE
30: Quipu is
31: publicly available as part of the ISODE [3] package.
32: .PP
33: One of the key aspects of Directory Services not fully specified
34: in the standard is that of managing the distribution of the Directory. The
35: approach taken by the Quipu system in representing Directory knowledge and
36: handling Directory navigation across heterogeneous networks is described
37: here. The issues raised by this are discussed.
38: .PP
39: KEYWORDS: OSI, Directory, Quipu, Distributed System, Navigation.
40: .AE
41: .sp 5
42: .NH
43: Introduction
44: .LP
45: The first part of this paper introduces
46: OSI Directory Services. These have recently been standardised according to
47: the CCITT
48: X.500 recommendations / ISO 9594 International Standards [4]. This paper
49: gives a very brief overview of the standards framework.
50: .LP
51: The remainder of the paper discusses the approach taken by Quipu with regard
52: to directory navigation. The discussion focusses on how Quipu attempts to
53: provide a robust and efficient service, given less than fully reliable,
54: heterogeneous networks.
55: .NH
56: Overview of Directory Services model
57: .LP
58: The OSI Directory is intended to support human user querying, allowing
59: users to find, inter alia, telephone and address information of
60: organisations and other users.
61: .LP
62: It is also intended to support electronic
63: communication such as message handling systems and file transfer.
64: The Directory provides name to address mapping to support, for example, OSI
65: presentation address look-ups. Message handling systems will be provided with
66: support for user-friendly naming, security and
67: distribution lists.
68: .NH 2
69: Directory characteristics
70: .LP
71: In essence the Directory is a database with certain key characteristics.
72: .IP 1.
73: The Directory is intended to be very large and highly distributed. It is
74: anticipated that the Directory will be distributed largely on an
75: organisational basis.
76: .IP 2.
77: The Directory is hierarchically structured, the entries being arranged in
78: the form of a tree. Entries near the root of the tree will usually represent
79: objects such as countries and organisations, entries at or near the leaves
80: of the tree will represent people, equipment or application processes.
81: .IP 3.
82: Read and search operations will dominate over modification operations.
83: .IP 4.
84: Temporary inconsistencies in the data are acceptable. This greatly
85: facilitates the replication of data in the Directory by obviating concerns
86: about record locking and atomic operations.
87: .NH 2
88: Directory Object Model
89: .LP
90: The Directory can be decomposed into objects as in figure 1.
91: .KF
92: .PS
93: arc at 1.307,9.134 from 1.800,9.637 to 1.863,8.700
94: ellipse at 2.200,9.200 wid 1.125 ht 1.125
95: ellipse at 4.638,8.363 wid 1.075 ht 1.075
96: ellipse at 5.888,9.262 wid 1.225 ht 1.225
97: ellipse at 3.925,9.488 wid 1.025 ht 1.025
98: line from 2.840,9.002 to 2.737,9.012 to 2.823,8.955
99: line from 2.737,9.012 to 4.112,8.512
100: line from 4.010,8.523 to 4.112,8.512 to 4.027,8.570
101: line from 5.166,8.788 to 5.112,8.700 to 5.201,8.753
102: line from 5.112,8.700 to 5.362,8.950
103: line from 5.309,8.862 to 5.362,8.950 to 5.274,8.897
104: line from 4.590,9.458 to 4.487,9.450 to 4.582,9.409
105: line from 4.487,9.450 to 5.237,9.325
106: line from 5.135,9.317 to 5.237,9.325 to 5.143,9.366
107: line from 2.831,9.367 to 2.737,9.325 to 2.840,9.318
108: line from 2.737,9.325 to 3.425,9.450
109: line from 3.331,9.408 to 3.425,9.450 to 3.322,9.457
110: line from 3.300,10.137 to 7.237,10.137 to 7.237,7.513 to 3.300,7.513 to 3.300,10.137
111: .ps 11
112: "The Directory" at 5.425,7.606 ljust
113: .ps 11
114: "Figure 1: Directory Object Model" at 2.300,6.918 ljust
115: .ps 11
116: "DSA 3" at 4.362,8.293 ljust
117: .ps 11
118: "DSA 2" at 5.612,9.231 ljust
119: .ps 11
120: "DSA 1" at 3.675,9.481 ljust
121: .ps 11
122: "DUA" at 1.988,9.168 ljust
123: .ps 11
124: "USER" at 0.863,9.106 ljust
125: .PE
126: .KE
127: .sp 2
128: .LP
129: A user accesses the Directory by means of a
130: .I
131: Directory User Agent
132: .R
133: (DUA).
134: The DUA communicates with the Directory by using
135: .I
136: Directory Access Protocol
137: .R
138: (DAP).
139: .PP
140: The Directory comprises a collection of
141: .I
142: Directory System Agents
143: .R
144: (DSAs). Each
145: DSA has an associated database which holds some portion of the global
146: database. The
147: DSAs cooperate to provide the Directory Service. The DSAs communicate with
148: each other by using
149: .I
150: Directory System Protocol
151: .R
152: (DSP).
153: .PP
154: The distributed operation of the Directory is implemented by using one or
155: more of the following modes of operation:
156: .IP
157: Chaining is where a DSA passes an operation onto a further DSA, awaits the
158: response, and passes it back to the initiating DUA.
159: .IP
160: Referral is where a DSA returns a reference to another DSA back to the
161: initiating DUA or DSA. This reference consists of the name of another DSA
162: which the operation might be passed to.
163: .IP
164: Multicasting is where a request is broadcast to several DSAs, which may
165: then collectively resolve the request.
166: .LP
167: The combination of these modes of operation used by the Quipu implementation
168: are discussed later.
169: .NH 2
170: Structure of the Directory
171: .LP
172: It was noted earlier that the Directory is organised
173: hierarchically in the form of
174: a tree. The Directory database is usually referred to as the
175: .I
176: Directory Information Tree
177: .R
178: (DIT).
179: .PP
180: The overall structure of the DIT is shown in figure 2.
181: .sp
182: .KF
183: .PS
184: line from 4.050,6.950 to 4.862,6.638
185: line from 4.760,6.650 to 4.862,6.638 to 4.778,6.697
186: line from 3.237,6.950 to 2.862,6.638
187: line from 2.923,6.721 to 2.862,6.638 to 2.955,6.682
188: line from 4.362,6.638 to 6.300,6.638 to 6.300,6.138 to 4.362,6.138 to 4.362,6.638
189: line from 1.613,6.638 to 3.612,6.638 to 3.612,6.138 to 1.613,6.138 to 1.613,6.638
190: line from 5.362,8.075 to 5.737,7.450
191: line from 5.665,7.523 to 5.737,7.450 to 5.707,7.549
192: line from 4.800,8.075 to 3.862,7.450
193: line from 3.932,7.526 to 3.862,7.450 to 3.960,7.485
194: line from 4.862,9.075 to 5.300,8.575
195: line from 5.215,8.634 to 5.300,8.575 to 5.253,8.667
196: line from 4.300,9.075 to 3.237,8.512
197: line from 3.314,8.581 to 3.237,8.512 to 3.338,8.537
198: line from 3.550,9.887 to 4.425,9.512
199: line from 4.323,9.529 to 4.425,9.512 to 4.343,9.575
200: line from 2.862,9.887 to 2.050,9.512
201: line from 2.130,9.577 to 2.050,9.512 to 2.151,9.532
202: line from 4.925,7.450 to 6.612,7.450 to 6.612,7.013 to 4.925,7.013 to 4.925,7.450
203: line from 2.737,7.450 to 4.300,7.450 to 4.300,6.950 to 2.737,6.950 to 2.737,7.450
204: line from 4.675,8.575 to 6.237,8.575 to 6.237,8.075 to 4.675,8.075 to 4.675,8.575
205: line from 2.175,8.512 to 3.675,8.512 to 3.675,8.075 to 2.175,8.075 to 2.175,8.512
206: line from 3.987,9.512 to 5.300,9.512 to 5.300,9.075 to 3.987,9.075 to 3.987,9.512
207: line from 1.300,9.512 to 2.550,9.512 to 2.550,9.075 to 1.300,9.075 to 1.300,9.512
208: line from 2.675,10.262 to 3.800,10.262 to 3.800,9.887 to 2.675,9.887 to 2.675,10.262
209: .ps 11
210: "OU=Computer Science" at 2.800,7.168 ljust
211: .ps 11
212: "University" at 2.487,8.168 ljust
213: .ps 11
214: "O=Nottingham" at 2.425,8.356 ljust
215: .ps 11
216: "OU=Physics" at 5.175,7.168 ljust
217: .ps 11
218: "College London" at 4.925,8.231 ljust
219: .ps 11
220: "O=University" at 4.987,8.418 ljust
221: .ps 11
222: "Figure 2: Hypothetical DIT" at 1.988,5.606 ljust
223: .ps 11
224: "CN=Colin Robbins" at 4.675,6.356 ljust
225: .ps 11
226: "CN=Paul Barker" at 1.925,6.356 ljust
227: .ps 11
228: "C=GB" at 4.300,9.293 ljust
229: .ps 11
230: "C=NL" at 1.488,9.293 ljust
231: .ps 11
232: "ROOT" at 2.925,10.043 ljust
233: .PE
234: .KE
235: .sp 2
236: The hypothetical
237: entries illustrate the hierarchy of the Directory and how entries are named
238: within the Directory. At each point in the Directory, entries are
239: differentiated by unambiguous
240: .I
241: Relative Distinguished Names
242: .R
243: (RDNs). Thus, in figure 2, "C=GB" and "C=NL" are RDNs under the root of the
244: DIT.
245: An entry's
246: .I
247: Distinguished Name
248: .R
249: is derived by concatenating all the RDNs of the entries from the root of the
250: tree to the entry itself.
251: .LP
252: Each entry may be further decomposed as shown in figure 3.
253: .KS
254: .PS
255: line from 5.237,7.700 to 6.112,7.200
256: line from 3.675,7.700 to 1.300,7.200
257: line from 3.800,9.262 to 5.487,8.575
258: line from 2.612,9.262 to 1.863,8.575
259: line from 5.050,6.950 to 5.987,6.950 to 5.987,6.325 to 5.050,6.325 to 5.050,6.950
260: line from 3.112,6.950 to 4.237,6.950 to 4.237,6.325 to 3.112,6.325 to 3.112,6.950
261: line from 1.488,6.950 to 2.800,6.950 to 2.800,6.325 to 1.488,6.325 to 1.488,6.950
262: line from 1.300,7.200 to 6.112,7.200 to 6.112,6.013 to 1.300,6.013 to 1.300,7.200
263: line from 3.675,8.262 to 5.237,8.262 to 5.237,7.700 to 3.675,7.700 to 3.675,8.262
264: line from 2.112,8.262 to 3.362,8.262 to 3.362,7.700 to 2.112,7.700 to 2.112,8.262
265: line from 1.863,8.575 to 5.487,8.575 to 5.487,7.450 to 1.863,7.450 to 1.863,8.575
266: line from 4.925,9.700 to 6.112,9.700 to 6.112,9.262 to 4.925,9.262 to 4.925,9.700
267: line from 2.612,9.700 to 3.800,9.700 to 3.800,9.262 to 2.612,9.262 to 2.612,9.700
268: line from 1.238,9.700 to 2.300,9.700 to 2.300,9.262 to 1.238,9.262 to 1.238,9.700
269: line from 0.988,10.012 to 6.237,10.012 to 6.237,9.012 to 0.988,9.012 to 0.988,10.012
270: .ps 11
271: "Figure 3: Structure of an entry" at 2.300,5.481 ljust
272: .ps 11
273: "Value" at 5.175,6.606 ljust
274: .ps 11
275: "Value" at 3.362,6.606 ljust
276: .ps 11
277: "Value" at 1.675,6.606 ljust
278: .ps 11
279: "Value(s)" at 3.925,7.918 ljust
280: .ps 11
281: "Type" at 2.300,7.918 ljust
282: .ps 11
283: "..." at 3.987,9.356 ljust
284: .ps 11
285: "Attribute" at 5.050,9.418 ljust
286: .ps 11
287: "Attribute" at 2.737,9.418 ljust
288: .ps 11
289: "Attribute" at 1.300,9.418 ljust
290: .PE
291: .KE
292: .sp 2
293: .PP
294: An entry comprises a set of attributes, which in turn consist of a type and
295: a value or set of values. It should be noted that an entry's distinguished
296: name is merely a special attribute type-value pair. For example, an entry
297: for a human being will have, inter alia, an attribute type
298: .I
299: Common Name.
300: .R
301: This attribute will often be multi-valued. The Common Name attribute for
302: Steve Kille's entry might take the values "Steve Kille", "Stephen E. Kille"
303: and "S. Kille" with "Steve Kille" being the distinguished value.
304: .NH 2
305: Accessing the Directory
306: .LP
307: A user makes use of the Directory by means of the
308: .I
309: Directory Abstract Service.
310: .R
311: The services provided are grouped into three
312: .I
313: ports,
314: .R
315: the read port, the search port and the modify port.
316: .PP
317: The read and search
318: ports provide querying facilities onto the Directory. It is possible to
319: read or compare an entry identified by its distinguished name. The powerful
320: search operation allows querying of entire sub-trees, returning specified
321: attributes for all entries which satisfy the criteria specified in the search
322: arguments. This allows entries to be identified by attributes other than
323: just the distinguished name and thus provides users with a highly flexible
324: mechanism for identifying entries and retrieving information
325: from the Directory.
326: .PP
327: Modification operations allow the addition and removal of
328: entries from the DIT, the amendment of entries and the renaming of entries.
329: .NH 2
330: Other aspects Of Directory Services
331: .LP
332: There are many aspects of the Directory Services standard which cannot be
333: described in detail. Such aspects include:
334: .IP \(bu
335: Access control
336: .IP \(bu
337: Authentication
338: .IP \(bu
339: Service controls
340: .IP \(bu
341: Schemas
342: .IP \(bu
343: Use of OSI
344: .sp 3
345: .NH
346: Distributed Operations in Quipu
347: .PP
348: The remainder of the paper focusses on the issue of distributed operations.
349: As the Directory is widely distributed,
350: .I
351: knowledge
352: .R
353: must be maintained of how the DIT is distributed amongst the collection of
354: DSAs which comprise the Directory. The standard does not specify how this
355: knowledge should be represented in the Directory.
356: The approach followed by Quipu is discussed.
357: .LP
358: It was noted earlier that the model allows for several modes of interaction
359: between DSAs as they cooperate to service requests made by DUAs; namely
360: chaining, referral and multicasting. The approach used by Quipu is discussed,
361: with particular reference to the problem of coping with the situation where
362: the DIT is fragmented into DSAs on disjoint networks.
363: .NH 2
364: Directory Service requests requiring distributed operation
365: .LP
366: When considering the effects of directory distribution, there are four
367: possible results which can result from a request being presented by a DUA to
368: the DSA at the directory access point.
369: .IP i)
370: The request may be satisfied locally.
371: .IP ii)
372: The "local" DSA may be able to determine that the request cannot be serviced
373: by any DSA. The directory knowledge indicates that the entry required would
374: be held in that DSA if such an entry existed. In this case the DSA would
375: return a
376: .I
377: name error
378: .R
379: to the DUA.
380: .IP iii)
381: A request is made to the local DSA which requires navigating down to
382: a sub-tree not
383: held locally. A set of references is acquired
384: indicating other DSAs which might be able to
385: satisfy the request.
386: .IP iv)
387: A request is made which requires navigating to a higher point in the tree
388: than that held locally. The addresses of DSAs nearer the root must be found
389: from local tables.
390: .LP
391: The rest of the paper discusses how Quipu proceeds in cases iii and iv above.
392: .NH 2
393: Representing directory knowledge
394: .LP
395: Case iii above requires the existence of knowledge information. This is
396: information which a DSA has about which entries it holds and how to locate
397: other entries in the Directory.
398: The standard does not specify how or where this knowledge is stored.
399: Quipu takes the approach that the OSI Directory itself should be used, and
400: stores the knowledge in the DIT.
401: .PP
402: The first step in storing the knowledge is to give every DSA in the
403: directory an entry in the DIT which contains information about the DSA.
404: For example
405: the DSA holding the data for University College London has the
406: distinguished name "(Country=GB, CommonName=Vicuna)", and has the following attributes:-
407: .DS
408: presentationAddress= Internet=128.16.8.50+50987 | X121=23421920030045
409: description= A wild animal of the Alpacca family,
410: description= DSA running on vs1 holding full UCL bit of tree.
411: supportedApplicationContext= x500DAP & x500DSP & QuipuDSP
412: CommonName= Vicuna
413: objectClass= quipuDSA & dSA & applicationEntity & top
414: .DE
415: The first thing to notice is the name. It is a Quipu convention that all
416: Quipu DSAs are named after endangered South American wildlife. Quipu was
417: originally developed under the aegis of the ESPRIT project, INCA.
418: .LP
419: The above entry enables a DSA to determine the address or addresses of other
420: DSAs.
421: However, a DSA still needs to determine which DSA to
422: contact to answer a particular request. Quipu DSAs achieves this by requiring
423: that every non-leaf object
424: has a "masterDSA" attribute, the value of which is the DN of the DSA to
425: contact.
426: It is important to note that Quipu makes an important simplification of the
427: model in this respect. It is assumed that if an entry is held in a DSA,
428: then all sibling entries are held in that DSA. This assumption allows for a
429: relatively straightforward replication mechanism based on Quipu's getedb
430: mechanism. This is discussed in [1].
431: .PP
432: In addition, Quipu has added the concept of
433: .I
434: slave
435: .R
436: DSAs to the model.
437: These are DSAs which hold a shadow copy of some data, and are prepared
438: to answer requests regarding that data.
439: Thus a non-leaf entry may have "slaveDSA" attributes which give the DNs of
440: DSAs that hold such data.
441: .RS
442: .B
443: .sp
444: A Caveat on naming DSAs
445: .R
446: .LP
447: Using this approach, care must be taken to name the DSAs high enough in the
448: DIT to prevent looping.
449: For example consider a DSA holding the subtree for "(Country=GB, Organisation=University
450: College London)" which is named
451: "(Country=GB, Organisation=University College London, CommonName=Vicuna)".
452: If an operation attempted to list the subordinates of "(Country=GB, Organisation=University
453: College London)", a referral would have to be made to the DSA
454: "(Country=GB, Organisation=University College London, CommonName=Vicuna)". This would require the
455: entry "(Country=GB, Organisation=University College London, CommonName=Vicuna)" to be read by the DSA.
456: To read this entry, the DSA would have to know how to navigate to
457: "(Country=GB, Organisation=University College London)" -- but does not know how to do that,
458: without seeing the "(Country=GB, Organisation=University College London, CommonName=Vicuna)"
459: entry!
460: Thus a (detectable) loop has been created.
461: To avoid this, DSAs should be named at the same level, or higher, in the DIT as
462: the entries they are holding.
463: This has the effect that there are lots of DSAs named at the higher
464: levels of the DIT.
465: .RE
466: .LP
467: When an operation cannot be satisfied locally,
468: a list of DSAs which either master or shadow the information will be
469: generated by looking at these attributes.
470: We will now consider how Quipu chooses DSAs from this list to resolve
471: the request.
472: .NH 2
473: DSA selection criteria
474: .LP
475: It will be seen that randomly selecting a DSA from a list of possible DSAs
476: is not an optimal strategy. The reasons for this are discussed below.
477: Quipu uses a number of criteria when establishing which DSA it will forward
478: a request to. Rather than picking a single "best" DSA, Quipu sorts the list
479: of DSAs into an order of preference.
480: A simple insert sort algorithm is used which successively compares pairs
481: of DSAs to see which is the "best".
482: .PP
483: It is worth noting here the reason why Quipu sorts the list of DSAs rather
484: than merely selecting the best DSA. As will be explained in some detail
485: shortly, a Quipu DSA is able to make some assumptions about another
486: DSA's behaviour if it knows that it is a Quipu DSA. The semantics of X.500
487: dictate that a subordinate reference contains a single DSA
488: if a request cannot be
489: satisfied at a given DSA. However, the syntax of X.500 allows more than one
490: DSA
491: to be named in a continuation reference. Quipu sometimes takes advantage
492: of this when communicating with other Quipu DSAs, by passing a
493: .I
494: Quipu-Specific Subordinate Reference
495: .R
496: (QSSR) which references multiple DSAs. QSSRs cannot always be used
497: as some requests, for example
498: modification operations, and operations which specify the "don't use copy"
499: service control, must be directed at the sole master DSA. In these cases a
500: standard subordinate reference is used.
501: .PP
502: This section discusses the criteria
503: which are used. The order of discussion indicates the weight given
504: to the criteria. The less important criteria are only used if no preference
505: can be deduced from the more important.
506: .NH 3
507: DAP only DSAs
508: .LP
509: DSAs which do not support DSP impose referral mode when other
510: considerations might tend to favour chaining. This restriveness means that
511: such DSAs are not favoured and any such DSAs
512: are placed at the bottom of the sorted DSAs list.
513: .NH 3
514: Prefer a Quipu DSA
515: .LP
516: The first choice it to select a Quipu DSA.
517: The main reason for this is that the DSAs can then talk over their own
518: application context (rather than the standard X500 DSP context), which
519: allows them to make a few simplifying assumptions, e.g. QSSRs (although
520: the protocol used is the same).
521: .LP
522: This is represented in the Directory by a DSA having the attribute type
523: .I
524: Supported Application Context
525: .R
526: with a value "quipuApplicationContext".
527: .NH 3
528: Prefer a reliable DSA
529: .LP
530: Experience with Quipu-5.0 in which a DSA was chosen effectively at random
531: (but for the same query the same "random" DSA would be picked!)
532: showed that the network connections to some DSAs were much more unreliable
533: than others.
534: As a result, a lot of time was spent attempting associations that were almost
535: certain to fail.
536: Thus a mechanism has been introduced which attempts to identify reliable
537: DSAs.
538: .LP
539: To make this choice
540: every DSA holds the following information on each other DSA it tries to
541: contact:
542: .IP \(bu
543: Distinguished name of DSA
544: .IP \(bu
545: Time of last attempt
546: .IP \(bu
547: Time of last success
548: .IP \(bu
549: No. of failures since last success
550: .LP
551: Every time an association is attempted to a DSA, its DSAInfo is found, and
552: the
553: .I
554: lastAttempt
555: .R
556: field is set to the current time.
557: If the association succeeds
558: .I
559: lastSuccess
560: .R
561: is set to the current time, and
562: .I
563: failures-since-last-success
564: .R
565: is set to zero.
566: If the association fails
567: .I
568: failures-since-last-success
569: .R
570: is incremented.
571: .LP
572: The notion of
573: .I
574: recent
575: .R
576: success or failure is used to decide which DSA to prefer. "Recent" is in
577: practice the value of the tailorable variable selected to age the cache of
578: connectivity information. It is not at present clear what the optimum
579: timeout period is for aging this information. This area requires further
580: experimentation.
581: .LP
582: The following algorithm is then used to select the more reliable DSA.
583: .LP
584: If both DSAs have been accessed successfully recently, prefer a DSA which
585: has suffered no recent communication failures.
586: If either communication with both DSAs has failed recently, or neither DSA
587: has a record of failure, then some other DSA selection criterion must be
588: used. No attempt is made to discriminate between DSAs on the basis of how
589: recently the successes or failures occurred.
590: .LP
591: If only one of the DSAs has been successfully contacted recently, prefer
592: that DSA unless it also has a record of recent failure. In the case of a
593: recent failure, prefer the other DSA, unless it also failed recently in
594: which case no discrimination can be made.
595: .LP
596: If neither DSA has been contacted successfully recently, some other
597: criterion must be used to choose between the DSAs.
598: .NH 3
599: Prefer a close DSA
600: .LP
601: A close DSA may be preferable for a number of reasons.
602: Network charges may be lower, or non-existent, for proximate DSAs.
603: Physically close DSAs may often be connected by networks offering greater
604: bandwidth. Physically close DSAs may be separated by fewer gateways than
605: DSAs separated by great distances.
606: .LP
607: The following sections suggest 3 ways a
608: .I
609: close
610: .R
611: DSA may be selected.
612: .sp
613: .LP
614: Clearly it is preferable to choose a DSA on the same local area network,
615: or using
616: the preferred network type if possible.
617: To make this decision, we need a method of addressing DSAs on different
618: networks, that is:
619: .IP i)
620: compatible with the standard, that is it can be stored in the "presentation
621: address" attribute of a DSA;
622: .IP ii)
623: can supply sub network details.
624: .LP
625: OSI purists may well be alarmed at this point. Network layer details should
626: be hidden from applications. NSAPs should not contain routing information.
627: .LP
628: However, at present, real users do not use OSI network services. Network
629: services are currently provided largely by TCP/IP and X.25 (1980) networks.
630: These network domains are themselves not fully connected. TCP/IP is often
631: used on LANs which are not connected to the Internet. X.25 domains exist,
632: such as the U.K.'s JANET, which are not fully connected to the international
633: X.25 networks.
634: .PP
635: Until OSI network services are available to and used by almost all users, a
636: work-around solution is required. Kille [5] has defined a mapping between
637: the various network address spaces and OSI presentation addresses. This
638: uses a part of the Telex address space to hold the encoded addresses.
639: .sp
640: .LP
641: Every DSA has a distinguished name and this can be used to select a potentially
642: close DSA.
643: For example, if our DSA is called "Country=GB, Organisation=University
644: College London, CommonName=Tamarin", and
645: we have a references to DSAs "Country=US, CommonName=Fruit Bat", and "Country=GB, CommonName=Vicuna",
646: then on the basis of distinguished names, "Country=GB, CommonName=Vicuna" is
647: .I
648: likely
649: .R
650: to be closer.
651: .sp
652: .LP
653: DSAs may be managed in Directory Management Domains (DMD) for accounting
654: purposes. If a DSA is in the same DMD as the requestor, then if may be best
655: to use this DSA in preference to a DSA in a different domain.
656: .LP
657: Quipu does not currently use this as a selector, as the concept of DMD has
658: not been utilised fully in current pilot exercises, thus the selector would
659: always return "no difference" when comparing two DSAs.
660: .NH 3
661: Need for experimentation
662: .LP
663: How successful this algorithm is in practice remains to be seen.
664: Quipu-6.0, which attempts to make the above decisions, is about to
665: be released.
666: However successful the algorithm proves to be, one may be fairly confident
667: that the method is better that a random selection.
668: .NH 2
669: Chaining, referrals, multicasting
670: .LP
671: Having decided which DSA or DSAs to contact to follow references, the
672: decision of which intercation model to use still has to be made. This is
673: now considered.
674: .PP
675: Quipu has a basic framework for interaction between DUA and DSA, and between
676: two DSAs. We will see later that are several situations which force
677: departure from this model.
678: .LP
679: The basic model is as follows:
680: .IP
681: If the first DSA contacted cannot satisfy a request, it chains that request
682: on to a second DSA. If the second DSA cannot satisfy the request it sends a
683: referral back to the initial DSA which then chains the request to the
684: referenced
685: DSA. From the viewpoint of the DUA, the model is one of chaining. From the
686: viewpoint of the first DSA, the model is one of referral.
687: .sp
688: .LP
689: The advantages of this model are as follows:
690: .IP i)
691: The work of the DUA is simplified by placing a heavy onus on the DSA at
692: the DUA's access point. All references are
693: followed by the DSA. The DUA only needs a single access point onto the
694: Directory.
695: .IP ii)
696: A corollary of the access point DSA shouldering the burden of chasing
697: referrals is that the DSA is able to cache all the information that it
698: acquires from other DSAs. Caching can dramatically improve performance for
699: all the DUAs and DSAs which communicate with that DSA. Obviously care needs
700: to be exercised as the cache ages and caches have to be purged periodically.
701: Great care also needs to be taken that access control mechanisms are not
702: circumvented by the use of caching.
703: .IP iii)
704: The DUA only needs to be on the same network as its access point DSA. Full
705: connectivity with the Directory can be achieved so long as that DSA can
706: contact other DSAs by chaining or referral. It should be noted that this
707: problem can be circumvented by the use of transport service bridges.
708: .IP iv)
709: The model is a good basis for a charging policy.
710: The best model for charging would be one of DUA referral where all charges
711: could be assigned to the originating DUAs. For reasons already discussed
712: this is not the best model for a variety of other reasons. The DSA referral
713: model provides a reasonable, second best approach.
714: All DUA requests which
715: generate requests across wide area, chargeable networks, are initiated by a
716: single DSA which represents the DUA. It is clearly very difficult to
717: administer a charging policy for any model which allows for a
718: substantial amount of chaining.
719: To cope with this problem, Quipu in fact allows a DSA to "defend" itself
720: against chaining requests by setting a "dsp_chaining" variable to "off".
721: .IP v)
722: The DSA referral model allows more control over an operation and may be
723: beneficial if some DSAs are not highly reliable. Under the chaining model,
724: if knowledge is fairly minimal, unreliable DSAs may cause part of the DIT to
725: become detached and unreachable. Under the DSA referral model, a local
726: Directory administrator can try and guard against this by ensuring that
727: considerable knowledge is held locally.
728: .LP
729: It should be noted that the above model cannot always be adhered to. The
730: following reasons all require a different approach.
731: .IP
732: Service controls might, for example, be set such that chaining is prohibited
733: whereas the model indicates that a DSA should chain.
734: .IP
735: Some DSA implementations only support DAP although supporting DSP is a
736: requirement of the standard. If such DSAs are referenced when a request
737: cannot be satisfied locally, the request can only be pursued further
738: by DUA referral.
739: .IP
740: It is a fact of life, as noted earlier, that DSAs will
741: be run on disjoint networks. Ensuring that the Directory does not itself
742: become disjointed requires cognisance of the underlying networks when
743: assessing whether to chain or refer a directory request.
744: .IP
745: A basic assumption of the model is that DSAs should trust each other.
746: However, such trust can in practice only be based on DSAs being able to
747: authenticate each other. Quipu does not currently use authentication
748: between DSAs for the following reasons: simple authentication is regarded as
749: being too simple to forge to be worthwhile; strong authentication is
750: time-consuming and requires a framework to manage the requisite certificates.
751: However, the performance of the encryption algorithms has been considerably
752: improved of late and strong authentication is being actively considered for
753: the next release of Quipu.
754: For this reason, Quipu will not perform modification
755: operations over DSP. Thus DSAs must send referrals back to a DUA, whatever
756: the model suggests is the preferred mode of interaction.
757: .NH 2
758: Chaining preferred
759: .LP
760: If the above model indicates that chaining is preferred, the following
761: algorithm is then used to finally select a DSA to contact:
762: .IP
763: The ordered list of DSAs is searched to see if there is a connection already
764: open to any of the DSAs. If there is, the request is forwarded to the first
765: such DSA on the list.
766: .IP
767: If the DSA does not have a connection open to any of the DSAs in the list,
768: the DSA tries to open a connection to each DSA in turn until a connection
769: attempt is successful.
770: .IP
771: If all connection attempts fail, the DSA then tries to send a referral. The
772: DSA attempts to select the first DSA in the list which appears to be on a
773: compatible network.
774: .IP
775: If none of the DSAs in the list appear to be on a compatible network, a
776: referral is sent back which names the first DSA in the list.
777: .NH 2
778: Referral preferred
779: .LP
780: If the model indicates that referral is preferred, the following procedure
781: is used. It should be noted that the network compatibility testing is
782: crucial in creating a widely distributed Directory spread over
783: heterogeneous networks.
784: .IP
785: The DSA searched the list for any DSA with apparent network compatibility
786: with the calling DUA or DSA.
787: .IP
788: If any DSA is found which appears to be on compatible network, then if
789: the initiating DSA is a Quipu DSA, the list of references are returned
790: to that DSA. If the initiator is not a Quipu DSA, then only the single,
791: "network compatible" reference is returned. If the initiating DSA is a Quipu
792: DSA and receives a list of DSAs, the procedure described earlier to sort the
793: DSAs into an order of preference, is followed. The initiating DSA must
794: discard any earlier lists of DSAs it had compiled or received earlier while
795: trying to
796: complete the operation, on receipt of a further list of references.
797: .IP
798: If no DSA in the list appears to on a network compatible with the
799: originator, then an attempt is made to chain the operation, service controls
800: permitting. If chaining fails, a referral is sent to the originating DSA.
801: .NH 2
802: Multicasting
803: .LP
804: In general, Quipu does not need to multicast because of the assumption that all
805: sibling entries are held within a single DSA.
806: However there are two occasions when Quipu makes use of multicasting.
807: .IP i)
808: Subtree searches, where the subtree is held in multiple DSAs.
809: .IP ii)
810: When following a non-specific subordinate references, generated by non-Quipu
811: DSAs.
812: .NH
813: Conclusions
814: .LP
815: The approach used by Quipu to store OSI Directory knowledge has been described.
816: It seems prudent that this information should be stored in the Directory
817: itself.
818: .PP
819: The Directory is distributed across a large number of DSAs. These DSAs may
820: reside on disjoint networks. The approach taken by Quipu to solve this
821: problem has been discussed.
822: .PP
823: Some replication of the Directory will tend to improve the Directory's
824: resilience to DSA failure and may also improve performance generally. The
825: mechanisms used by Quipu to determine which
826: DSA to forward requests to has been described.
827: .PP
828: Some differences between the standard X.500 model and the Quipu
829: implementation have been noted. Quipu takes account of DSAs being
830: situated on disjoint networks. Furthermore, Quipu tries to provide a robust
831: and efficient service by noting DSA reliability, connectivity and proximity.
832: .sp 3
833: .br
834: .B
835: References
836: .R
837: .IP [1]
838: "The design of Quipu", Stephen E. Kille, Research Note RN/89/19, Department
839: of Computer Science, University College London, March 1989.
840: .IP [2]
841: "The QUIPU Directory Service", Stephen E. Kille, IFIP WG 6.5 Conference on
842: Message Handling Systems and Distributed Applications, pp173-186. North
843: Holland Publishing, October 1988.
844: .IP [3]
845: "The ISO Development Environment Users's Manual (Version 5.0)",
846: Marshall T. Rose, The Wollongong Group, Palo Alto, March 1989.
847: .IP [4]
848: "The Directory - Overview of Concepts, Models and Services", X.500 and ISO
849: 9594, 1988.
850: .IP [5]
851: "An interim approach to the use of network addresses", Stephen E. Kille,
852: Research Note RN/89/19, Department of Computer Science,
853: University College London, March 1989.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.