Return to duug.tex CVS log

Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / doc / duug

Annotation of 43BSDReno/contrib/isode-beta/doc/duug/duug.tex, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.