DIRECTORY Arpa USING [Address, NetNumber, nullAddress], ArpaBuf USING [Buffer], ArpaRouter USING [Hops, RoutingTableEntry, unreachable], ArpaRouterPrivate USING [EventProc, TakeThis], ArpaRoutingBuf USING [Buffer, hdrBytes, maxBytes, maxTuples, NumTuplesFromUserBytes, Tuple, UserBytesFromNumTuples], Basics USING [Card32FromF, Card16FromH, FFromCard32, HFromCard16], BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds], Booting USING [RegisterProcs, RollbackProc], CardTab USING [Create, EachPairAction, Fetch, Insert, Key, Pairs, Ref], CommDriver USING [GetNetworkChain, InsertReceiveProc, Network], Process USING [PauseMsec], XNS USING [Address, broadcastNet, GetThisHost, Host, Net, Socket, unknownAddress, unknownHost, unknownNet, unknownSocket], XNSErrorTypes USING [protocolViolationErr], XNSSocket USING [AllocBuffer, Broadcast, Create, dontWait, FixupSourceAndDest, FreeBuffer, Get, GetUserBytes, Handle, Milliseconds, ReturnError, Send, SetGetTimeout, SetUserBytes], XNSWKS USING [routing]; ArpaRouterImpl: CEDAR MONITOR LOCKS routingEntry USING routingEntry: RoutingEntry IMPORTS Arpa, ArpaRouterPrivate, Basics, BasicTime, Booting, CardTab, CommDriver, Process, XNS, XNSRoutingBuf, XNSSocket EXPORTS ArpaRouter, ArpaRouterPrivate ~ { Net: TYPE ~ XNS.Net; -- presumed equivalent to Basics.FWORD Address: TYPE ~ Arpa.Address; unknownAddress: Address ~ Arpa.nullAddress; thisHost: Host ~ XNS.GetThisHost[]; -- ???? Network: TYPE ~ CommDriver.Network; Hops: TYPE ~ ArpaRouter.Hops; unreachable: Hops ~ ArpaRouter.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; RoutingTable: TYPE ~ CardTab.Ref; initialTableSize: NAT _ 311; RoutingEntry: TYPE ~ REF RoutingEntryObject; RoutingEntryObject: TYPE ~ MONITORED RECORD [ hops: Hops _ unreachable, -- hops to the desired net immediate: Address _ unknownAddress, -- first router on route network: Network _ NIL, -- directly connected net to first router sweepsSinceRefresh: CARDINAL _ 0]; routingTable: RoutingTable _ CardTab.Create[initialTableSize]; KeyFromAddress: PROC [address: Address] RETURNS [CardTab.Key] ~ --INLINE-- { RETURN [ Basics.Card32FromF[LOOPHOLE[Arpa.NetNumber[address]]] ] }; NetAddressFromKey: PROC [key: CardTab.Key] RETURNS [Address] ~ --INLINE-- { RETURN [ LOOPHOLE[Basics.FFromCard32[key]] ] }; LookupEntry: PROC [address: Address] RETURNS [val: REF] ~ --INLINE-- { [val~val] _ CardTab.Fetch[routingTable, KeyFromAddress[address]] }; GetEntry: PROC [address: Address] RETURNS [val: REF] ~ { key: CardTab.Key ~ KeyFromAddress[address]; new: REF _ NIL; DO [val~val] _ CardTab.Fetch[routingTable, key]; IF val # NIL THEN RETURN; IF new = NIL THEN new _ NEW[RoutingEntryObject]; val _ new; IF CardTab.Insert[routingTable, key, val] THEN RETURN; ENDLOOP; }; 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: CardTab.EachPairAction -- [key, val] RETURNS [quit]-- ~ { IF (sendBuf # NIL) AND (iSend >= XNSRoutingBuf.maxTuples) THEN { Send[]; sendBuf _ NIL }; IF sendBuf = NIL THEN { sendBuf _ XNSSocket.AllocBuffer[handle~routingSocketHandle]; iSend _ 0 }; AddToSendBufInner[routingEntry~NARROW[val], net~NetAddressFromKey[key]]; iSend _ iSend + 1; RETURN [FALSE] }; AddToSendBufInner: ENTRY PROC [routingEntry: RoutingEntry, net: Net] ~ --INLINE-- { TRUSTED { srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf]; srb.body.tuples[iSend] _ [net~net, delay~Basics.HFromCard16[routingEntry.hops]]; }; }; 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 { [] _ CardTab.Pairs[routingTable, AddToSendBuf]; } ELSE { FOR iReq: CARDINAL IN [0 .. nReq) DO net: Net ~ b.body.tuples[iReq].net; routingEntry: RoutingEntry ~ NARROW[ LookupEntry[????net] ]; IF routingEntry # NIL THEN [] _ AddToSendBuf[Basics.Card32FromF[net], routingEntry]; 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; UpdateEntryFromTuple: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { IF (routingEntry.network = network) AND (routingEntry.immediate = immediate) THEN { IF Monitoring[] AND (routingEntry.hops # hops) THEN PostChange[tuple.net, routingEntry, hops, network.xns.net, immediate]; } ELSE { IF routingEntry.sweepsSinceRefresh < suspectSweeps THEN { IF routingEntry.hops < hops THEN RETURN; IF (routingEntry.hops = hops) AND (routingEntry.network # NIL) AND (routingEntry.network.speed >= network.speed) THEN RETURN; }; IF (hops >= unreachable) AND (network # routingEntry.network) THEN RETURN; IF Monitoring[] THEN PostChange[tuple.net, routingEntry, hops, network.xns.net, immediate]; routingEntry.network _ network; routingEntry.immediate _ immediate; }; routingEntry.hops _ hops; routingEntry.sweepsSinceRefresh _ 0; IF hops >= unreachable THEN { routingEntry.network _ NIL; routingEntry.immediate _ unknownAddress }; }; IF network.xns.net = unknownNet THEN { network.xns.net _ b.hdr1.source.net; -- NOT ATOMIC but there's only one daemon ... ConnectNets[] }; FOR i: CARDINAL IN [0 .. XNSRoutingBuf.NumTuplesFromUserBytes[userBytes]) DO tuple _ b.body.tuples[i]; hops _ Basics.Card16FromH[tuple.delay]; UpdateEntryFromTuple[NARROW[GetEntry[tuple.net]]]; ENDLOOP; }; ConnectNets: PROC [] ~ { network: Network; ConnectNetInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { routingEntry.hops _ 0; routingEntry.network _ network; routingEntry.sweepsSinceRefresh _ 0; }; FOR network _ CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO IF network.xns.net # unknownNet THEN ConnectNetInner[NARROW[GetEntry[network.xns.net]]]; ENDLOOP; }; Sweep: PROC ~ { CheckEntry: CardTab.EachPairAction -- [key, val] RETURNS [quit]-- ~ { CheckEntryInner[NARROW[val]]; RETURN [FALSE] }; CheckEntryInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { IF routingEntry.sweepsSinceRefresh >= invalidSweeps THEN routingEntry.hops _ unreachable; routingEntry.sweepsSinceRefresh _ routingEntry.sweepsSinceRefresh.SUCC; }; [] _ CardTab.Pairs[routingTable, CheckEntry]; }; packetsReceived: INT _ 0; requestsReceived: INT _ 0; responsesReceived: INT _ 0; badLength: INT _ 0; badProtocol: INT _ 0; sweeps: CARD _ 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; }; WeUseTranslation: PROC RETURNS [yes: BOOL] ~ { FOR network: CommDriver.Network _ CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO IF network.xns.translation # NIL THEN RETURN [TRUE]; ENDLOOP; RETURN [FALSE] }; PokeGateways: PROC ~ { nTries: INT _ IF WeUseTranslation[] THEN 2 ELSE 1; FOR try: INT _ 0, try+1 WHILE try < nTries DO b: XNSBuf.Buffer; rB: XNSRoutingBuf.Buffer; IF try > 0 THEN Process.PauseMsec[1111]; b _ XNSSocket.AllocBuffer[handle~routingSocketHandle]; TRUSTED { rB _ LOOPHOLE[b] }; rB.hdr1.type _ routing; rB.hdr2.type _ request; rB.body.tuples[0] _ [net~broadcastNet, delay~Basics.HFromCard16[unreachable]]; XNSSocket.SetUserBytes [b~b, bytes~XNSRoutingBuf.UserBytesFromNumTuples[1]]; XNSSocket.Broadcast[b~b, socket~XNSWKS.routing]; ENDLOOP; }; Route: PUBLIC PROC [him: Arpa.Address] RETURNS [network: Network, immediate: Address] ~ { entry: REF ~ LookupEntry[him]; RouteInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { network _ routingEntry.network; immediate _ IF routingEntry.hops = 0 THEN him.host ELSE routingEntry.immediate; }; IF entry = NIL THEN RETURN [NIL, unknownAddress]; RouteInner[NARROW[entry]]; }; Rollback: Booting.RollbackProc = { SmashEntry: CardTab.EachPairAction -- [key, val] RETURNS [quit]-- ~ { SmashEntryInner[NARROW[val]]; RETURN [FALSE] }; SmashEntryInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { routingEntry.sweepsSinceRefresh _ invalidSweeps.PRED; }; [] _ CardTab.Pairs[routingTable, SmashEntry]; PokeGateways[]; }; eventLock: RoutingEntry _ NEW[RoutingEntryObject]; 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 PROC [proc: EventProc] ~ { SetEventProcInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { eventProcList _ NEW[ EventProcObject _ [next~eventProcList, proc~proc] ] }; SetEventProcInner[eventLock] }; ClearEventProc: PUBLIC PROC [proc: EventProc] ~ { p, prev: EventProcList; ClearEventProcInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { 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 }; }; ClearEventProcInner[eventLock] }; Monitoring: PROC RETURNS [BOOL] ~ INLINE { RETURN [eventProcList # NIL] }; PostChange: PROC [net: Net, old: RoutingEntry, hops: Hops, immNet: Net, immHost: Host] ~ { PostChangeInner: ENTRY PROC [routingEntry: RoutingEntry -- lock --] ~ --INLINE-- { oldStaticBuffer^ _ [ hops~old.hops, immediate~[net~(IF old.network # NIL THEN old.network.xns.net ELSE unknownNet), host~old.immediate, socket~unknownSocket], time~(old.sweepsSinceRefresh*sweepSeconds)]; newStaticBuffer^ _ [ hops~hops, immediate~[net~immNet, host~immHost, socket~unknownSocket], time~0]; FOR pH: EventProcList _ eventProcList, pH.next WHILE pH # NIL DO (pH.proc)[net, oldStaticBuffer, newStaticBuffer]; ENDLOOP; }; PostChangeInner[eventLock] }; Fast: PUBLIC PROC [address: Address] RETURNS [yes: BOOL] ~ { routingEntry: RoutingEntry ~ NARROW[LookupEntry[address]]; IF (routingEntry = NIL) OR (routingEntry.network = NIL) THEN RETURN[FALSE]; SELECT routingEntry.network.type FROM ethernet => RETURN[TRUE]; ethernetOne => RETURN[TRUE]; ENDCASE => RETURN[FALSE]; }; GetHops: PUBLIC PROC [address: Address] RETURNS [hops: Hops _ unreachable] ~ { entry: REF ~ LookupEntry[address]; GetHopsInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { IF routingEntry # NIL THEN hops _ routingEntry.hops }; IF entry # NIL THEN GetHopsInner[NARROW[entry]]; }; GetRouting: PUBLIC PROC [address: Address] RETURNS [rte: XNSRouter.RoutingTableEntry _ [hops~unreachable, immediate~unknownAddress, time~0]] ~ { entry: REF ~ LookupEntry[address]; GetRoutingInner: ENTRY PROC [routingEntry: RoutingEntry] ~ --INLINE-- { rte _ [ hops~routingEntry.hops, immediate~[ net~(IF routingEntry.network # NIL THEN routingEntry.network.xns.net ELSE unknownNet), host~routingEntry.immediate, socket~unknownSocket], time~(routingEntry.sweepsSinceRefresh*sweepSeconds)]; }; IF entry # NIL THEN GetRoutingInner[NARROW[entry]] }; Enumerate: PUBLIC PROC [ low: Hops _ 0, high: Hops _ unreachable, proc: PROC [Net, XNSRouter.RoutingTableEntry]] ~ { EachPair: CardTab.EachPairAction -- [key, val] RETURNS [quit] -- ~ { rte: XNSRouter.RoutingTableEntry; EachPairInner: ENTRY PROC [routingEntry: RoutingEntry] RETURNS [inRange: BOOL] ~ --INLINE-- { IF (inRange _ ((routingEntry.hops >= low) AND (routingEntry.hops <= high))) THEN { rte _ [ hops~routingEntry.hops, immediate~[ net~(IF routingEntry.network # NIL THEN routingEntry.network.xns.net ELSE unknownNet), host~routingEntry.immediate, socket~unknownSocket], time~(routingEntry.sweepsSinceRefresh*sweepSeconds)]; }; }; IF EachPairInner[NARROW[val]].inRange THEN proc[ NetAddressFromKey[key], rte ]; }; [] _ CardTab.Pairs[routingTable, EachPair]; }; daemonProcess: PROCESS; routingSocketHandle: XNSSocket.Handle; Init: PROC ~ { CommDriver.InsertReceiveProc[network~NIL, type~xns, proc~XNSRouterPrivate.TakeThis]; Booting.RegisterProcs[r: Rollback]; routingSocketHandle _ XNSSocket.Create[local~XNSWKS.routing]; daemonProcess _ FORK Daemon[]; PokeGateways[]; }; Init[]; }. œArpaRouterImpl.mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Demers, August 18, 1987 10:33:56 am PDT An implementation of the Arpa Routing Information Protocol. 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 kept in a hash table, keyed by the net you're trying to reach. INVARIANT: routingEntry.hops = unreachable IFF routingEntry.network = NIL. Lookup entry. Return NIL is no entry exists. Lookup entry, or create a new one if none exists. Never return NIL. 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 routingEntry 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. Responses are in the same order as the requests ... Update the routing table using information from b^ (which must be a routing information response packet of length userBytes). Update is from owner of entry, we will accept it. Update is not from owner of entry, we may want to reject it. Update less desirable than the current entry is rejected. Update making an (unowned) entry unreachable is rejected if it comes from a gateway on a different net from the old route. That's just a heuristic. We have just learned the network number of a directly-connected net. Ensure that there's a valid 0-hops routing entry for each connected network for which the network number (network.ns.net) has already been filled in. Throw away (i.e. mark as unreachable) any routing entries that are too old to be credible. Receive and process a routing info packet. Sweep the table. Requesting Tables From the Gateways If we use translation, this pokes the gateways twice, with a one-second pause in between, to give them time to fill their address translation caches. Routing a Packet Rollback Event Monitoring (Exported to XNSRouterPrivate) Client Interface (Exported to ArpaRouter) Initialization Install recv proc for each network on chain. Register rollback proc. Start routing daemon. ΚL˜šœ™Icodešœ Οmœ1™˜>K˜š‘œžœžœž œ˜LKšžœžœ˜CK˜—š‘œžœžœ ž œ˜KKšžœžœ˜/K˜—š ‘ œžœžœžœž œ˜FK™-KšœC˜C—K˜š‘œžœžœžœ˜8K™DKšœ+˜+Kšœžœžœ˜šž˜Kšœ-˜-Kšžœžœžœžœ˜Kšžœžœžœžœ˜0K˜ Kšžœ(žœžœ˜6Kšžœ˜—K˜——™Kšœžœ˜K˜š‘œžœ&žœ˜GK™²Kšœžœ ˜1Kšœžœ ˜-Kšœžœ 1˜Eš‘œžœ˜K™-šžœ˜ Kšœžœ ˜.K˜K˜—KšœM˜Mšžœž˜ Kšžœ.˜2Kšžœ'žœ ˜;—K˜—š‘ œ œ˜GKšœ™šžœ žœžœ#žœ˜@Kšœžœ˜—šžœ žœ˜Kšœ<˜