What is Time-Proportionate Reverse Computation (TiPRC)?

The state of the system might be as shown in Figure 1 (a). The qlen variable is used to keep track of the current buffer occupancy; sent and lost are variables that accumulate statistics respectively of the total number of cells transferred to the output link and the total number of cells dropped because of a full buffer. The array delays measures the number of cells experiencing a given amount of delay, which in combination with the sent counter gives the cell delay distribution.

The cell arrival event handler processes newly arriving cells, as shown in Figure 1 (b). Upon a cell arrival, if the queue has no more room, then the counter lost is incremented representing that the cell has been dropped. Otherwise, the array element delay[qlen] is incremented representing that one more cell experienced a delay of qlen emission time units followed by an increment to qlen which represents that a cell has been added to the queue.

Figure 1: ATM multiplexor model with TiPRC

int qlen;
int sent;
int lost;
int delays[B];

bit b1;

if( qlen < B )
  {
  b1 = 1;
  delays[qlen]++;
  qlen++;
  }
else
  {
  b1 = 0;
  lost++;
  }

if( b1 == 1 )
  {
  --qlen;
  --delays[qlen];
  }
else
  {
  --lost;
  }

(a) State

(b) Cell arrival

Now, to support TiPRC, we have also added a single bit variable to the state of the multiplexor. This variable is used to note whether the if statement was executed or not (i.e., b1 = 1 if qlen

B and 0 otherwise).

If we look carefully at the cell arrival event, we can see that the state of the original model is fully captured by the bit variable b1. In other words, the state-trajectory set

of the variables $\{qlen, sent, lost, delays\}$ has a one-to-one correspondence with that of the set $S'=\{ b1 \}$ . The point here is that the values of the variables in

can be easily recovered based only on the value of

. To recover, we can run the event computations backwards, which will restore the variables of

to their before-computation values. More abstractly, the bit variable b1 is used to make the original model reversible. Indeed, it is easy to find the reverse code for each of the event handler of the modified model. For example, the reverse code shown in Figure 1 (c) performs a perfect undo of the operations of the cell arrival event handler given in Figure 1 (b). Thus, it is sufficient to maintain the history of the bit b1, instead of the whole set of state variables

of the original model.