// PupRoute.bcpl -- Module implementing the Pup Routing Table // Copyright Xerox Corporation 1979, 1982 // Last modified September 24, 1982 4:13 PM by Taft get "Pup0.decl" get "Pup1.decl" get "PupRoute.decl" external [ // outgoing procedures GatewayListener; LocateNet RTLookup; RTEnumerate; RTInsert; RTDelete // incoming procedures Forwarder; ForwarderCtx SetTimer; TimerHasExpired; Dismiss; Min ReleasePBI; GetPBI; CompletePup Allocate; Zero; SetBlock; MoveBlock; Enqueue; Dequeue HLookup; HEnumerate; HInsert; HDelete // outgoing statics pupRT; gatewayListenerSoc // incoming statics ndbQ; pupZone ] static [ pupRT; gatewayListenerSoc ] // This module plugs into GateForward.bcpl - the Gateway Forwarder, // or into PupDummyGate, if this isn't a gateway. // Routing table maintenance: // The routing table is treated as a cache of recently-used routing // information. It is implemented as a fixed-length queue of RTQIs // (routing table queue items), each of which contains an RTE. // Lookups are implemented simply by searching the queue. Each successful // lookup causes the associated RTE to be promoted to the front of the queue, // thereby speeding subsequent lookups of the same net. A new entry is // inserted by taking an RTE off the end of the queue and re-using it. // The GatewayListener maintains all existing RTEs, and adds new ones // only if free RTEs happen to exist. When a higher-level caller // (e.g., RoutePup) requires a route to a net for which there is no RTE, // it calls LocateNet, which creates a new RTE and initiates a routing probe. // Conventions: // A free RTE is represented by net = rtFreeEntry. // All free RTEs are maintained at the end of the queue. // RTEs for directly-connected networks are never deleted. // An RTE that has been created in response to LocateNet but not yet // filled in has hops = maxHops+1 and ndb = 0. //---------------------------------------------------------------------------- let LocateNet(net) = valof //---------------------------------------------------------------------------- // Externally-called procedure that attempts to locate a route to a net. // If a route is known, returns the RTE for it; if not, initiates activity // to attempt to locate the desired route and returns zero. [ let rte = HLookup(pupRT, net) if rte ne 0 & rte>>RTE.hops le maxHops then resultis rte if rte eq 0 then [ // No RTE exists. Insert an RTE for net so as to get it into the cache rte = HInsert(pupRT, net) rte>>RTE.hops = maxHops+1 SetTimer(lv rte>>RTE.timer, 3000) // Delete in 30 sec if no route found ] // initiate a probe for routing information. pupRT>>RT.probeCount = 10 // try 10 times SetTimer(lv pupRT>>RT.probeTimer, 0) resultis 0 ] //---------------------------------------------------------------------------- and RTLookup(rt, net, dontPromote; numargs na) = valof //---------------------------------------------------------------------------- // Returns pointer to RTE for net, or zero if not found. // Moves the matching RTE to the head of the queue unless dontPromote. [ // See whether head item is the one we want; if so, return it quickly. let rtqi = rt>>RT.head if net eq rtqi>>RTQI.rte.net resultis lv rtqi>>RTQI.rte // Search queue for matching rte [ // repeat let nrtqi = rtqi>>RTQI.next if nrtqi eq 0 resultis 0 // not found if net eq nrtqi>>RTQI.rte.net then [ // found matching RTE (nrtqi) unless na ge 3 & dontPromote do [ // promote it to the head of the queue rtqi>>RTQI.next = nrtqi>>RTQI.next if rtqi>>RTQI.next eq 0 then rt>>RT.tail = rtqi nrtqi>>RTQI.next = rt>>RT.head rt>>RT.head = nrtqi ] resultis lv nrtqi>>RTQI.rte ] rtqi = nrtqi ] repeat ] //---------------------------------------------------------------------------- and RTEnumerate(rt, Proc, arg) be //---------------------------------------------------------------------------- // Calls Proc(rte, arg) for every valid entry in rt [ let rtqi = rt>>RT.head [ if rtqi>>RTQI.rte.net ne rtFreeEntry then Proc(lv rtqi>>RTQI.rte, arg) rtqi = rtqi>>RTQI.next ] repeatwhile rtqi ne 0 ] //---------------------------------------------------------------------------- and RTInsert(rt, net) = valof //---------------------------------------------------------------------------- // Returns pointer to an RTE where net can be inserted. // net is in the net field and the rest of the RTE is zeroed. [ let rte = HLookup(rt, net) if rte eq 0 then [ // Not found, grab the tail item and put it at the head. // n.b. Do not allow RTEs for directly-connected networks to be deleted. rte = HLookup(rt, rt>>RT.tail>>RTQI.rte.net) ] repeatwhile rte>>RTE.net ne rtFreeEntry & rte>>RTE.hops eq 0 Zero(rte, lenRTE) rte>>RTE.net = net resultis rte ] //---------------------------------------------------------------------------- and RTDelete(rt, net) be //---------------------------------------------------------------------------- [ let rte = HLookup(rt, net) if rte ne 0 then [ // Mark RTE deleted and put it at the end of the queue. // n.b. we know it is at the head now, because RTLookup put it there. rte>>RTE.net = rtFreeEntry Enqueue(lv rt>>RT.head, Dequeue(lv rt>>RT.head)) ] ] //---------------------------------------------------------------------------- and GatewayListener() be //---------------------------------------------------------------------------- // This process listens for gratuitous routing table broadcasts from // gateways and updates our local routing table. // If we are a gateway, also listens for gateway info requests // and responds appropriately. // Purges routing table entries that haven't been updated recently. // Generates gateway routing info probes if required. [ let updateTimer = nil; SetTimer(lv updateTimer, 0) [ if TimerHasExpired(lv updateTimer) then [ //every 15 seconds age the RT entries RTEnumerate(pupRT, AgeRTE, pupRT) SetTimer(lv updateTimer, 1500) ] while gatewayListenerSoc>>PupSoc.iQ.head ne 0 do [ let pbi = Dequeue(lv gatewayListenerSoc>>PupSoc.iQ) test pbi>>PBI.pup.type eq ptRouteReply ifso test pbi>>PBI.pup.sPort.host ne pbi>>PBI.ndb>>NDB.localHost ifso ProcessRouteInfoReply(pbi) //ignore our own bcsts ifnot ReleasePBI(pbi) ifnot Forwarder(pbi) // maybe the gateway knows how to handle it ] if pupRT>>RT.probeCount gr 0 & TimerHasExpired(lv pupRT>>RT.probeTimer) then [ //broadcast a routing info request on each directly-connected network let pbi = GetPBI(gatewayListenerSoc, true) if pbi ne 0 then [ pbi>>PBI.allNets = true CompletePup(pbi, ptRouteRequest, pupOvBytes) SetTimer(lv pupRT>>RT.probeTimer, 200) // 2 seconds pupRT>>RT.probeCount = pupRT>>RT.probeCount-1 ] ] // If this is a gateway, let it forward some packets. // This is a call to Dismiss(1) if no forwarder is present. ForwarderCtx(1) ] repeat ] //---------------------------------------------------------------------------- and AgeRTE(rte, rt) be //---------------------------------------------------------------------------- if rte>>RTE.hops ne 0 & TimerHasExpired(lv rte>>RTE.timer) then test rte>>RTE.recent ifso //first timeout, make entry eligible for replacement [ rte>>RTE.recent = false SetTimer(lv rte>>RTE.timer, rtTimeoutInterval) ] ifnot HDelete(rt, rte>>RTE.net) //second timeout, purge entry //---------------------------------------------------------------------------- and ProcessRouteInfoReply(pbi) be //---------------------------------------------------------------------------- // Update local RT with stuff in ImAGateway pup. // Note that the identity of the directly connected net has already been // established in PupLevel1, if it wasn't previously known. Here we update // our rt as appropriate with each of the 4-byte info blocks in the Pup. [ let net = pbi>>PBI.pup.dPort.net //directly connected net let host = pbi>>PBI.pup.sPort.host //gateway host on net if net ne 0 & pbi>>PBI.pup.sPort.socket^1 eq 0 & // Just being suspicious... pbi>>PBI.pup.sPort.socket^2 eq psRouteInfo then [ pupRT>>RT.probeCount = 0 for c = 1 to pbi>>PBI.pup.length-pupOvBytes by 4 do [ // Compute our hop count to target net via this gateway. let hops = Min(pbi>>PBI.pup.bytes^(c+3), maxHops)+1 // Look up target net in RT. net = pbi>>PBI.pup.bytes^c let rte = HLookup(pupRT, net, true) test rte eq 0 ifso [ // Target net not in RT. // If target net is inaccessible, don't insert new RTE for it. // Otherwise, insert new RTE only if a free RTE is available. if hops gr maxHops loop if pupRT>>RT.tail>>RTQI.rte.net ne rtFreeEntry loop rte = HInsert(pupRT, net) // Sets entire rte to zero ] ifnot // Target net already in RT. If directly connected, do nothing. if rte>>RTE.hops eq 0 loop // Update rt entry with this info block if // (1) an rte didn't previously exist for this net, or // (2) the existing entry has timed out (recent = false), or // (3) the new gateway net/host is the same as in the rte, or // (4) the new route has fewer hops than the existing one. // Note that if (1) was true, a new rte will have been created (above), // with contents zeroed out, which will satisfy (2) here. if rte>>RTE.recent eq false % // (2) pbi>>PBI.ndb eq rte>>RTE.ndb & host eq rte>>RTE.host % // (3) hops ls rte>>RTE.hops then // (4) [ // Note whether anything has really changed. unless hops eq rte>>RTE.hops do pupRT>>RT.changed = true // Insert route into rte. rte>>RTE.host = host //via gateway host rte>>RTE.ndb = pbi>>PBI.ndb //RT->ndb rte>>RTE.hops = hops // Reset rte timeout only if the target net is now accessible. // The idea is to cause permanently inaccessible nets eventually // to be purged. Actually, in non-gateway hosts, we could purge // inaccessible nets immediately; however, knowledge of a network's // inaccessibility must be remembered for a while by gateway hosts // and passed among them explicitly so that alternate routes will // be discovered quickly. if hops le maxHops then [ rte>>RTE.recent = true //recently updated SetTimer(lv rte>>RTE.timer, rtTimeoutInterval) ] ] ] ] ReleasePBI(pbi) ]