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