-- File: InrRoutingTableImpl.mesa - last edit:
-- AOF 5-Feb-88 13:48:34
-- Leong 16-Sep-87 13:42:15
-- Kluger 22-Oct-85 8:05:50
-- Copyright (C) 1984, 1985, 1986, 1988 by Xerox Corporation. All rights reserved.
-- Function: The implementation module for the NS INR's routing table.
<<
IMPLEMENTATION NOTE:
Note that opaque types System.NetworkNumber and System.HostNumber are EXPORTed here as well as in module INRImpl. This is to allow referencing of the type without LOOPHOLEs.
>>
DIRECTORY
Buffer USING [],
CommHeap USING [zone],
CommFlags USING [doDebug],
CourierInternal USING [ExchWords],
Driver USING [GetDeviceChain, Glitch, Device],
InrFriends USING [
DriverDetails, HopCount, Method, RoutingTableEntry, RoutingTableObject],
Inline USING [BITAND],
InrInternal USING [
defaultNumberOfHashBits, deadEntryHopCount, infinityHopCount, inrLock,
localHop, maxInternetrouterHops, pleaseStop, INRRoutingTable,
SendGratuitousResponse, stats, updateCycles],
InrStats USING [RoutingTableSearch, tupleIndexTableSize],
NSConstants USING [routingInformationSocket],
Process USING [EnableAborts, Pause, SecondsToTicks, SetTimeout],
Protocol1 USING [GetContext],
Router USING [NoTableEntryForNet],
RoutingTable USING [NetworkContext],
Space USING [ScratchMap, Unmap, wordsPerPage],
SpecialSystem USING [HostNumber, NetworkNumber],
System USING [
broadcastHostNumber, GetClockPulses, NetworkAddress, NetworkNumber,
nullHostNumber, nullNetworkAddress, nullNetworkNumber, nullSocketNumber,
Pulses];
InrRoutingTableImpl: MONITOR LOCKS InrInternal.inrLock
IMPORTS InrInternal,
CommHeap, CourierInternal, Driver,
Inline, Process, Protocol1, Router, Space, System
EXPORTS
Buffer, InrFriends, InrInternal, InrStats, System =
BEGIN
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- TYPEs locally and externally declared
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
NetworkContext: TYPE = RoutingTable.NetworkContext;
Device: PUBLIC TYPE = Driver.Device; -- clear the opaque type in Buffer
NetworkNumber: PUBLIC TYPE = SpecialSystem.NetworkNumber;
-- NetworkNumber is also EXPORTed here (in addition to INRImpl) because
-- System defines NetworkNumber to an opaque type, TYPE[2], and we want
-- to be able to work with the internals
HostNumber: PUBLIC TYPE = SpecialSystem.HostNumber; -- also EXPORTed by INRImpl
HopCount: TYPE = InrFriends.HopCount;
RoutingTableEntry : TYPE = InrFriends.RoutingTableEntry;
RoutingTableObject: TYPE = InrFriends.RoutingTableObject;
INRRoutingTable: TYPE = InrInternal.INRRoutingTable;
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- CONSTANTS that make it all happen
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
unknownHostID: HostNumber = System.nullHostNumber;
nullNetworkNumber: NetworkNumber = System.nullNetworkNumber;
-- routing info request network number that indicates all networks
localHop: InrFriends.HopCount = InrInternal.localHop;
-- rte delay for attached network(s) is zero hops.
allLocalInternetRouters: System.NetworkAddress = [
net: nullNetworkNumber, host: System.broadcastHostNumber,
socket: NSConstants.routingInformationSocket];
updateCycles: CARDINAL = InrInternal.updateCycles;
-- timeUnits gets reset to this; number of routing table update cycles.
maxInternetrouterHops: CARDINAL = InrInternal.maxInternetrouterHops;
infinityHopCount: CARDINAL = InrInternal.infinityHopCount;
deadEntryHopCount: CARDINAL = InrInternal.deadEntryHopCount;
decrementTO: CARDINAL = 40; -- seconds for decrementing table entries
emptyINRRoutingTable: INRRoutingTable = DESCRIPTOR[NIL, 0];
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- VARIABLES or semi-Variables
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
hashingMask: CARDINAL ← 0;
hashTableSize: CARDINAL ← 0; -- the number of buckets, determined by
-- the number of bits used for accessing the table
markDeadEntries: BOOLEAN ← TRUE; -- flag to indicate if an invalid routing
-- table entry should be just marked as dead or actually removed from the
-- routing table
--various Glitches generated by the Router
INRRoutingTableScrambled: ERROR = CODE;
nullEnum: NetworkNumber ← nullNetworkNumber;
routingTableChanged: PUBLIC CONDITION; << mucked with in INRImpl >>
-- notified to send info on routes that have changed
routingTable: PUBLIC INRRoutingTable ← emptyINRRoutingTable;
-- hash table (fixed number of buckets) of routing table entries
routingTableSize: CARDINAL ← 0;
numSequencedList: PUBLIC RoutingTableEntry ← NIL;
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- routines to the Internetwork Router's routing table
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This procedure adds an entry to the inr's routing table. The entry is
-- also properly inserted into the numerically sequenced list. Be careful
-- that the entry does not already exist in the table (check should have
-- been made before calling this routine - FindNetworkNumber[]).
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- Only the added entry's two links fields are changed in this routine.
AddEntry: PUBLIC INTERNAL PROCEDURE [e: RoutingTableEntry] =
BEGIN
bucket: CARDINAL;
nse, prev: RoutingTableEntry;
-- FIRST, add entry to routing table (at beginning of collision chain)
bucket ← HashNetworkNumber[e.destNetwork];
e.nextRTE ← routingTable[bucket];
routingTable[bucket] ← e;
-- SECOND, add entry to the numerically sequenced network number list
prev ← nse ← numSequencedList;
UNTIL (nse = NIL) DO --find point of insertion
IF CommFlags.doDebug AND (nse.destNetwork = e.destNetwork) THEN
Driver.Glitch[INRRoutingTableScrambled];
IF NetAgtNetB[a: nse.destNetwork, b: e.destNetwork] THEN EXIT;
-- the given entry belongs just before the entry with the next
-- greatest network number
prev ← nse;
nse ← nse.nextNSE;
ENDLOOP;
-- and insert into the list
IF (nse = numSequencedList) THEN
BEGIN --insert into the very beginning of list (first entry)
temp: RoutingTableEntry ← numSequencedList;
numSequencedList ← e;
e.nextNSE ← temp;
END
ELSE
BEGIN --is not the first entry in list
prev.nextNSE ← e;
e.nextNSE ← nse;
END;
-- now that an entry has been added increment size
routingTableSize ← routingTableSize + 1;
StatIncr [@InrInternal.stats.destNetsAdded];
END; --of AddEntry
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine acquires the monitor lock and adds a network to the routing
-- table. After the addition, a NOTIFY is done allow a broadcast of the
-- changes. AddNet is passed to Pilot Router
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
AddNet: PUBLIC ENTRY PROCEDURE [net: NetworkContext] =
BEGIN ENABLE UNWIND => NULL;
AddNetDeviceInternal[net]; --AddNet
-- send out gratuitous routing response so inrs learn about each other
NOTIFY routingTableChanged;
END; --of AddNet
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This procedure tells the NS Router about a new network (device).
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
AddNetDeviceInternal: PUBLIC INTERNAL PROCEDURE [newNetwork: NetworkContext] =
BEGIN
IF NOT newNetwork.network.alive THEN RETURN;
IF (newNetwork.netNumber # nullNetworkNumber) THEN
BEGIN
-- the driver already knows the number of its net, add or modify a rte
e: RoutingTableEntry ← FindNetworkNumber[newNetwork.netNumber, FALSE];
IF (e = NIL) THEN
BEGIN -- add a new routing table entry
e ← CommHeap.zone.NEW[RoutingTableObject];
e↑ ← RoutingTableObject[
nextRTE: NIL, nextNSE: NIL, destNetwork: newNetwork.netNumber,
delay: localHop, timeUnits: updateCycles, route: unknownHostID,
context: newNetwork, changed: TRUE];
AddEntry[e];
END
ELSE -- modify an existing routing table entry if better hop
IF e.delay > localHop THEN e↑ ← RoutingTableObject[
nextRTE: e.nextRTE, nextNSE: e.nextNSE,
destNetwork: newNetwork.netNumber, delay: localHop,
timeUnits: updateCycles, route: unknownHostID,
context: newNetwork, changed: TRUE];
END;
IF (FindNetworkNumber[nullNetworkNumber, FALSE] = NIL) THEN
BEGIN
-- there is no "default" rte, add one
e: RoutingTableEntry ← CommHeap.zone.NEW[RoutingTableObject];
e↑ ← RoutingTableObject[
nextRTE: NIL, nextNSE: NIL, destNetwork: nullNetworkNumber,
delay: localHop, timeUnits: updateCycles, route: unknownHostID,
context: newNetwork, changed: FALSE];
AddEntry[e];
END;
END; --AddNetDeviceInternal
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- CleanUpRoutingTable free the entries in the routing table and then the
-- table itself. Global variables are reset.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
--Question: Can/Should this be made into an INLINE?
CleanUpRoutingTable: PUBLIC ENTRY PROCEDURE =
BEGIN ENABLE UNWIND => NULL;
e, temp: RoutingTableEntry;
-- go through linked numerically sequenced list to deallocate all entries
e ← numSequencedList;
WHILE (e # NIL) DO
temp ← e;
e ← e.nextNSE;
CommHeap.zone.FREE[@temp];
ENDLOOP;
-- free the hash routing table
[] ← Space.Unmap[pointer: BASE[routingTable]];
-- reinitialize the global variables
numSequencedList ← NIL;
routingTable ← emptyINRRoutingTable;
routingTableSize ← 0;
END; --of CleanUpRoutingTable
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- FORKED INTERNETWORK ROUTER PROCESS
-- This routine, waking up once every interval, acquires the monitor lock
-- and decrements the age count of each routing table entry. If an entry's
-- age is already zero before the decrementation, meaning it may be a bad
-- entry, the entry is deleted.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- Invalid entry detection: minimum of ((updateCycles + 1)*decrementTO) seconds
DecrementRoutingTableEntries: PUBLIC ENTRY PROCEDURE =
BEGIN ENABLE UNWIND => NULL;
rte: RoutingTableEntry;
timer: CONDITION;
Process.SetTimeout [@timer, Process.SecondsToTicks [decrementTO]];
Process.EnableAborts [@timer];
UNTIL InrInternal.pleaseStop DO
ENABLE ABORTED => EXIT; --exit the until loop
WAIT timer;
rte ← numSequencedList;
WHILE (rte # NIL) DO
-- local network's entries' <timeUnits> should not be decremented
IF ~((rte.delay=localHop) OR (rte.delay=deadEntryHopCount)) THEN
BEGIN
IF (rte.timeUnits = 0) THEN
BEGIN -- remove the dead entry
temp: RoutingTableEntry ← rte;
rte ← rte.nextNSE; --first increment pointer
IF markDeadEntries THEN MarkEntryDead[temp]
ELSE {RemoveEntry[temp]; CommHeap.zone.FREE[@temp]};
LOOP; --go to next entry
END
ELSE rte.timeUnits ← rte.timeUnits - 1;
END;
rte ← rte.nextNSE;
ENDLOOP; --while not of list loop
-- now go back and wait awhile
ENDLOOP; --until InrInternal.pleaseStop loop
END; --of DecrementRoutingTableEntries
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine enumerates the routing table by distance first and network
-- number second. Start the enumeration with nullNetworkNumber and the hop
-- count of choice. The enumeration is finished when the returned net is
-- nullNetworkNumber. The table can change between calls.
-- EnumerateByDistance is passed to Pilot Router.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- Dead routing table entries can be enumerated with this routine passing
-- a <delay> value of InrInternal.deadEntryHopCount
EnumerateByDistance: PUBLIC ENTRY PROCEDURE [
previous: NetworkNumber, delay: CARDINAL]
RETURNS [net: NetworkNumber] =
--Start enumeration with nullNetworkNumber and finish with lastNetworkNumber
--enumeration happens in order of net #, so table can change between calls
BEGIN ENABLE UNWIND => NULL;
foundContextInList: BOOLEAN ← FALSE;
rte: RoutingTableEntry;
pulses: System.Pulses ← System.GetClockPulses[]; --for time duration
IF (numSequencedList = NIL) THEN RETURN [net ← nullEnum];
rte ← FindNetworkNumber[previous]; -- try to find context
IF (rte # NIL) THEN
BEGIN
-- found context in list, start enumeration from next entry
foundContextInList ← TRUE;
rte ← rte.nextNSE;
END
ELSE
BEGIN
-- didn't find context in list, must start enumeration from
-- beginning of numerically sequenced network number list
foundContextInList ← FALSE;
rte ← numSequencedList;
END;
UNTIL (rte = NIL) DO
IF (rte.delay = delay) --within the desired hop count
AND (foundContextInList OR NetAgtNetB[rte.destNetwork, previous])
AND ((rte.context # NIL) OR (rte.delay = infinityHopCount)
OR (rte.delay = deadEntryHopCount)) THEN EXIT; -- found it!
-- Note: the check for infinityHopCount and deadEntryHopCount allows
-- for the enumeration of unreachable/dead routing table entries
rte ← rte.nextNSE; -- continue looking for the next one
ENDLOOP;
-- At this point, rte should be pointing to the next entry
net ← IF (rte = NIL) THEN nullEnum ELSE rte.destNetwork;
SearchDurationBump[pulses, enumerateByDistance]; --increments duration
END; --of EnumerateByDistance
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine enumerates the routing table by network number. Start the
-- enumeration with nullNetworkNumber. The enumeration is finished when the
-- returned net is nullNetworkNumber. The table can change between calls.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
EnumerateByNetNumber: PUBLIC ENTRY PROCEDURE [previous: NetworkNumber]
RETURNS [net: NetworkNumber, delay: HopCount] =
BEGIN ENABLE UNWIND => NULL;
foundContextInList: BOOLEAN ← FALSE;
rte: RoutingTableEntry;
pulses: System.Pulses ← System.GetClockPulses[]; --for time duration
IF (numSequencedList = NIL) THEN
RETURN [net ← nullEnum, delay ← infinityHopCount];
rte ← FindNetworkNumber[previous]; -- try to find context
IF (rte # NIL) THEN
BEGIN
-- found context in list, start enumeration from next entry
foundContextInList ← TRUE;
rte ← rte.nextNSE;
END
ELSE
BEGIN
-- didn't find context in list, must start enumeration from
-- beginning of numerically sequenced network number list
foundContextInList ← FALSE;
rte ← numSequencedList;
END;
UNTIL (rte = NIL) DO
IF (foundContextInList OR NetAgtNetB[rte.destNetwork, previous])
AND (rte.context # NIL) THEN EXIT; --found it!
rte ← rte.nextNSE; -- continue looking for the next one
ENDLOOP;
-- At this point, rte should be pointing to the next entry
IF (rte = NIL) THEN {net ← nullEnum; delay ← infinityHopCount;}
ELSE {net ← rte.destNetwork; delay ← rte.delay;};
SearchDurationBump[pulses, enumerateByNetNumber]; --increments duration
END; --of EnumerateByNetNumber
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine enumerates the routing table by the given method. Only
-- valid routing table entries will be enumerated.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
nullDriverDetails: InrFriends.DriverDetails = [
driverType: other, driverNetwork: System.nullNetworkNumber,
via: System.nullNetworkAddress, statsPtr: NIL];
-- Dead entries will not be enumerated.
EnumerateRoutes: PUBLIC PROCEDURE [previousNet: NetworkNumber,
previousDelay: HopCount, method: InrFriends.Method,
alwaysDetermineViaNet: BOOLEAN ← FALSE]
RETURNS [net: NetworkNumber,
delay: HopCount, details: InrFriends.DriverDetails] =
BEGIN
--Stateless enumerator starts with nullNetworkNumber and zeroHopCount.
--Ends with nullNetworkNumber.
SELECT method FROM
byNetNumber =>
BEGIN
ENABLE Router.NoTableEntryForNet => RETRY; --start here and do it again
-- the entry that was just found (which raised the error) is a dead
-- entry, but repeat to find the next valid entry
[net, delay] ← EnumerateByNetNumber [previousNet];
IF (net = nullEnum) THEN --finished table enumeration
RETURN [nullEnum, infinityHopCount, nullDriverDetails];
details ← GetRouteDetails[net, alwaysDetermineViaNet].details;
END; --byNetNumber
byDistance =>
BEGIN
ENABLE Router.NoTableEntryForNet => RETRY;
net ← EnumerateByDistance [previousNet, previousDelay];
UNTIL (net # nullEnum) OR (previousDelay = maxInternetrouterHops) DO
-- enumeration for the previous hop count has been completed,
-- now it is time to start enumeration for the next hop count
previousDelay ← previousDelay + 1;
previousNet ← nullEnum; -- start over
net ← EnumerateByDistance [previousNet, previousDelay];
ENDLOOP;
IF (net = nullEnum) THEN --finished table enumeration
RETURN [nullEnum, infinityHopCount, nullDriverDetails];
delay ← previousDelay;
previousNet ← net;
details ← GetRouteDetails[net, alwaysDetermineViaNet].details;
END; --byDistance
ENDCASE => NULL; -- we handled all of the enumerated type's values
END; --of EnumerateRoutes
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- FindFarNet is an internal procedure and thus requires the monitor lock.
-- A non-null netork number is returned for the given medium driver.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
FindFarNet: PUBLIC INTERNAL PROCEDURE [net: NetworkContext]
RETURNS [farNet: NetworkNumber] =
BEGIN ENABLE UNWIND => NULL;
<< net is a network driver that is anonyomous--it isn't assigned
its own network number. Point to Point connections between INRs
are anonymous E.g. a phoneline between two INRs.
This procedure searches to find the rte in the table
that uses <net> and has the lowest delay to a destination net of
all the rtes that use <net>. That rte's destNetwork should be
a viable network for reaching the INR at the far end of the anonymous
driver.
We make only one pass through the rtes. >>
bestHopsSoFar: HopCount ← infinityHopCount;
oneAway: HopCount ← localHop + 1;
farNet ← nullNetworkNumber;
FOR e: RoutingTableEntry ← numSequencedList, e.nextNSE
UNTIL (e = NIL) OR (bestHopsSoFar = oneAway) DO
IF (e.context # net) OR (e.destNetwork = nullNetworkNumber)
THEN LOOP; -- ignore
IF (e.delay < bestHopsSoFar) THEN
BEGIN
farNet ← e.destNetwork;
bestHopsSoFar ← e.delay;
END;
ENDLOOP;
END; --of FindFarNet
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- FindNetID returns the ID of the locally connected network most suitable
-- to get to the destination network.
-- This routine is passed to Pilot Router
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- CALLED FROM RoutingInformationSupplier[]
FindNetID: PUBLIC ENTRY PROCEDURE [net: NetworkNumber]
RETURNS [NetworkNumber] =
BEGIN ENABLE UNWIND => NULL;
RETURN[FindNetIDInternal[net]];
END; -- of FindNetID
-- CALLED FROM RoutAndSendRoutingInfoResponse[]
FindNetIDInternal: PUBLIC INTERNAL PROCEDURE [
destNet: NetworkNumber] RETURNS [netNumber: NetworkNumber] =
BEGIN
e: RoutingTableEntry;
netNumber ←
IF (destNet = nullNetworkNumber) OR -- accelerator so we don't search
-- for the net zero rte
((e ← FindNetworkNumber[destNet]) = NIL) OR (e.context = NIL) THEN
nullNetworkNumber ELSE e.context.netNumber;
IF (netNumber = nullNetworkNumber) THEN
BEGIN
--since nullNetworkNumber is uninformative find the first network
--with a known network Number and use it.
FOR n: Driver.Device ← Driver.GetDeviceChain[], n.next UNTIL n = NIL DO
c: NetworkContext ← Protocol1.GetContext[n, ns];
IF (netNumber ← c.netNumber) # nullNetworkNumber THEN EXIT;
ENDLOOP;
END; --find non - nullNetworkNumber network clause
END; --FindNetIDInternal
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- FindNetwork searches for an entry with network field equal to <net> and
-- returns that entry. If the entry cannot be found then e is NIL. If the
-- <startFromNum> is provided, then the search begins from the corresponding
-- routing table entry.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- CALLED ONLY BY RemoveNetworkLocked[]
-- Hopefully, providing the <startFromNum> feature will minimize the total
-- number of searches required to remove a network.
-- Reordering of the collision chain will be done by MarkEntryDead[].
FindNetwork: INTERNAL PROCEDURE [
net: NetworkContext, startFromNum: NetworkNumber ← nullNetworkNumber]
RETURNS [e: RoutingTableEntry ← NIL] =
BEGIN
pulses: System.Pulses ← System.GetClockPulses[]; --for time duration
IF (startFromNum = nullNetworkNumber)
THEN e ← numSequencedList
ELSE BEGIN
rte: RoutingTableEntry ← FindNetworkNumber[startFromNum];
e ← IF (rte = NIL) THEN numSequencedList ELSE rte.nextNSE; --redundant ck
END;
UNTIL (e = NIL) DO
IF (e.context = net) THEN EXIT; -- found it!
e ← e.nextNSE;
ENDLOOP;
SearchDurationBump[pulses, findByNetworkDriver]; --increments duration
END; --of FindNetwork
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This hot 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: PUBLIC INTERNAL PROCEDURE [
num: NetworkNumber, advanceEntry: BOOLEAN ← TRUE]
RETURNS [e: RoutingTableEntry] =
BEGIN
prev: RoutingTableEntry;
i: CARDINAL ← 0;
bucket: CARDINAL;
pulses: System.Pulses ← System.GetClockPulses[]; --for time duration
IF (numSequencedList = NIL) OR (routingTable.BASE = NIL) THEN
RETURN [NIL]; -- not started
bucket ← HashNetworkNumber[num];
e ← prev ← routingTable[bucket];
UNTIL (e = NIL) DO
IF (e.destNetwork = num) THEN -- found it!
BEGIN
IF advanceEntry AND (i > 4) THEN
BEGIN
--advance entry to the beginning of the list
prev.nextRTE ← e.nextRTE;
e.nextRTE ← routingTable[bucket];
routingTable[bucket] ← e;
END;
IF advanceEntry THEN StatIncr [@InrInternal.stats.tupleIndexTable[
MIN[i, (InrStats.tupleIndexTableSize-1)]]];
EXIT; -- exit the until-do loop
END;
prev ← e;
e ← e.nextRTE;
i ← i + 1;
ENDLOOP;
SearchDurationBump[pulses, findByNetNumber]; --increments duration
END; --of FindNetworkNumber
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine gets the details for a route. If <alwaysDetermineViaNet> is
-- TRUE, then it will try to determine the network number of the immediate
-- host.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- CALLED BY EnumerateRoutes[] and GetRouteInfo[]
GetRouteDetails: PROCEDURE [
destNet: NetworkNumber, alwaysDetermineViaNet: BOOLEAN]
RETURNS [details: InrFriends.DriverDetails, delay: HopCount] =
BEGIN
e: RoutingTableEntry;
net: NetworkContext;
host: HostNumber;
LockedFindNet: ENTRY PROC = INLINE
{ENABLE UNWIND => NULL; e ← FindNetworkNumber[destNet, FALSE]};
LockedFindFarNet: ENTRY PROCEDURE [net: NetworkContext]
RETURNS [farNet: NetworkNumber] =
BEGIN ENABLE UNWIND => NULL;
farNet ← FindFarNet[net];
END; --of LockedFindFarNet
-- Mainline of the procedure ...
LockedFindNet[]; --try searching first time
IF (e = NIL) OR (e.context = NIL) THEN
ERROR Router.NoTableEntryForNet; --no such entry in table
net ← e.context;
delay ← e.delay;
host ← e.route;
details.driverType ← net.network.device;
details.driverNetwork ← net.netNumber;
details.statsPtr ← net.network.stats;
IF (delay # localHop) THEN
BEGIN
details.via.socket ← System.nullSocketNumber;
details.via.host ← host;
details.via.net ←
IF alwaysDetermineViaNet AND (net.netNumber = nullNetworkNumber)
THEN LockedFindFarNet [net] ELSE net.netNumber;
END
ELSE details.via ← System.nullNetworkAddress;
END; --of GetRouteDetails
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This statistics routine just returns a READONLY pointer to the counter
-- which keeps track of the number entries in the routing table.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
GetHashTableSize: PUBLIC PROCEDURE
RETURNS [CARDINAL] = { RETURN [hashTableSize] };
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine retreive route information.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
GetRouteInfo: PUBLIC PROCEDURE [net: System.NetworkNumber]
RETURNS [delay: HopCount, details: InrFriends.DriverDetails] =
BEGIN
[delay: delay, details: details] ← GetRouteDetails [
destNet: net, alwaysDetermineViaNet: TRUE];
END;
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This statistics routine just returns a READONLY pointer to the counter
-- which keeps track of the number entries in the routing table.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
GetRoutingTableSize: PUBLIC PROCEDURE RETURNS [LONG POINTER TO
READONLY CARDINAL] = {RETURN [@routingTableSize]};
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- HashNetworkNumber returns the hashed value of the given network number.
-- This number is the index to the routing table to find/insert the network
-- number's corresponding routing table entry.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
HashNetworkNumber: PROCEDURE [networkNumber: NetworkNumber]
RETURNS [hashValve: CARDINAL] = INLINE
BEGIN
hashValve ← Inline.BITAND[hashingMask, networkNumber.b];
END; --of HashNetworkNumber
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This routine marks a routing table entry as being dead. <delay> is set
-- to deadEntryHopCount, and the entry is reordered to be last in its
-- respective hash table bucket's link list.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
MarkEntryDead: INTERNAL PROCEDURE [e: RoutingTableEntry] =
BEGIN
first: BOOLEAN ← FALSE; --first in collision chain
prev: RoutingTableEntry ← NIL;
bucket: CARDINAL ← HashNetworkNumber[e.destNetwork];
last: RoutingTableEntry ← routingTable[bucket];
e↑ ← [destNetwork: e.destNetwork, delay: deadEntryHopCount,
timeUnits: 0, nextRTE: e.nextRTE, nextNSE: e.nextNSE,
route: unknownHostID, context: NIL, changed: TRUE];
-- reorder entry in the routing table's collision chain
SELECT TRUE FROM
(e.nextRTE = NIL) => RETURN; --already last in list
(last = NIL) => --the bucket's collision chain is nil
IF CommFlags.doDebug THEN Driver.Glitch[INRRoutingTableScrambled]
ELSE RETURN;
(last = e) => first ← TRUE; --first in list of size > 1
ENDCASE;
UNTIL (last.nextRTE = NIL) DO
IF (last.nextRTE = e) THEN prev ← last;
last ← last.nextRTE;
ENDLOOP;
IF CommFlags.doDebug AND ~first AND (prev = NIL) THEN
Driver.Glitch[INRRoutingTableScrambled];
IF first THEN routingTable[bucket] ← e.nextRTE
ELSE prev.nextRTE ← e.nextRTE;
last.nextRTE ← e;
e.nextRTE ← NIL;
END; --of MarkEntryDead
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This inline procedure compare the two given network number and returns
-- TRUE if the first is greater than the second. Note that the two network
-- number should not be equal.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
NetAgtNetB: PROC [a, b: NetworkNumber] RETURNS [BOOLEAN] = INLINE
BEGIN --RETURNS[a > b];
RETURN[LOOPHOLE[CourierInternal.ExchWords[LOOPHOLE[a]], LONG CARDINAL] >
LOOPHOLE[CourierInternal.ExchWords[LOOPHOLE[b]], LONG CARDINAL] ];
END;
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This procedure removes the given entry from the inr's routing table. The
-- routing table entry, however, is not deallocated. It is up to the calling
-- procedure to free it. The routing table entry's correponding numerically
-- ordered list entry is also removed and freed.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- ONLY CALLED FROM DecrementRoutingTableEntries[]
RemoveEntry: INTERNAL PROCEDURE [e: RoutingTableEntry] =
BEGIN
prev: RoutingTableEntry ← NIL;
temp: RoutingTableEntry ← NIL;
bucket: CARDINAL ← HashNetworkNumber[e.destNetwork];
-- remove entry from the routing table's collision chain
temp ← routingTable[bucket];
IF CommFlags.doDebug AND (temp = NIL) THEN
Driver.Glitch[INRRoutingTableScrambled];
UNTIL (temp = NIL) OR (temp = e) DO
prev ← temp;
temp ← temp.nextRTE;
ENDLOOP;
IF CommFlags.doDebug AND (temp = NIL) THEN
Driver.Glitch[INRRoutingTableScrambled];
IF (prev = NIL) THEN routingTable[bucket] ← e.nextRTE
ELSE
BEGIN
IF CommFlags.doDebug
AND ((prev.nextRTE # e) OR (prev.nextRTE = NIL))
THEN Driver.Glitch[INRRoutingTableScrambled];
prev.nextRTE ← e.nextRTE;
END;
e.nextRTE ← NIL;
-- remove entry from the numerically sequenced network number list
prev ← NIL;
temp ← numSequencedList;
UNTIL (temp = NIL) OR (temp = e) DO
prev ← temp;
temp ← temp.nextNSE;
ENDLOOP;
IF CommFlags.doDebug AND (temp = NIL) THEN
Driver.Glitch[INRRoutingTableScrambled];
IF (prev = NIL) THEN numSequencedList ← e.nextNSE
ELSE
BEGIN
IF CommFlags.doDebug
AND ((prev.nextNSE # e) OR (prev.nextNSE = NIL))
THEN Driver.Glitch[INRRoutingTableScrambled];
prev.nextNSE ← e.nextNSE;
END;
e.nextNSE ← NIL;
routingTableSize ← routingTableSize - 1;
StatIncr [@InrInternal.stats.destNetsDeleted];
END; --of RemoveEntry
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This procedure removes a network from the NS Router's tables.
-- RemoveNet is passed to Pilot Router
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
RemoveNet: PUBLIC PROCEDURE [net: NetworkContext] =
BEGIN
unknownNetwork: Driver.Device;
FindNetworkNumberLocked: ENTRY PROCEDURE [n: NetworkNumber]
RETURNS [e: RoutingTableEntry] = INLINE
BEGIN ENABLE UNWIND => NULL;
e ← FindNetworkNumber[n, FALSE-- don't reorder chain--]; END;
RemoveNetDeviceLocked[net];
--we may have removed the nullNetworkNumber network; if so replace it
IF (FindNetworkNumberLocked[nullNetworkNumber] = NIL) THEN
BEGIN
unknownNetwork ← Driver.GetDeviceChain[];
UNTIL (unknownNetwork # net.network) OR (unknownNetwork = NIL) DO
unknownNetwork ← unknownNetwork.next;
ENDLOOP; --try to find another network
IF (unknownNetwork # NIL) THEN
AddNet[Protocol1.GetContext[unknownNetwork, ns]];
END; -- of replacing the net 0 rte
END; --of RemoveNet
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- This procedure removes a network (device) from the NS Router's tables.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
RemoveNetDeviceLocked: PUBLIC ENTRY PROCEDURE [oldNetwork: NetworkContext] =
BEGIN ENABLE UNWIND => NULL;
e: RoutingTableEntry;
anyChanges: BOOLEAN ← FALSE;
DO
IF (e ← FindNetwork[oldNetwork]) = NIL THEN EXIT;
-- mark the rte as pointing to an obsolete network driver
e↑ ← [destNetwork: e.destNetwork, delay: infinityHopCount,
timeUnits: updateCycles, -- so we keep the rte entry around for awhile
nextRTE: e.nextRTE, nextNSE: e.nextNSE, route: unknownHostID,
context: NIL, changed: TRUE];
anyChanges ← TRUE;
ENDLOOP;
IF anyChanges THEN
-- send out gratuitous routing response for the new info
NOTIFY routingTableChanged;
END; --of RemoveNetDeviceLocked
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- RoutingTableActivate create and initialize routing table.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
RoutingTableActivate: PUBLIC ENTRY PROCEDURE [
numberOfHashBits: CARDINAL ← InrInternal.defaultNumberOfHashBits,
markInvalidEntriesDead: BOOLEAN ← TRUE] =
BEGIN ENABLE UNWIND => NULL;
pageCount, tableLength: CARDINAL;
markDeadEntries ← markInvalidEntriesDead;
-- calculate the length of the routing table
tableLength ← 1;
FOR i: CARDINAL IN [0..numberOfHashBits) DO
tableLength ← tableLength * 2;
ENDLOOP;
hashingMask ← tableLength - 1;
hashTableSize ← tableLength;
pageCount ← (SIZE[RoutingTableEntry]*tableLength) / Space.wordsPerPage;
IF ((SIZE[RoutingTableEntry]*tableLength) MOD Space.wordsPerPage) > 0
THEN pageCount ← pageCount + 1;
routingTable ← DESCRIPTOR [Space.ScratchMap[count: pageCount], tableLength];
FOR i:CARDINAL IN [0..tableLength) DO routingTable[i] ← NIL; ENDLOOP;
numSequencedList ← NIL;
routingTableSize ← 0;
END; --of RoutingTableActivate
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
-- FORKED INTERNETWORK ROUTER PROCESS
-- This process sends out gratuitous routing response packets for tuples
-- that have changed. It will not send out packets faster than once per
-- second.
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --
RoutingTableChanged: PUBLIC PROCEDURE =
BEGIN
Wait: ENTRY PROCEDURE = INLINE {
ENABLE UNWIND => NULL;
WAIT routingTableChanged;
}; --end of Wait
UNTIL InrInternal.pleaseStop DO
ENABLE ABORTED => EXIT;
Wait []; --wait for a routing change to occur
Process.Pause [Process.SecondsToTicks [1]]; --pause to possibly make
-- other routing table changes thus possibly minimazing the amount
-- of traffic
-- announce to everyone the routing changes
InrInternal.SendGratuitousResponse [to: allLocalInternetRouters,
b: NIL, allAreUnreachable: FALSE, onlyChangedEntries: TRUE];
StatIncr [@InrInternal.stats.gratuitousRoutingResponseSent];
ENDLOOP;
END; -- of INRRoutingTableChanged
--**************** Statistics ****************
PulsesBump: PROCEDURE [
counter: LONG POINTER TO System.Pulses, bumpAmount: System.Pulses] = INLINE
BEGIN
overflow: System.Pulses = LOOPHOLE[LAST[LONG CARDINAL]];
counter↑ ← System.Pulses[MIN[(counter↑ + bumpAmount), overflow]];
END;
SearchDurationBump: PROCEDURE [
pulses: System.Pulses, search: InrStats.RoutingTableSearch] = INLINE
BEGIN
IF (InrInternal.stats = NIL) THEN RETURN;
pulses ← System.Pulses[System.GetClockPulses[] - pulses];
StatBump [@InrInternal.stats.searchTable[search].totalSearches, 1];
PulsesBump [@InrInternal.stats.searchTable[search].pulsesSearching, pulses];
END; --of SearchDurationBump
StatBump: PROCEDURE [
counter: LONG POINTER TO LONG CARDINAL, bumpAmount: CARDINAL] = INLINE
BEGIN
--locals
<<
--add bumpAmount to counter; if bumpAmount < 10000, there will never
--be overflow
counter↑ ← (counter↑ + bumpAmount) MOD (LAST[LONG CARDINAL] - 10000);
>>
counter↑ ← MIN[(counter↑ + bumpAmount), (LAST[LONG CARDINAL] - 10000)];
END;
StatIncr: PROCEDURE [counter: LONG POINTER TO LONG CARDINAL] = INLINE
--add one to counter
BEGIN
--locals
counter↑ ← (counter↑ + 1) MOD (LAST[LONG CARDINAL] - 1);
END;
-- MAINLINE CODE --
-- no action
END... --of InrINRRoutingTableImpl
<<
LOG
5-Feb-88 13:48:21 AOF Trimmed for PupGateway
>>