home *** CD-ROM | disk | FTP | other *** search
/ ftp.umcs.maine.edu / 2015-02-07.ftp.umcs.maine.edu.tar / ftp.umcs.maine.edu / pub / WISR / wisr6 / proceedings / ascii / omalley.ascii < prev    next >
Text File  |  1993-10-19  |  11KB  |  246 lines
  1.  
  2.  
  3.  
  4.  
  5.       Action  at  a  Distance:  A  Case  Study  in  Composability
  6.  
  7.  
  8.  
  9.                                            Sean W. O'Malley
  10.  
  11.  
  12.  
  13.                                  Department of Computer Science
  14.  
  15.                                          University of Arizona
  16.  
  17.                                             Tucson, AZ 85721
  18.  
  19.                                            Tel:  (602) 621-6613
  20.  
  21.                                      Email: sean@cs.arizona.edu
  22.  
  23.  
  24.  
  25.                                                   Abstract
  26.  
  27.  
  28.     We believe that the key to software reuse is the ability to arbitrarily compose a library of
  29. single purpose modules into large systems.  Over the last five years we have createdsuch a
  30. system (the x-kernel) which supports the arbitrary composition of protocols into large proto-
  31. col graphs.  We have designed a number of communications systems which extensively reused
  32. protocol modules and have constructed numerous small protocol modules which were designed
  33. from scratch to be reusable. This paper attempts to give some insight as to how such protocols
  34. are produced and the problems that can interfere with composition.
  35.  
  36.  
  37. Keywords: module compostion, reuse pragmantics, reuse experience
  38.  
  39.  
  40. Workshop Goals: The integrating of reuse theory and practice.
  41.  
  42.  
  43. Working Groups: domain analysis, tools and environments, reuse and object oriented methods
  44.  
  45.  
  46.  
  47.                                                 O'Malley- 1
  48.  
  49.  
  50. 1      Introduction
  51.  
  52.  
  53.  
  54. The x-kernel[1] supports a model of software reuse where collections of small single purpose com-
  55. munications protocols can be arbitrarily composed into novelcommunications systems.  Acommu-
  56. nications system is represented as a directed acyclic graph of proto colob jects. The edges of the
  57. graph explicitly define the uses and depends upon relationships between protocol objects. Objects
  58. may be multiply instantiated.
  59.  
  60.  
  61. As our approach to modular protocol reuse has evolved there has b een aconstant problem with how
  62. to support interaction between two proto cols arbitrarily separated in a DAG. We have called this
  63. the problem of action at a distance. Action at a distance is basically caused by protocol interactions
  64. which cannot be represented in our graphical notation. These iterations can radically reduce the
  65. potential composability of a collection of protocols and hence seriously inhibit reuse.  In the worst
  66. case one ends up with a collection of protocols which can only be composed in one specific way.
  67. While our own experience with action at a distance is with communications protocols, we suspect
  68. that this is a common problem with reuse systems based upon arbitrary composition.
  69.  
  70.  
  71. Action at a distance is commonly found when decomposing a monolithic protocol implementation
  72. into a collection of single purpose micro-protocols.  For those proto cols to b e truly reusable,  all
  73. action at a distance problems must be resolved in the most general way possible.  If no such solution
  74. is found every change in the protocol graph will require code modification in theindividual protocols.
  75. In this paper I will describe the action at a distance problems encountered while developing a set
  76. of modular RPC protocol components and describe several attempts to resolve theseproblems.
  77.  
  78.  
  79.  
  80. 2      Sprite  RPC  and  xSprite
  81.  
  82.  
  83.  
  84. The protocols described here are a result of decomposing the Sprite RPC protocol developed at
  85. Berkeley. A description of the basic Sprite RPC protocol can be found in [2].  Sprite RPC imple-
  86. ments the basic Birrell-Nelson[3] remote procedure call protocol. A partial and simplified pictorial
  87. representation of our modular implementation of Sprite RPC (xSprite)is given in Figure 1.  This
  88. graph provides a super-set of the semantics found in Sprite RPC but cannot interoperate with Sprite
  89. RPC. xSprite differs from Sprite RPC in that it can be used over the Internet and it supports very
  90. large messages. More complete descriptions of xSprite can be found in [4 ][5 ].
  91.  
  92.  
  93.  
  94.                                       Figure 1:  The xSprite Protocol Graph
  95.  
  96.  
  97. xSprite consists of the following protocols CHAN, BLAST, VSIZE, and VMUX. xSprite uses the
  98. Ethernet and the standard Internet protocol suite to deliverpackets.  CHANimplements the basic
  99. Birrell-Nelson RPC mechanism.  BLAST implements an optimistic blast algorithm to send large
  100. messages between hosts connected via a LAN. VSIZE dynamically selects a transport subgraph
  101. based upon the size of the outgoing message. VMUX statically selects a transport subgraph based
  102. on the address of the target machine. If the target machine is reachable on the local net the Internet
  103. protocols are bypassed. This graph uses the Ethernet (ETH) to send short packets locally, BLAST
  104.  
  105.  
  106.  
  107.                                                        O'Malley- 2
  108.  
  109.  
  110. to send medium packets locally,  TCP to send very large packets locally, IP to send short packets
  111. across the Internet, and TCP to send large packets over the Internet.  The protocol graphs under
  112. all the transport protocols are ignored for simplicity.
  113.  
  114.  
  115.  
  116. 3      Action  at  a  Distance  Problems
  117.  
  118.  
  119.  
  120. This decomposition of Sprite RPC created at least two action at a distance problems.  First, for
  121. xSprite to implement the same semantics as SpriteRPC, BLAST  cannot positively acknowledge
  122. the arrival of all the fragments of a large message.  Thus the client BLAST does not know when to
  123. delete the fragments that were sent tothe server.  However since CHAN will get an acknowledgment
  124. for every RPC, it does know when BLAST can free its fragments.  The question is how to get that
  125. information where it needs to go.  The second action at a distance problem arises from the fact
  126. that ETH, IP, and BLAST are unreliableproto cols but TCP is reliable.  For both performance and
  127. correctness reasons CHAN should not retransmit the body of a message when it is usinga reliable
  128. transport protocol.
  129.  
  130.  
  131.  
  132. 4      Solutions
  133.  
  134.  
  135.  
  136. Originally we attempted to solve the first problemas follows.  When a message is sent, BLAST
  137. would  return  a  ticket  to  CHAN which  would  uniquely  identify  the  storage  associated  with  that
  138. message.  BLAST supported a free resources operation which would free the message fragments
  139. associated with a valid ticket. When CHAN received an acknowledgment for a message it would
  140. invoke the BLAST free resource operation with the ticket. Unfortunately the only hint that CHAN
  141. had about the location of the BLAST protocol was that it was lo cated b elow CHAN in the protocol
  142. graph. Thus the free resources control operation had to be inherited up the protocol graph. This
  143. is expensive and unfortunately will not work if there are two instances of BLAST configured below
  144. CHAN.
  145.  
  146.  
  147. What is required is for some form of temporary communications link be set up between  CHAN
  148. and whatever lower level proto col was used to send the current message.  Hence the path of the
  149. message in question determines which lower level protocol needs to communicate with CHAN. Given
  150. that in the x-kernel messages traversethe graph using a series of successive xPush operations, the
  151. transport  protocol  could  return  any  required  information  to  CHAN as  the  return  value  for the
  152. xPush operation.
  153.  
  154.  
  155. CHAN requires three pieces of information to resolve its actionat a distance problems:  an object
  156. pointer  to  the  transport  protocol  it  should  invoke  a free  resource  operation  on,  a  ticket which
  157. allows the transport protocol to uniquely identify the message in question,  and a reliability flag.
  158. By default CHAN assumes that there is no need to free resources and the underlying proto col is
  159. unreliable. Thus in the graph, ETH and IP do not have to return any information. BLAST must
  160. return a pointer to itself and a ticket. TCP need only return the information that it is reliable.
  161.  
  162.  
  163.  
  164.                                                        O'Malley- 3
  165.  
  166.  
  167. 5      Recursion
  168.  
  169.  
  170.  
  171. While the x-kernel does not support cyclic protocol graphs there are instances of static recursion, for
  172. example composing an instance of the protocol BLAST on top of another instance of the protocol
  173. BLAST. This composition results in a protocol graph which can handle much larger messages than
  174. BLAST itself.  Unfortunately as defined above there is no way for CHAN to free the resources of
  175. the lower level BLAST protocol. Hence BLAST must support the chaining of CHAN information
  176. requests.  If BLAST  receives a transport protocol and a ticket as the return value from one of its
  177. xPush calls it must save that information and p erform a free resources operation on each saved
  178. transport protocol when CHAN performs a free resources operation on it. In addition since CHAN
  179. is a reliable transport protocol its xPush operation must return this information.
  180.  
  181.  
  182.  
  183. 6      Conclusions
  184.  
  185.  
  186.  
  187. In any reuse system based upon the free composition of software  components maintaining com-
  188. posability is a constant concern.  The temptation toresolve action at a distance problems in an
  189. ad-hoc fashion inevitably leads to a reduction in the composability of the systemas a whole.  We
  190. have identified in the x-kernel a case where the communications required is defined by the subgraph
  191. traversed by a specific message rather than a static proto col graph.  By treating this as a general
  192. problem a solution was derived which should restore arbitrary composition to a collection of impor-
  193. tant protocols.  While every effort was made to insure generality the information exchanged may
  194. still be too CHAN specific.  This approach should be tried on other protocol graphs.  Work is also
  195. needed to come up a semantically cleaner way to implement these interactions.
  196.  
  197.  
  198.  
  199. 7      References
  200.  
  201.  
  202.  
  203. References
  204.  
  205.  
  206.  
  207. [1]  N. C. Hutchinson and L. L. Peterson, "The x-kernel: An architecture for implementing network
  208.      protocols," IEEE Transactions on Software Engineering, vol. 17, pp. 64-76, Jan. 1991.
  209.  
  210.  
  211. [2]  B. B. Welch, "The Sprite remote procedure call system," Tech. Rep. UCB/CSD  86/302, Uni-
  212.      versity of California Berkeley, Berkeley, Calif., June 1988.
  213.  
  214.  
  215. [3]  A. Birrell andB. Nelson, "Implementing remote procedure calls," ACM Transactions on Com-
  216.      puter Systems, vol. 2, pp. 39-59, Feb. 1984.
  217.  
  218.  
  219. [4]  N. C. Hutchinson,  L. L. Peterson, M. Abbott, and S. O'Malley, "RPC in the x-Kernel: Eval-
  220.      uating new design techniques,"  in Proceedings  of  the  Twelfth  ACM  Symposium  on  Operating
  221.      System Principles, pp.91-101, Dec. 1989.
  222.  
  223.  
  224. [5]  S. W. O'Malleyand L. L. Peterson, "A dynamic network architecture," ACM Transactions on
  225.      Computer Systems, vol. 10, pp. 110-143, May 1992.
  226.  
  227.  
  228.  
  229.                                                        O'Malley- 4
  230.  
  231.  
  232. 8      Biography
  233.  
  234.  
  235.  
  236. Sean W. O'Malley is an Assistant Research Scientist in the Department of Computer Science at
  237. the University of Arizona. He has been working on the x-kernel,a modular architecture for protocol
  238. development.  He leads an effort in the development of a suite of modular and reusable security
  239. protocols. His work is funded by ARPAand the National Computer Security Center. Before that he
  240. was an Assistant Professor of Computer Science atthe University of Texas at Austin. He received
  241. a Ph.D. in Computer Science from the University ofArizona in 1991.
  242.  
  243.  
  244.  
  245.                                                        O'Malley- 5
  246.