Simulation Model

The Certificate Revocation Simulator is designed to model three schemes, CRL, Delta CRL with Distribution Points, and OCSP. In order to produce a flexible simulator, a general approach that is capable of modelling all the schemes is preferred. This also facilitates easy adaptation to simulating Delta CRL and CRL DPs separately. Thus this simulator simulates five schemes:

CRL
CRL Distribution Points
Delta CRL
CRL Distribution Points with Delta CRLs
OCSP

Note that the implementation readily supports a simulation of "OCSP with Distribution Points", i.e. multiple OCSP responders with different responsibilities. This is, however, not standardized or simulated in this project.

Simulation Input Variables

There are seven input-variables to the simulator alltogether. The following four variables are general, and applies to any scheme:

Simulation timespan in minutes (T)
System Size in EndEntities (N)
Average Validations per day (v)
Revocation Rate (r_r)

Furthermore, there are three scheme specific parameters:

Revocation Information validity period in minutes (r_u): if this is set to 1, there is no caching in the scheme
Number of Distribution Points/ segments (s): if this is set to 1, there is only one distributor
Delta CRLs per validity period (d): if this is set to 1, there is no delta CRLs

Output Variables

There are eight output-variables from the simulator. Two of the variables are only relevant if Delta CRLs are used. These are the output-variables:

Max Request Rate (RQ_max)
Max Delta CRL Request Rate (RQ_delta,max)
Max Network Load (NW_max)
Max Processing Load (PROC_max)
Max Delay (DL_max)

The maximum values are chosen to describe the scheme in its worst case, so that a minimal performance may be guaranteed.

Computing the Intermediate Variables

RevocationRate per validity period (r_r,v): this value is necessary in order to compute the revocation size for delta CRLs:
r_r,v=v * r_r / (365 * 24 * 60)
Revocation Size in bits (SIZE):
SIZE_CRL(r_r,N)=8*(128 + 51+9*r_r*N)

SIZE_DeltaCRL(r_r,N)=SIZE_CRL(r_r,v / 2,N)=8*(128 + 51+9*r_r,v*N/2)

SIZE_OCSP(r_r,N)=1000

Assumptions and Model Constants

The certificate validity time is one year
The certificate revocation rate represents the percentage of revoked certificates over one year
The bandwith (BW) of the system is set to 10Mbit
The processing load is measured in units. The processing capactity is set to 1000, so that a unit describes the processing equivalent of 1ms. Hence, if the processing load is larger than 1000 units per second, the work will queue up, causing delay.
A digital signature is 128 bytes. A CRL request is 51 bytes plus 9 per certificate plus the signature. An OCSP Response is estimated to be 1000 bits.
It takes 1 ms to process a request an already signed CRL. It takes 43 ms to process an OCSP request.
A delta CRL or CRL DP has the same size and processing properties as a CRL. They contain less certificate information and are consequently slower.
The responsibility of each Distribution Points is random and equally large as any other DP. Hence any revocation information request is equally likely to be directed at any of the Distribution Points
Time periods are given in minutes, validation frequency is per day, the request rates are measured in seconds, whereas delay is given in ms. The values are chosen in order to follow standard measurements and to provide more realism to the simulation variables.
If the maximum network load is higher than the bandwidth, the network is congested. If the average network load is higher than the bandwidth, the network is always congested, and the scheme will not work. The same is true for the processing time, where a processing time above 1000 indicates a congested repository.

Computing the Results

This paragraph describes how the output variables are simulated or computed based on simulation variables. Note that the simulation checks what scheme is used and uses the appropriate size or processing time in the equations.

The maximum request rate and maximum delta CRL request rate are not computed, but simulated. For both the values, the requests for each time unit (minute) is stored in two arrays (requests, deltaRequests) in the Statistics class. A procedure finds the maximum request rate and divides this by 60 to represent requests per second.
RQ_max=max(requests)/60

RQ_delta,max=max(deltaRequests)/60
The maximum network load is computed on the basis of the maximum request rate and maximum delta CRL request rate. The request rates for each time unit are multiplied by the respective estimated revocation information size. The values are then added together and stored in an array in the Statistics class. A procedure finds the maximum network load.
NWarray_t=RQ_t*SIZE_{CRL or
OCSP} + RQ_delta,t*SIZE_DeltaCRL
NW_max=max(NWarray(
The maximum processing load is computed in the same way as the maximum network load, except that the Processing time is used instead of the Size.
PROCarray_t=RQ_t*PROC_{CRL or
OCSP} + RQ_delta,t*PROC_DeltaCRL

PROCarray_max=max(PROCarray)
The maximum delay represents the sum og the network- and the processing- delay:
DL_max=DL_{NW,
max}+DL_{PROC, max}
The netwok delay is the sum of the total transmission time and the waiting/ queueing time:
DL_NW,max=2*max(queue_NW)+SIZE/BW
Here, the queueing time is computed as the network load in the time period minus the bandwidth plus the size of the queue from the last time period (minute). The queueing time is defined to always be positive or zero.
queue_NW,t=(NW_t+queue_NW,t-1)-BW
Similarly, the processing total delay is the sum of the total processing time and the waiting/ queueing time:
DL_PROC,max=max(queue_PROC+SIZE
) The processing queueing time is computing in a similar way as the network queueing time, except that the the processing capacity (PC) is used instead of the bandwidth.
queue_PROC,t=(PROC_t+queue_PROC,t-1)-PC
It was assumed in these calculations that the transmission time for requests is relatively small and can be ignored, and that the maximum delay occurs for a base revocation request rather than for a delta request. This is reasonable because the base revocation reques is larger and requires more network resources.

andrearn@pvv.ntnu.no

Last modified: Tue Apr 25 20:31:48 CEST 2000