![[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.