Copyright Xerox Corporation 1979Inter-Office MemorandumToCommunication ProtocolsDateMay 29, 1979FromEd TaftLocationPARC/CSLSubjectCaching Pup routing informationFile[Maxc1]CacheRoute.bravoXEROX Attributes:informal, technical, Alto, Distributed computingAbstract:A technique is described by means of which non-gateway hosts may maintain a minimum amount ofinternetwork routing information, without loss of generality, through use of a cache.While working on the Bcpl Pup package recently, I noticed that the size of the Pup internet(somewhere around 25 networks) was once again approaching the compiled-in size of the Puprouting table (32 entries this time). For implementation reasons, the number of entries in this tablehad to be a power of two. At four words per entry, increasing the size of the table to 64 entrieswould have caused it to consume an entire page of Alto memory.Such an increase would be wasteful, since on any given Alto only a small number of routes are inuse at one time. This seemed like a good opportunity to put into practice various ideas aboutcaching routing information that have emerged from conversations among Dave Boggs, Hal Murray,Yogen Dalal, myself, and undoubtedly others.I have implemented a routing information cache that will be included in the next release of the BcplPup package. This memo describes the basic mechanisms, presents some relatively subtle issues thatcame to light during implementation, and touches on some possible variations to the strategies.Pup routing algorithm and routing update protocolA general overview of the Pup routing procedures may be found in [1], and the detailed protocolspecifications are contained in [2] and [3]. The routing protocols are divided into two parts: arouting algorithm that is applied to every outgoing Pup to direct it closer to its ultimate destination,and a routing update protocol by means of which dynamic routing information is maintained anddistributed.Internetwork routingEach host (gateways included) executes a routing procedure on every outgoing Pup. This proceduredecides, as a function of the Pup destination port field, upon which directly-connected network thePup is to be transmitted (if there is more than one choice), and it yields an immediate destinationhost which is the address on that network of either the ultimate destination or some gatewaybelieved to be closer to the destination. As a Pup travels through the internet, each router employsthe same algorithm based on local routing information, and each Pup is routed independently.Under this organization, every host must maintain a local routing table containing an entry for eachnetwork to which the host might wish to direct Pups. For the purposes of routing Pups, each entrymust either identify a network as being directly-connected or specify the address (network and hostnumbers) of a gateway on a directly-connected network. This information changes over timethrough the actions of the routing update protocol. &pX]g~qi cr]pX-r5`p \r]p-r5`p Vr]p-r5`Osp LUr  p0 Ir $9 HVU Bp/, A+U ?f >!3/ <> 9` 82A 6V 5(, 2CG 0P /9O *t1 'pB &B#> $up0' #8u p@ ! u p01 9 up  2u p; M |M 31 '; :) < 3 >Qd 5Caching Pup routing information2Routing information updateRouting information is maintained in a manner very similar to the Arpanet-style adaptive procedures[4]. Each gateway periodically broadcasts on every directly-connected network a Pup containing acopy of its own routing table. Other gateways that hear such a broadcast use the information in itto update their own local routing tablesspecifically, to incorporate new routes to networks orinvalidate old routes to inaccessible networks as the internetwork topology changes.With this arrangement, each gateway must maintain and distribute a routing table containing entriesfor every network known to be accessible. The routing information must include some measure ofthe quality of the route; the metric presently used is a fairly primitive one based on hop counts, butincorporating a better one based on delay or throughput would be a straightforward extension.Since gateways broadcast their routing tables, non-gateway hosts on directly-connected networks canalso hear these broadcasts and maintain their own routing tables in a similar manner. Indeed,existing implementations of the routing table maintenance procedures are identical for gateway andnon-gateway hosts. (It is perhaps worth mentioning that at the basic Pup level, gateway and non-gateway hosts differ in only two respects: gateways forward Pups whereas non-gateway hosts simplydiscard Pups not addressed to them, and gateways both send and receive routing information Pupswhereas non-gateways only receive them.)A host may also broadcast a request for routing information and receive immediate responses fromevery gateway on the directly-connected network. This permits quick initialization of a host'srouting table when it comes upa frequent event for most Altosas opposed to waiting for thenext periodic routing information broadcast.The routing information cacheAgainst this background, we desire to minimize the amount of routing information that individualnon-gateway hosts must maintain locally. (We will consider extending this to gateway hosts later.)The obvious approach is for a host to maintain a cache of routing entries for those networks towhich clients within the host are sending Pups; the number of such networks is quite small at anygiven time.Cache maintenanceSince connections (or virtual circuits'') are not maintained at the Pup internet level but rather areartifacts of higher-level, end-to-end protocols, the routing table maintenance algorithms must operateentirely on the basis of information gained during the Pup routing process itself. (This informationcan be augmented by hints provided by client programs, but the existence of such hints must neverbe depended upon.)Thus, for each outgoing Pup, the router looks up the destination network in the cache. If an entryfor that network is present, it is used to route the Pup. If no such entry exists, the Pup is discardedand activity is initiated to locate the network; specifically, a routing information request is broadcast.A dummy cache entry is created for the new network, possibly displacing the least recently usedentry for some other network.The routing information update procedure, upon receiving a routing table Pup from some gateway,updates the existing entries in its cache with the corresponding information from the Pup anddiscards the remainder of the routing table. fpG bu _9p21 ]O \/c Z!> Y%T V@5. Tup H S6$B Q= Nc MGE K^ J=I H*7 G3'8 E( BE ADS ?L >:, 9t 6p` 5C): 30/ 29K 0 ,u *pX (f ' 23 %"? $ !Z "F #G K   $.1 A , F ?/S7/Caching Pup routing information3Details and pitfallsThe cache is arranged in order from most to least recently used to permit the replacement algorithmto work properly. It is acceptable to use a relatively simple structure to represent the cache, e.g., aqueue, since in a machine with only a small number of simultaneous active connections, the relevantentries will almost always be near the front of the queue.Use of an entry to route a Pup causes the entry to be promoted to the front of the queue (unless itis already at the frontwhich it is usually is). Note, however, that the routing update procedureshould not change the order of the entries.Care must be taken not to permit entries for directly-connected networks to be displaced from thecache (though they may be demoted in the ordering due to lack of use), since a host must alwaysknow the identity of the networks to which it is connected in order to send Pups outside thosenetworks.The routing table update procedure may be improved further, as follows: after receiving a routingtable Pup and updating existing entries in the cache, it then fills in any empty cache entries withinformation about other networks in the order they appear in the Pup. Assuming the entries in thePup are ordered according to how recently they were used by the gateway that sent the Pup, this hasthe beneficial effect of initializing a host's cache with entries for the networks accessed most activelyfrom within the local area.Given this modification, a gateway may use precisely the same routing table management algorithmso long as its cache is large enough to hold entries for the entire accessible internet.An externally-callable procedure called LocateNet is provided to permit clients to pass hints aboutnetworks they expect to send Pups to in the near future. LocateNet performs the same actions asthe router (described previously) if no entry for the specified network is present in the cache. Thisfacility is used, for example, within the Name Lookup Protocol module, since the address returnedby a name lookup is almost always used to initiate a conversation.Degenerate implementationsA much simpler mechanism is usable in specialized applications where it is known that there will beonly one active conversation at a time. In this case, the cache may in effect consist of a single entrycorresponding to the network of the other partner in the conversation. (Of course, the router mustalso keep information about the identity of the directly-connected networks.) This is precisely thetechnique used in the existing TeleSwat user implementation.A further simplification is employed in certain very primitive servers that never send Pupsspontaneously but only in response to request Pups. When generating a response to a Pup, such aserver simply uses the immediate source network and host (i.e., the host that sent the Pup over itsfinal hop) as the immediate destination network and host for the response. This takes advantage ofthe assumption that the reverse of the route taken by the request Pup is an acceptable route for theresponse; it does not require processing routing information Pups at all. This technique is used bythe TeleSwat server, the EFTP receiver used in the Alto bootstrap process, the Spruce status server,and others.Future workIt is clear that a similar technique could be used to maintain routing caches (as opposed to completerouting tables) in gateway hosts. The routing update protocol would have to be changed so that ahost could request information about a specific network rather than only obtain the full internetrouting table as it does at present. A gateway receiving such a request for a network not in its owncache would in turn interrogate all its neighboring gateways, and the request would propagatethrough the internet until the desired network had been located. The resulting routing informationwould thereafter be retained in the caches of all gateways lying along the best route, so long as the fpG bu _9pK ]f \/J Z: WZ V@#? Tup! QH PQ5* N^ MG JbY HJ GX[ E\ DNT B ?*6 >_X ;zW 9` 8p-9 6.3 5fB 1u .pD -CI +O *9[ (< %K $JT "'< !@@# 22 6O rp2 , t p` 5_ O +V R !I *; U>/]]Caching Pup routing information4route continued to be used.Extending the routing cache strategy in this manner introduces several additional problems. Thefirst is that of properly controlling what is in effect an internet broadcast, i.e., to prevent unboundedregeneration of the request. There is a known technique for accomplishing this, called reverse-pathforwarding [5], but it depends on all nodes having complete and more-or-less consistent routingtablesthe very requirement we are trying to eliminate. Second, in a large internet such broadcastswould be extremely costly. Third, a route that had been discovered by such means would notthereafter be replaced automatically by better routes as it is at present, since information aboutreaching a particular network would tend to remain only in the caches of gateways along the routethat was actually being used.David Boggs is working on some techniques for finding and maintaining routes in a large internet.In the meantime, the Pup design requires that gateways maintain and distribute complete routingtables but permits non-gateway hosts to cache subsets of the routing information that they require.References[1]D. Boggs, J. Shoch, E. Taft, and R. Metcalfe, Pup: "An Internetwork Architecture", file[Maxc1]PupPaper.press.[2]E. Taft and R. Metcalfe, "Pup Specifications", file [Maxc1]PupSpec.press.[3]E. Taft, "Gateway Information Protocol", file [Maxc1]GatewayInformation.press.[4]J. McQuillan, Adaptive Routing Algorithms for Distributed Computer Networks, HarvardPh.D. thesis, Report no. 2831, Bolt Beranek and Newman, May 1974.[5]Y. Dalal and R. Metcalfe, "Reverse Path Forwarding of Broadcast Packets", CACM, vol. 21no. 12, December 1978. fpG b _93- ] \ \/(0u Z p1$ Y%@$ W$7 VJ T W S P,a NN M"P Ht EpCD+ AFN >aS ;| u"p9A 7Bvp5 5F?/2 TIMESROMAN  TIMESROMAN  TIMESROMANLOGO TIMESROMAN  TIMESROMAN  TIMESROMAN  N j/#!cacheroute.bravoTaftSeptember 3, 1979 5:35 PM