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],
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],
NSAddress USING [broadcastHostNumber, HostNumber, NetworkAddress, NetworkNumber, nullNetworkNumber];

RoutingTableImpl: MONITOR
IMPORTS BufferDefs, Checksums, DriverDefs, OISCP, Process, Router, StatsDefs
EXPORTS BufferDefs, CommunicationInternal, Router, SpecialCommunication
SHARES BufferDefs =
BEGIN OPEN OISCP, Router, StatsDefs, SpecialCommunication;

Network: PUBLIC TYPE = DriverDefs.Network;


myHostID: NSAddress.HostNumber; -- host ID of this system element
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
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;

RoutingTableScrambled: PUBLIC ERROR = CODE;
routingTableSanityChecking: BOOLEAN = FALSE;



SanityCheck: PROCEDURE = INLINE
BEGIN
e: RoutingTableEntry _ routingTableHead;
WHILE e#NIL DO
IF e.delay=0 THEN ERROR;
e _ e.next;
ENDLOOP;
END;

FindNetworkNumber: PROCEDURE [num: NSAddress.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;

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;

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;

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: NSAddress.NetworkNumber] =
BEGIN
b: BufferDefs.OisBuffer;
e: RoutingTableEntry _ NEW[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;
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

FindNetworkAndTransmit: PUBLIC ENTRY PROCEDURE [b: BufferDefs.OisBuffer]
RETURNS [stat: XmitStatus] =
BEGIN
ENABLE UNWIND => NULL;
destHost: NSAddress.HostNumber _ b.ois.destination.host;
nextHost: NSAddress.HostNumber;
destNetNumber: NSAddress.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,
b.status _ LOOPHOLE[stat _ XmitStatus[noRouteToNetwork]];
DriverDefs.PutOnGlobalDoneQueue[b];
IF e=NIL THEN RoutingTableCacheFault[destNetNumber];
IF CommFlags.doStats THEN StatIncr[statOisSentNowhere];
RETURN;
END;

IF (nextHost _ e.route) = unknownHostID
THEN nextHost _ destHost; -- intranet
b.status _ LOOPHOLE[stat _ XmitStatus[goodCompletion]];
network.encapsulateOis[b, nextHost];
network.sendBuffer[b];
END; -- FindNetworkAndTransmit

ForwardPacket: PUBLIC PROCEDURE [b: BufferDefs.OisBuffer] =
BEGIN
ENABLE UNWIND => NULL;
nextHost: NSAddress.HostNumber;
e: RoutingTableEntry;
network: Network;

NotFoundDestinationNetworkLocked: ENTRY PROCEDURE RETURNS [BOOLEAN] = INLINE
{RETURN[(e _ FindNetworkNumber[b.ois.destination.net])=NIL OR (network _ e.network)=NIL]};

IF b.ois.transCntlAndPktTp.transportControl.hopCount >= maxInternetrouterHops THEN
BEGIN
Router.SendErrorPacket[b, excessHopsOisErrorCode, 0];
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]];
DriverDefs.PutOnGlobalDoneQueue[b];
END
ELSE
BEGIN -- outgoing packet
Checksums.IncrOisTransportControlAndUpdateChecksum[b];
IF (nextHost _ e.route) = unknownHostID THEN nextHost _ b.ois.destination.host;
network.encapsulateOis[b, nextHost];
network.sendBuffer[b];
IF CommFlags.doStats THEN StatIncr[statOisForwarded];
END;
END; -- ForwardPacket

AddNetwork: PUBLIC ENTRY PROCEDURE [newNetwork: Network] =
BEGIN
AddNetworkLocked[newNetwork];
END; -- AddNetwork

AddNetworkLocked: PRIVATE PROCEDURE [newNetwork: Network] =
BEGIN
unknownNetIdEntry, e: RoutingTableEntry;
IF NOT newNetwork.alive THEN RETURN;
e _ FindNetworkNumber[newNetwork.netNumber, FALSE];
IF e = NIL THEN
BEGIN
e _ NEW[RoutingTableObject];
AddEntry[e];
IF newNetwork.netNumber = unknownNetID THEN
BEGIN
probeAnInternetRouterCounter _ probeAnInternetRouterCounter + 1;
Process.Detach[FORK ProbeAnInternetRouter[newNetwork]];
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 FindNetworkNumber[unknownNetID, FALSE]=NIL THEN
BEGIN
unknownNetIdEntry _ NEW[RoutingTableObject];
unknownNetIdEntry^ _ RoutingTableObject[
next:, destNetwork: unknownNetID, delay: oneHop, timeUnits: updateCycles,
route: unknownHostID, network: newNetwork];
AddEntry[unknownNetIdEntry];
END;
END; -- AddNetworkLocked

RemoveNetwork: PUBLIC ENTRY PROCEDURE [oldNetwork: Network] =
BEGIN
unknownNetwork: Network;
RemoveNetworkLocked[oldNetwork];
IF FindNetworkNumber[unknownNetID, FALSE]=NIL AND
(unknownNetwork _ DriverDefs.GetDeviceChain[])#NIL THEN
AddNetworkLocked[unknownNetwork];
END; -- RemoveNetwork

RemoveNetworkLocked: PRIVATE PROCEDURE [oldNetwork: Network] =
BEGIN
e: RoutingTableEntry;
DO
IF (e _ FindNetwork[oldNetwork])=NIL THEN EXIT;
RemoveEntry[e];
ENDLOOP;
END; -- RemoveNetworkLocked

StateChanged: PUBLIC ENTRY PROCEDURE [network: Network] =
BEGIN
unknownNetwork: Network;
RemoveNetworkLocked[network];
AddNetworkLocked[network];
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: NSAddress.NetworkNumber;
sameRoute, betterDelay, awfulDelay, newNetwork: BOOLEAN;
localRouterDelay: INTEGER = 1;
newRoute: NSAddress.HostNumber = b.ois.source.host;
e: RoutingTableEntry;
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 _ NEW[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);
IF sameRoute THEN
BEGIN
IF awfulDelay THEN
BEGIN
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 routersFunction=interNetworkRouting AND changed THEN NOTIFY internetRouterTimer;
END; -- UpdateRoutingTabler

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: NSAddress.NetworkNumber = b.ois.source.net;
net: Network _ incomingNetwork;
host: NSAddress.HostNumber _ b.ois.source.host;
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
UpdateUnnumberedNetTable[];
UpdateRoutingTable[];
END;
IF routingTableSanityChecking THEN SanityCheck;
END; -- RoutingInformationPacket

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

SendRoutingInfoResponse: PROCEDURE [to: NSAddress.NetworkAddress, host: NSAddress.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 # NSAddress.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 = NSAddress.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

InternetRouterServer: ENTRY PROCEDURE =
BEGIN
inrAccessHandle: BufferDefs.BufferAccessHandle;
inrRunning _ TRUE;
inrAccessHandle _ BufferDefs.MakeBufferPool[inrBufferCount, 0, 0, 0, TRUE];
DriverDefs.ChangeNumberOfInputBuffers[TRUE];
UNTIL pleaseStop OR iNRpleaseStop DO
WAIT internetRouterTimer;
IF pleaseStop OR iNRpleaseStop  THEN EXIT;
SendRoutingInfoResponse[[unknownNetID, NSAddress.broadcastHostNumber, OISCPConstants.routingInformationSocket], NSAddress.broadcastHostNumber, DriverDefs.GetDeviceChain[]];
ENDLOOP;
DriverDefs.ChangeNumberOfInputBuffers[FALSE];
BufferDefs.FreeBufferPool[inrAccessHandle];
inrRunning _ FALSE;
END; -- InternetRouterServer

RoutingTableUpdater: ENTRY PROCEDURE =
BEGIN
rte: RoutingTableEntry;
UNTIL pleaseStop DO
IF routingTableSanityChecking THEN SanityCheck[];
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];
LOOP;
END
ELSE rte.timeUnits _ rte.timeUnits - 1;
END;
rte _ rte.next;
ENDLOOP;
WAIT routingTableUpdateTimer;
ENDLOOP;
END; -- RoutingTableUpdater

FindDestinationRelativeNetID: PUBLIC ENTRY PROCEDURE [destNet: NSAddress.NetworkNumber]
RETURNS [netNumber: NSAddress.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
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

GetRouterFunction: PUBLIC ENTRY PROCEDURE RETURNS [RoutersFunction] =
BEGIN RETURN[routersFunction]; END;


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

SetFunction[];
IF joinTheINRServer THEN JOIN zombieINRServer;
END;


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;
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


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.  


NRoutingTableImpl.mesa - implementation module for the Pilot OISCP Router's routing table
Copyright c 1985 by Xerox Corporation.  All rights reserved.
BLyon on: March 19, 1981  5:41 PM
EXPORTed TYPEs
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
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;
controlling the entry processes
various Glitches generated by the Router
Hot Procedures
Routing list manipulation Routines
used only for debugging
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 .
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.
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.
This procedure adds an entry to the beginning of the Routingtable list.
GetInputBuffer is used to reliably get a buffer;
we need some like "get ois system buffer"
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).
return b to the system buffer pool
outgoing packet to be transmitted over the correct network
synchronous buffer send
see if we have traversed max number of internet routers already
return b to the system buffer pool
return b to the system buffer pool
now transmit it over the correct network
same net
Cool Procedures
This procedure tell the OISCP Router about a new network.  
This procedure tell the OISCP Router about a new network.
network must be alive to be added to table
do not add a network of unknown number if an unknown number network already exists
this will help find the net number
if an unKnownNetID network does not exist, then then make an entry for it 
using this network.
This procedure removes a network from the OISCP Router's tables.
we may have removed the unknownNetID network;  if so replace it
This procedure removes a network from the OISCP Router's tables.
Heap.FreeNode[p: e];--
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.
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...
Note: the value of sameRoute must be tested before the value of newNetwork
timeUnits is NOT updated because the net is unreachable.
newDelay is set to avoid Nibble arithmetic wrap-around.
if we are a INR and something has changes then progate the information
main body of the procedure
we hope at this point that incomingNetwork isn't a dangling pointer
Examine Packet
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!
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.
This process wakes up every 30 seconds and sends out Routing Information
- Protocol Response packets gratuitously, if this system element is an internet router.
since we are an INR, make sure the drivers have plenty of buffers 
and get a few of out own too.
undo  the buffer allocated for the INR
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.
no need to probe an internet router, since they broadcast every 30 secs.
Heap.FreeNode[p: temp];--
This returns the ID of the locally connected networkmost suitable to get to the
destination network.
since unknownNetID is uniformative find the first network with a known
network Number and use it.
This procedure returns what the router is.
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.
mainline code of SetRouterFunction
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.
clean up all the detached ProbeAnInternetRouter(s)
initialization (Cold)
Κή˜
codeš
œX™XKšœ
Οm
œ1™<Kš
œ!™!—K˜š
Οk	˜	KšœžœA˜QKšœ
žœ9˜HKšœžœ˜Kšœ
žœ˜#Kšœžœ|˜Œ
Kšžœ
žœa˜lKšœžœ˜0KšœžœZ˜jKšœžœ#˜0Kšœžœ£
˜―
Kšœ
žœ˜Kšœžœ˜-šœ
žœU˜dK˜——šœž˜Kšžœ$žœ˜LKšžœ@˜GKšžœ
˜Kšž
œ
žœ*˜:K˜Kš
œ™Kšœ	žœ
žœ˜*K˜Kš
œP™PKš
œO™OKš
œY™YK˜Kš
œ™Kšœ Οc!˜AKš
œ%™%Kš
œR™RKš
œQ™QKšœ&žœ
˜*Kšœžœ˜Kšœžœ˜#KšœžœŸ+˜T˜6Kšœžœ˜'—KšœŸ9˜MKšœŸG˜aKšœ!žœŸI˜xKšœžœŸ˜;KšœžœŸ$˜JKš
œ™KšœžœŸ-˜MKšœ'žœŸ'˜W˜IKšž	œ
˜
—Kšœ,žœ
˜4K˜Kš
œ(™(Kšœžœ
žœžœ
˜+Kšœžœžœ
˜,K˜Kš
œ™K˜Kš
œ"™"K˜Kš
œ™šΟnœž	œž˜Kš
ž˜K˜(šžœžœ
ž˜Kšžœžœ
žœ
˜K˜Kšžœ
˜—Kšžœ
˜K˜—Kš
œU™UKš
œ9™9š œž	œ.žœžœ
˜YKšžœ˜ Kš
ž˜K˜/šžœžœ
žœ
˜šžœž˜Kš
ž˜šžœžœž˜0Kš
ž˜K˜K˜K˜Kšžœ
˜—Kšžœ
˜Kšžœ
˜—K˜	K˜Kšžœ
˜—Kšžœ
˜K˜—Kš
œQ™QKš
œ8™8š œž	œ˜%Kšžœ˜ Kš
ž˜K˜/šžœžœ
žœ
˜šžœž˜Kš
ž˜šžœž˜Kš
ž˜K˜K˜K˜Kšžœ
˜—Kšžœ
˜Kšžœ
˜—K˜	K˜Kšžœ
˜—Kšžœ
˜K˜—Kš
œT™TKš
œ1™1š œž	œ˜/Kš
ž˜Kšœžœ
˜K˜+šžœ	žœžœž˜#K˜K˜Kšžœ
˜—Kšžœžœ	žœžœ*˜TKšžœžœ
žœ˜,š
ž˜Kš
ž˜Kšžœžœžœ*˜WKšžœžœžœžœ*˜YK˜Kšžœ
˜—Kšœ	žœ
˜
K˜(Kšžœžœ&žœ*˜lKšžœ
˜K˜—Kš
œG™Gš œž	œ˜,Kš
ž˜K˜K˜K˜(Kšžœžœ&žœ*˜lKšžœ
˜K˜—š œžœ
žœ
ž	œ˜/Kšœž	œ˜&Kš
ž˜K˜(Kšžœžœžœžœ
˜0KšžœŸ˜K˜—š œž	œ+˜LKš
ž˜K˜Kšœžœ˜/˜K˜:Kšœ8žœ˜=—K˜Kšžœžœ˜1Kšžœžœžœžœ
žœ
žœ
˜YKš
œ0™0Kš
œ)™)K˜
K˜HKšœŸ˜6K˜'K˜KšžœŸ˜K˜—Kš
œQ™QKš
œO™OKš
œO™OKš
œ™š œžœ
žœ
ž	œ˜HKšžœ˜Kš
ž˜Kšžœ
žœžœ
˜K˜8K˜K˜'K˜K˜Pš	žœžœ
žœžœ
ž˜(Kšžœ
Ÿ#˜)Kš
œ"™"Kšœžœ&˜9K˜#Kšžœžœ
žœ'˜4Kšžœžœ˜7Kšžœ
˜Kšžœ
˜K˜—Kš
œ:™:šžœ%˜'KšžœŸ˜%—Kšœžœ$˜7K˜$Kš
œ™K˜KšžœŸ˜K˜—š 
œžœ
ž	œ˜;Kš
ž˜Kšžœ
žœžœ
˜K˜K˜K˜K˜Kš  œžœ
ž	œ
žœžœž˜LKš	œ
žœ0žœ
žœžœ˜ZK˜Kš
œ?™?šžœLž˜RKš
ž˜K˜5Kš
œ"™"K˜#Kšžœžœ)˜BKšžœ
˜Kšžœ
˜K˜—šžœ$ž˜*Kšžœ
Ÿ"˜(K˜7Kšžœžœ˜8Kšœžœ˜2Kš
œ"™"K˜#Kš
ž˜—š
ž˜Kšžœ
Ÿ˜K˜6Kš
œ(™(Kšžœ&žœ#˜OKš
œ™K˜$K˜Kšžœžœ˜5Kšžœ
˜—KšžœŸ˜K˜—Kš
œ™Kš
œ;™;š 
œžœ
žœ
ž	œ˜:Kš
ž˜K˜KšžœŸ
˜K˜—Kš
œ9™9š œžœ
ž	œ˜;Kš
ž˜K˜(Kšžœ
žœžœ
žœ
˜$Kš
œ*™*Kšœ,žœ˜3Kš
œR™Ršžœžœ
ž˜Kš
ž˜Kšœžœ˜K˜šžœ%ž˜+Kš
ž˜K˜@Kšœžœ$˜7Kš
œ"™"KšžœŸ&˜,—KšžœŸ˜—˜K˜?K˜D—Kšžœžœ˜1Kš
œJ™JKš
œ™šžœ!žœžœ
ž˜2Kš
ž˜Kšœžœ˜,˜(K˜IK˜+—K˜Kšžœ
˜—KšžœŸ˜K˜—Kš
œ@™@š 
œžœ
žœ
ž	œ˜=Kš
ž˜K˜K˜ Kš
œ?™?šžœ!žœžœ
ž˜1Kšœ/žœ
ž˜7K˜!—KšžœŸ˜K˜—Kš
œ@™@š œžœ
ž	œ˜>Kš
ž˜K˜š
ž˜Kšžœžœ
žœ
žœ
˜/K˜Kš
œ™Kšžœ
˜—KšžœŸ˜K˜—š œžœ
žœ
ž	œ˜9Kš
ž˜K˜K˜K˜Kš
œE™EKš
œK™Kšžœ!žœžœ
ž˜1Kšœ/žœ
ž˜7K˜!—Kšžœžœ˜1KšžœŸ˜K˜—š œžœ
žœž	œ˜MKš
ž˜Kšœ
žœ
˜K˜%Kšœ0žœ
˜8Kšœžœ˜K˜3K˜Kš
œN™NKš
œS™SKš
œ™K˜%K˜BKšœžœ7Ÿ
˜_Kšœ
žœ
žœ
žœ6˜RK˜š œžœ
ž	œ˜.Kš
ž˜Kšžœ*žœ
žœ
˜8K˜-K˜"KšžœŸ˜ K˜—š œžœ
ž	œ˜(Kš
ž˜Kšœ	žœžœ
˜šžœžœ ž˜GK˜;K˜'K˜&Kšœžœ˜>Kšžœžœ
žœ
˜Kšžœ%žœžœ
ž˜7—Kšžœ"žœžœ
ž˜;šžœŸE˜KKš
ž˜Kšœžœ˜K˜}K˜Kšœ
žœ
˜šžœ
˜Kšœžœ˜?K˜!Kšœ=žœžœ˜R———š
œJ™Jšžœž˜Kš
ž˜šžœž˜Kš
ž˜Kš
œ8™8Kš
œ7™7K˜Kš
ž˜—š
ž˜Kš
ž˜K˜Kšžœ
˜—Kšžœžœžœ
˜(K˜Kš
ž˜—š
ž˜š
žœ
žœ
žœ
žœžœžœž˜KKš
ž˜——šœ
žœ
˜˜K˜8K˜D—Kšžœ
˜šžœ
˜Kš
œF™FKšžœ%žœ	žœ
žœ˜S——KšžœŸ˜K˜Kš
œ™Kšžœžœ˜1Kšžœ8˜:Kšžœžœ)Ÿ!˜lKšžœ˜Kšžœžœ
žœ
žœ
˜%Kšžœžœ%˜>šžœ'žœ˜@Kšœž˜Kš
ž˜K˜K˜6K˜K˜/Kš
œC™Cšžœž˜Kš
ž˜Kšœ!žœ˜(Kš
žœžœ
žœžœ
žœ
žœŸ%˜RKšžœžœ˜-Kšžœ
˜—K˜1Kšžœ
˜Kšžœ
˜—šžœ)ž˜/Kš
ž˜Kš
œ™K˜K˜Kšžœ
˜—Kšžœžœ
˜/KšžœŸ˜ K˜——Kš
œJ™JKš
œL™LKš
œN™NKš
œS™SKš
œQ™QKš
œ*™*š œž	œ˜5Kš
ž˜˜6Kšœ;žœ˜B—K˜K˜š œžœ
ž	œž˜7Kš
ž˜šžœ"žœŸ'˜RKšžœ˜ Kšžœ
˜—K˜@Kšž	œ˜$Kšžœ
˜K˜—š "œžœ
ž	œ
žœžœž˜NKš
ž˜Kšžœ˜ Kšžœ#˜)KšžœŸ%˜*K˜—šžœ	žœž˜#Kšœžœ4˜=K˜HKšœŸ˜6˜"K˜W—K˜K˜'K˜Kšžœžœ&˜?Kšžœ&žœ
žœ
˜2Kšžœ
˜—K˜ K˜0KšžœŸ˜K˜—Kš
œQ™QKš
œP™PKš
œV™VKš
œ™Kš
œ<™<Kš
œJ™Jš œž	œO˜qKš
ž˜Kšœžœ!žœ˜eK˜7Kšœ žœ
˜$Kšœžœ
˜Kšžœžœ˜1šžœžœ
ž˜Kšžœ;˜=šžœžœ
žœŸ0˜YKš
ž˜šžœ	žœ
žœ
˜Kš
ž˜Kš	žœ0žœ
žœ
žœŸ˜OK˜NK˜.K˜\K˜K˜9K˜K˜9K˜KšžœŸ˜%—K˜eK˜*Kšœ0žœ˜RKšžœ
˜—K˜)Kšžœ
žœžœžœ
˜,šžœ4ž˜:Kš
ž˜šžœž˜Kš
ž˜K˜)Kš
ž˜—š
ž˜Kš
ž˜Kšžœ	žœ žœ ˜SK˜&K˜Kšžœ
˜—Kšœ
žœ
˜KšžœŸ#˜)—KšžœŸ˜—KšžœŸ˜K˜—Kš
œH™HKš
œW™Wš œžœ
ž	œ˜'Kš
ž˜K˜/Kšœ
žœ
˜KšœEžœ˜KKš
œB™BKš
œ™Kšœ&žœ˜,šžœžœž˜$Kšžœ˜Kšžœžœžœ
žœ
˜*K˜¬
Kšžœ
˜—Kš
œ&™&Kšœ&žœ˜-K˜+Kšœ
žœ
˜KšžœŸ˜K˜—Kš
œI™IKš
œK™KKš
œN™Nš œžœ
ž	œ˜&Kš
ž˜K˜šžœž˜Kšžœžœ˜1Kš
œH™HK˜šžœžœž˜šžœž˜Kš
ž˜šžœž˜Kš
ž˜K˜K˜K˜Kš
œ™Kšžœ
˜Kš
ž˜—Kšžœ#˜'Kšžœ
˜—K˜Kšžœ
˜—Kšžœ˜Kšžœ
˜—KšžœŸ˜K˜—Kš
œO™OKš
œ™š œžœ
žœ
ž	œ#˜WKšžœ'˜.Kš
ž˜K˜Kšžœ"žœ
žœžœžœ
žœ˜UK˜ šžœž˜Kš
ž˜Kš
œF™FKš
œ™K˜)š
ž˜Kšžœ(žœ
žœŸ	˜>Kš	žœžœ
žœ
žœŸ/˜NKšžœ
˜—KšžœŸ)˜.—KšžœŸ˜$K˜—Kš
œ*™*š
 œžœ
žœ
ž	œ
žœ˜EKšžœ
žœžœ
˜#K˜—Kš
œ™K˜Kš
œ2™2Kš
œA™AKš
œG™GKš
œG™GKš
œ
™
š œžœ
ž	œ2žœ
˜^Kšžœ!˜(Kš
ž˜Kšœžœžœ
˜"Kšœžœ
˜K˜š œžœ
ž	œ˜Kš
ž˜Kšœž	œ
˜K˜K˜šžœž˜Kš
ž˜šžœ!ž˜'Kš
ž˜K˜4Kšœ#žœ
˜(K˜+šžœž˜Kšžœ˜Kšžœ˜
Kšžœ
˜—Kšžœ
˜—šžœ!ž˜'Kš
ž˜Kšœžœ
˜K˜"Kšœžœ˜7Kšžœ
˜—KšžœŸ˜—KšžœŸ˜K˜—Kš
œ"™"K˜Kšžœžœ
žœ˜.Kšžœ
˜K˜K˜—Kš
œS™SKš
œQ™QKš
œR™RKš
œS™Sš œžœ
ž	œ˜"Kš
ž˜Kšœ*žœ
˜0šžœž˜Kš
ž˜K˜/K˜šžœ!žœžœ
ž˜:Kšœžœ
˜—šžœ'ž˜-Kšœžœ˜7—Kšœžœ˜.Kšžœ
˜—KšžœŸ˜K˜—š œžœ
ž	œž˜.Kšžœžœ
˜K˜!K˜!K˜KšžœŸ˜K˜—š œžœ
ž	œ˜#Kš
ž˜šžœž˜Kš
ž˜K˜Kšžœ˜Kšžœ'žœ
žœ˜LK˜Kšžœ
˜—KšžœŸ˜K˜—š œžœ
ž	œž˜0Kš
ž˜Kšœžœ
˜"Kšžœ˜Kšž	œ˜%Kšžœ'žœ
žœ˜IKš
œ2™2šžœ"ž˜)Kšž	œ˜%Kšžœ˜ Kšžœ
˜—KšžœŸ˜K˜—š œžœ
ž	œž˜-Kš
ž˜K˜K˜Kš
žœžœ
žœŸœ
žœ
˜KK˜KšžœŸ˜K˜—Kš
œ™K˜K˜IK˜KK˜EK˜KšžœŸ˜!K˜—Kš
ž˜K˜Kšœžœ0˜OKšœžœ{˜˜
Kšœžœd˜
KšœžœZ˜wKšœžœžœ˜FKšœžœ]˜~Kšœžœ0˜NKšœžœ(žœ˜dKšœžœr˜
K˜K˜—…—T*ƒV