-- File: PacketTimerImpl.mesa - last edit:
-- AOF 19-Jun-87 18:29:06
-- DWG.PA 9-Apr-85 16:37:42
-- Copyright (C) 1985, 1986, 1987 by Xerox Corporation. All rights reserved.
DIRECTORY
NSBuffer USING [Buffer, ReturnBuffer],
Inline USING [DBITAND, LowHalf],
PacketTimer USING [ResponseProc],
PacketExchange USING [
Error, CreateRequestor, Delete, ExchangeHandle, ExchangeClientType,
nullExchangeHandle, SetWaitTimes, ExchangeID],
PacketExchangeInternal USING [SendRequestPacket],
Process USING [Detach, MsecToTicks, SetTimeout],
Router USING [infinity, GetDelayToNet, NoTableEntryForNet],
<<SocketInternal USING [SocketHandle],>>
System USING [
GetClockPulses, MicrosecondsToPulses, Pulses, PulsesToMicroseconds];
PacketTimerImpl: MONITOR
IMPORTS
NSBuffer, Inline, PacketExchange, PacketExchangeInternal,
Process, Router, System
EXPORTS PacketTimer =
BEGIN
<<
This module sets timeouts on PacketExchange handles to minimize NET TRAFFIC
and maximize response time. We want to retransmit a packet when the foreign
host does not respond within the average round-trip delay time.
It currently takes 1 millisec to set an ExchangeHandle timeout, or 7 millisecs
to create one, so we cache a single handle.
By sending varying client ID's in each packet, we can compute the real round
trip delay [RTD](because we know which packet the foreign host responds to).
>>
triesConstant: CARDINAL = 6; -- # of times we retransmit pkts
tries: PUBLIC CARDINAL ← triesConstant;
ExchangeHandle: TYPE = PacketExchange.ExchangeHandle;
HopRecord: TYPE = RECORD [
delay: LONG CARDINAL, -- RTD in millisecs
workedTries: CARDINAL,
workedPackets: CARDINAL,
extraPackets: CARDINAL, -- ones we didn't have to send
failedPackets: CARDINAL];
cache: CacheRecord;
CacheRecord: TYPE = RECORD[
condition: CONDITION, --what the process is waiting on
watcher: PROCESS ← NIL, --detached process watching the cache
oldID: LONG CARDINAL ← firstID, --the last unique ID returned
cachedHandle: ExchangeHandle ← PacketExchange.nullExchangeHandle,
timeout, timein: LONG CARDINAL ← System.MicrosecondsToPulses[10D6],
cache: ARRAY NATURAL[0..Router.infinity] OF HopRecord ← TRASH];
-- Constants
firstID: LONG CARDINAL = 0; -- must be multiple of space
space: LONG CARDINAL = 8; -- gap between UIDs
bottomPart: LONG CARDINAL = 7B; -- reads the gap (lower three bits)
topPart: LONG CARDINAL = 37777777770B; -- zeroes the gap (upper 29)
weightHistory: CARDINAL = 8; -- credence given to past RTD statistics
maxWaitTime: LONG CARDINAL = 180000; -- 3 minutes max wait for a response
maxTimeout: LONG CARDINAL = maxWaitTime/triesConstant; -- millisecs per pkt max
minTimeout: LONG CARDINAL = 200; -- milisecs per pkt minimum before rexmit
GetElapsedTime: PROC [sent, received: System.Pulses] RETURNS [LONG CARDINAL] =
INLINE {RETURN[System.PulsesToMicroseconds[[received - sent]] / 1024]};
-- looks up a packet uid in a table of transmit times, and returns
-- the elasped time since this the packet with "uid" was transmitted.
RoundTripDelay: PROC [
uid: LONG CARDINAL, transmitTimes:LONG DESCRIPTOR FOR ARRAY OF System.Pulses]
RETURNS[LONG CARDINAL] = INLINE {
RETURN[GetElapsedTime[transmitTimes[Delta[uid]],System.GetClockPulses[]]]};
Delta: PROC[uid: LONG CARDINAL] RETURNS[CARDINAL] = INLINE
{RETURN[Inline.LowHalf[Inline.DBITAND[uid, bottomPart]]]};
Init: ENTRY PROCEDURE =
BEGIN
-- We start with static timeouts based on the following formula,
-- eliminating a special case for the first transmission to a given
-- hop-distance. The timeout is large to assure that we get a response.
Process.SetTimeout[@cache.condition, Process.MsecToTicks[1000]];
cache.watcher ← NIL; --detached process watching the cache
cache.oldID ← firstID; --the last unique ID returned
cache.cachedHandle ← PacketExchange.nullExchangeHandle; --cached handle
cache.timeout ← cache.timein ← System.MicrosecondsToPulses[10D6];
FOR i: CARDINAL IN [0..Router.infinity] DO
cache.cache[i] ← [i * 2048 + 512, 0, 0, 0, 0]; ENDLOOP;
END;
-- PUBLIC procs
-- transmits some packets to the foreign host, and calls back with the first
-- response. Checks in the px handle, and deletes send/receive buffers.
SendPackets: PUBLIC PROCEDURE [
pxH: ExchangeHandle, requestBuffer: NSBuffer.Buffer,
firstResponse: PacketTimer.ResponseProc, numberOfPackets: CARDINAL ← tries] =
BEGIN
hops: CARDINAL;
ptc: LONG POINTER TO HopRecord;
replyBuffer: NSBuffer.Buffer ← NIL;
baseTime: System.Pulses ← System.GetClockPulses[];
sendTimes: ARRAY [0..triesConstant) OF System.Pulses;
id: LONG CARDINAL; -- universal ID used for sending packet.
Cleanup: PROC = {
IF replyBuffer # NIL THEN NSBuffer.ReturnBuffer[replyBuffer];
NSBuffer.ReturnBuffer[requestBuffer]; GiveHandle[pxH]};
-- This generates special UIDs, whose upper 29 bits are unique, and
-- guaranteed to stay unique for a long time (>> minutes)
GetUniqueID: ENTRY PROC[] RETURNS[uid: PacketExchange.ExchangeID] =
BEGIN
id: LONG CARDINAL ← System.GetClockPulses[];
IF id <= cache.oldID + space THEN id ← cache.oldID + space;
RETURN[LOOPHOLE[cache.oldID ← Inline.DBITAND[id, topPart]]];
END;
hops ← Router.GetDelayToNet[requestBuffer.ns.destination.net !
Router.NoTableEntryForNet => {hops ← Router.infinity; CONTINUE}];
ptc ← @cache.cache[hops]; --makes it easier to get the record
requestBuffer.ns.exchangeID ← GetUniqueID[]; -- we use our own UIDs
FOR packets: CARDINAL IN [0..numberOfPackets) DO -- send a single packet
ENABLE UNWIND => Cleanup[];
sendTimes[packets] ← System.GetClockPulses[]; -- record send time
replyBuffer ← PacketExchangeInternal.SendRequestPacket[
pxH, requestBuffer, requestBuffer.ns.exchangeType, topPart !
PacketExchange.Error => IF why=timeout THEN CONTINUE ELSE EXIT;];
IF replyBuffer # NIL THEN
BEGIN -- got a response
id ← LOOPHOLE[replyBuffer.ns.exchangeID];
ptc.workedTries ← ptc.workedTries + 1;
ptc.workedPackets ← ptc.workedPackets + packets + 1;
ptc.extraPackets ← ptc.extraPackets + (packets - Delta[id]);
firstResponse[replyBuffer, hops];
NSBuffer.ReturnBuffer[replyBuffer];
NSBuffer.ReturnBuffer[requestBuffer];
Checkin[pxH, hops, RoundTripDelay[id, DESCRIPTOR[sendTimes]]];
RETURN;
END;
requestBuffer.ns.exchangeID ← -- increment the UID so we can measure RTD.
LOOPHOLE[LOOPHOLE[requestBuffer.ns.exchangeID, LONG CARDINAL] + 1];
ENDLOOP;
ptc.failedPackets ← ptc.failedPackets + numberOfPackets;
Cleanup[];
END; -- SendPackets
-- Checks out a packet Exchange Handle suitable for sending a single packet.
Checkout: PUBLIC PROCEDURE [hops: CARDINAL] RETURNS [pxH: ExchangeHandle] =
BEGIN
rexmitTime: LONG CARDINAL;
[pxH, rexmitTime] ← CheckoutInternal[@cache.cache[hops]];
IF (pxH = PacketExchange.nullExchangeHandle) THEN -- wasn't cached
pxH ← PacketExchange.CreateRequestor[rexmitTime, rexmitTime]
ELSE PacketExchange.SetWaitTimes[pxH, rexmitTime, rexmitTime];
END;
-- Checks in a packet Exchange Handle. Updates statistics.
Checkin: PUBLIC ENTRY PROCEDURE [
pxH: PacketExchange.ExchangeHandle, hops: CARDINAL, timeout: LONG CARDINAL] =
BEGIN
oldTimeout: LONG CARDINAL ← cache.cache[hops].delay;
-- weighted average formula is: [[N-1]*old + 1.5*new] / N, N a power of two.
timeout ← ((oldTimeout * weightHistory - oldTimeout) +
(timeout + timeout / 2)) / weightHistory;
-- now clip the timeout at upper and lower boundaries to prevent divergence.
cache.cache[hops].delay ← IF timeout<minTimeout THEN minTimeout
ELSE IF timeout > maxTimeout THEN maxTimeout ELSE timeout;
SELECT TRUE FROM
(cache.watcher = NIL) =>
BEGIN
Process.Detach[(cache.watcher ← FORK Watcher[])]; --create process
cache.cachedHandle ← pxH; --load the single element cache
cache.timein ← System.GetClockPulses[]; --restart the clock
END;
(cache.cachedHandle = PacketExchange.nullExchangeHandle) =>
BEGIN
cache.cachedHandle ← pxH; --load the single element cache
cache.timein ← System.GetClockPulses[]; --restart the clock
END;
ENDCASE => PacketExchange.Delete[pxH];
END;
ReadTimeout: PUBLIC ENTRY PROCEDURE [hops: CARDINAL]
RETURNS [timeout: LONG CARDINAL] = {RETURN[cache.cache[hops].delay]};
-- INTERNAL, PRIVATE ENTRY PROCS
GiveHandle: -- back -- ENTRY PROCEDURE [pxH: ExchangeHandle] =
BEGIN
SELECT TRUE FROM
(cache.watcher = NIL) =>
BEGIN
Process.Detach[(cache.watcher ← FORK Watcher[])]; --create process
cache.cachedHandle ← pxH; --load the single element cache
cache.timein ← System.GetClockPulses[]; --restart the clock
END;
(cache.cachedHandle = PacketExchange.nullExchangeHandle) =>
BEGIN
cache.cachedHandle ← pxH; --load the single element cache
cache.timein ← System.GetClockPulses[]; --restart the clock
END;
ENDCASE => PacketExchange.Delete[pxH];
END;
CheckoutInternal: ENTRY PROCEDURE [cH: LONG POINTER TO HopRecord]
RETURNS [pxH: ExchangeHandle, timeout: LONG CARDINAL] =
BEGIN
pxH ← cache.cachedHandle;
cache.cachedHandle ← PacketExchange.nullExchangeHandle;
timeout ← cH.delay;
END;
Watcher: <<DETACHED>> ENTRY PROC[] =
BEGIN
--FOR A WHILE-- DO
SELECT TRUE FROM
(cache.cachedHandle = PacketExchange.nullExchangeHandle),
((System.GetClockPulses[] - cache.timein) < cache.timeout) =>
WAIT cache.condition; --wait for a small period of time
ENDCASE => EXIT; --let's get out of here
ENDLOOP;
cache.watcher ← NIL; --cleanup our tracks
PacketExchange.Delete[cache.cachedHandle]; --get rid of exchange object
cache.cachedHandle ← PacketExchange.nullExchangeHandle; --and wipe out that
END; --Watcher
Init[];
END..
LOG
3-Dec-84 15:41:41 DWG created
14-Mar-85 22:14:48 DWG rewritten to remove multiple cached handles
15-Apr-85 15:47:00 DWG bent to Jody and Mark's will.
17-Jan-86 10:53:55 AOF gunned interface OPEN statement
6-Feb-86 8:54:58 AOF Merged PacketExchangeExtras
6-Jun-86 14:31:08 AOF Put cache array (+) into Courier's heap
18-Aug-86 18:45:38 AOF Allocate one more for the array
23-Dec-86 18:23:17 AOF Put the +1 in the right place
17-Feb-87 11:51:37 AOF Watcher on PEX handle caches.
19-Jun-87 18:05:27 AOF cache back in gf.