DIRECTORY BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds], CommDriver USING [GetNetworkChain, InsertReceiveProc, Network], Endian USING [CardFromF, CardFromH, HFromCard], XNS USING [Address, broadcastNet, GetThisHost, Host, Net, Socket, unknownAddress, unknownHost, unknownNet, unknownSocket], XNSBuf USING [Buffer], XNSErrorTypes USING [protocolViolationErr], XNSRouter USING [Hops, RoutingTableEntry, unreachable], XNSRouterPrivate USING [EventProc, TakeThis], XNSRoutingBuf USING [Buffer, hdrBytes, maxBytes, maxTuples, NumTuplesFromUserBytes, Tuple, UserBytesFromNumTuples], XNSSocket USING [AllocBuffer, Broadcast, Create, dontWait, FixupSourceAndDest, FreeBuffer, Get, GetUserBytes, Handle, Milliseconds, ReturnError, Send, SetGetTimeout, SetUserBytes], XNSWKS USING [routing]; XNSRouterImpl: CEDAR MONITOR IMPORTS BasicTime, CommDriver, Endian, XNS, XNSRouterPrivate, XNSRoutingBuf, XNSSocket EXPORTS XNSRouter, XNSRouterPrivate ~ { Net: TYPE ~ XNS.Net; Host: TYPE ~ XNS.Host; Socket: TYPE ~ XNS.Socket; Address: TYPE ~ XNS.Address; NetGT: PROC [x,y: Net] RETURNS [BOOL] ~ TRUSTED INLINE { RETURN [ Endian.CardFromF[LOOPHOLE[x]] > Endian.CardFromF[LOOPHOLE[y]] ] }; unknownHost: Host ~ XNS.unknownHost; unknownNet: Net ~ XNS.unknownNet; broadcastNet: Net ~ XNS.broadcastNet; unknownSocket: Socket ~ XNS.unknownSocket; unknownAddress: Address ~ XNS.unknownAddress; thisHost: Host ~ XNS.GetThisHost[]; Network: TYPE ~ CommDriver.Network; Hops: TYPE ~ XNSRouter.Hops; unreachable: Hops ~ XNSRouter.unreachable; Pulses: TYPE ~ BasicTime.Pulses; Msecs: TYPE ~ XNSSocket.Milliseconds; PulsesSince: PROC [then: Pulses] RETURNS[Pulses] ~ INLINE { RETURN [BasicTime.GetClockPulses[] - then] }; sweepSeconds: CARDINAL ~ 15; sweepPulses: Pulses ~ BasicTime.MicrosecondsToPulses[ LONG[sweepSeconds] * 1000000 ]; suspectSweeps: CARDINAL ~ 6; invalidSweeps: CARDINAL ~ 12; numHashHeaders: CARDINAL ~ 300; HashIndex: TYPE ~ [0 .. numHashHeaders); RoutingTable: TYPE ~ REF RoutingTableRep; RoutingTableRep: TYPE ~ ARRAY HashIndex OF RoutingEntry; RoutingEntry: TYPE ~ REF RoutingEntryObject; RoutingEntryObject: TYPE ~ RECORD [ next: RoutingEntry, sortedNext, sortedPrev: RoutingEntry, dest: Net, hops: Hops, network: Network, immediate: Host, sweepsSinceRefresh: CARDINAL]; routingTable: RoutingTable ~ NEW[RoutingTableRep]; sortedHead: RoutingEntry _ NIL; Hash: PROC [net: Net] RETURNS [HashIndex] ~ TRUSTED INLINE { RETURN [ Endian.CardFromF[LOOPHOLE[net]] MOD numHashHeaders ] }; FindEntry: PROC [net: Net] RETURNS [eH: RoutingEntry] ~ INLINE { FOR eH _ routingTable^[Hash[net]], eH.next WHILE (eH # NIL) AND (eH.dest # net) DO NULL ENDLOOP; RETURN [eH] }; additions: INT _ 0; AddEntry: PROC [newH: RoutingEntry] ~ { h: HashIndex ~ Hash[newH.dest]; prevH, leftH, rightH: RoutingEntry _ NIL; additions _ additions.SUCC; IF Monitoring[] THEN PostEvent[newH~newH]; rightH _ sortedHead; WHILE (rightH # NIL) AND NetGT[newH.dest, rightH.dest] DO leftH _ rightH; rightH _ rightH.sortedNext; ENDLOOP; newH.next _ routingTable^[h]; routingTable^[h] _ newH; newH.sortedPrev _ leftH; newH.sortedNext _ rightH; IF rightH # NIL THEN rightH.sortedPrev _ newH; IF leftH # NIL THEN leftH.sortedNext _ newH ELSE sortedHead _ newH; }; replacements: INT _ 0; ReplaceEntry: PROC [newH: RoutingEntry, oldH: RoutingEntry] ~ { h: HashIndex ~ Hash[newH.dest]; prevH: RoutingEntry _ NIL; replacements _ replacements.SUCC; IF Monitoring[] THEN PostEvent[oldH~oldH, newH~newH]; FOR temp: RoutingEntry _ routingTable^[h], temp.next WHILE temp # oldH DO prevH _ temp ENDLOOP; newH.next _ routingTable^[h]; routingTable^[h] _ newH; IF prevH # NIL THEN prevH.next _ oldH.next ELSE newH.next _ oldH.next; IF (newH.sortedPrev _ oldH.sortedPrev) # NIL THEN newH.sortedPrev.sortedNext _ newH ELSE sortedHead _ newH; IF (newH.sortedNext _ oldH.sortedNext) # NIL THEN newH.sortedNext.sortedPrev _ newH; }; deletions: INT _ 0; DeleteEntry: PROC [oldH: RoutingEntry] ~ { h: HashIndex ~ Hash[oldH.dest]; prevH: RoutingEntry _ NIL; deletions _ deletions.SUCC; IF Monitoring[] THEN PostEvent[oldH~oldH]; FOR temp: RoutingEntry _ routingTable^[h], temp.next WHILE temp # oldH DO prevH _ temp ENDLOOP; IF prevH # NIL THEN prevH.next _ oldH.next ELSE routingTable^[h] _ oldH.next; IF oldH.sortedPrev # NIL THEN oldH.sortedPrev.sortedNext _ oldH.sortedNext ELSE sortedHead _ oldH.sortedNext; IF oldH.sortedNext # NIL THEN oldH.sortedNext.sortedPrev _ oldH.sortedPrev; }; changes: INT _ 0; ChangeEntry: PROC [oldH: RoutingEntry, newHops: Hops] ~ INLINE { IF oldH.hops # newHops THEN { changes _ changes.SUCC; IF Monitoring[] THEN PostChangeEvent[oldH, newHops]; oldH.hops _ newHops }; oldH.sweepsSinceRefresh _ 0 }; responsesSent: INT _ 0; ProcessRequest: PROC [b: XNSRoutingBuf.Buffer, userBytes: CARDINAL] ~ { sendBuf: XNSBuf.Buffer _ NIL; -- the send buffer. iSend: CARDINAL; -- index into sb.body.tuples nReq: CARDINAL _ 0; -- number of request tuples in b, or 0 if b = NIL Send: PROC ~ { TRUSTED { srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf]; srb.hdr1.type _ routing; srb.hdr2.type _ response }; XNSSocket.SetUserBytes[sendBuf, XNSRoutingBuf.UserBytesFromNumTuples[iSend]]; IF b # NIL THEN XNSSocket.Send[b~sendBuf, dest~b.hdr1.source] ELSE XNSSocket.Broadcast[b~sendBuf, socket~XNSWKS.routing]; }; AddToSendBuf: PROC [eH: RoutingEntry] ~ { IF (sendBuf # NIL) AND (iSend >= XNSRoutingBuf.maxTuples) THEN { Send[]; sendBuf _ NIL }; IF sendBuf = NIL THEN { sendBuf _ XNSSocket.AllocBuffer[handle~routingSocketHandle]; iSend _ 0 }; TRUSTED { srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf]; srb.body.tuples[iSend] _ [net~eH.dest, delay~eH.hops] }; iSend _ iSend + 1; }; IF b # NIL THEN { IF b.hdr1.dest.host # thisHost THEN RETURN; -- Simple router responds only to requests directed at it. TRUSTED { XNSSocket.FixupSourceAndDest[LOOPHOLE[b]] }; nReq _ XNSRoutingBuf.NumTuplesFromUserBytes[userBytes] }; IF (b = NIL) OR ((nReq > 0) AND (b.body.tuples[0].net = broadcastNet)) THEN { FOR eH: RoutingEntry _ sortedHead, eH.sortedNext WHILE eH # NIL DO AddToSendBuf[eH]; ENDLOOP; } ELSE { FOR iReq: CARDINAL IN [0 .. nReq) DO eH: RoutingEntry ~ FindEntry[b.body.tuples[iReq].net]; IF eH # NIL THEN AddToSendBuf[eH]; ENDLOOP; }; IF sendBuf # NIL THEN { Send[]; sendBuf _ NIL }; responsesSent _ responsesSent.SUCC; }; ProcessResponse: PROC [b: XNSRoutingBuf.Buffer, userBytes: CARDINAL] ~ { network: Network _ NARROW[b.ovh.network]; immediate: Host _ b.hdr1.source.host; tuple: XNSRoutingBuf.Tuple; hops: CARDINAL; eH, newH: RoutingEntry; IF network.xns.net = unknownNet THEN { network.xns.net _ b.hdr1.source.net; -- NOT ATOMIC ConnectNets[] }; FOR i: CARDINAL IN [0 .. XNSRoutingBuf.NumTuplesFromUserBytes[userBytes]) DO tuple _ b.body.tuples[i]; hops _ Endian.CardFromH[tuple.delay]; IF (eH _ FindEntry[tuple.net]) # NIL THEN { IF (eH.network = network) AND (eH.immediate = immediate) THEN { IF hops < unreachable THEN { ChangeEntry[eH, hops] } ELSE { DeleteEntry[eH] }; LOOP }; IF eH.sweepsSinceRefresh < suspectSweeps THEN { IF eH.hops < hops THEN LOOP; IF (eH.hops = hops) AND (eH.network.speed >= network.speed) THEN LOOP; }; IF hops >= unreachable THEN { IF eH.sweepsSinceRefresh >= suspectSweeps AND (eH.network = network) THEN { DeleteEntry[eH] }; LOOP }; newH _ NEW [RoutingEntryObject _ [dest~tuple.net, hops~hops, network~network, immediate~immediate, sweepsSinceRefresh~0]]; ReplaceEntry[newH~newH, oldH~eH]; LOOP; }; IF hops >= unreachable THEN LOOP; newH _ NEW [RoutingEntryObject _ [dest~tuple.net, hops~hops, network~network, immediate~immediate, sweepsSinceRefresh~0]]; AddEntry[newH]; ENDLOOP; }; ConnectNets: PROC [] ~ { oldH, newH: RoutingEntry; FOR network: Network _ CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO IF network.xns.net = unknownNet THEN LOOP; oldH _ FindEntry[network.xns.net]; IF oldH # NIL AND oldH.hops = 0 THEN { oldH.sweepsSinceRefresh _ 0; LOOP }; newH _ NEW[RoutingEntryObject _ [dest~network.xns.net, hops~0, network~network, immediate~unknownHost, sweepsSinceRefresh~0]]; IF oldH # NIL THEN ReplaceEntry[newH~newH, oldH~oldH] ELSE AddEntry[newH~newH]; ENDLOOP; }; Sweep: PROC ~ { eH, nextH: RoutingEntry; FOR eH _ sortedHead, nextH WHILE eH # NIL DO nextH _ eH.sortedNext; IF eH.sweepsSinceRefresh >= invalidSweeps THEN DeleteEntry[eH] ELSE eH.sweepsSinceRefresh _ eH.sweepsSinceRefresh.SUCC; ENDLOOP; }; packetsReceived: INT _ 0; requestsReceived: INT _ 0; responsesReceived: INT _ 0; badLength: INT _ 0; badProtocol: INT _ 0; sweeps: INT _ 0; minSweepPulses: Pulses _ sweepPulses; lastSweep: Pulses _ BasicTime.GetClockPulses[]; Daemon: PROC ~ { DO b: XNSBuf.Buffer; sinceSweep: Pulses ~ PulsesSince[lastSweep]; getTimeout: Msecs ~ IF sinceSweep >= sweepPulses THEN XNSSocket.dontWait ELSE (1 + (BasicTime.PulsesToMicroseconds[sweepPulses - sinceSweep] / 1000)); XNSSocket.SetGetTimeout[routingSocketHandle, getTimeout]; IF (b _ XNSSocket.Get[routingSocketHandle]) # NIL THEN BEGIN userBytes: CARDINAL ~ XNSSocket.GetUserBytes[b]; rB: XNSRoutingBuf.Buffer; packetsReceived _ packetsReceived.SUCC; IF b.hdr1.type # routing THEN { badProtocol _ badProtocol.SUCC; XNSSocket.ReturnError[b~b, type~XNSErrorTypes.protocolViolationErr]; b _ NIL; GOTO Next }; IF (userBytes < XNSRoutingBuf.hdrBytes) OR (userBytes > XNSRoutingBuf.maxBytes) THEN { badLength _ badLength.SUCC; GOTO Next }; TRUSTED { rB _ LOOPHOLE[b] }; SELECT rB.hdr2.type FROM request => { requestsReceived _ requestsReceived.SUCC; ProcessRequest[rB, userBytes] }; response => { responsesReceived _ responsesReceived.SUCC; ProcessResponse[rB, userBytes] }; ENDCASE => { XNSSocket.ReturnError[b~b, type~XNSErrorTypes.protocolViolationErr]; b _ NIL }; GOTO Next; EXITS Next => IF b # NIL THEN XNSSocket.FreeBuffer[b]; END ELSE BEGIN minSweepPulses _ MIN[minSweepPulses, PulsesSince[lastSweep]]; ConnectNets[]; Sweep[]; sweeps _ sweeps.SUCC; lastSweep _ BasicTime.GetClockPulses[]; END; ENDLOOP; }; PokeGateways: PROC ~ { b: XNSBuf.Buffer; rB: XNSRoutingBuf.Buffer; b _ XNSSocket.AllocBuffer[handle~routingSocketHandle]; TRUSTED { rB _ LOOPHOLE[b] }; rB.hdr1.type _ routing; rB.hdr2.type _ request; rB.body.tuples[0] _ [net~broadcastNet, delay~Endian.HFromCard[unreachable]]; XNSSocket.SetUserBytes [b~b, bytes~XNSRoutingBuf.UserBytesFromNumTuples[1]]; XNSSocket.Broadcast[b~b, socket~XNSWKS.routing]; }; Route: PUBLIC PROC [him: XNS.Address] RETURNS [network: Network, immediate: XNS.Host] ~ { eH: RoutingEntry ~ FindEntry[him.net]; IF eH = NIL THEN RETURN [NIL, unknownHost]; IF eH.hops = 0 THEN RETURN [eH.network, him.host]; IF eH.hops >= unreachable THEN ERROR; -- Gateways: RETURN [NIL, unknownHost]; RETURN [eH.network, eH.immediate]; }; RTEHandle: TYPE ~ REF RTEObject; RTEObject: TYPE ~ XNSRouter.RoutingTableEntry; oldStaticBuffer: RTEHandle ~ NEW [RTEObject _ [hops~, immediate~, time~]]; newStaticBuffer: RTEHandle ~ NEW [RTEObject _ [hops~, immediate~, time~]]; EventProc: TYPE ~ XNSRouterPrivate.EventProc; EventProcList: TYPE ~ REF EventProcObject; EventProcObject: TYPE ~ RECORD [ next: EventProcList _ NIL, proc: EventProc]; eventProcList: EventProcList _ NIL; SetEventProc: PUBLIC ENTRY PROC [proc: EventProc] ~ { eventProcList _ NEW[ EventProcObject _ [next~eventProcList, proc~proc] ]; }; ClearEventProc: PUBLIC ENTRY PROC [proc: EventProc] ~ { p, prev: EventProcList; p _ eventProcList; prev _ NIL; WHILE (p # NIL) AND (p.proc # proc) DO prev _ p; p _ p.next ENDLOOP; IF p # NIL THEN { IF prev = NIL THEN eventProcList _ p.next ELSE prev.next _ p.next }; }; Monitoring: PROC RETURNS [BOOL] ~ INLINE { RETURN [eventProcList # NIL] }; PostEvent: PROC [oldH, newH: RoutingEntry _ NIL] ~ { net: Net; oldRTEH, newRTEH: RTEHandle _ NIL; IF oldH # NIL THEN { oldRTEH _ oldStaticBuffer; oldRTEH^ _ [hops~oldH.hops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~(oldH.sweepsSinceRefresh*sweepSeconds)]; net _ oldH.dest }; IF newH # NIL THEN { newRTEH _ newStaticBuffer; newRTEH^ _ [hops~newH.hops, immediate~[net~newH.network.xns.net, host~newH.immediate, socket~unknownSocket], time~(newH.sweepsSinceRefresh*sweepSeconds)]; net _ newH.dest }; FOR pH: EventProcList _ eventProcList, pH.next WHILE pH # NIL DO (pH.proc)[net, oldRTEH, newRTEH]; ENDLOOP; }; PostChangeEvent: PROC [oldH: RoutingEntry, newHops: Hops] ~ { oldStaticBuffer^ _ [hops~oldH.hops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~(oldH.sweepsSinceRefresh*sweepSeconds)]; newStaticBuffer^ _ [hops~newHops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~0]; FOR pH: EventProcList _ eventProcList, pH.next WHILE pH # NIL DO (pH.proc)[oldH.dest, oldStaticBuffer, newStaticBuffer]; ENDLOOP; }; Fast: PUBLIC PROC [net: Net] RETURNS [yes: BOOL] ~ { eH: RoutingEntry ~ FindEntry[net]; IF eH = NIL THEN RETURN[FALSE]; SELECT eH.network.type FROM ethernet => RETURN[TRUE]; ethernetOne => RETURN[TRUE]; ENDCASE => RETURN[FALSE]; }; GetHops: PUBLIC PROC [net: Net] RETURNS [Hops] ~ { eH: RoutingEntry ~ FindEntry[net]; IF eH = NIL THEN RETURN [unreachable]; RETURN [eH.hops]; }; GetRouting: PUBLIC PROC [net: Net] RETURNS [XNSRouter.RoutingTableEntry] ~ { eH: RoutingEntry ~ FindEntry[net]; IF eH = NIL THEN RETURN [[ hops~unreachable, immediate~unknownAddress, time~0]]; RETURN [[ hops~eH.hops, immediate~[net~eH.network.xns.net, host~eH.immediate, socket~unknownSocket], time~(eH.sweepsSinceRefresh*sweepSeconds)]]; }; Enumerate: PUBLIC PROC [ low: Hops _ 0, high: Hops _ unreachable, proc: PROC [Net, XNSRouter.RoutingTableEntry]] ~ { FOR eH: RoutingEntry _ sortedHead, eH.sortedNext WHILE eH # NIL DO IF eH.hops >= low AND eH.hops <= high THEN proc[ eH.dest, [ hops~eH.hops, immediate~[net~eH.network.xns.net, host~eH.immediate, socket~unknownSocket], time~(eH.sweepsSinceRefresh*sweepSeconds)] ]; ENDLOOP; }; daemonProcess: PROCESS; routingSocketHandle: XNSSocket.Handle; Init: PROC ~ { CommDriver.InsertReceiveProc[network~NIL, type~xns, proc~XNSRouterPrivate.TakeThis]; routingSocketHandle _ XNSSocket.Create[local~XNSWKS.routing]; daemonProcess _ FORK Daemon[]; PokeGateways[]; }; Init[]; }. œXNSRouterImpl.mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Demers, October 15, 1986 3:22:02 pm PDT An implementation of the XNS Routing information protocol per XSIS 028112, December 1981. This implementation is a requestor, not a supplier, of routing information. It can't be used in a gateway. Timeouts Routing Table Routing entries are stored in a hash table, keyed by destination net number, using chained overflow. Entries are also doubly-linked in a list sorted by network number. The sorted list, which contains all the routing entries, is used e.g. by Sweep and Enumerate. In a requestor (not a gateway) an entry with hops = unreachable is semantically equivalent to no entry, so we never allow such an entry to appear in the table. Add new entry newH^ into hash table and insert it in the correct position in the sorted list. This involves an O(n) search, but it only happens on addition - NOT replacement - and that's fairly infrequent. Add new entry newH^ into hash table replacing oldH^, and insert it in the correct position in the sorted list. Note oldH^ is used to determine newH's position in the sorted list, eliminating the O(n) search. Of course, this means oldH and newH MUST be for the same dest network. Delete the entry oldH^ from the hash table and the sorted list. Update the hop count of entry oldH^. Routing Daemon Reply to b^ (which must be a routing information request packet of length userBytes). For a simple router (not gateway) this is done only if the b^ was directed at this host (rather than broadcast). The request buffer b may be NIL, in which case we "reply" to it by broadcasting our entire routing table. Send sendBuf^ to destination computed from b. Add info from eH to response packet in sendBuf^, sending the old response packet and allocating a new one if necessary. Dump the entire routing table. Reply with routing table entries for requested nets only. Note the response will be sorted by net number only if the request was ... Update the routing table using information from b^ (which must be a routing information response packet of length userBytes). We have just learned the network number of a directly-connected net. Update from owner of entry can be performed in place. Update less desirable than the current entry can be ignored. Update making an (unowned) entry unreachable is either performed in place or ignored. NOTE: there's a plausible argument that it should ALWAYS be ignored. Here it's ignored unless the "unreachable" update comes from a gateway on the same net as the old route. That's just a heuristic ... Too bad, update is significant and the entry must be replaced. Create of a new unreachable entry can be ignored. Too bad, must create a new entry. Ensure that there's a valid 0-hops routine entry for each connected network for which the network number (network.ns.net) has already been filled in. Throw away routing entries that are too old to be credible. Receive and process a routing info packet. Sweep the table. Routing a Packet Event Monitoring (Exported to XNSRouterPrivate) Client Interface (Exported to XNSRouter) Initialization Install recv proc for each network on chain. Start routing daemon. Κΰ˜codešœ™Kšœ Οmœ1™Kšœžœp˜zK˜!Kšžœ˜—K˜K˜—K˜™1Kšžœžœžœ˜!K˜—™!Kšœžœp˜zJšœ˜—K˜Kšžœ˜—K˜K˜—K˜š  œžœ˜K™•Kšœ˜K˜šžœ?žœ žœž˜Xšžœ˜Kšžœžœ˜ —Kšœ"˜"šžœžœžœ˜Kšžœ!žœ˜,—Kšœžœt˜~šžœž˜ Kšžœ#˜'Kšžœ˜—Kšžœ˜—K˜K˜—K˜š œžœ˜K™