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