tech_report/node1.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
   2 <!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
   3 originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
   4 * revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
   5 * with significant contributions from:
   6   Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
   7 <HTML>
   8 <HEAD>
   9 <TITLE>The problem</TITLE>
  10 <META NAME="description" CONTENT="The problem">
  11 <META NAME="keywords" CONTENT="tech_report">
  12 <META NAME="resource-type" CONTENT="document">
  13 <META NAME="distribution" CONTENT="global">
  14 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
  15 <LINK REL="STYLESHEET" HREF="tech_report.css">
  16 <LINK REL="next" HREF="node2.html">
  17 <LINK REL="previous" HREF="tech_report.html">
  18 <LINK REL="up" HREF="tech_report.html">
  19 <LINK REL="next" HREF="node2.html">
  20 </HEAD>
  21 <BODY >
  22 <!--Navigation Panel-->
  23 <A NAME="tex2html22"
  24  HREF="node2.html">
  25 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
  26  SRC="next.gif"></A>
  27 <A NAME="tex2html20"
  28  HREF="tech_report.html">
  29 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
  30  SRC="up.gif"></A>
  31 <A NAME="tex2html14"
  32  HREF="tech_report.html">
  33 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
  34  SRC="previous.gif"></A>
  35 <BR>
  36 <B> Next:</B> <A NAME="tex2html23"
  37  HREF="node2.html">The rsync algorithm</A>
  38 <B> Up:</B> <A NAME="tex2html21"
  39  HREF="tech_report.html">The rsync algorithm</A>
  40 <B> Previous:</B> <A NAME="tex2html15"
  41  HREF="tech_report.html">The rsync algorithm</A>
  42 <BR>
  43 <BR>
  44 <!--End of Navigation Panel-->
  45
  46 <H1><A NAME="SECTION00010000000000000000">
  47 The problem</A>
  48 </H1>
  49
  50 <P>
  51 Imagine you have two files, <I>A</I> and <I>B</I>, and you wish to update <I>B</I> to be
  52 the same as <I>A</I>. The obvious method is to copy <I>A</I> onto <I>B</I>.
  53
  54 <P>
  55 Now imagine that the two files are on machines connected by a slow
  56 communications link, for example a dial up IP link.  If <I>A</I> is large,
  57 copying <I>A</I> onto <I>B</I> will be slow.  To make it faster you could
  58 compress <I>A</I> before sending it, but that will usually only gain a
  59 factor of 2 to 4.
  60
  61 <P>
  62 Now assume that <I>A</I> and <I>B</I> are quite similar, perhaps both derived
  63 from the same original file. To really speed things up you would need
  64 to take advantage of this similarity. A common method is to send just
  65 the differences between <I>A</I> and <I>B</I> down the link and then use this
  66 list of differences to reconstruct the file.
  67
  68 <P>
  69 The problem is that the normal methods for creating a set of
  70 differences between two files rely on being able to read both files.
  71 Thus they require that both files are available beforehand at one end
  72 of the link.  If they are not both available on the same machine,
  73 these algorithms cannot be used (once you had copied the file over,
  74 you wouldn't need the differences).  This is the problem that rsync
  75 addresses.
  76
  77 <P>
  78 The rsync algorithm efficiently computes which parts of a source file
  79 match some part of an existing destination file.  These parts need not
  80 be sent across the link; all that is needed is a reference to the part
  81 of the destination file.  Only parts of the source file which are not
  82 matched in this way need to be sent verbatim.  The receiver can then
  83 construct a copy of the source file using the references to parts of
  84 the existing destination file and the verbatim material.
  85
  86 <P>
  87 Trivially, the data sent to the receiver can be compressed using any
  88 of a range of common compression algorithms, for further speed
  89 improvements.
  90
  91 <P>
  92 <HR>
  93 <!--Navigation Panel-->
  94 <A NAME="tex2html22"
  95  HREF="node2.html">
  96 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
  97  SRC="next.gif"></A>
  98 <A NAME="tex2html20"
  99  HREF="tech_report.html">
 100 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 101  SRC="up.gif"></A>
 102 <A NAME="tex2html14"
 103  HREF="tech_report.html">
 104 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 105  SRC="previous.gif"></A>
 106 <BR>
 107 <B> Next:</B> <A NAME="tex2html23"
 108  HREF="node2.html">The rsync algorithm</A>
 109 <B> Up:</B> <A NAME="tex2html21"
 110  HREF="tech_report.html">The rsync algorithm</A>
 111 <B> Previous:</B> <A NAME="tex2html15"
 112  HREF="tech_report.html">The rsync algorithm</A>
 113 <!--End of Navigation Panel-->
 114 <ADDRESS>
 115 <I>Andrew Tridgell</I>
 116 <BR><I>1998-11-09</I>
 117 </ADDRESS>
 118 </BODY>
 119 </HTML>