// 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)
]