DIRECTORY
BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds],
CommDriver USING [GetNetworkChain, InsertReceiveProc, Network],
Endian USING [CardFromF, CardFromH, HFromCard],
XNS USING [Address, broadcastNet, GetThisHost, Host, Net, Socket, unknownAddress, unknownHost, unknownNet, unknownSocket],
XNSBuf USING [Buffer],
XNSErrorTypes USING [protocolViolationErr],
XNSRouter USING [Hops, RoutingTableEntry, unreachable],
XNSRouterPrivate USING [EventProc, TakeThis],
XNSRoutingBuf USING [Buffer, hdrBytes, maxBytes, maxTuples, NumTuplesFromUserBytes, Tuple, UserBytesFromNumTuples],
XNSSocket USING [AllocBuffer, Broadcast, Create, dontWait, FixupSourceAndDest, FreeBuffer, Get, GetUserBytes, Handle, Milliseconds, ReturnError, Send, SetGetTimeout, SetUserBytes],
XNSWKS USING [routing];
XNSRouterImpl:
CEDAR
MONITOR
IMPORTS BasicTime, CommDriver, Endian, XNS, XNSRouterPrivate, XNSRoutingBuf, XNSSocket
EXPORTS XNSRouter, XNSRouterPrivate
~ {
Net: TYPE ~ XNS.Net;
Host: TYPE ~ XNS.Host;
Socket: TYPE ~ XNS.Socket;
Address: TYPE ~ XNS.Address;
NetGT:
PROC [x,y: Net]
RETURNS [
BOOL] ~
TRUSTED
INLINE {
RETURN [ Endian.CardFromF[LOOPHOLE[x]] > Endian.CardFromF[LOOPHOLE[y]] ] };
unknownHost: Host ~ XNS.unknownHost;
unknownNet: Net ~ XNS.unknownNet;
broadcastNet: Net ~ XNS.broadcastNet;
unknownSocket: Socket ~ XNS.unknownSocket;
unknownAddress: Address ~ XNS.unknownAddress;
thisHost: Host ~ XNS.GetThisHost[];
Network: TYPE ~ CommDriver.Network;
Hops: TYPE ~ XNSRouter.Hops;
unreachable: Hops ~ XNSRouter.unreachable;
Timeouts
Pulses: TYPE ~ BasicTime.Pulses;
Msecs: TYPE ~ XNSSocket.Milliseconds;
PulsesSince:
PROC [then: Pulses]
RETURNS[Pulses] ~
INLINE {
RETURN [BasicTime.GetClockPulses[] - then] };
sweepSeconds: CARDINAL ~ 15;
sweepPulses: Pulses ~ BasicTime.MicrosecondsToPulses[ LONG[sweepSeconds] * 1000000 ];
suspectSweeps: CARDINAL ~ 6;
invalidSweeps: CARDINAL ~ 12;
Routing Table
Routing entries are stored in a hash table, keyed by destination net number, using chained overflow. Entries are also doubly-linked in a list sorted by network number. The sorted list, which contains all the routing entries, is used e.g. by Sweep and Enumerate.
In a requestor (not a gateway) an entry with hops = unreachable is semantically equivalent to no entry, so we never allow such an entry to appear in the table.
numHashHeaders: CARDINAL ~ 300;
HashIndex: TYPE ~ [0 .. numHashHeaders);
RoutingTable: TYPE ~ REF RoutingTableRep;
RoutingTableRep: TYPE ~ ARRAY HashIndex OF RoutingEntry;
RoutingEntry: TYPE ~ REF RoutingEntryObject;
RoutingEntryObject:
TYPE ~
RECORD [
next: RoutingEntry,
sortedNext, sortedPrev: RoutingEntry,
dest: Net,
hops: Hops,
network: Network,
immediate: Host,
sweepsSinceRefresh: CARDINAL];
routingTable: RoutingTable ~ NEW[RoutingTableRep];
sortedHead: RoutingEntry ← NIL;
Hash:
PROC [net: Net]
RETURNS [HashIndex] ~
TRUSTED INLINE {
RETURN [ Endian.CardFromF[LOOPHOLE[net]] MOD numHashHeaders ] };
FindEntry:
PROC [net: Net]
RETURNS [eH: RoutingEntry] ~
INLINE {
FOR eH ← routingTable^[Hash[net]], eH.next WHILE (eH # NIL) AND (eH.dest # net) DO NULL ENDLOOP;
RETURN [eH] };
additions: INT ← 0;
AddEntry:
PROC [newH: RoutingEntry] ~ {
Add new entry newH^ into hash table and insert it in the correct position in the sorted list. This involves an O(n) search, but it only happens on addition - NOT replacement - and that's fairly infrequent.
h: HashIndex ~ Hash[newH.dest];
prevH, leftH, rightH: RoutingEntry ← NIL;
additions ← additions.SUCC;
IF Monitoring[] THEN PostEvent[newH~newH];
rightH ← sortedHead;
WHILE (rightH #
NIL)
AND NetGT[newH.dest, rightH.dest]
DO
leftH ← rightH; rightH ← rightH.sortedNext;
ENDLOOP;
newH.next ← routingTable^[h];
routingTable^[h] ← newH;
newH.sortedPrev ← leftH; newH.sortedNext ← rightH;
IF rightH # NIL THEN rightH.sortedPrev ← newH;
IF leftH # NIL THEN leftH.sortedNext ← newH ELSE sortedHead ← newH;
};
replacements: INT ← 0;
ReplaceEntry:
PROC [newH: RoutingEntry, oldH: RoutingEntry] ~ {
Add new entry newH^ into hash table replacing oldH^, and insert it in the correct position in the sorted list. Note oldH^ is used to determine newH's position in the sorted list, eliminating the O(n) search. Of course, this means oldH and newH MUST be for the same dest network.
h: HashIndex ~ Hash[newH.dest];
prevH: RoutingEntry ← NIL;
replacements ← replacements.SUCC;
IF Monitoring[] THEN PostEvent[oldH~oldH, newH~newH];
FOR temp: RoutingEntry ← routingTable^[h], temp.next
WHILE temp # oldH
DO prevH ← temp ENDLOOP;
newH.next ← routingTable^[h];
routingTable^[h] ← newH;
IF prevH # NIL THEN prevH.next ← oldH.next ELSE newH.next ← oldH.next;
IF (newH.sortedPrev ← oldH.sortedPrev) #
NIL
THEN newH.sortedPrev.sortedNext ← newH
ELSE sortedHead ← newH;
IF (newH.sortedNext ← oldH.sortedNext) #
NIL
THEN newH.sortedNext.sortedPrev ← newH;
};
deletions: INT ← 0;
DeleteEntry:
PROC [oldH: RoutingEntry] ~ {
Delete the entry oldH^ from the hash table and the sorted list.
h: HashIndex ~ Hash[oldH.dest];
prevH: RoutingEntry ← NIL;
deletions ← deletions.SUCC;
IF Monitoring[] THEN PostEvent[oldH~oldH];
FOR temp: RoutingEntry ← routingTable^[h], temp.next
WHILE temp # oldH
DO prevH ← temp ENDLOOP;
IF prevH # NIL THEN prevH.next ← oldH.next ELSE routingTable^[h] ← oldH.next;
IF oldH.sortedPrev #
NIL
THEN oldH.sortedPrev.sortedNext ← oldH.sortedNext
ELSE sortedHead ← oldH.sortedNext;
IF oldH.sortedNext #
NIL
THEN oldH.sortedNext.sortedPrev ← oldH.sortedPrev;
};
changes: INT ← 0;
ChangeEntry:
PROC [oldH: RoutingEntry, newHops: Hops] ~
INLINE {
Update the hop count of entry oldH^.
IF oldH.hops # newHops
THEN {
changes ← changes.SUCC;
IF Monitoring[] THEN PostChangeEvent[oldH, newHops];
oldH.hops ← newHops };
oldH.sweepsSinceRefresh ← 0 };
Routing Daemon
responsesSent: INT ← 0;
ProcessRequest:
PROC [b: XNSRoutingBuf.Buffer, userBytes:
CARDINAL] ~ {
Reply to b^ (which must be a routing information request packet of length userBytes). For a simple router (not gateway) this is done only if the b^ was directed at this host (rather than broadcast). The request buffer b may be NIL, in which case we "reply" to it by broadcasting our entire routing table.
sendBuf: XNSBuf.Buffer ← NIL; -- the send buffer.
iSend: CARDINAL; -- index into sb.body.tuples
nReq: CARDINAL ← 0; -- number of request tuples in b, or 0 if b = NIL
Send:
PROC ~ {
Send sendBuf^ to destination computed from b.
TRUSTED {
srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf];
srb.hdr1.type ← routing;
srb.hdr2.type ← response };
XNSSocket.SetUserBytes[sendBuf, XNSRoutingBuf.UserBytesFromNumTuples[iSend]];
IF b #
NIL
THEN XNSSocket.Send[handle~routingSocketHandle, b~sendBuf, dest~b.hdr1.source]
ELSE XNSSocket.Broadcast[handle~routingSocketHandle, b~sendBuf, socket~XNSWKS.routing];
};
AddToSendBuf:
PROC [eH: RoutingEntry] ~ {
Add info from eH to response packet in sendBuf^, sending the old response packet and allocating a new one if necessary.
IF (sendBuf #
NIL)
AND (iSend >= XNSRoutingBuf.maxTuples)
THEN {
Send[]; sendBuf ← NIL };
IF sendBuf =
NIL THEN {
sendBuf ← XNSSocket.AllocBuffer[handle~routingSocketHandle];
iSend ← 0 };
TRUSTED {
srb: XNSRoutingBuf.Buffer ~ LOOPHOLE[sendBuf];
srb.body.tuples[iSend] ← [net~eH.dest, delay~eH.hops] };
iSend ← iSend + 1;
};
IF b #
NIL
THEN {
IF b.hdr1.dest.host # thisHost THEN RETURN; -- Simple router responds only to requests directed at it.
TRUSTED { XNSSocket.FixupSourceAndDest[LOOPHOLE[b]] };
nReq ← XNSRoutingBuf.NumTuplesFromUserBytes[userBytes] };
IF (b =
NIL)
OR ((nReq > 0)
AND (b.body.tuples[0].net = broadcastNet))
THEN {
Dump the entire routing table.
FOR eH: RoutingEntry ← sortedHead, eH.sortedNext
WHILE eH #
NIL
DO
AddToSendBuf[eH];
ENDLOOP;
}
ELSE {
Reply with routing table entries for requested nets only. Note the response will be sorted by net number only if the request was ...
FOR iReq:
CARDINAL
IN [0 .. nReq)
DO
eH: RoutingEntry ~ FindEntry[b.body.tuples[iReq].net];
IF eH # NIL THEN AddToSendBuf[eH];
ENDLOOP;
};
IF sendBuf # NIL THEN { Send[]; sendBuf ← NIL };
responsesSent ← responsesSent.SUCC;
};
ProcessResponse:
PROC [b: XNSRoutingBuf.Buffer, userBytes:
CARDINAL] ~ {
Update the routing table using information from b^ (which must be a routing information response packet of length userBytes).
network: Network ← NARROW[b.ovh.network];
immediate: Host ← b.hdr1.source.host;
tuple: XNSRoutingBuf.Tuple;
hops: CARDINAL;
eH, newH: RoutingEntry;
IF network.xns.net = unknownNet
THEN {
We have just learned the network number of a directly-connected net.
network.xns.net ← b.hdr1.source.net; -- NOT ATOMIC
ConnectNets[] };
FOR i:
CARDINAL
IN [0 .. XNSRoutingBuf.NumTuplesFromUserBytes[userBytes])
DO
tuple ← b.body.tuples[i];
hops ← Endian.CardFromH[tuple.delay];
IF (eH ← FindEntry[tuple.net]) #
NIL
THEN {
Update from owner of entry can be performed in place.
IF (eH.network = network)
AND (eH.immediate = immediate)
THEN {
IF hops < unreachable
THEN { ChangeEntry[eH, hops] }
ELSE { DeleteEntry[eH] };
LOOP
};
Update less desirable than the current entry can be ignored.
IF eH.sweepsSinceRefresh < suspectSweeps
THEN {
IF eH.hops < hops THEN LOOP;
IF (eH.hops = hops) AND (eH.network.speed >= network.speed) THEN LOOP;
Update making an (unowned) entry unreachable is either performed in place or ignored. NOTE: there's a plausible argument that it should ALWAYS be ignored. Here it's ignored unless the "unreachable" update comes from a gateway on the same net as the old route. That's just a heuristic ...
IF hops >= unreachable
THEN {
IF eH.sweepsSinceRefresh >= suspectSweeps
AND (eH.network = network)
THEN { DeleteEntry[eH] };
LOOP
};
Too bad, update is significant and the entry must be replaced.
newH ← NEW [RoutingEntryObject ← [dest~tuple.net, hops~hops, network~network, immediate~immediate, sweepsSinceRefresh~0]];
ReplaceEntry[newH~newH, oldH~eH];
LOOP;
};
Create of a new unreachable entry can be ignored.
IF hops >= unreachable THEN LOOP;
Too bad, must create a new entry.
newH ← NEW [RoutingEntryObject ← [dest~tuple.net, hops~hops, network~network, immediate~immediate, sweepsSinceRefresh~0]];
AddEntry[newH];
ENDLOOP;
};
ConnectNets:
PROC [] ~ {
Ensure that there's a valid 0-hops routine entry for each connected network for which the network number (network.ns.net) has already been filled in.
oldH, newH: RoutingEntry;
FOR network: Network ← CommDriver.GetNetworkChain[], network.next
UNTIL network =
NIL
DO
IF network.xns.net = unknownNet
THEN LOOP;
oldH ← FindEntry[network.xns.net];
IF oldH #
NIL
AND oldH.hops = 0
THEN { oldH.sweepsSinceRefresh ← 0; LOOP };
newH ← NEW[RoutingEntryObject ← [dest~network.xns.net, hops~0, network~network, immediate~unknownHost, sweepsSinceRefresh~0]];
IF oldH #
NIL
THEN ReplaceEntry[newH~newH, oldH~oldH]
ELSE AddEntry[newH~newH];
ENDLOOP;
};
Sweep:
PROC ~ {
Throw away routing entries that are too old to be credible.
eH, nextH: RoutingEntry;
FOR eH ← sortedHead, nextH
WHILE eH #
NIL
DO
nextH ← eH.sortedNext;
IF eH.sweepsSinceRefresh >= invalidSweeps
THEN DeleteEntry[eH]
ELSE eH.sweepsSinceRefresh ← eH.sweepsSinceRefresh.SUCC;
ENDLOOP;
};
packetsReceived: INT ← 0;
requestsReceived: INT ← 0;
responsesReceived: INT ← 0;
badLength: INT ← 0;
badProtocol: INT ← 0;
sweeps: INT ← 0;
minSweepPulses: Pulses ← sweepPulses;
lastSweep: Pulses ← BasicTime.GetClockPulses[];
Daemon:
PROC ~ {
DO
b: XNSBuf.Buffer;
sinceSweep: Pulses ~ PulsesSince[lastSweep];
getTimeout: Msecs ~
IF sinceSweep >= sweepPulses
THEN XNSSocket.dontWait
ELSE (1 + (BasicTime.PulsesToMicroseconds[sweepPulses - sinceSweep] / 1000));
XNSSocket.SetGetTimeout[routingSocketHandle, getTimeout];
IF (b ← XNSSocket.Get[routingSocketHandle]) #
NIL
THEN
BEGIN
Receive and process a routing info packet.
userBytes: CARDINAL ~ XNSSocket.GetUserBytes[b];
rB: XNSRoutingBuf.Buffer;
packetsReceived ← packetsReceived.SUCC;
IF b.hdr1.type # routing
THEN {
badProtocol ← badProtocol.SUCC;
XNSSocket.ReturnError[handle~routingSocketHandle, b~b, type~XNSErrorTypes.protocolViolationErr]; b ← NIL;
GOTO Next };
IF (userBytes < XNSRoutingBuf.hdrBytes)
OR (userBytes > XNSRoutingBuf.maxBytes)
THEN {
badLength ← badLength.SUCC;
GOTO Next };
TRUSTED { rB ← LOOPHOLE[b] };
SELECT rB.hdr2.type
FROM
request => {
requestsReceived ← requestsReceived.SUCC;
ProcessRequest[rB, userBytes] };
response => {
responsesReceived ← responsesReceived.SUCC;
ProcessResponse[rB, userBytes] };
ENDCASE => {
XNSSocket.ReturnError[handle~routingSocketHandle, b~b, type~XNSErrorTypes.protocolViolationErr]; b ← NIL };
GOTO Next;
EXITS
Next => IF b # NIL THEN XNSSocket.FreeBuffer[routingSocketHandle, b];
END
ELSE BEGIN
Sweep the table.
minSweepPulses ← MIN[minSweepPulses, PulsesSince[lastSweep]];
ConnectNets[];
Sweep[];
sweeps ← sweeps.SUCC;
lastSweep ← BasicTime.GetClockPulses[];
END;
ENDLOOP;
};
PokeGateways:
PROC ~ {
b: XNSBuf.Buffer;
rB: XNSRoutingBuf.Buffer;
b ← XNSSocket.AllocBuffer[handle~routingSocketHandle];
TRUSTED { rB ← LOOPHOLE[b] };
rB.hdr1.type ← routing;
rB.hdr2.type ← request;
rB.body.tuples[0] ← [net~broadcastNet, delay~Endian.HFromCard[unreachable]];
XNSSocket.SetUserBytes [b~b, bytes~XNSRoutingBuf.UserBytesFromNumTuples[1]];
XNSSocket.Broadcast[handle~routingSocketHandle, b~b, socket~XNSWKS.routing];
};
Routing a Packet
Route:
PUBLIC PROC [him:
XNS.Address]
RETURNS [network: Network, immediate:
XNS.Host] ~ {
eH: RoutingEntry ~ FindEntry[him.net];
IF eH = NIL THEN RETURN [NIL, unknownHost];
IF eH.hops = 0 THEN RETURN [eH.network, him.host];
IF eH.hops >= unreachable THEN ERROR; -- Gateways: RETURN [NIL, unknownHost];
RETURN [eH.network, eH.immediate];
};
Event Monitoring (Exported to XNSRouterPrivate)
RTEHandle: TYPE ~ REF RTEObject;
RTEObject: TYPE ~ XNSRouter.RoutingTableEntry;
oldStaticBuffer: RTEHandle ~ NEW [RTEObject ← [hops~, immediate~, time~]];
newStaticBuffer: RTEHandle ~ NEW [RTEObject ← [hops~, immediate~, time~]];
EventProc: TYPE ~ XNSRouterPrivate.EventProc;
EventProcList: TYPE ~ REF EventProcObject;
EventProcObject:
TYPE ~
RECORD [
next: EventProcList ← NIL,
proc: EventProc];
eventProcList: EventProcList ← NIL;
SetEventProc:
PUBLIC
ENTRY PROC [proc: EventProc] ~ {
eventProcList ← NEW[ EventProcObject ← [next~eventProcList, proc~proc] ];
};
ClearEventProc:
PUBLIC
ENTRY PROC [proc: EventProc] ~ {
p, prev: EventProcList;
p ← eventProcList; prev ← NIL;
WHILE (p # NIL) AND (p.proc # proc) DO prev ← p; p ← p.next ENDLOOP;
IF p #
NIL
THEN {
IF prev = NIL THEN eventProcList ← p.next ELSE prev.next ← p.next };
};
Monitoring: PROC RETURNS [BOOL] ~ INLINE { RETURN [eventProcList # NIL] };
PostEvent:
PROC [oldH, newH: RoutingEntry ←
NIL] ~ {
net: Net;
oldRTEH, newRTEH: RTEHandle ← NIL;
IF oldH #
NIL THEN {
oldRTEH ← oldStaticBuffer;
oldRTEH^ ← [hops~oldH.hops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~(oldH.sweepsSinceRefresh*sweepSeconds)];
net ← oldH.dest };
IF newH #
NIL THEN {
newRTEH ← newStaticBuffer;
newRTEH^ ← [hops~newH.hops, immediate~[net~newH.network.xns.net, host~newH.immediate, socket~unknownSocket], time~(newH.sweepsSinceRefresh*sweepSeconds)];
net ← newH.dest };
FOR pH: EventProcList ← eventProcList, pH.next
WHILE pH #
NIL
DO
(pH.proc)[net, oldRTEH, newRTEH];
ENDLOOP;
};
PostChangeEvent:
PROC [oldH: RoutingEntry, newHops: Hops] ~ {
oldStaticBuffer^ ← [hops~oldH.hops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~(oldH.sweepsSinceRefresh*sweepSeconds)];
newStaticBuffer^ ← [hops~newHops, immediate~[net~oldH.network.xns.net, host~oldH.immediate, socket~unknownSocket], time~0];
FOR pH: EventProcList ← eventProcList, pH.next
WHILE pH #
NIL
DO
(pH.proc)[oldH.dest, oldStaticBuffer, newStaticBuffer];
ENDLOOP;
};
Client Interface (Exported to XNSRouter)
Fast:
PUBLIC
PROC [net: Net]
RETURNS [yes:
BOOL] ~ {
eH: RoutingEntry ~ FindEntry[net];
IF eH = NIL THEN RETURN[FALSE];
SELECT eH.network.type
FROM
ethernet => RETURN[TRUE];
ethernetOne => RETURN[TRUE];
ENDCASE => RETURN[FALSE];
};
GetHops:
PUBLIC PROC [net: Net]
RETURNS [Hops] ~ {
eH: RoutingEntry ~ FindEntry[net];
IF eH = NIL THEN RETURN [unreachable];
RETURN [eH.hops];
};
GetRouting:
PUBLIC PROC [net: Net]
RETURNS [XNSRouter.RoutingTableEntry] ~ {
eH: RoutingEntry ~ FindEntry[net];
IF eH =
NIL
THEN
RETURN [[
hops~unreachable,
immediate~unknownAddress,
time~0]];
RETURN [[
hops~eH.hops,
immediate~[net~eH.network.xns.net, host~eH.immediate, socket~unknownSocket],
time~(eH.sweepsSinceRefresh*sweepSeconds)]];
};
Enumerate:
PUBLIC PROC [
low: Hops ← 0, high: Hops ← unreachable,
proc: PROC [Net, XNSRouter.RoutingTableEntry]] ~ {
FOR eH: RoutingEntry ← sortedHead, eH.sortedNext
WHILE eH #
NIL
DO
IF eH.hops >= low
AND eH.hops <= high
THEN proc[
eH.dest,
[ hops~eH.hops,
immediate~[net~eH.network.xns.net, host~eH.immediate, socket~unknownSocket],
time~(eH.sweepsSinceRefresh*sweepSeconds)]
];
ENDLOOP;
};
Initialization
daemonProcess: PROCESS;
routingSocketHandle: XNSSocket.Handle;
Init:
PROC ~ {
Install recv proc for each network on chain.
CommDriver.InsertReceiveProc[network~NIL, type~xns, proc~XNSRouterPrivate.TakeThis];
Start routing daemon.
routingSocketHandle ← XNSSocket.Create[local~XNSWKS.routing];
daemonProcess ← FORK Daemon[];
PokeGateways[];
};
Init[];
}.