rfc1036 December 1987

5.  The News Propagation Algorithm

    This section describes the overall scheme of USENET and the
    algorithm followed by hosts in propagating news to the entire
    logical network.  Since all hosts are affected by incorrectly
    formatted messages and by propagation errors, it is important
    for the method to be standardized.

    USENET is a directed graph.  Each node in the graph is a host
    computer, and each arc in the graph is a transmission path from
    one host to another host.  Each arc is labeled with a newsgroup
    pattern, specifying which newsgroup classes are forwarded along
    that link.  Most arcs are bidirectional, that is, if host A
    sends a class of newsgroups to host B, then host B usually sends
    the same class of newsgroups to host A.  This bidirectionality
    is not, however, required.

    USENET is made up of many subnetworks.  Each subnet has a name, such
    as comp or btl.  Each subnet is a connected graph, that is, a path
    exists from every node to every other node in the subnet.  In
    addition, the entire graph is (theoretically) connected.  (In
    practice, some political considerations have caused some hosts to be
    unable to post messages reaching the rest of the network.)

    A message is posted on one machine to a list of newsgroups. That
    machine accepts it locally, then forwards it to all its neighbors
    that are interested in at least one of the newsgroups of the
    message.  (Site A deems host B to be "interested" in a newsgroup if
    the newsgroup matches the pattern on the arc from A to B.  This
    pattern is stored in a file on the A machine.)  The hosts receiving
    the incoming message examine it to make sure they really want the
    message, accept it locally, and then in turn forward the message to
    all their interested neighbors.  This process continues until the
    entire network has seen the message.

    An important part of the algorithm is the prevention of loops.  The
    above process would cause a message to loop along a cycle forever.
    In particular, when host A sends a message to host B, host B will
    send it back to host A, which will send it to host B, and so on.
    One solution to this is the history mechanism.  Each host keeps
    track of all messages it has seen (by their Message-ID) and
    whenever a message comes in that it has already seen, the incoming
    message is discarded immediately.  This solution is sufficient to
    prevent loops, but additional optimizations can be made to avoid
    sending messages to hosts that will simply throw them away.

    One optimization is that a message should never be sent to a machine
    listed in the "Path" line of the header.  When a machine name is
    in the "Path" line, the message is known to have passed through the
    machine.  Another optimization is that, if the message originated
    on host A, then host A has already seen the message.  Thus, if a
    message is posted to newsgroup misc.misc, it will match the pattern
    misc.all (where all is a metasymbol that matches any string), and
    will be forwarded to all hosts that subscribe to misc.all (as
    determined by what their neighbors send them).  These hosts make up
    the misc subnetwork.  A message posted to btl.general will reach all
    hosts receiving btl.all, but will not reach hosts that do not get
    btl.all.  In effect, the messages reaches the btl subnetwork.  A
    messages posted to newsgroups misc.misc,btl.general will reach all
    hosts subscribing to either of the two classes.

Notes

    <1>  UNIX is a registered trademark of AT&T.