romkey@kaos.UUCP (John Romkey) (05/12/88)
In article <8805102321.AA26819@hogg.cc.uoregon.edu> jqj@HOGG.CC.UOREGON.EDU writes: >>You REALLY DON'T want hosts to know about routing. >At issue here is a critical point: how smart is it desirable for hosts >to be? Braden argues that they should be very dumb. I would argue >that they can be dumb if they don't really need connectivity off their >network, but should be a little bit smarter if possible. As the network grows the part which will give out is the routing substrate. The Internet has already had this happen a few times. We went from GGP to EGP, then EGP broke and it had to support multiple packet updates, and now we're in the process of scrapping EGP for the next step. Each of these steps was good enough for networks of a certain size and broke as the network grew. If we can keep the hosts as stupid as possible with regard to the routing algorithms and bottle the complexity up in the routers then we're in a better position to deal with the next time the Internet hits a level where the existing routing protocols break. Whatever the next solution is, it may not hold for 10,000 networks. Or 100,000 networks. With one or two hundred hosts per network. [I've been working with TCP/IP long enough that when I started, we called routers 'gateways', so know that I'm using them as synonyms in this message.] I'd rather treat the network as a black box from the host's point of view. For a host with a single network interface, I think the best way for it to route is to have a list of default gateways which it cycles through, caching a route with a 'connection'. If TCP notices problems with lots of retransmissions, it could call IP and request that it reroute the connection (IP flushes the route and uses a different default gateway). Since the gateways know the TRUTH they can send ICMP redirects when they believe there is a better route. If some new protocols were cooked up to allow hosts to query routers for some useful information WITHOUT the hosts understanding how the routers worked, that would be okay as far as I'm concerned. Multihomed hosts are a more substantial problem, and right now they probably do have to at least listen to routing protocols in order to figure out the best routes to use. This way, the next time the routing substrate breaks because the Internetwork has grown too much, only the routing substrate needs to be changed. Just fixing this will be a bad enough problem without having to change all the host software in the world. We'll have a lot more flexibility to change the routing substrate then. -- - john romkey UUCP: romkey@kaos.uucp ARPA: romkey@xx.lcs.mit.edu ...harvard!spdcc!kaos!romkey Telephone: (617) 776-3121
smb@ulysses.homer.nj.att.com (Steven Bellovin) (05/12/88)
One problem I see is that ICMP Redirect is largely useless. It's only useful for the first gateway along the way to tell the originating host to use a different gateway; it can't be used to tell an intermediate gateway what the proper next hop is. That is, assume we have a large LAN behind a single gateway G to the Internet. If a host H on that LAN wants to talk to host H' on another LAN behind another gateway G', all H can do is send the packets to G. G must know that G' is the proper next hop; if it chooses to use G'' instead, G'' cannot send an ICMP Redirect. Or rather, it can, but the Redirect will go to H, which can't do anything but send to G no matter what it receives. G'' doesn't know that the packet came from G, and hence can't advise G of the proper route. (To be sure, RFC1009 says that gateways within an autonomous system can use Redirects among themselves, but that's not a standardized use for the Internet.) The conclusion of all this is that local gateways must be extremely smart. The current scheme, with EGP, works well enough in the current environment, where there's one central net (ARPANET+MILNET); it would fail miserably if there were a large number of interconnected backbone nets. I'm not certain what to do about the problem. If Record Route were used more, or Loose Source route, a host could handle such a redirect more intelligently. (Of course, under the current spec it wouldn't be sent.) Perhaps we need a new option, ``Last Hop''; it would tell each gateway the immediate predecessor gateway to be advised of a routing correction. Then we'd need some new sort of Redirect message, possibly one that includes a loose source route, rather than just a simple gateway address. The combination of these might even allow a very smart gateway to straighten out twisty paths, though I'm not sure that that's feasible. And the security implications of enhanced Redirects needs to be considered very carefully. --Steve Bellovin ulysses!smb smb@ulysses.att.com
jqj@hogg.cc.uoregon.EDU (05/12/88)
John, I sympathize, and agree that yours is a defendable position. One problem with it is that it doesn't work if the local network is extremely dynamic, with lots of routers coming and going. An "ad absurdum" extension to your argument is that a host shouldn't have to have ARP; it should be able to make do with some static tables -- of course, that would be ridiculous since the list of hosts on the local network is much too dynamic to make such a table reasonable (though note that some implementations, e.g. SunOS 3.x diskless bootstrap, required just such a table). Similarly, I claim that we will need some sort of discovery mechanism if the list of gateways on a local network is expected to be large and dynamic. We have such a discovery mechanism in place today; passive RIP. I'm not recommending that we improve it, or that hosts use it for anything except finding the first gateway. Note that if in fact most host implementations already supported a list of default gateways then I'd be willing to live with that as an alternative. Unfortunately, they don't; most implementations give you exactly ONE default, which is not enough when that gateway crashes and stops sending ICMP redirects. >fixing this will be a bad enough problem without having to change all >the host software in the world I believe that a gateway can be taught to send out RIP packets saying "I'm a default router" without sending out any other data. If so, this would provide my desired discovery mechanism with no changes to a common flavor of host software (i.e. BSD derivatives).
ROMKEY@XX.LCS.MIT.EDU (John Romkey) (05/13/88)
>One problem with it is that it doesn't work if the local network is >extremely dynamic, with lots of routers coming and going. I envision networks where links to other networks come and go, but not the actual routers themselves. It's a strange idea to me. I don't see any application for it off the top of my head. >An "ad absurdum" extension to your argument is that a host shouldn't have to >have ARP; No, I think there's a big difference between the two examples. I don't want the hosts to have complete lists of all the routers on their network. Just a list of a few - the default routers. Many systems nowadays have an idea of one default router; I'd like to increase it to an arbitrary list of them which is cycled through for reliability. If you have only one default router then you lose big when it goes down. Since the routers all talk to one another, they know the best routes and if the default router chosen for a particular connection isn't the best, it will send an ICMP redirect and the host should change its route. It occurs to me that we're agreeing to some extent, but arguing over details. I don't care too much how the host discovers what its default routers are. Could be statically configured (though this isn't too good), BOOTP or some new broadcast ICMP message. I think that the details that we're disagreeing over are: 1. How many routers the host knows about. I want it to only have to know about a few. I don't really care how many, I'd like it to be more than one. At least nothing should depend on it knowing about them all. It doesn't bother me if the host does or doesn't know them all; ICMP will clean up the mess. I'm not sure that we're really disagreeing over this one... 2. How it discovers them. I'm very opposed to the host discovering routes by using routing protocols that the routers use internally. Having part of the routers' protocol be an interface to hosts which says "I'm a default router" or "This is a list of default routers for this subnet" is okay, as long as the host implementations don't sticky their fingers by prying open the routing protocols any more than that. If there's some way to do it without a broadcast protocol, or with one that minimizes the number of broadcasts, that would be a good thing. - john -------
romkey@kaos.UUCP (John Romkey) (05/13/88)
In article <10285@ulysses.homer.nj.att.com> smb@ulysses.homer.nj.att.com (Steven Bellovin) writes: >One problem I see is that ICMP Redirect is largely useless. It's only >useful for the first gateway along the way to tell the originating host >to use a different gateway; it can't be used to tell an intermediate >gateway what the proper next hop is. But that's not really a problem with ICMP redirects at all. Look at it this way: ICMP redirects are the (okay, *a*) way routers communicate routing information to hosts XYZ (fill in your favorite routing protocol(s)) is the way routers communicate routing information to one another. If the routers are doing their job properly then the routers on the same subnet as the host will redirect it to the proper router via ICMP; this router will then do XYZ things to figure out how to route the packet from there. It's because of XYZ that the routers know when to redirect in the first place. >The conclusion of all this is that local gateways must be extremely >smart. The current scheme, with EGP, works well enough in the current >environment, where there's one central net (ARPANET+MILNET); it would >fail miserably if there were a large number of interconnected backbone >nets. > >I'm not certain what to do about the problem. The example assumes that the routers are screwed up in the first place. You don't necessarily have to have an incredible amount of information in your routers that are used by your host - you just have to have routing protocols that do the right thing (which may actually require incredible amounts of information...oh well). The thing to do about it is to refine the XYZ protocols (ancient GGP, RIP, EGP) so that they work better for larger, more complicated networks. Yes, the current system doesn't deal with complicated networks very well. It doesn't handle redundant routes well. It doesn't handle load-sharing very well. It doesn't route on Type of Service very well (because not a lot of routers support it and virtually no hosts set the TOS field in the IP header). I believe there are people on an IETF task force or working group or some such working on this problem. -- - john romkey UUCP: romkey@kaos.uucp ARPA: romkey@xx.lcs.mit.edu ...harvard!spdcc!kaos!romkey Telephone: (617) 776-3121
KASTEN@MITVMA.MIT.EDU (05/13/88)
> Similarly, I claim that we will need some sort of discovery mechanism >if the list of gateways on a local network is expected to be large and >dynamic. We have such a discovery mechanism in place today; passive >RIP. I'm not recommending that we improve it, or that hosts use it for >anything except finding the first gateway. UNfortunately, not all of the systems that use IP are (easily) capable of running a RIP listener. PC's are the best example - they do not have multitasking, making it difficult to load in a program to listen to the RIP traffic. There are ways of doing it but this is not a forum for discussing PC stuff. >I believe that a gateway can be taught to send out RIP packets saying >"I'm a default router" without sending out any other data. If so, this >would provide my desired discovery mechanism with no changes to a >common flavor of host software (i.e. BSD derivatives). Not all of us are so lucky as to have a BSD system available on which we can build our stuff. I like the idea of the "I am a Router" broadcast's. The problem, again, is that not all hosts may be capable of listening at all times for that broadcast (even a BSD machine could be turned off). Instead, a query and response type of protocol could be used. When a host needs to send something off net and either A) does not have the IP Address of any router (if it had one address, it could send a packet to that router and get the redirect) or B) the host decides that the router it is using is dead (e.g. TCP has retransmitted too often) then the host broadcast a "Who can route to network X?" request and the routers on the local network would respond. This would require changes to both routers and hosts, but I think is the most flexible over the widest range of hosts - from the single "tasked" PC's up to Crays. Of course, you still can listen to RIP (but what if the routers want to use another protocol?) Frank Kastenholz
Dave_Katz@UM.CC.UMICH.EDU (05/13/88)
The OSI approach to this problem is to use the End System-Intermediate
System protocol (ISO 9542). In this scheme the ES's (hosts) and IS's
(routers) periodically multicast "hello" packets to one another in order
to determine reachability. The period used can ultimately be controlled
by the IS's. This usually means that address mapping info is already
cached so the "hold on a minute while I find out where this packet
needs to go" approach that ARP uses is most often not needed.
Hosts will discover all routers on the subnet using this mechanism.
Redirects are used to teach the hosts which routers to use for
particular addresses. The redirects can contain address masks defining
equivalence classes of destination addresses to redirect, as well as
possibly hinting that the host can algorithmically derive the MAC
layer address from the network layer address (OSI NSAP addresses are
big enough to embed MAC addresses in them if somebody wants to).
This protocol is purposely decoupled from IS-IS routing ("IGP") with
the philosophy that hosts should be kept insulated from the details
of what happens in the routers, and should be kept simple. Thus the
only a priori information needed is the ES's own address.
This obviously doesn't help in the TCP/IP world, but it's worth
mentioning.
--Dave Katz
Merit Computer Network/NSFnet
Dave_Katz@UM.CC.UMICH.EDUmar@ATHENA.MIT.EDU (05/14/88)
You are right in that ICMP redirects are only good in indicating the first hop from a host. But that does not make them largely useless, since this is their intended use, and is a valuble part of not requiring hosts to understand complicated routing. This way a host only needs to know about one local gateway *which is currently functioning* and redirects will do the rest. Gateways, on the other hand, must understand routing within their own autonomous system, and to other systems. It is expected that gateways will make use of other protocols for this, not try to use ICMP for something it was not designed for. As in the discussion about how hosts find out about the different first-hop gateways available: the hosts shouldn't listen to RIP, a gateway routing protocol, just as gateways don't for the most part receive ICMP redirects. We will get nothing but trouble if we try to use the same protocols between gateways and for hosts to communicate with gateways. A gateway-to-gateway protocol is necessarily going to be much more complicated than what a host needs, and *will* evolve over time as the internet grows. It should be possible to specify a gateway-to-host protocol in such a way that it is simple and not likely to change so that it will get implemented by all vendors for all operating systems. -Mark Rosenstein
philipp@LARRY.MCRCIM.MCGILL.EDU (Philip Prindeville [CC]) (05/14/88)
Date: Thu 12 May 88 14:38:09-EDT
From: John Romkey <ROMKEY@xx.lcs.mit.edu>
Subject: Re: Dumb vs. smart host routing
To: jqj@hogg.cc.uoregon.edu
Cc: tcp-ip@sri-nic.arpa
[ ... ]
I envision networks where links to other networks come and go, but not the
actual routers themselves. It's a strange idea to me. I don't see any
application for it off the top of my head.
On our network, which is fairly real-worldish, we have a uVAX-II with
very flakey dequna board. It panics several times a day, leaving us with
an alternative route but no way to know about it. Your vision could be
a little broader, without going over your head. :-)
[ ... ]
of one default router; I'd like to increase it to an arbitrary list of them
which is cycled through for reliability. If you have only one default router
Won't this affect your TCP RTT and cause some sort of oscillation (or force
you to bind connections to routes)?
-PhilipBILLW@MATHOM.CISCO.COM (William Westfield) (05/14/88)
Well, I might as well throw some more ideas into the fire. At cisco
(where we make routers), we also believe that hosts should know nothing
about routing protocols. This becomes much more obvious when your router
is running 4 different routing protocols simultaneously, and translating
metrics from one to another is both difficult and dangerous.
Of course, it ought to be possible to use any of the gateways you've
learned about via redirects as new default gateways, but this is probably
not easy to add to existing code. However, John Romkey said:
If some new protocols were cooked up to allow hosts to query routers
for some useful information WITHOUT the hosts understanding how the
routers worked, that would be okay as far as I'm concerned.
We believe that such a protocol already exists which provides this
function, and is implemented by nearly all tcp/ip vendors. It is called
ARP. A router can respond to ARP requests that it recognizes as being for
hosts not connected to the local cable if it knows a route to that network.
This technique is being called "Proxy ARP", and is frequently used to make
subnetting transparent to hosts. It works equally well to make any network
topology transparent to hosts. Redundancy is handled automatically if you
convince TCP and other high level protocols to flush ARP entries when they
are about to time out.
Of course, this only works with hosts on networks where ARP is used for
address resolution (broadcasts are possible). But if a host has only a
point-to-point link to the network, it might as well use whatever gateway
is at the other end of that link as its default gateway. This leaves only
networks like X.25 and the ARPANet (non-broadcast, but not really point-to-
point either), and it might not be such a bad idea to have those hosts know
about routing, at least to the extent of having multiple default gateways.
Bill Westfield
cisco Systems.
-------ROMKEY@XX.LCS.MIT.EDU (John Romkey) (05/14/88)
> On our network, which is fairly real-worldish, we have a uVAX-II with > very flakey dequna board. It panics several times a day, leaving us with > an alternative route but no way to know about it. Your vision could be > a little broader, without going over your head. :-) Originally we were discussing 'extremely dynamic' router changes. A crash every few hours doesn't cut it with me for 'extremely dynamic'. There are two things that should be done here. First, the microvax should be fixed. Second, the software should have the list of default gateways that I keep bringing up rather than just one. > Won't this affect your TCP RTT and cause some sort of oscillation (or force > you to bind connections to routes)? Not a problem at all. You cache a route for each connection; if the connection starts having problems or an appropriate redirect is received, you recompute the route. It's very simple and quite efficient if implemented correctly. - john -------
mcc@ETN-WLV.EATON.COM (Merton Campbell Crockett) (05/14/88)
Binding connections to routes is not necessarily bad. Binding connections to routes will probably be a necessity if, and when, multi-level security is implemented. Not all gateways, hosts, etc. may be accredited to service a transmission at a given security level. Which we lead to some requirement for a node to be able to request of each node in a path "can you provide me this class (type) of service at this security level?" Merton
jis@BITSY.MIT.EDU (Jeffrey I. Schiller) (05/15/88)
> ...When a host needs to send >something off net and either A) does not have the IP Address of any >router (if it had one address, it could send a packet to that router >and get the redirect) or B) the host decides that the router it is >using is dead (e.g. TCP has retransmitted too often) then the host >broadcast a "Who can route to network X?" request and the routers on >the local network would respond. Now be VERY careful with protocols that broadcast questions that may get simultaneously answered by a large number of machines. In a network with only one or two routers what you suggest would work fine. However when you have about 20 routers on an Ethernet you are likely to get a monster Ethernet collision when they all go to respond to the broadcast. There have been several horror stories posted to this mailing list of "monster collision" problems (I know, I was one of the senders!). ARP works using broadcast questions, but in a properly functioning network exactly one machine should respond, so no collision. However you do bring up a problem with single threaded machines. What if we modify your scheme so that all routers on a network speak some (as yet undefined) protocol to elect one of them the "advertised default router" and only this router would respond to the "Who can route" message. If this router went down the other routers would know and elect a new default router. [Note I have simplified the question from "Who can route to network X?" to just a simple request for a default router. That router can then send redirects later when packets arrive.] -Jeff
KASTEN@MITVMA.MIT.EDU (Frank Kastenholz) (05/16/88)
> However you do bring up a problem with single threaded >machines. What if we modify your scheme so that all routers on a >network speak some (as yet undefined) protocol to elect one of them >the "advertised default router" and only this router would respond to >the "Who can route" message. If this router went down the other >routers would know and elect a new default router. "Note I have >simplified the question from "Who can route to network X?" to just a >simple request for a default router. That router can then send >redirects later when packets arrive." The basic idea is good, unfortunately, I need to deal in the real world (SHUDDER) where a certain well known computer company has made a network package for PC's and PS/2's that does not understand ICMP redirect. In fact, the only ICMP that this package supports is Address Mask Query. Cheers Frank Kastenholz
dab@oliver.CRAY.COM (Dave Borman) (05/16/88)
Bill Westfield of cisco Systems while talking about "Proxy ARP" writes: > Of course, this only works with hosts on networks where ARP is used for > address resolution (broadcasts are possible). But if a host has only a > point-to-point link to the network, it might as well use whatever gateway > is at the other end of that link as its default gateway. This leaves only > networks like X.25 and the ARPANet (non-broadcast, but not really point-to- > point either), and it might not be such a bad idea to have those hosts know > about routing, at least to the extent of having multiple default gateways. There's more. For instance, the A series of HYPERchannel adaptors does not support broadcast, and is not point-to-point. As far as I know, "Proxy ARP" only works with subnets, for nodes that don't know about subnets. In order to send out the ARP request, the host has to already belive that he can get to the remote host in one hop. If my machine is on net 128.62, and I want to get to a machine on net 128.63, I don't send out an ARP request for the machine on net 128.63. I have to have a route to 128.63 which points to a machine on net 128.62, and then I'll be ARPing for the machine on 128.62 which is the next hop to 128.63. "Proxy ARP" is a wonderful fix in the real world to keep your subnetted network running when you have hosts that don't know about subnets. I don't think that it should be used for anything else, or promoted as a standard. -Dave Borman CRAY Research, Inc.
brescia@PARK-STREET.BBN.COM (Mike Brescia) (05/17/88)
<from kasten@mitvma.mit.edu>
a certain well known computer company has made a network package for PC's
and PS/2's that does not understand ICMP redirect.
This is an interesting turn. What if they try to send to a gateway that does
not forward packets which needed redirect.
a. host sends to gw A
b. gw A redirects host to gw B
c. gw A now has no more buffers, drops pkt
d. host ignores redirect
e. go to a
The IP spec does imply some effort be made to forward a redirected packet, but
I interpret the priority to be higher to get the redirect to the host, and
only secondary that the packet be forwarded.
Mike Brescia,
BBNCC gateway groupKASTEN@MITVMA.MIT.EDU (Frank Kastenholz) (05/17/88)
>From: Mike Brescia <brescia@PARK-STREET.BBN.COM> > > <from kasten@mitvma.mit.edu> > a certain well known computer company has made a network package for PC's > and PS/2's that does not understand ICMP redirect. > >This is an interesting turn. What if they try to send to a gateway that does >not forward packets which needed redirect. > a. host sends to gw A > b. gw A redirects host to gw B > c. gw A now has no more buffers, drops pkt > d. host ignores redirect > e. go to a >The IP spec does imply some effort be made to forward a redirected packet, but >I interpret the priority to be higher to get the redirect to the host, and >only secondary that the packet be forwarded. If this occurs then I imagine that the host will remain mute for all eternity. I was not able to try anything like this though - we are just going to tell our customers that "Here is a failure mode that we (ATEX) can not fix - so if it occurs, ......." We have aother PC based (using the P.D. MIT PC/IP code) product that will have "multiple default" gateways, as was discussed on the list earlier. The transport/application layer will ask IP to try another route in the event of excessive transmission errors (i.e. no receipt of an ACK) Cheers Frank Kastenholz Atex/EPPS - a Kodak Company All opinions are mine and in no way belong to Atex/EPPS/Kodak (in fact they don't even know that I am saying this)
Doug_Nelson@UM.CC.UMICH.EDU (05/17/88)
> As far as I know, "Proxy ARP" only works with subnets, for nodes that > don't know about subnets. In order to send out the ARP request, the > host has to already belive that he can get to the remote host in one > hop. If my machine is on net 128.62, and I want to get to a machine on > net 128.63, I don't send out an ARP request for the machine on net 128.63. > I have to have a route to 128.63 which points to a machine on net 128.62, > and then I'll be ARPing for the machine on 128.62 which is the next hop to > 128.63. Proxy ARP also works in networks where the gateway(s) aren't using any routing protocol at all. We teach many of our systems here that the default route is to themself, with a metric of zero. This forces an ARP for most hosts outside the (sub)network, whether within or outside the full network. It helps that we only have one gateway to the outside world. Doug Nelson, Michigan State University, Computer Lab den@serv1.cl.msu.edu
cire@clash.cisco.COM (05/18/88)
>> Date: Sat, 14 May 88 20:47:14 EDT >> From: Jeffrey I. Schiller <jis@BITSY.MIT.EDU> >> To: KASTEN@MITVMA.MIT.EDU >> Cc: jqj@HOGG.CC.UOREGON.EDU, tcp-ip@SRI-NIC.ARPA >> Subject: Re: Dumb vs. smart host routing >> >> ... >> >> simplified the question from "Who can route to network X?" to just a >> simple request for a default router. That router can then send >> redirects later when packets arrive.] >> >> -Jeff A reasonable idea. It still requires the hosts involved to implement some kind of redundancy mechanism if the default router goes down. But it would not have to know about routing just that it needs to find a new default. -c cire|eric Eric B. Decker cisco Systems Menlo Park, California email: cire@cisco.com uSnail: 1360 Willow Rd., Menlo Park, CA 94025 Phone : (415) 326-1941
srg@quick.COM (Spencer Garrett) (05/18/88)
Why can't a host just ARP for any destination and expect the appropriate gateway(s) to answer? If there were a hopcount field in the ARP record, I think this would solve all the problems.
hedrick@athos.rutgers.edu (Charles Hedrick) (05/20/88)
Proxy ARP can be used for all routing, not just subnet routing. The idea is to give your hosts default routes that tell them to treat everything as on the local cable. This is done in Unix by doing route add 0.0.0.0 YOURADDRESS 0 where YOURADDRESS is the Internet address associated with your Ethernet interface (if you have more than one, the one you want used as default). By using a metric of 0, you tell the system to treat this route as on the local cable, so it issues ARP's rather than using a gateway. It is of course possible that some TCP/IP implementations don't have an equivalent kludge, but many of them seem to.
tcs@USNA.MIL (Terry Slattery) (05/26/88)
> Second, the software should have the list of default gateways that I keep > bringing up rather than just one. The folks at BRL have done just that in some user mode software that they cooked up during the times when RIP was still being developed. They ping the list of gateways with a long time constant to get a metric on which ones are up and what the error rate is to them. (Remember, this is only done on the local network where the ping loading is deemed necessary to support the dynamic reconfiguration.) If the primary gateway goes down, the user mode process performs a system call (Unix 4.2/3) to change the default route to one of the secondary gateways. The primary gateway is still pinged. When it comes back up (or the loss rate becomes acceptable), the pings are increased in frequency to get a better indication of the link's operation. If everything still looks good, the kernel is told to switch back to the primary gateway. This type of dynamic routing could be put to good use in systems like the Excelan VMS product. -tcs