DIRECTORY
Basics USING [bytesPerWord],
BasicTime USING [GMT, Now, Period, Update],
Commander USING [CommandProc, Register],
CommDriver USING [AllocBuffer, Buffer],
ICMP USING [BodyRec, Create, Echo, EchoReply, Handle, Send, Receive],
IO USING [STREAM, PutF, rope, int], 
IPConfig USING [ourLocalAddress, impGatewayName, specialGateways],
IPDefs USING [Address, Byte, Datagram, DatagramRec, DByte, InternetHeader, nullAddress],
IPName USING [AddressToName, AddressToRope],
IPOps USING [MoveBytes, Send],
IPRouter,
Process USING [Detach, MsecToTicks, Pause],
Pup USING [Host],
PupName USING [NameLookup],
Rope USING [Cat, Concat, ROPE];
IPRouterImpl: CEDAR PROGRAM
IMPORTS BasicTime, Commander, CommDriver, ICMP, IO, IPConfig, IPName, IPOps, Process, PupName, Rope
EXPORTS IPRouter =
BEGIN OPEN IPRouter;
ROPE: TYPE = Rope.ROPE;
Encapsulation: TYPE = MACHINE DEPENDENT RECORD [ -- the layout of the data part of the Ethernet packet.
arpaAddr (0): IPDefs.Address,    -- the Arpanet address for the gateway
data (2): ARRAY [0..1] OF IPDefs.Byte];  -- we cheat here.
arpaEncapsulationBytes: INT = SIZE[IPDefs.Address, Basics.bytesPerWord];
ourLocalAddress: IPDefs.Address _ IPConfig.ourLocalAddress;
ourLocalNetwork: IPDefs.Address;
arpanet: IPDefs.Address _ [10,0,0,0];
milnet: IPDefs.Address _ [26,0,0,0];
maxPacketLength: INT = 576;   -- maximum size of datagram
impGatewayName: ROPE _ IPConfig.impGatewayName;
gatewayAddress: Pup.Host;   -- home of the gateway Alto.
stateChanged: PROC [rope: ROPE] _ NIL;
tooBig: INT _ 0;
routeTableSize: INT = 25;
routeTable: ARRAY [0..routeTableSize) OF RECORD[
net: IPDefs.Address,   -- network that this gateway serves or nullAddress if empty entry 
gateway: IPDefs.Address, -- gateway to use for this net
lastTimeUsed: INT];   -- used to find entry to discard
currentUseCount: INT _ 0;  -- the counter used to provide lastTimeUsed values
specialGateways: LIST OF IPDefs.Address _ IPConfig.specialGateways;   -- list of special BBN gateways
specialGatewayPointer: LIST OF IPDefs.Address; -- points to CONS cell of current one
currentSpecialGateway: IPDefs.Address;   -- current BBN gateway
lastTimeGatewayResponded: BasicTime.GMT; -- last time we heard from him
sleepTime: INT = 300;   -- probe this often
gatewayDeadTime: INT = 300+60; -- assume dead after this long.
IPRoutingTable: Commander.CommandProc =
BEGIN
out: IO.STREAM _ cmd.out;
out.PutF["Current special gateway is %G = %G.\n", [rope[IPName.AddressToRope[currentSpecialGateway]]],
[rope[IPName.AddressToName[currentSpecialGateway]]] ];
FOR i: INT IN [0..routeTableSize) DO
net: ROPE = IPName.AddressToRope[routeTable[i].net];
constant: ROPE = IPName.AddressToRope[routeTable[i].gateway];
gateway: ROPE = IPName.AddressToName[routeTable[i].gateway];
IF routeTable[i].lastTimeUsed = 0 THEN LOOP;
out.PutF["%5g  %-15g %-15g %-5g.\n",
IO.int[routeTable[i].lastTimeUsed], IO.rope[net], IO.rope[constant], IO.rope[gateway]];
ENDLOOP;
END;
SetStateChangeProc: PUBLIC PROC [proc: PROC [Rope.ROPE] ] =
BEGIN
stateChanged _ proc;
AnnounceCurrentSpecialGateway[];
END;
AnnounceCurrentSpecialGateway: PROC =
BEGIN
IF stateChanged = NIL THEN RETURN;
stateChanged[Rope.Concat["Current special gateway is ", IPName.AddressToRope[currentSpecialGateway]]];
END;
BestAddress: PUBLIC PROC [addresses: LIST OF IPDefs.Address] RETURNS [addr: IPDefs.Address] = {
addr _ addresses.first;
FOR list: LIST OF IPDefs.Address _ addresses, list.rest UNTIL list = NIL DO
address: IPDefs.Address _ list.first;
net: IPDefs.Address _ NetOf[address];
IF net = ourLocalNetwork THEN RETURN[address];
IF net = arpanet AND NetOf[addr] # arpanet THEN addr _ address;
IF net = milnet AND NetOf[addr] # arpanet THEN addr _ address;
ENDLOOP;
RETURN[addr]; };
GoodAddress: PUBLIC PROC [address: IPDefs.Address] RETURNS [yes: BOOL] = {
net: IPDefs.Address _ NetOf[address];
RETURN[net = ourLocalNetwork OR net = arpanet OR net = milnet]; };

SortAddresses: PUBLIC PROC [list: LIST OF IPDefs.Address] RETURNS[result: LIST OF IPDefs.Address] = {
rest: LIST OF IPDefs.Address;
bestAddress:  IPDefs.Address _ BestAddress[list];
result _ LIST[bestAddress];
rest _ RemoveAddress[list, bestAddress];
UNTIL rest = NIL DO
bestAddress _ BestAddress[rest];
result _ AppendAddress[result, bestAddress];
rest _ RemoveAddress[rest, bestAddress];
ENDLOOP;
};
DatagramPointer: PUBLIC UNSAFE PROC [b: CommDriver.Buffer] RETURNS [d: LONG POINTER TO IPDefs.InternetHeader] = UNCHECKED
BEGIN
ePtr: LONG POINTER TO Encapsulation ~ LOOPHOLE[@b.data];
RETURN [LOOPHOLE[@ePtr.data]];
END;
SendDatagram: PUBLIC PROC [data: IPDefs.Datagram] =
BEGIN
b: CommDriver.Buffer;
headerLength: INT _ data.inHdr.IHL * 4;
packetLength: INT _ data.inHdr.packetLength;

IF packetLength > maxPacketLength THEN {
tooBig _ tooBig + 1;
RETURN; };
b _ CommDriver.AllocBuffer[];
TRUSTED {
dataPtr: LONG POINTER ~ DatagramPointer[b];
IPOps.MoveBytes[dataPtr, 0, @data.inHdr, 0, headerLength];
IPOps.MoveBytes[dataPtr, headerLength, @data.data, 0, data.inHdr.packetLength-headerLength]; };
FinishAndSendIP[b];
END;

RemoveAddress: PROC [list: LIST OF IPDefs.Address, target: IPDefs.Address] RETURNS[result: LIST OF IPDefs.Address] =  {
z: LIST OF IPDefs.Address _ NIL;
result _ NIL;
UNTIL list = NIL DO
IF list.first # target THEN
{IF result = NIL THEN {result _ CONS[list.first, NIL]; z _ result}
ELSE {z.rest _ CONS[list.first, z.rest]; z _ z.rest}};
list _ list.rest;
ENDLOOP;		
}; -- of RemoveAddress	

AppendAddress:  PROC [list: LIST OF IPDefs.Address, element: IPDefs.Address] RETURNS[result: LIST OF IPDefs.Address] = {
z: LIST OF IPDefs.Address _ NIL;
result _ LIST[element];
IF list = NIL THEN RETURN[result];
result _ CONS[list.first, result];
z _ result;
UNTIL (list _ list.rest) = NIL DO
z.rest _ CONS[list.first, z.rest];
z _ z.rest;
ENDLOOP;
RETURN[result];
}; -- of AppendAddress

NetOf: PROC [addr: IPDefs.Address] RETURNS [net: IPDefs.Address] =
BEGIN
net _ [0, 0, 0, 0];
net[0] _ addr[0];
IF addr[0] >= 128 THEN {
net[1] _ addr[1];
IF addr[0] >= 192 THEN
net[2] _ addr[2];
};
END;
IPRoute: PROC [addr: IPDefs.Address] RETURNS [immediateDest: IPDefs.Address] =
BEGIN
net: IPDefs.Address _ NetOf[addr];

IF net = ourLocalNetwork THEN RETURN [addr]
ELSE {
FOR i: INT IN [0..routeTableSize) DO
IF net = routeTable[i].net THEN {
routeTable[i].lastTimeUsed _ currentUseCount;
currentUseCount _ currentUseCount+1;
RETURN [routeTable[i].gateway]; };
ENDLOOP;
IF stateChanged # NIL THEN {
rope: ROPE = Rope.Cat[
"Sending packets to ", IPName.AddressToRope[net],
" via ", IPName.AddressToRope[currentSpecialGateway]];
stateChanged[rope]; };
FixRoutingTable[net, currentSpecialGateway];
RETURN [currentSpecialGateway]; };
END;
EtherRoute: PROC [addr: IPDefs.Address] RETURNS [host: Pup.Host] =
BEGIN
RETURN[gatewayAddress];
END;
FinishAndSendIP: PUBLIC PROC [b: CommDriver.Buffer] = TRUSTED
BEGIN
e: LONG POINTER TO Encapsulation _ LOOPHOLE[@b.data];
h: LONG POINTER TO IPDefs.InternetHeader _ DatagramPointer[b];
ipDest: IPDefs.Address;
etherDest: Pup.Host;
bytes: CARDINAL _ h.packetLength + 1 + arpaEncapsulationBytes;

ipDest _ IPRoute[h.destination];
etherDest _ EtherRoute[ipDest];
e.arpaAddr _ ipDest;
IPOps.Send[etherDest, b, bytes];
END;
Redirect: PUBLIC PROC [dest, gateway, source: IPDefs.Address] =
BEGIN
dest _ NetOf[dest];
IF stateChanged # NIL THEN {
rope: ROPE = Rope.Cat[
 IPName.AddressToRope[source],
" told us to send packets to ",  IPName.AddressToRope[dest],
" via ", IPName.AddressToRope[gateway]];
stateChanged[rope]; };
FixRoutingTable[dest, gateway];
END;
FixRoutingTable: PROC [dest, gateway: IPDefs.Address] =
BEGIN
min, new: INT;
min _ currentUseCount;
new _ 0;
FOR i: INT IN [0..routeTableSize) DO
IF routeTable[i].net = dest THEN {
routeTable[i].gateway _ gateway;
routeTable[i].lastTimeUsed _ currentUseCount;
currentUseCount _ currentUseCount+1;
RETURN; };
IF routeTable[i].lastTimeUsed < min THEN {
min _ routeTable[i].lastTimeUsed;
new _ i; };
ENDLOOP;
routeTable[new].net _ dest;
routeTable[new].gateway _ gateway;
routeTable[new].lastTimeUsed _ currentUseCount;
currentUseCount _ currentUseCount+1;
END;
GatewayPinger: PROC =
BEGIN
handle: ICMP.Handle _ ICMP.Create[currentSpecialGateway];
sequenceNo: IPDefs.DByte _ 0;
DO
now: BasicTime.GMT _ BasicTime.Now[];
since: INT = BasicTime.Period[from: lastTimeGatewayResponded, to: now];
SELECT since FROM
> gatewayDeadTime => {
specialGatewayPointer _ specialGatewayPointer.rest;
IF specialGatewayPointer = NIL THEN
specialGatewayPointer _ specialGateways;
currentSpecialGateway _ IF specialGatewayPointer # NIL THEN specialGatewayPointer.first ELSE IPDefs.nullAddress;
AnnounceCurrentSpecialGateway[];
lastTimeGatewayResponded _ BasicTime.Update[now, -sleepTime]; -- Force ping
LOOP; }; -- Do ping
> sleepTime => TRUSTED {
data: IPDefs.Datagram _ NEW [IPDefs.DatagramRec];
icmp: LONG POINTER TO ICMP.BodyRec _ LOOPHOLE[@data.data];
handle.him _ currentSpecialGateway; -- Slight cheat
data.inHdr.timeToLive _ 60;
icmp.type _ ICMP.Echo;
icmp.code _ 0;
icmp.sequenceNo _ (sequenceNo _ sequenceNo+1);
ICMP.Send[handle, data, 8];
data _ NIL;
data _ ICMP.Receive[handle, 5000];
IF data = NIL THEN LOOP;
icmp _ LOOPHOLE[@data.data];
IF icmp.type = ICMP.EchoReply THEN
lastTimeGatewayResponded _ BasicTime.Now[]; };
ENDCASE;
Process.Pause[Process.MsecToTicks[5000]];
ENDLOOP;
END;
FOR i: INT IN [0..routeTableSize) DO
routeTable[i].net _ routeTable[i].gateway _ IPDefs.nullAddress;
routeTable[i].lastTimeUsed _ 0;
ENDLOOP;
specialGatewayPointer _ LIST[IPDefs.Address[10, 4, 0, 51]]; 
IF specialGateways # NIL THEN specialGatewayPointer _ specialGateways;
ourLocalNetwork _ NetOf[ourLocalAddress];
currentSpecialGateway _ IF specialGatewayPointer # NIL THEN specialGatewayPointer.first ELSE IPDefs.nullAddress;
lastTimeGatewayResponded _ BasicTime.Update[BasicTime.Now[], -sleepTime]; -- force ping
gatewayAddress _ PupName.NameLookup[impGatewayName, [0, 0, 0, 0]].host; -- assume right network
Commander.Register["IPRoutingTable", IPRoutingTable, "Print IP Routing Table."];
TRUSTED {Process.Detach[FORK GatewayPinger[]]};
END.
Copyright (C) 1983, 1984, 1985 by Xerox Corporation. All rights reserved. The following program was created in 1983 but has not been published within the meaning of the copyright law, is furnished under license, and may not be used, copied and/or disclosed except in accordance with the terms of said license.
IPRouterImpl.mesa
Last Edited by: HGM, October 13, 1984 8:24:38 pm PDT
Last Edited by: Nichols, August 22, 1983 12:01 pm
Last Edited by: Taft, January 5, 1984 5:21 pm
Hal Murray June 27, 1985 0:22:16 am PDT
John Larson, June 12, 1987 10:12:50 pm PDT
Our buffers are much bigger (1500). The Imp relay Alto has some (?) limit. The previous Cedar could just barely keep up with 576 byte IP packets. When the Alto gets out of the way, we should rethink this mess.
Routing table stuff
Given a buffer from the buffer pool, returns a pointer to where the datagram should begin.
Allocate a buffer, do the routing, and send it.
Extract the net part of the internet address.
Where do I send this datagram?
Does routing and encapsulation.  b already has the data filled in.
Wake up every so often try to provoke our special gateway into talking to us.
Try to use next gateway.  This isn't synchronized with anything, but it isn't particularly important.
Initialization code
Κ–

"cedar" style˜Icode2š
œ΅™΅
headš
œ™JšœΟkœ™4J™1J™-Jšœ$™'Icodeš
œ*™*š
	˜	Kšœœ˜Kšœ
œœ˜+Kšœ
œ˜(Kšœœ˜'Kšœ
œ;˜EKšœ
œœ˜$Kšœ	œ4˜BKšœœL˜XKšœœ ˜,Kšœœ˜K˜	Kšœœ˜+Kšœœ˜Kšœœ˜Kšœœœ˜——šΟnœœ
˜Kšœ#œœ1˜cKšœ˜Kšœ
œ
˜Kšœœœ
˜š
œœœ
	œ
œΟc6˜gKšœ!Ÿ&˜GKšœ
œœŸ˜:—Kšœœœ&˜HKš
œ;˜;Kš
œ ˜ Kš
œ%˜%Kš
œ$˜$šœœ
Ÿ˜9Kšœ†
œI™Ρ
—Kšœœ˜/KšœŸ˜8Kšœœœœ
˜&Kšœœ˜—™Kšœœ˜šœœœ
œ
˜0KšœŸB˜YKšœŸ˜7KšœœŸ ˜6—KšœœŸ2˜MKšœœ
œ.Ÿ˜eKšœœ
œŸ%˜TKšœ)Ÿ˜?Kšœ$œŸ˜GKšœœ
Ÿ˜+KšœœŸ˜>šžœ˜'Kš
˜Kšœœ
œ˜Kš
œ
˜
šœœ
œ˜$Kšœœ+˜4Kšœ
œ/˜=Kšœ	œ/˜<Kšœ œ
œ
˜,Kš	œ%œ"œœœ˜|Kšœ
˜—Kšœ
˜—š
žœœ
œœœ˜;Kš
˜Kš
œ˜Kš
œ ˜ Kšœ
˜—šžœœ˜%Kš
˜Kšœœ
œ
œ
˜"Kš
œf˜fKšœ
˜—šžœœ
œ
œ
œœ˜_Kš
œ˜šœœ
œ'œœ
˜KKš
œ%˜%Kš
œ%˜%Kšœœ
œ
˜.Kšœœœ˜?Kšœœœ˜>Kšœ
˜—Kšœ
˜—š
žœœ
œœœ˜JKš
œ%˜%Kšœœœ˜BK˜—šž
œœ
œœ
œœ	œ
œ˜eJšœœ
œ˜Jš
œ1˜1Jšœ	œ˜Jš
œ(˜(šœœ
˜Jš
œ ˜ Jš
œ,˜,Jš
œ(˜(Jšœ
˜—J˜—šžœœ
œ
œœœ
œ
œ	˜yKš
˜K™ZKš	œœ
œ
œœ
˜8Kšœœ˜Kšœ
˜—šžœœ
œ˜3Kš
˜K™/K˜Kšœœœ˜'Kšœœ˜,K˜šœ œ˜(Kš
œ˜Kšœ˜
—Kš
œ˜šœ˜	Kšœ	œ
œ˜+Kš
œ:˜:Kš
œ_˜_—K˜Kšœ
˜K˜—šž
œœœ
œ)œ	œ
œ˜wMšœœ
œœ
˜ Mšœ	œ
˜
šœœ
˜šœ˜Mšœ
œ
œ
œœ
œ˜BMšœœ#˜6——M˜Mšœ˜
MšœŸœ
˜—šž
œœœ
œ*œ	œ
œ˜xMšœœ
œœ
˜ Mšœ	œ
˜Mšœœ
œ
œ	˜"Mšœ	œ˜"M˜šœœ
˜!Mšœ	œ˜"M˜Mšœ
˜—Mšœ	˜MšœŸœ
˜—šžœœœ˜BKš
˜K™-K˜K˜šœœ˜K˜šœ˜K˜—K˜—Kšœ
˜—šžœœœ"˜NKš
˜K™Kš
œ"˜"K˜Kšœœ
œ˜+šœ˜šœœ
œ˜$šœœ˜!K˜-K˜$Kšœ˜"—Kšœ
˜—šœœ
œ˜šœœ˜Kš
œ1˜1Kš
œ6˜6—K˜—Kš
œ,˜,Kšœ˜"—Kšœ
˜—šž
œœœ˜BKš
˜Kšœ˜Kšœ
˜—šžœœ
œ˜=Kš
˜K™BKš	œœ
œ
œœ
˜5Kšœœ
œ
œ,˜>Kš
œ˜Kš
œ˜Kšœœ/˜>K˜Kš
œ ˜ Kš
œ˜K˜Kš
œ ˜ Kšœ
˜—šžœœ
œ*˜?Kš
˜Kš
œ˜šœœ
œ˜šœœ˜Kš
œ˜Kš
œ<˜<Kš
œ(˜(—K˜—Kš
œ˜Kšœ
˜—šžœœ"˜7Kš
˜Kšœ
œ
˜Kš
œ˜K˜šœœ
œ˜$šœœ˜"Kš
œ ˜ K˜-K˜$Kšœ˜
—šœ"œ˜*Kš
œ!˜!K˜—Kšœ
˜—Kš
œ˜Kš
œ"˜"K˜/K˜$Kšœ
˜—šž
œœ˜Kš
˜Kšœœ
œ˜9Kš
œ˜K™Mš
˜Kšœœ˜%Kšœœ=˜Gšœ˜š
œ˜K™eKš
œ3˜3šœœ
˜#Kš
œ(˜(—Kš	œœœ
œœ˜pKš
œ ˜ Kšœ>Ÿ
˜KKšœŸ
˜—šœœ˜Kšœœ˜1Kšœœ
œ
œ
œœ
˜:Kšœ$Ÿ˜3K˜Kšœœ˜K˜K˜.Kšœ˜Kšœœ
˜Kšœœ˜"Kšœœ
œ
œ
˜Kšœœ
˜šœ
œ˜"Kš
œ.˜.——Kšœ
˜—K˜)Kšœ
˜—Kšœ
˜——™šœœ
œ˜$Kš
œ?˜?K˜Kšœ
˜—Kšœœ ˜<Kšœœ
œ)˜FK˜)Kš	œœœ
œœ˜pKšœJŸ
˜WKšœHŸ˜_Kš
œP˜PKšœœ˜/Kšœ
˜——…—'&8.