share/doc/smm/18.net/a.t

   1 .\" Copyright (c) 1983, 1986, 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   4 .\" Redistribution and use in source and binary forms, with or without
   5 .\" modification, are permitted provided that the following conditions
   6 .\" are met:
   7 .\" 1. Redistributions of source code must retain the above copyright
   8 .\"    notice, this list of conditions and the following disclaimer.
   9 .\" 2. Redistributions in binary form must reproduce the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer in the
  11 .\"    documentation and/or other materials provided with the distribution.
  12 .\" 3. Neither the name of the University nor the names of its contributors
  13 .\"    may be used to endorse or promote products derived from this software
  14 .\"    without specific prior written permission.
  15 .\"
  16 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  17 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  20 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26 .\" SUCH DAMAGE.
  27 .\"
  28 .\"     @(#)a.t 8.1 (Berkeley) 6/8/93
  29 .\"
  30 .nr H2 1
  31 .\".ds RH "Gateways and routing
  32 .br
  33 .ne 2i
  34 .NH
  35 \s+2Gateways and routing issues\s0
  36 .PP
  37 The system has been designed with the expectation that it will
  38 be used in an internetwork environment.  The ``canonical''
  39 environment was envisioned to be a collection of local area
  40 networks connected at one or more points through hosts with
  41 multiple network interfaces (one on each local area network),
  42 and possibly a connection to a long haul network (for example,
  43 the ARPANET).  In such an environment, issues of
  44 gatewaying and packet routing become very important.  Certain
  45 of these issues, such as congestion
  46 control, have been handled in a simplistic manner or specifically
  47 not addressed.
  48 Instead, where possible, the network system
  49 attempts to provide simple mechanisms upon which more involved
  50 policies may be implemented.  As some of these problems become
  51 better understood, the solutions developed will be incorporated
  52 into the system.
  53 .PP
  54 This section will describe the facilities provided for packet
  55 routing.  The simplistic mechanisms provided for congestion
  56 control are described in chapter 12.
  57 .NH 2
  58 Routing tables
  59 .PP
  60 The network system maintains a set of routing tables for
  61 selecting a network interface to use in delivering a
  62 packet to its destination.  These tables are of the form:
  63 .DS
  64 .ta \w'struct   'u +\w'u_long   'u +\w'sockaddr rt_gateway;    'u
  65 struct rtentry {
  66         u_long  rt_hash;                /* hash key for lookups */
  67         struct  sockaddr rt_dst;        /* destination net or host */
  68         struct  sockaddr rt_gateway;    /* forwarding agent */
  69         short   rt_flags;               /* see below */
  70         short   rt_refcnt;              /* no. of references to structure */
  71         u_long  rt_use;                 /* packets sent using route */
  72         struct  ifnet *rt_ifp;          /* interface to give packet to */
  73 };
  74 .DE
  75 .PP
  76 The routing information is organized in two separate tables, one
  77 for routes to a host and one for routes to a network.  The
  78 distinction between hosts and networks is necessary so
  79 that a single mechanism may be used
  80 for both broadcast and multi-drop type networks, and
  81 also for networks built from point-to-point links (e.g
  82 DECnet [DEC80]).
  83 .PP
  84 Each table is organized as a hashed set of linked lists.
  85 Two 32-bit hash values are calculated by routines defined for
  86 each address family; one based on the destination being
  87 a host, and one assuming the target is the network portion
  88 of the address.  Each hash value is used to
  89 locate a hash chain to search (by taking the value modulo the
  90 hash table size) and the entire 32-bit value is then
  91 used as a key in scanning the list of routes.  Lookups are
  92 applied first to the routing
  93 table for hosts, then to the routing table for networks.
  94 If both lookups fail, a final lookup is made for a ``wildcard''
  95 route (by convention, network 0).
  96 The first appropriate route discovered is used.
  97 By doing this, routes to a specific host on a network may be
  98 present as well as routes to the network.  This also allows a
  99 ``fall back'' network route to be defined to a ``smart'' gateway
 100 which may then perform more intelligent routing.
 101 .PP
 102 Each routing table entry contains a destination (the desired final destination),
 103 a gateway to which to send the packet,
 104 and various flags which indicate the route's status and type (host or
 105 network).  A count
 106 of the number of packets sent using the route is kept, along
 107 with a count of ``held references'' to the dynamically
 108 allocated structure to insure that memory reclamation
 109 occurs only when the route is not in use.  Finally, a pointer to the
 110 a network interface is kept; packets sent using
 111 the route should be handed to this interface.
 112 .PP
 113 Routes are typed in two ways: either as host or network, and as
 114 ``direct'' or ``indirect''.  The host/network
 115 distinction determines how to compare the \fIrt_dst\fP field
 116 during lookup.  If the route is to a network, only a packet's
 117 destination network is compared to the \fIrt_dst\fP entry stored
 118 in the table.  If the route is to a host, the addresses must
 119 match bit for bit.
 120 .PP
 121 The distinction between ``direct'' and ``indirect'' routes indicates
 122 whether the destination is directly connected to the source.
 123 This is needed when performing local network encapsulation.  If
 124 a packet is destined for a peer at a host or network which is
 125 not directly connected to the source, the internetwork packet
 126 header will
 127 contain the address of the eventual destination, while
 128 the local network header will address the intervening
 129 gateway.  Should the destination be directly connected, these addresses
 130 are likely to be identical, or a mapping between the two exists.
 131 The RTF_GATEWAY flag indicates that the route is to an ``indirect''
 132 gateway agent, and that the local network header should be filled in
 133 from the \fIrt_gateway\fP field instead of
 134 from the final internetwork destination address.
 135 .PP
 136 It is assumed that multiple routes to the same destination will not
 137 be present; only one of multiple routes, that most recently installed,
 138 will be used.
 139 .PP
 140 Routing redirect control messages are used to dynamically
 141 modify existing routing table entries as well as dynamically
 142 create new routing table entries.  On hosts where exhaustive
 143 routing information is too expensive to maintain (e.g. work
 144 stations), the
 145 combination of wildcard routing entries and routing redirect
 146 messages can be used to provide a simple routing management
 147 scheme without the use of a higher level policy process.
 148 Current connections may be rerouted after notification of the protocols
 149 by means of their \fIpr_ctlinput\fP entries.
 150 Statistics are kept by the routing table routines
 151 on the use of routing redirect messages and their
 152 affect on the routing tables.  These statistics may be viewed using
 153 .IR netstat (1).
 154 .PP
 155 Status information other than routing redirect control messages
 156 may be used in the future, but at present they are ignored.
 157 Likewise, more intelligent ``metrics'' may be used to describe
 158 routes in the future, possibly based on bandwidth and monetary
 159 costs.
 160 .NH 2
 161 Routing table interface
 162 .PP
 163 A protocol accesses the routing tables through
 164 three routines,
 165 one to allocate a route, one to free a route, and one
 166 to process a routing redirect control message.
 167 The routine \fIrtalloc\fP performs route allocation; it is
 168 called with a pointer to the following structure containing
 169 the desired destination:
 170 .DS
 171 ._f
 172 struct route {
 173         struct  rtentry *ro_rt;
 174         struct  sockaddr ro_dst;
 175 };
 176 .DE
 177 The route returned is assumed ``held'' by the caller until
 178 released with an \fIrtfree\fP call.  Protocols which implement
 179 virtual circuits, such as TCP, hold onto routes for the duration
 180 of the circuit's lifetime, while connection-less protocols,
 181 such as UDP, allocate and free routes whenever their destination address
 182 changes.
 183 .PP
 184 The routine \fIrtredirect\fP is called to process a routing redirect
 185 control message.  It is called with a destination address,
 186 the new gateway to that destination, and the source of the redirect.
 187 Redirects are accepted only from the current router for the destination.
 188 If a non-wildcard route
 189 exists to the destination, the gateway entry in the route is modified
 190 to point at the new gateway supplied.  Otherwise, a new routing
 191 table entry is inserted reflecting the information supplied.  Routes
 192 to interfaces and routes to gateways which are not directly accessible
 193 from the host are ignored.
 194 .NH 2
 195 User level routing policies
 196 .PP
 197 Routing policies implemented in user processes manipulate the
 198 kernel routing tables through two \fIioctl\fP calls.  The
 199 commands SIOCADDRT and SIOCDELRT add and delete routing entries,
 200 respectively; the tables are read through the /dev/kmem device.
 201 The decision to place policy decisions in a user process implies
 202 that routing table updates may lag a bit behind the identification of
 203 new routes, or the failure of existing routes, but this period
 204 of instability is normally very small with proper implementation
 205 of the routing process.  Advisory information, such as ICMP
 206 error messages and IMP diagnostic messages, may be read from
 207 raw sockets (described in the next section).
 208 .PP
 209 Several routing policy processes have already been implemented.  The
 210 system standard
 211 ``routing daemon'' uses a variant of the Xerox NS Routing Information
 212 Protocol [Xerox82] to maintain up-to-date routing tables in our local
 213 environment.  Interaction with other existing routing protocols,
 214 such as the Internet EGP (Exterior Gateway Protocol), has been
 215 accomplished using a similar process.