-- RoutingTableImpl.mesa
-- last edited by: BLyon on: March 19, 1981 5:41 PM
-- Function: The implementation module for the Pilot OISCP Router's routing table.
DIRECTORY
BufferDefs USING [
BufferAccessHandle, FreeBufferPool, MakeBufferPool, OisBuffer],
Checksums USING [IncrOisTransportControlAndUpdateChecksum, SetChecksum],
CommunicationInternal USING [],
CommFlags USING [doDebug, doStats],
DriverDefs USING [
ChangeNumberOfInputBuffers, GetDeviceChain, GetInputBuffer,
MaybeGetFreeOisBuffer, Glitch, Network, PutOnGlobalDoneQueue],
Heap USING [FreeNode, MakeNode],
OISCP USING [
allHostIDs, GetFreeSendOisBufferFromPool,
SetOisPacketTextLength, unknownHostID, unknownNetID],
OISCPConstants USING [routingInformationSocket],
OISCPTypes USING [
bytesPerPktHeader, maxBytesPerPkt, RoutingInfoTuple, RoutingInfoType,
TransPortControl],
Process USING [Detach, MsecToTicks, SetTimeout],
Router USING [
BroadcastThisPacket, checkIt, FindMyHostID, routersFunction, Nibble,
primaryMDS, RoutingTableEntry, RoutingTableObject, SendErrorPacket,
SendPacket, XmitStatus],
StatsDefs USING [StatIncr],
SpecialCommunication USING [RoutersFunction],
SpecialSystem USING [
broadcastHostNumber, HostNumber, NetworkAddress, NetworkNumber, nullNetworkNumber];
RoutingTableImpl: MONITOR
IMPORTS
BufferDefs, Checksums, DriverDefs, Heap, OISCP, Process,
Router, StatsDefs
EXPORTS BufferDefs, CommunicationInternal, Router, SpecialCommunication
SHARES BufferDefs =
BEGIN
OPEN OISCP, Router, StatsDefs, SpecialCommunication;
-- EXPORTed TYPEs
Network: PUBLIC TYPE = DriverDefs.Network;
-- Many of these variables must eventually live in outerspace so that multiple MDSs
-- access the same router variables. The modules in the primary MDS will have the
-- proceses and will perform the initialization of the "globals", while the others will not.
-- monitor data
myHostID: SpecialSystem.HostNumber; -- host ID of this system element
-- routing table constants and variables
-- network ids and now 32 bits. Therefore numberOfNets, LegalNets, destNet, net, will
-- have to change. Righrt now we will use the low order bits of the Network Number;
routingTableHead: RoutingTableEntry ← NIL;
routingTableSize: CARDINAL ← 0;
maxRoutingTableSize: CARDINAL = 50;
probeAnInternetRouterCounter: CARDINAL; -- keeps track of num of detached processes
initialTransportControl: OISCPTypes.TransPortControl =
[trace: FALSE, filler: 0, hopCount: 0];
oneHop: Nibble = 1; -- delay to local network is assumd to be one router hop.
updateCycles: Nibble = 4; -- timeUnits gets reset to this; number of routing table update cycles.
alternatePathTimeUnitThreshHold: CARDINAL = 3; -- we look for alternate routing path if timeUnits fall BELOW this value.
maxRouterDelay: CARDINAL = 15; -- max number of router hops
maxInternetrouterHops: CARDINAL = 15; -- max number of internetrouter hops
-- controlling the entry processes
inrBufferCount: CARDINAL ← 20; -- the number of buffers allocated by an INR.
inrRunning, iNRpleaseStop, pleaseStop: BOOLEAN; -- switch to tell the processes to stop
routingTableUpdateTimer, responseFromInternetRouter, internetRouterTimer:
CONDITION;
routingTableFork, internetRouterServerFork: PROCESS;
-- various Glitches generated by the Router
RoutingTableScrambled: PUBLIC ERROR = CODE;
routingTableSanityChecking: BOOLEAN = FALSE;
--Hot Procedures
-- Routing list manipulation Routines
--used only for debugging
SanityCheck: PROCEDURE = INLINE
BEGIN
e: RoutingTableEntry ← routingTableHead;
WHILE e#NIL DO
IF e.delay=0 THEN ERROR;
e ← e.next;
ENDLOOP;
END;
-- This procedure searches for an entry with destNetwork field equal to num and returns
-- that entry. If the entry cannot be found then e is NIL .
FindNetworkNumber: PROCEDURE [num: SpecialSystem.NetworkNumber, advanceEntry: BOOLEAN ← TRUE]
RETURNS [e: RoutingTableEntry] =
BEGIN
prev: RoutingTableEntry ← e ← routingTableHead;
UNTIL e=NIL DO
IF e.destNetwork=num THEN
BEGIN
IF advanceEntry AND (prev#routingTableHead) THEN
BEGIN
prev.next ← e.next;
e.next ← routingTableHead;
routingTableHead ← e;
END;
RETURN;
END;
prev ← e;
e ← e.next;
ENDLOOP;
END;
-- This procedure searches for an entry with network field equal to net and returns
-- that entry. If the entry cannot be found then e is NIL.
FindNetwork: PROCEDURE [net: Network]
RETURNS [e: RoutingTableEntry] =
BEGIN
prev: RoutingTableEntry ← e ← routingTableHead;
UNTIL e=NIL DO
IF e.network=net THEN
BEGIN
IF prev#routingTableHead THEN
BEGIN
prev.next ← e.next;
e.next ← routingTableHead;
routingTableHead ← e;
END;
RETURN;
END;
prev ← e;
e ← e.next;
ENDLOOP;
END;
-- This procedure removes RoutingTableEntry e from the list. prev is the previous entry
-- to e. If prev is not known then its value is NIL.
RemoveEntry: PROCEDURE [e: RoutingTableEntry] =
BEGIN
prev: RoutingTableEntry ← NIL;
temp: RoutingTableEntry ← routingTableHead;
UNTIL (temp = NIL) OR (temp = e) DO
prev ← temp;
temp ← temp.next;
ENDLOOP;
IF CommFlags.doDebug AND (temp = NIL) THEN DriverDefs.Glitch[RoutingTableScrambled];
IF prev = NIL THEN routingTableHead ← e.next
ELSE
BEGIN
IF CommFlags.doDebug AND (prev.next # e) THEN DriverDefs.Glitch[RoutingTableScrambled];
IF CommFlags.doDebug AND (prev.next = NIL) THEN DriverDefs.Glitch[RoutingTableScrambled];
prev.next ← e.next;
END;
e.next ← NIL;
routingTableSize ← routingTableSize - 1;
IF CommFlags.doDebug AND routingTableSize>maxRoutingTableSize THEN DriverDefs.Glitch[RoutingTableScrambled];
END;
-- This procedure adds an entry to the beginning of the Routingtable list.
AddEntry: PROCEDURE [e: RoutingTableEntry] =
BEGIN
e.next ← routingTableHead;
routingTableHead ← e;
routingTableSize ← routingTableSize + 1;
IF CommFlags.doDebug AND routingTableSize>maxRoutingTableSize THEN DriverDefs.Glitch[RoutingTableScrambled];
END;
EnumerateRoutingTable: PUBLIC ENTRY PROCEDURE [
proc: PROCEDURE [RoutingTableEntry]] =
BEGIN
e: RoutingTableEntry ← routingTableHead;
WHILE (e # NIL) DO proc[e]; e ← e.next; ENDLOOP;
END; -- EnumerateRoutingTable
RoutingTableCacheFault: PROCEDURE [destNetNumber: SpecialSystem.NetworkNumber] =
BEGIN
b: BufferDefs.OisBuffer;
e: RoutingTableEntry ← Heap.MakeNode[n: SIZE[RoutingTableObject]];
e↑ ← RoutingTableObject[
next: , destNetwork: destNetNumber, delay: maxRouterDelay,
timeUnits: updateCycles, route: unknownHostID, network: NIL];
AddEntry[e];
IF routingTableSanityChecking THEN SanityCheck[];
IF (b ← LOOPHOLE[DriverDefs.GetInputBuffer[TRUE], BufferDefs.OisBuffer])=NIL THEN RETURN;
-- GetInputBuffer is used to reliably get a buffer;
-- we need some like "get ois system buffer"
b.type ← ois;
b.ois.transCntlAndPktTp ← [initialTransportControl, routingInformation];
SetOisPacketTextLength[b, 2]; -- just one word of data
b.ois.routingType ← routingInfoRequest;
Router.BroadcastThisPacket[b];
END; -- RoutingTableCacheFault
-- This procedure fills in some routing information and sends the buffer out on the
-- appropriate network. The send is asynchronous; the caller owns the buffer and
-- receives its back from the the dispatcher via b.requeueProcedure (when the send
-- is completed).
FindNetworkAndTransmit: PUBLIC ENTRY PROCEDURE [b: BufferDefs.OisBuffer]
RETURNS [stat: XmitStatus] =
BEGIN
ENABLE UNWIND => NULL;
destHost: SpecialSystem.HostNumber ← b.ois.destination.host;
nextHost: SpecialSystem.HostNumber;
destNetNumber: SpecialSystem.NetworkNumber;
network: Network;
e: RoutingTableEntry ← FindNetworkNumber[destNetNumber ← b.ois.destination.net];
IF e=NIL OR (network←e.network)=NIL THEN
BEGIN -- outgoing packet for unknown net,
-- return b to the system buffer pool
b.status ← LOOPHOLE[stat ← XmitStatus[noRouteToNetwork]];
DriverDefs.PutOnGlobalDoneQueue[b];
IF e=NIL THEN RoutingTableCacheFault[destNetNumber];
IF CommFlags.doStats THEN StatIncr[statOisSentNowhere];
RETURN;
END;
-- outgoing packet to be transmitted over the correct network
IF (nextHost ← e.route) = unknownHostID
THEN nextHost ← destHost; -- intranet
b.status ← LOOPHOLE[stat ← XmitStatus[goodCompletion]];
network.encapsulateOis[b, nextHost];
-- synchronous buffer send
network.sendBuffer[b];
END; -- FindNetworkAndTransmit
ForwardPacket: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] =
BEGIN
ENABLE UNWIND => NULL;
nextHost: SpecialSystem.HostNumber;
e: RoutingTableEntry;
network: Network;
NotFoundDestinationNetworkLocked: ENTRY PROCEDURE RETURNS [BOOLEAN] = INLINE
{RETURN[(e ← FindNetworkNumber[b.ois.destination.net])=NIL OR (network ← e.network)=NIL]};
-- see if we have traversed max number of internet routers already
IF b.ois.transCntlAndPktTp.transportControl.hopCount >= maxInternetrouterHops THEN
BEGIN
Router.SendErrorPacket[b, excessHopsOisErrorCode, 0];
-- return b to the system buffer pool
DriverDefs.PutOnGlobalDoneQueue[b];
IF CommFlags.doStats THEN StatsDefs.StatIncr[statOisNotForwarded];
RETURN;
END;
IF NotFoundDestinationNetworkLocked[] THEN
BEGIN -- outgoing packet for unknown net
Router.SendErrorPacket[b, cantGetThereOisErrorCode, 0];
IF CommFlags.doStats THEN StatIncr[statOisNotForwarded];
b.status ← LOOPHOLE[XmitStatus[noRouteToNetwork]];
-- return b to the system buffer pool
DriverDefs.PutOnGlobalDoneQueue[b];
END
ELSE
BEGIN -- outgoing packet
Checksums.IncrOisTransportControlAndUpdateChecksum[b];
-- now transmit it over the correct network
IF (nextHost ← e.route) = unknownHostID THEN nextHost ← b.ois.destination.host;
-- same net
network.encapsulateOis[b, nextHost];
network.sendBuffer[b];
IF CommFlags.doStats THEN StatIncr[statOisForwarded];
END;
END; -- ForwardPacket
-- Cool Procedures
-- This procedure tell the OISCP Router about a new network.
AddNetwork: PUBLIC ENTRY PROCEDURE [newNetwork: Network] =
BEGIN
AddNetworkLocked[newNetwork];
END; -- AddNetwork
-- This procedure tell the OISCP Router about a new network.
AddNetworkLocked: PRIVATE PROCEDURE [newNetwork: Network] =
BEGIN
unknownNetIdEntry, e: RoutingTableEntry;
IF NOT newNetwork.alive THEN RETURN;
-- network must be alive to be added to table
e ← FindNetworkNumber[newNetwork.netNumber, FALSE];
-- do not add a network of unknown number if an unknown number network already exists
IF e = NIL THEN
BEGIN
e ← Heap.MakeNode[n: SIZE[RoutingTableObject]];
AddEntry[e];
IF newNetwork.netNumber = unknownNetID THEN
BEGIN
probeAnInternetRouterCounter ← probeAnInternetRouterCounter + 1;
Process.Detach[FORK ProbeAnInternetRouter[newNetwork]];
-- this will help find the net number
END; -- of null network number non-existant
END; -- of entry not found
e↑ ← RoutingTableObject[
next: e.next, destNetwork: newNetwork.netNumber, delay: oneHop,
timeUnits: updateCycles, route: unknownHostID, network: newNetwork];
IF routingTableSanityChecking THEN SanityCheck[];
-- if an unKnownNetID network does not exist, then then make an entry for it
-- using this network.
IF FindNetworkNumber[unknownNetID, FALSE]=NIL THEN
BEGIN
unknownNetIdEntry ← Heap.MakeNode[n: SIZE[RoutingTableObject]];
unknownNetIdEntry↑ ← RoutingTableObject[
next:, destNetwork: unknownNetID, delay: oneHop, timeUnits: updateCycles,
route: unknownHostID, network: newNetwork];
AddEntry[unknownNetIdEntry];
END;
END; -- AddNetworkLocked
-- This procedure removes a network from the OISCP Router's tables.
RemoveNetwork: PUBLIC ENTRY PROCEDURE [oldNetwork: Network] =
BEGIN
unknownNetwork: Network;
RemoveNetworkLocked[oldNetwork];
-- we may have removed the unknownNetID network; if so replace it
IF FindNetworkNumber[unknownNetID, FALSE]=NIL AND
(unknownNetwork ← DriverDefs.GetDeviceChain[])#NIL THEN
AddNetworkLocked[unknownNetwork];
END; -- RemoveNetwork
-- This procedure removes a network from the OISCP Router's tables.
RemoveNetworkLocked: PRIVATE PROCEDURE [oldNetwork: Network] =
BEGIN
e: RoutingTableEntry;
DO
IF (e ← FindNetwork[oldNetwork])=NIL THEN EXIT;
RemoveEntry[e];
Heap.FreeNode[p: e];
ENDLOOP;
END; -- RemoveNetworkLocked
StateChanged: PUBLIC ENTRY PROCEDURE [network: Network] =
BEGIN
unknownNetwork: Network;
RemoveNetworkLocked[network];
AddNetworkLocked[network];
-- if the state changed on the unknownNetID network then that entry was
-- possibly deleted and NOT added back in; therefore, a new one must be found.
IF FindNetworkNumber[unknownNetID, FALSE]=NIL AND
(unknownNetwork ← DriverDefs.GetDeviceChain[])#NIL THEN
AddNetworkLocked[unknownNetwork];
IF routingTableSanityChecking THEN SanityCheck[];
END; -- StateChanged
RoutingInformationPacket: PUBLIC ENTRY PROCEDURE [b: BufferDefs.OisBuffer] =
BEGIN
newDelay: INTEGER;
objectNetID: SpecialSystem.NetworkNumber;
sameRoute, betterDelay, awfulDelay, newNetwork: BOOLEAN;
localRouterDelay: INTEGER = 1;
newRoute: SpecialSystem.HostNumber = b.ois.source.host;
e: RoutingTableEntry;
-- tricky, incomingNetwork must not become a dangling pointer while we don't have
-- the monitor locked. This could happen if the network over which the packet arrived
-- was removed. Sigh...
incomingNetwork: Network = b.network;
routingPacketType: OISCPTypes.RoutingInfoType = b.ois.routingType;
routingInfoLength: CARDINAL = b.ois.pktLength - OISCPTypes.bytesPerPktHeader - 2; -- first word
routingInfo: LONG POINTER TO OISCPTypes.RoutingInfoTuple ← @b.ois.routingTuple[0];
UpdateUnnumberedNetTable: INTERNAL PROCEDURE =
BEGIN
IF incomingNetwork.netNumber # unknownNetID THEN RETURN;
incomingNetwork.netNumber ← b.ois.source.net;
AddNetworkLocked[incomingNetwork];
END; -- UpdateUnnumberedNetTable
UpdateRoutingTable: INTERNAL PROCEDURE =
BEGIN
changed: BOOLEAN ← FALSE;
THROUGH [0..routingInfoLength/(2*SIZE[OISCPTypes.RoutingInfoTuple])) DO
newDelay ← routingInfo.interrouterDelay + localRouterDelay;
awfulDelay ← newDelay > maxRouterDelay;
objectNetID ← routingInfo.objectNetID;
routingInfo ← routingInfo + SIZE[OISCPTypes.RoutingInfoTuple];
IF newDelay = oneHop THEN LOOP;
IF (e ← FindNetworkNumber[objectNetID, FALSE])=NIL THEN
IF (routersFunction=vanillaRouting) OR awfulDelay THEN LOOP
ELSE -- INR - keeps a large table of info that doesn't have an awful delay
BEGIN
e ← Heap.MakeNode[n: SIZE[RoutingTableObject]];
e↑ ← [next: , destNetwork: objectNetID, delay: newDelay, timeUnits: updateCycles, route: newRoute, network: incomingNetwork];
AddEntry[e];
changed ← TRUE;
END;
sameRoute ← e.route = newRoute AND e.network = incomingNetwork;
betterDelay ← newDelay < e.delay;
newNetwork ← (e.timeUnits < alternatePathTimeUnitThreshHold) OR (e.network = NIL);
-- Note: the value of sameRoute must be tested before the value of newNetwork
IF sameRoute THEN
BEGIN
IF awfulDelay THEN
BEGIN
-- timeUnits is NOT updated because the net is unreachable.
-- newDelay is set to avoid Nibble arithmetic wrap-around.
newDelay ← maxRouterDelay;
END
ELSE
BEGIN
e.timeUnits ← updateCycles;
END;
IF e.delay#newDelay THEN changed ← TRUE;
e.delay ← newDelay;
END
ELSE
IF (newNetwork AND NOT awfulDelay) OR (NOT newNetwork AND betterDelay) THEN
BEGIN
changed ← TRUE;
e↑ ← RoutingTableObject[
next: e.next, destNetwork: objectNetID, delay: newDelay,
timeUnits: updateCycles, route: newRoute, network: incomingNetwork];
END;
ENDLOOP;
-- if we are a INR and something has changes then progate the information
IF routersFunction=interNetworkRouting AND changed THEN NOTIFY internetRouterTimer;
END; -- UpdateRoutingTabler
-- main body of the procedure
IF routingTableSanityChecking THEN SanityCheck[];
IF b.ois.transCntlAndPktTp.packetType # routingInformation
OR (b.ois.source.host=myHostID AND routingPacketType=routingInfoResponse) -- don't need to listen to myself
OR newRoute = unknownHostID
OR incomingNetwork = NIL THEN RETURN;
IF CommFlags.doStats THEN StatIncr[statOisGatewayPacketsRecv];
IF routersFunction = interNetworkRouting AND routingPacketType =
routingInfoRequest THEN
BEGIN
e: RoutingTableEntry;
netNumber: SpecialSystem.NetworkNumber = b.ois.source.net;
net: Network ← incomingNetwork;
host: SpecialSystem.HostNumber ← b.ois.source.host;
-- we hope at this point that incomingNetwork isn't a dangling pointer
IF netNumber#unknownNetID THEN
BEGIN
e ← FindNetworkNumber[netNumber, FALSE];
IF e=NIL OR (net←e.network)=NIL THEN RETURN; -- can't find route back to requestor
IF e.route#unknownHostID THEN host ← e.route;
END;
SendRoutingInfoResponse[b.ois.source, host, net];
RETURN;
END;
IF routingPacketType = routingInfoResponse THEN
BEGIN
-- Examine Packet
UpdateUnnumberedNetTable[];
UpdateRoutingTable[];
END;
IF routingTableSanityChecking THEN SanityCheck;
END; -- RoutingInformationPacket
-- This procedure sends out Routing Information Protocol Request packets when
-- a new network is added to the OISCP Router's tables. If the Network were to
-- go away while we probe, we are in trouble, because we release the monitor when
-- we do a wait. In general this is a bad thing, but we asume that broadcast networks
-- like the Ethernet will be the only ones over which we can bind the network number
-- dynamically and they will be permenantish!
ProbeAnInternetRouter: PROCEDURE [network: Network] =
BEGIN
myBufferAccessHandle: BufferDefs.BufferAccessHandle ←
BufferDefs.MakeBufferPool[total: 1, send: 1, forSystemUse: FALSE];
b: BufferDefs.OisBuffer;
ExitFromProbeAnInternetRouter: ENTRY PROCEDURE = INLINE
BEGIN
WHILE myBufferAccessHandle.sendInUse#0 DO -- wait for all async sends to complete
WAIT responseFromInternetRouter;
ENDLOOP;
probeAnInternetRouterCounter ← probeAnInternetRouterCounter - 1;
BROADCAST responseFromInternetRouter
END;
ResponseFromInternetRouterPositive: ENTRY PROCEDURE RETURNS [BOOLEAN] = INLINE
BEGIN
WAIT responseFromInternetRouter;
RETURN[network.netNumber # unknownNetID];
END; -- ResponseFromInternetRouterPositive
THROUGH [0..30) UNTIL pleaseStop DO
b ← OISCP.GetFreeSendOisBufferFromPool[myBufferAccessHandle];
b.ois.transCntlAndPktTp ← [initialTransportControl, routingInformation];
SetOisPacketTextLength[b, 2]; -- just one word of data
b.ois.source ← b.ois.destination ←
[net: unknownNetID, host: allHostIDs, socket: OISCPConstants.routingInformationSocket];
b.ois.source.host ← myHostID;
b.ois.routingType ← routingInfoRequest;
Router.SendPacket[b];
IF CommFlags.doStats THEN StatsDefs.StatIncr[statOisBroadcast];
IF ResponseFromInternetRouterPositive[] THEN EXIT;
ENDLOOP;
ExitFromProbeAnInternetRouter[];
BufferDefs.FreeBufferPool[myBufferAccessHandle];
END; -- ProbeAnInternetRouter
-- This procedure sends out Routing Information Protocol Response packet on request.
-- Note that this is not an (network) ENTRY procedure even though we are touching a
-- Network. RouterSee had a pointer to the Network, and we hope that this hasn't become a
-- dangling pointer.
-- NOTE: this should be called from inside an ENTRY procedure.
-- 'to' is the ultimate destination, 'host' is the encapsulation destination.
SendRoutingInfoResponse: PROCEDURE [to: SpecialSystem.NetworkAddress, host: SpecialSystem.HostNumber, network: Network] =
BEGIN
maxBytesPerRoutingPacket: CARDINAL = OISCPTypes.maxBytesPerPkt - 2*SIZE[OISCPTypes.RoutingInfoTuple];
nextRoutingEntry: RoutingTableEntry ← routingTableHead;
sendBuf: BufferDefs.OisBuffer ← NIL;
nextResponseEntry: INTEGER;
IF routingTableSanityChecking THEN SanityCheck[];
UNTIL nextRoutingEntry=NIL DO
IF nextRoutingEntry.destNetwork # SpecialSystem.nullNetworkNumber
AND nextRoutingEntry.network # NIL THEN -- bypass the null network entry or a nil entry
BEGIN
IF sendBuf=NIL THEN
BEGIN
IF (sendBuf ← DriverDefs.MaybeGetFreeOisBuffer[])=NIL THEN RETURN; -- give up!
sendBuf.ois.transCntlAndPktTp ← [initialTransportControl, routingInformation];
sendBuf.ois.routingType ← routingInfoResponse;
sendBuf.ois.source ← [network.netNumber, myHostID, OISCPConstants.routingInformationSocket];
sendBuf.ois.destination ← to;
sendBuf.ois.pktLength ← OISCPTypes.bytesPerPktHeader + 2;
sendBuf.network ← network;
sendBuf.allNets ← (host = SpecialSystem.broadcastHostNumber);
nextResponseEntry ← 0;
END; -- of getting a new send buffer
sendBuf.ois.routingTuple[nextResponseEntry] ← [nextRoutingEntry.destNetwork, nextRoutingEntry.delay];
nextResponseEntry ← nextResponseEntry + 1;
sendBuf.ois.pktLength ← sendBuf.ois.pktLength+2*SIZE[OISCPTypes.RoutingInfoTuple];
END;
nextRoutingEntry ← nextRoutingEntry.next;
IF (sendBuf#NIL) AND ((nextRoutingEntry=NIL)
OR (sendBuf.ois.pktLength>=maxBytesPerRoutingPacket)) THEN
BEGIN
IF ~network.alive THEN
BEGIN
DriverDefs.PutOnGlobalDoneQueue[sendBuf];
END
ELSE
BEGIN
IF checkIt THEN Checksums.SetChecksum[sendBuf] ELSE sendBuf.ois.checksum ← 177777B;
network.encapsulateOis[sendBuf, host];
network.sendBuffer[sendBuf];
END;
sendBuf ← NIL;
END; -- of sending a full routing buffer
ENDLOOP; -- end of send loop
END; -- SendRoutingInfoResponse
-- This process wakes up every 30 seconds and sends out Routing Information
--- Protocol Response packets gratuitously, if this system element is an internet router.
InternetRouterServer: ENTRY PROCEDURE =
BEGIN
inrAccessHandle: BufferDefs.BufferAccessHandle;
inrRunning ← TRUE;
inrAccessHandle ← BufferDefs.MakeBufferPool[inrBufferCount, 0, 0, 0, TRUE];
-- since we are an INR, make sure the drivers have plenty of buffers
-- and get a few of out own too.
DriverDefs.ChangeNumberOfInputBuffers[TRUE];
UNTIL pleaseStop OR iNRpleaseStop DO
WAIT internetRouterTimer;
IF pleaseStop OR iNRpleaseStop THEN EXIT;
SendRoutingInfoResponse[[unknownNetID, SpecialSystem.broadcastHostNumber, OISCPConstants.routingInformationSocket], SpecialSystem.broadcastHostNumber, DriverDefs.GetDeviceChain[]];
ENDLOOP;
-- undo the buffer allocated for the INR
DriverDefs.ChangeNumberOfInputBuffers[FALSE];
BufferDefs.FreeBufferPool[inrAccessHandle];
inrRunning ← FALSE;
END; -- InternetRouterServer
-- This process wakes up every 60 seconds. On awakening it goes through the
-- routing table entries decrementing by one the time since the entry was last
-- updated. If the time is zero, then the destination net is deemed unreachable.
RoutingTableUpdater: ENTRY PROCEDURE =
BEGIN
rte: RoutingTableEntry;
UNTIL pleaseStop DO
IF routingTableSanityChecking THEN SanityCheck[];
-- no need to probe an internet router, since they broadcast every 30 secs.
rte ← routingTableHead;
WHILE (rte # NIL) DO
IF rte.delay # oneHop THEN
BEGIN
IF rte.timeUnits = 0 THEN
BEGIN
temp: RoutingTableEntry ← rte;
rte ← rte.next;
RemoveEntry[temp];
Heap.FreeNode[p: temp];
LOOP;
END
ELSE rte.timeUnits ← rte.timeUnits - 1;
END;
rte ← rte.next;
ENDLOOP;
WAIT routingTableUpdateTimer;
ENDLOOP;
END; -- RoutingTableUpdater
-- This returns the ID of the locally connected networkmost suitable to get to the
-- destination network.
FindDestinationRelativeNetID: PUBLIC ENTRY PROCEDURE [destNet: SpecialSystem.NetworkNumber]
RETURNS [netNumber: SpecialSystem.NetworkNumber] =
BEGIN
e: RoutingTableEntry;
IF (e ← FindNetworkNumber[destNet])=NIL OR (e.network=NIL) THEN RETURN[unknownNetID];
netNumber ← e.network.netNumber;
IF netNumber=unknownNetID THEN
BEGIN
-- since unknownNetID is uniformative find the first network with a known
-- network Number and use it.
n: Network ← DriverDefs.GetDeviceChain[];
DO
IF (netNumber ← n.netNumber)#unknownNetID THEN EXIT; -- gotIt!
IF (n ← n.next)=NIL THEN EXIT; -- a non - unknownNetID network does not exist!
ENDLOOP;
END; -- find non - unknownNetID network clause
END; -- FindDestinationRelativeNetID
-- This procedure returns what the router is.
GetRouterFunction: PUBLIC ENTRY PROCEDURE RETURNS [RoutersFunction] =
BEGIN RETURN[routersFunction]; END;
--Cold Procedures
-- The router must be told which function to perform.
-- Race condition with RoutingTableOn and RoutingTableOff concerning
-- FORKing and JOINing internetRouterServerFork. Races should not occur
-- because all of these are very Cold and only this procedure is exported
-- out of Pilot.
SetRouterFunction: PUBLIC PROCEDURE [newFunction: RoutersFunction, numberINRBuffers: CARDINAL]
RETURNS [oldFunction: RoutersFunction] =
BEGIN
joinTheINRServer: BOOLEAN ← FALSE;
zombieINRServer: PROCESS;
SetFunction: ENTRY PROCEDURE =
BEGIN
temp: CONDITION;
oldFunction ← routersFunction;
routersFunction ← newFunction;
IF primaryMDS THEN
BEGIN
IF oldFunction=interNetworkRouting THEN
BEGIN
Process.SetTimeout[@temp, Process.MsecToTicks[500]];
joinTheINRServer ← iNRpleaseStop ← TRUE;
zombieINRServer ← internetRouterServerFork;
WHILE inrRunning DO
NOTIFY internetRouterTimer;
WAIT temp;
ENDLOOP;
END;
IF newFunction=interNetworkRouting THEN
BEGIN
iNRpleaseStop ← FALSE;
inrBufferCount ← numberINRBuffers;
internetRouterServerFork ← FORK InternetRouterServer[];
END;
END; -- primaryMDS clause
END; -- inline of SetFunction
-- mainline code of SetRouterFunction
SetFunction[];
IF joinTheINRServer THEN JOIN zombieINRServer;
END;
-- This procedure turns the router on. The Communication software is written with the
-- idea of eventually turning the code on and off during execution, and so we should
-- get the latest values of netID when being turned back on. The processes asociated
-- with the routing table should be created only if this module is in the primary MDS.
RoutingTableOn: PUBLIC PROCEDURE =
BEGIN
inrRunning ← iNRpleaseStop ← pleaseStop ← FALSE;
IF primaryMDS THEN
BEGIN
network: Network ← DriverDefs.GetDeviceChain[];
RoutingTableActivate[];
FOR network ← network, network.next UNTIL network = NIL DO
AddNetwork[network]; ENDLOOP;
IF routersFunction = interNetworkRouting THEN
internetRouterServerFork ← FORK InternetRouterServer[];
routingTableFork ← FORK RoutingTableUpdater[];
END;
END; -- RoutingTableOn
RoutingTableActivate: ENTRY PROCEDURE = INLINE
BEGIN routingTableHead ← NIL;
myHostID ← Router.FindMyHostID[];
probeAnInternetRouterCounter ← 0;
routingTableSize ← 0;
END; -- RoutingTableActivate
RoutingTableOff: PUBLIC PROCEDURE =
BEGIN
IF primaryMDS THEN
BEGIN
RoutingTableDeactivate[];
JOIN routingTableFork[];
IF routersFunction = interNetworkRouting THEN JOIN internetRouterServerFork;
CleanUpRoutingTable[];
END;
END; -- RoutingTableOff
RoutingTableDeactivate: ENTRY PROCEDURE = INLINE
BEGIN
iNRpleaseStop ← pleaseStop ← TRUE;
NOTIFY routingTableUpdateTimer;
BROADCAST responseFromInternetRouter;
IF routersFunction = interNetworkRouting THEN NOTIFY internetRouterTimer;
-- clean up all the detached ProbeAnInternetRouter(s)
WHILE (probeAnInternetRouterCounter>0) DO
BROADCAST responseFromInternetRouter;
WAIT responseFromInternetRouter;
ENDLOOP;
END; -- RoutingTableDeactivate
CleanUpRoutingTable: ENTRY PROCEDURE = INLINE
BEGIN
e, temp: RoutingTableEntry;
e ← routingTableHead;
WHILE e # NIL DO temp ← e; e ← e.next; Heap.FreeNode[p: temp]; ENDLOOP;
routingTableSize ← 0;
END; -- RoutingTableDeactivate
-- initialization (Cold)
Process.SetTimeout[@routingTableUpdateTimer, Process.MsecToTicks[60000]];
Process.SetTimeout[@responseFromInternetRouter, Process.MsecToTicks[1000]];
Process.SetTimeout[@internetRouterTimer, Process.MsecToTicks[30000]];
END. -- RoutingTableImpl module.
LOG
Time: January 19, 1980 4:05 PM By: Dalal Action: Split OISCPRouter into two.
Time: March 13, 1980 5:11 PM By: BLyon Action: FindNetworkAndTransmit synchronously sends non-system buffers and asynchronously sends system buffers.
Time: July 31, 1980 11:53 AM By: BLyon Action: replaced internetRouter with routersFunction and added Get/SetRoutersFunction.
Time: August 5, 1980 4:25 PM By: BLyon Action: RoutingTable is now linked list and no such concept as primaryNetID.
Time: September 13, 1980 6:15 PM By: HGM Action: Add StateChanged.
Time: September 18, 1980 3:16 PM By: BLyon Action: modified StateChanged, Add/Delete Network .., removed FindPrimaryNetID.
Time: January 5, 1981 4:00 PM By: BLyon Action: added EnumerateRoutingTable.
Time: February 24, 1981 2:58 PM By: BLyon Action: added stuff to tell INR how many buffers to use.
Time: March 19, 1981 10:38 AM By: BLyon Action: Modified FindDestinationRelativeNetID to try and not return unknownNetID if at all possible.