Copyright Xerox Corporation 1979Inter-Office MemorandumToCommunication ProtocolsDateMay 30, 1979FromEd TaftLocationPARC/CSLSubjectGateway Information ProtocolFile[Maxc1]GatewayInformation.press(revised)XEROX Attributes:technical, Distributed computingAbstract:The Gateway Information Protocol is the means by which a host discovers the identity of its directlyconnected network(s) and locates gateways to other networks. This memo documents the protocol, presentsalgorithms for implementing it, and discusses some of its strengths and weaknesses.The Gateway Information Protocol is the means by which a host discovers the identity of its directlyconnected network(s) and locates gateways to other networks. This topic is discussed at some lengthin another document [1]. This memo describes the actual protocol and algorithms presentlyemployed for dealing with it.The protocolAll gateway hosts implement a server on socket 2 that responds to requests for gateway information.Gateway Information RequestPup Type: 200 (octal)Pup ID: arbitraryPup Contents: noneGateway Information ResponsePup Type: 201 (octal)Pup ID: same as in Request PupPup Contents: one or more groups of four bytes, each providing routing information forone network, as follows: In each group, the first byte specifies the target network number. If the gateway host isdirectly connected to that network, then the is zero and the and describe the gateway's connection to the network.If the gateway host is not directly connected to the target network, then the second andthird bytes give the network and host numbers of another gateway through which theresponding gateway routes Pups to that network, and the fourth byte gives the hop count,i.e., the number of additional gateways (not including itself) through which the respondinggateway believes a Pup must pass to reach the specified network. A hop count greater thanthe constant maxHops (presently 15) signifies that the target network is believed to beinaccessible.It should be noted that the and bytes are not required by the routing &pX]g~qi cr]pX-r5`p \r]p-r5`p Vr]p-r5`$]TpOsp LUr  p Ir 04 HV=+ GS Asp=' ?d >i#7 < 9+tX 6FpJ3at0|p.-r*t'p&#$E# 45OB8"E@`B0"VC>LJ tpCB ]J>Qd Gateway Information Protocol2table update algorithms. They are present for observation and debugging purposes.Each gateway host must also periodically broadcast Gateway Information Pups, as described above,on all directly-connected networks. The frequency of this broadcast should be approximately oneevery 30 seconds, and immediately whenever the gateway's own routing table changes (see below).These Pups should be sent from socket 2 to socket 2.Routing table maintenanceThe following algorithms are presently used in all hosts, including gateways, for maintaining localrouting tables. These algorithms serve two purposes:1.To permit quick initialization of the local routing table when a host starts running Pup-basedsoftware.2.To ensure that the local routing table remains up-to-date as inter-network topology changes(i.e., gateways come up or go down).The local routing table contains an entry for each network to which it is believed to be possible toroute Pups. (It is possible for a non-gateway host to maintain a subset of this routing table in theform of a cache, as discussed in a separate memo [2].) Each entry contains a hop count, the networkand host numbers of a directly-connected gateway (if the hop count is nonzero), and a timeout usedin the routing table maintenance algorithm. At initialization time, the routing table in a normal(non-gateway) host is empty; in a gateway host, it contains entries for all directly-connected networks(recall that gateway hosts must know the identity of all directly-connected networks).When a Gateway Information Pup is received (either in response to the host's initial GatewayInformation Request or gratuitously), the following procedure is used to process each four-byte entryin the Pup and update the local routing table. The network to which the entry refers (i.e., the onewhose number is the first byte of the four-byte group) is referred to below as the target network.First, a decision must be made whether or not it is appropriate to update the local routing tableentry with the new information. If the target network is known to be directly connected (i.e., itexists in the local routing table with a hop count of zero), then no update is necessary. Otherwise,the update should be performed if any of the following conditions is true:1.No entry for the target network presently exists in the local routing table.2.The Gateway Information Pup's source address (network and host) is the same as thegateway address in the existing local routing table entry; that is, we are receiving updatedinformation from the very gateway through which we are already routing Pups destined forthe target network.3.The existing entry in the local routing table has not been updated for some time, suggestingthat it may no longer be valid. The timeout interval presently used is 90 seconds.4.The hop count from the Gateway Information Pup, plus one, is less than the hop count inthe existing local routing table entry; that is, the new information describes a means ofreaching the target network through fewer intervening gateways than does the existing localrouting table entry.If any of these conditions holds, then the local routing table entry is updated (or a new one created)as follows:1.The gateway network and host numbers in the entry are set to the source of the GatewayInformation Pup.2.The hop count in the entry is set to the Gateway Information Pup's hop count plus one. Ifthis results in a hop count greater than maxHops, then the target network is deemed to have fpXG bR _9` ]D \/!> Z4 VtX T p V R5O+3NK8[I$ F[ EI6/ C+9 B?8* @\ ?5^ =tp7 :\ 9F@% 7N 6<Rt p 3W?" 1b 0MN .J+L(5'yF%2&$o!G L T'2U >( ' B9 F S)tp* ?/\RGateway Information Protocol3become inaccessible.3.The entry's timeout is reset to 90 seconds.In addition to processing Gateway Information Reply Pups, the routing table management softwarealso periodically checks for routing table entries that have not been updated for so long that they arealmost assuredly not valid. The timeout used for this is presently 3 minutes, or twice the 90-secondinterval after which the above algorithm deems an entry to be suspect. Entries not updated for 3minutes are simply purged from the routing table.Additional gateway proceduresWhen a gateway host's routing table changes, the gateway should immediately broadcast a GatewayInformation Pup reflecting the updated routing table, rather than waiting for the next periodicrouting broadcast. This is so that changes in topology will propagate through the internetimmediately rather than at a rate limited by the frequency of normal routing broadcasts.The criteria for what constitutes a change'' are important; incorrect choices may lead to oscillationor regenerative propagation of routing information. A gateway should immediately rebroadcast itsrouting table after updating it only in the following cases:1.A formerly inaccessible network became accessible;2.A formerly accessible network became inaccessible;3.The hop count for some network changed.In particular, a rebroadcast should not occur due to changing an entry to route through a differentgateway with the same number of hops as before.When a formerly accessible network becomes inaccessible, the gateway should continue to includethe entry (with a hop count of maxHops+1, of course) in the routing tables it broadcasts during thenext timeout interval (90 seconds). This ensures that knowledge of the network's inaccessibility willpropagate through the internet quickly.When a gateway is about to go down voluntarily, it should broadcast several Gateway InformationPups in which all entries are marked inaccessible (i.e., hop count of maxHops+1), but then continueto forward Pups for a few seconds. This ensures that if alternate routes exist they will be foundimmediately rather than as a result of timeout.Remarks on the protocolThe protocol and algorithms described above are adequate for maintaining routing information in aninternetwork whose topology changes relatively infrequently. Because the routing table updatealgorithms are based on hop counts, they are stable while the internetwork topology is unchanging.And because changes are propagated immediately, the algorithms respond quickly when gatewayscome up or go down.Routing changes caused by a gateway coming up are propagated immediately, i.e., at a rate notdetermined by timeouts but rather limited only by the store-and-forward propagation delay from thesource of the change to each host along the shortest path. The change gives rise to a number ofadditional routing table broadcasts bounded by the number of single-hop paths between pairs ofgateways in the internet.When a gateway goes down voluntarily, the change in routing information also propagatesimmediately. In an ideal situation, where routing tables were passed around at a constant rate andsynchronously, the change would propagate away from the gateway along the reverse of all routesdirected through that gateway, invalidating such routes as it went. If another valid route to anetwork reached through that gateway existed, the change would stop propagating as soon as it fpXGb_9+ \TE Z$C YJJ WI V@1 RtX OpK N_ LR KX H.O FE E$<B?2?Z2PupName.press.[2]E. Taft, Caching Pup Routing Information,'' file [Maxc1]CacheRoute.press.[3]J. McQuillan, Adaptive Routine Algorithms for Distributed Computer Networks, HarvardPh.D. thesis, Report no. 2831, Bolt Beranek and Newman, May 1974. fpXG bX `_ _ \/RGS ZL Y%@ WJ V)2 T] S2 P,F N*: M"W K?* JV H EK D)G BE?9<?;U(8pM 6)4O2U0H/w-.-G *9t 'TpO $oP ! t=p A ?/HL TIMESROMAN  TIMESROMAN  TIMESROMANLOGO TIMESROMAN    j/#!gatewayinformation.bravoTaftSeptember 3, 1979 5:38 PM