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
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
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.
impGatewayName: ROPE ← IPConfig.impGatewayName;
gatewayAddress: Pup.Host; -- home of the gateway Alto.
stateChanged: PROC [rope: ROPE] ← NIL;
tooBig: INT ← 0;
Routing table stuff
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
Given a buffer from the buffer pool, returns a pointer to where the datagram should begin.
ePtr: LONG POINTER TO Encapsulation ~ LOOPHOLE[@b.data];
RETURN [LOOPHOLE[@ePtr.data]];
END;
SendDatagram:
PUBLIC
PROC [data: IPDefs.Datagram] =
BEGIN
Allocate a buffer, do the routing, and send it.
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
Extract the net part of the internet address.
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
Where do I send this datagram?
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
Does routing and encapsulation. b already has the data filled in.
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;
Wake up every so often try to provoke our special gateway into talking to us.
DO
now: BasicTime.GMT ← BasicTime.Now[];
since: INT = BasicTime.Period[from: lastTimeGatewayResponded, to: now];
SELECT since
FROM
> gatewayDeadTime => {
Try to use next gateway. This isn't synchronized with anything, but it isn't particularly important.
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;
Initialization code
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.