-- 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.