home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_s_z / draft-vinod-carp-v1-02.txt < prev    next >
Text File  |  1997-10-20  |  13KB  |  391 lines
  1.  
  2.  
  3. INTERNET-DRAFT                                      Vinod Valloppillil
  4. <draft-vinod-carp-v1-02.txt>                     Microsoft Corporation
  5.                                                          Keith W. Ross
  6.                                             University of Pennsylvania
  7.                                                        20 October 1997
  8.                                                     Expires April 1998
  9.  
  10.  
  11.         Cache Array Routing Protocol v1.0
  12.  
  13. Status of this Memo
  14.  
  15.  This document is an Internet-Draft.  Internet-Drafts are working
  16.  documents of the Internet Engineering Task Force (IETF), its areas,
  17.  and its working groups.  Note that other groups may also distribute
  18.  working documents as Internet-Drafts.
  19.  
  20.  Internet-Drafts are draft documents valid for a maximum of six months
  21.  and may be updated, replaced, or obsoleted by other documents at any
  22.  time.  It is inappropriate to use Internet-Drafts as reference
  23.  material or to cite them other than as ``work in progress.''
  24.  
  25.  To learn the current status of any Internet-Draft, please check the
  26.  ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
  27.  Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
  28.  munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
  29.  ftp.isi.edu (US West Coast).
  30.  
  31. Abstract
  32.  
  33.   This draft documents the Cache Array Routing Protocol (CARP) v1.0
  34.   for dividing URL-space among an array of loosely coupled proxy 
  35.   servers.
  36.  
  37.   An HTTP client agent (either a proxy server or a client browser)
  38.   which implements CARP v1.0 can allocate and intelligently route
  39.   requests for the correct URLs to any member of the Proxy
  40.   Array.  Due to the resulting sorting of requests through these 
  41.   proxies, duplication of cache contents is eliminated and global
  42.   cache hit rates are improved.
  43.  
  44. Valloppillil                                           [Page 1]
  45.  
  46. INTERNET-DRAFT   Cache Array Routing Protocol v1.0    30 June 1997
  47.  
  48. Table of Contents
  49.  
  50.   1.  Overview........................................ 2
  51.   2.  Proxy Array Membership Table.................... 3
  52.       2.1  Global Information......................... 3
  53.       2.2  Member Information......................... 4
  54.   3.  Routing Function................................ 5
  55.       3.1  Hash Function.............................. 5
  56.       3.2  Hash Combination........................... 6
  57.       3.3  Load Factor................................ 6
  58.       3.4  Route Selection............................ 7
  59.       3.5  Member Failure Routing..................... 7
  60.   4.  Client-Side Implementation...................... 7 
  61.   5.  Versioning...................................... 7
  62.   6.  Security Considerations......................... 7
  63.   7.  Open Issues..................................... 7
  64.   8.  Acknowledgements................................ 7
  65.   9.  References...................................... 8
  66.   10. Author's Information............................ 8
  67.  
  68. Valloppillil                                           [Page 2]
  69.  
  70. INTERNET-DRAFT   Cache Array Routing Protocol v1.0    30 June 1997
  71.  
  72. 1. Overview
  73.  
  74.   The Cache Array Routing Protocol describes a distributed caching 
  75.   protocol based on
  76.  
  77.     1) a known membership list of loosely coupled proxies and
  78.     2) a hash function for dividing URL space among those proxies
  79.  
  80.   The Proxy Array Membership Table is defined as a plain ASCII text
  81.   file retrieved from an Array Configuration URL.  This document does
  82.   NOT describe how this table is constructed, merely the format of
  83.   the fields used by agents implementing.
  84.  
  85.   The hash function plus routing algorithm defined in this document 
  86.   take member proxies described in the Proxy Array Membership Table 
  87.   and make an on-the-fly determination as to which Proxy Array member 
  88.   should be the proper receptacle for a cached version of a resource 
  89.   keyed by URL.
  90.  
  91.   Downstream agents may then access the cached resource by forwarding
  92.   the proxied HTTP request [5] for that resource to the appropriate 
  93.   member of the Proxy Array.
  94.  
  95. Valloppillil                                           [Page 3]
  96.  
  97. INTERNET-DRAFT   Cache Array Routing Protocol v1.0        30 June 1997
  98.  
  99. 2. Proxy Array Membership Table
  100.  
  101.   The Proxy Array Membership Table is a plain-text ASCII file which
  102.   can be published from a URL.
  103.  
  104.   The format of the table is:
  105.  
  106.   Proxy Array Information/<Version number>
  107.   ArrayEnabled:  <0 | 1>
  108.   ConfigID:  <opaque string>
  109.   ArrayName:  <opaque string>
  110.   ListTTL:  <minutes until next check>
  111.  
  112.   <name> <IP addr> <listening port> <table URL> <agent str> 
  113.   <statetime> <status UP | DOWN> <load factor> <cache size>
  114.  
  115. 2.1 Global Information
  116.  
  117.   These are fields that describe the array itself and are not specific
  118.   to any one member of an array
  119.  
  120.   Global information is terminated in the Proxy Array Membership Table
  121.   by a CR/LF/CR/LF.
  122.  
  123. 2.1.1 Version number
  124.  
  125.   The version number for implementations of this specification is 
  126.   1.0
  127.  
  128. 2.1.2 ArrayEnabled
  129.  
  130.   This field allows proxies to advertise their implementation of CARP i
  131.   v1 even if they are not members of a Proxy Array. 
  132.  
  133. 2.1.3 ConfigID
  134.  
  135.   ConfigID is an opaque number no larger than 32bits similar to an 
  136.   ETag in HTTP 1.1.  It is used to track the current state of an 
  137.   Array table and may be used to match multiple yet independently 
  138.   published copies of the Proxy Array Membership Table.
  139.  
  140. 2.1.4 ArrayName
  141.  
  142.   ArrayName is an opaque string which is used to provide a convenient
  143.   administrative name for a given array.
  144.  
  145. 2.1.5 ListTTL
  146.  
  147.   ListTTL is the number of seconds for which an HTTP client entity 
  148.   should consider the current table image valid.  After ListTTL 
  149.   has expired, that client should retrieve a new copy of 
  150.   the Proxy Array Membership Table.
  151.  
  152. Valloppillil                                           [Page 4]
  153.  
  154. INTERNET-DRAFT   Cache Array Routing Protocol v1.0        30 June 1997
  155.  
  156. 2.2 Member Information
  157.  
  158.   The following fields are published per member in an array and are 
  159.   separated by single spaces.  The end of an array member's record is
  160.   terminated by a CR/LF.
  161.  
  162. 2.2.1 Name
  163.  
  164.   The name of the proxy server.  Typically this is the fully qualified
  165.   DNS name.  Downstream HTTP agents should use resolution of this name 
  166.   to determine how to connect to this proxy. 
  167.  
  168. 2.2.2 IP Addr
  169.  
  170.   The IP address that other proxy servers within this array should use
  171.   to connect to this proxy server.  This is necessary for proxy 
  172.   servers which may be hosted on multi-hommed servers where requests 
  173.   are only accepted by one of the interfaces.
  174.  
  175. 2.2.3 Listening Port
  176.  
  177.   The TCP port number this proxy is expecting requests on.
  178.  
  179. 2.2.4 Table URL
  180.  
  181.   A URL which may be maintained by this proxy server on which a copy
  182.   of the array membership table can be found. 
  183.  
  184. 2.2.5 Agent String
  185.  
  186.   An opaque string identifying the vendor / version of the 
  187.   proxy Server in the Array Membership Table.
  188.  
  189. 2.2.7 Statetime
  190.  
  191.   How long a Proxy Server has been in its current state and has been
  192.   a member of this table.  This is useful for dynamic generation of 
  193.   the Array Membership Table where the host generating the table has
  194.   knowledge of the proxy's operational status.
  195.  
  196. 2.2.8 Status
  197.  
  198.   Status provides a simple text string indicating whether a member
  199.   proxy is currently able to handle requests (UP) or refused a 
  200.   connection when last contacted (DOWN).
  201.  
  202. Valloppillil                                           [Page 5]
  203.  
  204. INTERNET-DRAFT   Cache Array Routing Protocol v1.0        30 June 1997
  205.  
  206. 2.2.9 Load Factor
  207.  
  208.   Load Factor is a relative amount of the total load for an array that
  209.   should be handled by any given member of the array.
  210.  
  211. 2.2.10 Cache Size
  212.  
  213.   Cache size is an informational field that indicates the size of the
  214.   cache held by a particular member of an array. 
  215.  
  216. 3. Routing Function
  217.  
  218.   Once an agent has a Proxy Array Membership Table.  It uses a 
  219.   mathematical hash function to determine which of the members of 
  220.   the array should be the receptacle of a particular URL request.
  221.  
  222.   This routing function involves constructing n "scores" using a hash
  223.   of the request URL plus a hash of each of the n proxies in the Proxy
  224.   Array Membership Table.  
  225.  
  226.   Both the URL and the proxy names are hashed in order to minimize the
  227.   disruption of target routes if a member of the target array can't
  228.   be contacted.
  229.  
  230.   Hashes of the URL and proxy name are constructed using the algorithm
  231.   described in 3.1 and combined using the algorithm described in 3.2.
  232.  
  233. 3.1. Hash Function
  234.  
  235.   The hash function outputs a 32 bit unsigned integers based on a 
  236.   zero-terminated ASCII input string.  The machine name and domain 
  237.   names of the URL, the protocol, and the machine names of each member 
  238.   proxy should be evaluated in lower case since that portion of the 
  239.   URL is case insensitive.
  240.  
  241.   Because irreversibility and strong cryptographic features are 
  242.   unnecessary for this application, a very simple and fast hash 
  243.   function based on the bitwise left rotate operator is used.  
  244.  
  245.   For (each char in URL):
  246.     URL_Hash +=  _rotl(URL_Hash, 19) + char ; 
  247.  
  248.   Member proxy hashes are computed in a similar manner:
  249.  
  250.   For (each char in MemberProxyName):
  251.     MemberProxy_Hash +=  _rotl(MemberProxy_Hash, 19) + char ; 
  252.  
  253.   MemberProxy_Hash += MemberProxy_Hash * 0x62531965 ;
  254.   MemberProxy_Hash = _rotl (MemberProxy_Hash, 21) ;
  255.  
  256. Valloppillil                                           [Page 6]
  257.  
  258. INTERNET-DRAFT   Cache Array Routing Protocol v1.0        30 June 1997
  259.  
  260. 3.2. Hash Combination
  261.  
  262.   Hashes are combined by first exclusive or-ing (XOR) the URL hash by 
  263.   the machine name and then multiplying by a constant and performing
  264.   a bitwise rotation.
  265.  
  266.   All final and intermediate values are 32 bit unsigned integers.
  267.  
  268.   Combined_Hash = (URL_hash ^ MemberProxy_Hash) ;  
  269.   Combined_Hash += Combined_Hash * 0x62531965 ; 
  270.   Combined_Hash = _rotl(Combined_Hash, 21) ; 
  271.   
  272. 3.3. Load Factor
  273.  
  274.   Support for array members with differing HTTP processing & caching
  275.   capacity is achieved by multiplying each of the combined hash values
  276.   by a Load Factor Multiplier.
  277.  
  278.   The Load Factor Multiplier for an individual member is calculated by
  279.   taking each member's relative Load Factor and applying the
  280.   following formula:
  281.  
  282.   For each proxy server 1,...,K, the Load Factor Multiplier, X_k, is
  283.   calculated iteratively as follows:
  284.  
  285.   X_1 = arbitrary positive constant
  286.  
  287.   X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1})
  288.   X_k += (X_{k-1}^{K-k+1})
  289.   X_k = X_k^{1/(K-k+1)}
  290.  
  291.   where:
  292.  
  293.   X_k = Load Factor Multiplier for proxy k
  294.   K = number of proxies in an array
  295.   P_k = relative percent of the load that proxy k should handle 
  296.  
  297.   This is then combined with the previously computed hashes as
  298.  
  299.   Resultant_value = Combined_Hash * X_k
  300.  
  301.  
  302. Valloppillil                                           [Page 7]
  303.  
  304. INTERNET-DRAFT   Cache Array Routing Protocol v1.0        30 June 1997
  305.  
  306. 3.4. Route Selection
  307.  
  308.   The "score" for a particular combination of URL plus proxy is its
  309.   resultant value. Once the agent determines of the scores of the 
  310.   K proxies, it routes the URL query to the proxy with the hightest 
  311.   score.
  312.  
  313. 3.5. Member Failure Routing
  314.  
  315.   If a proxy can not contact the designated member of a proxy array 
  316.   in order to forward an HTTP request, that proxy should route
  317.   the request to the second highest scoring proxy in the target array.
  318.  
  319. 4. Client-side implementation
  320.  
  321.   CARP can be implemented on client-side HTTP browsers via the 
  322.   use of the Proxy AutoConfig file described in [1] and [2].
  323.  
  324. 5. Versioning
  325.  
  326.   If a downstream proxy receives an Array Membership Table with a 
  327.   greater version # than that proxy is able to parse, it should 
  328.   fall back to simple proxy request routing to any administrator
  329.   defined upstream proxy server.
  330.  
  331. 6. Security Considerations
  332.  
  333.   This draft does not discuss relevant security considerations.
  334.  
  335. 7. Open Issues
  336.  
  337. 8. Acknowledgements
  338.  
  339.   The author would like to thank Brian Smith, Kip Compton, and 
  340.   Kerry Schwartz for their assistance in preparing this document.
  341.  
  342.   Most of the architecture & design of CARP stem from work conducted
  343.   by Brian Smith at Microsoft Corp.
  344.  
  345. Valloppillil                                           [Page 8]
  346.  
  347. INTERNET-DRAFT   Cache Array Routing Protocol v1.0       30 June 1997
  348.  
  349. 9. References
  350.  
  351.   [1] Luotonen, Ari., "Navigator Proxy Auto-Config File Format", 
  352.  Netscape Corporation, http://home.netscape.com/eng/mozilla/2.0/
  353.  relnotes/demo/proxy-live.html, March 1996.
  354.  
  355.   [2] Microsoft Corporation., "Automatic Proxy Configuration", 
  356.  http://www.microsoft.com/ie/ieak/autosys.htm, March 21, 1997.
  357.  
  358.   [3] Wessels, Duane., "Internet Cache Protocol Version 2", http://ds.
  359.  internic.net/internet-drafts/draft-wessels-icp-v2-00.txt, March 21, 
  360.  1997.
  361.  
  362.   [4] Sharp Corporation., "Super Proxy Script", 
  363.  http://naragw.sharp.co.jp/sps/, August 9, 1996.
  364.  
  365.   [5] Fielding, R., et. al, "Hypertext Transfer Protocol -- HTTP/1.1", 
  366.  RFC 2068, UC Irvine, January 1997.
  367.  
  368.   [6] Valloppillil & Cohen, "Hierarchical HTTP Routing Protocol", 
  369.  http://ircache.nlanr.net/Cache/ICP/draft-vinod-icp-traffic-dist-00.txt,
  370.  April 21, 1997.
  371.  
  372. 10.  Author Information
  373.  
  374.     Vinod Valloppillil
  375.     Microsoft Corporation
  376.     One Microsoft Way
  377.     Redmond, WA 98052
  378.  
  379.     Phone:  1.206.703.3460
  380.     Email:  VinodV@Microsoft.Com
  381.  
  382.     Keith W. Ross
  383.     University of Pennsylvania
  384.     Department of Systems Engineering
  385.     Philadelphia, PA  19104
  386.  
  387.     Phone:  1.215.898.6069 
  388.     Email:  Ross@UPenn.Edu
  389.  
  390. Expires April 1998
  391.