Exemplo de Uso de Modelos Analíticos
Redes de Filas

Francisco Heron de Carvalho Junior

Analysis of Open Queueing Networks

[Graphics:Images/OpenQueue_gr_1.gif]

Definitions (Box 34.1)

Inputs

X = external arival rate, system throughput
[Graphics:Images/OpenQueue_gr_2.gif] = service time per visit to the ith device
[Graphics:Images/OpenQueue_gr_3.gif] = number of visits to the ith device
M = number of devices (not including terminals)

Outputs

[Graphics:Images/OpenQueue_gr_4.gif] = mean number of jobs at ith device
R[Graphics:Images/OpenQueue_gr_5.gif] = response time of the ith device
R = system response time
[Graphics:Images/OpenQueue_gr_6.gif] = utilization of the ith device
[Graphics:Images/OpenQueue_gr_7.gif] = mean number of jobs in the system

Example

Figure 1 shown below represents a queueing model of a server consisting of a CPU and two disks, A and B. Measurements on a distributed system with six clients making requests to the file server produced the following data:

[Graphics:Images/OpenQueue_gr_8.gif]

[Graphics:Images/OpenQueue_gr_9.gif]

Based on these observations, we can compute the service demands and visit ratios as follows:

[Graphics:Images/OpenQueue_gr_10.gif]
[Graphics:Images/OpenQueue_gr_11.gif]
[Graphics:Images/OpenQueue_gr_12.gif]
[Graphics:Images/OpenQueue_gr_13.gif]
[Graphics:Images/OpenQueue_gr_14.gif]
[Graphics:Images/OpenQueue_gr_15.gif]
[Graphics:Images/OpenQueue_gr_16.gif]
[Graphics:Images/OpenQueue_gr_17.gif]

We now have all the input parameters required to analyse the system.

[Graphics:Images/OpenQueue_gr_18.gif]
[Graphics:Images/OpenQueue_gr_19.gif]
[Graphics:Images/OpenQueue_gr_20.gif]
[Graphics:Images/OpenQueue_gr_21.gif]
[Graphics:Images/OpenQueue_gr_22.gif]
[Graphics:Images/OpenQueue_gr_23.gif]
[Graphics:Images/OpenQueue_gr_24.gif]
[Graphics:Images/OpenQueue_gr_25.gif]
[Graphics:Images/OpenQueue_gr_26.gif]
[Graphics:Images/OpenQueue_gr_27.gif]
[Graphics:Images/OpenQueue_gr_28.gif]
[Graphics:Images/OpenQueue_gr_29.gif]
[Graphics:Images/OpenQueue_gr_30.gif]
[Graphics:Images/OpenQueue_gr_31.gif]
[Graphics:Images/OpenQueue_gr_32.gif]
[Graphics:Images/OpenQueue_gr_33.gif]
[Graphics:Images/OpenQueue_gr_34.gif]
[Graphics:Images/OpenQueue_gr_35.gif]

The model can be used to answer some of the typical questions. For example, we might want to quantify the impact of the following changes:
1. Increase the number of clients to B
2. Use a cache for disk B with a hit rate of 50%, although it increases the CPU overhead by 30% and the disk B service time (per I/O) by 10%.
3. Have a lower cost server with only one disk (disk A) and direct all I/O requests to it.

1st Case:

The first question can be answered if we assume that the new clients make requests similar to those measured. The request arrival rate will go up by a factor of [Graphics:Images/OpenQueue_gr_36.gif]. Since the arrival rate was three requests per second, with more clients it will become four requests per second. The new analysis is as follows:

[Graphics:Images/OpenQueue_gr_37.gif]
[Graphics:Images/OpenQueue_gr_38.gif]
[Graphics:Images/OpenQueue_gr_39.gif]
[Graphics:Images/OpenQueue_gr_40.gif]
[Graphics:Images/OpenQueue_gr_41.gif]
[Graphics:Images/OpenQueue_gr_42.gif]
[Graphics:Images/OpenQueue_gr_43.gif]
[Graphics:Images/OpenQueue_gr_44.gif]
[Graphics:Images/OpenQueue_gr_45.gif]
[Graphics:Images/OpenQueue_gr_46.gif]
[Graphics:Images/OpenQueue_gr_47.gif]
[Graphics:Images/OpenQueue_gr_48.gif]
[Graphics:Images/OpenQueue_gr_49.gif]
[Graphics:Images/OpenQueue_gr_50.gif]
[Graphics:Images/OpenQueue_gr_51.gif]
[Graphics:Images/OpenQueue_gr_52.gif]
[Graphics:Images/OpenQueue_gr_53.gif]
[Graphics:Images/OpenQueue_gr_54.gif]
[Graphics:Images/OpenQueue_gr_55.gif]
[Graphics:Images/OpenQueue_gr_56.gif]
[Graphics:Images/OpenQueue_gr_57.gif]
[Graphics:Images/OpenQueue_gr_58.gif]
[Graphics:Images/OpenQueue_gr_59.gif]
[Graphics:Images/OpenQueue_gr_60.gif]
[Graphics:Images/OpenQueue_gr_61.gif]
[Graphics:Images/OpenQueue_gr_62.gif]

Thus, if the number of clients is increased from 6 to 8, the server response time will degrade by a factor of

[Graphics:Images/OpenQueue_gr_63.gif]
[Graphics:Images/OpenQueue_gr_64.gif]
2nd case:

The second question requires changing [Graphics:Images/OpenQueue_gr_65.gif], [Graphics:Images/OpenQueue_gr_66.gif] and [Graphics:Images/OpenQueue_gr_67.gif] as follows:

[Graphics:Images/OpenQueue_gr_68.gif]
[Graphics:Images/OpenQueue_gr_69.gif]
[Graphics:Images/OpenQueue_gr_70.gif]
[Graphics:Images/OpenQueue_gr_71.gif]
[Graphics:Images/OpenQueue_gr_72.gif]
[Graphics:Images/OpenQueue_gr_73.gif]
[Graphics:Images/OpenQueue_gr_74.gif]
[Graphics:Images/OpenQueue_gr_75.gif]

The analysis of the changed systems is as follows

[Graphics:Images/OpenQueue_gr_76.gif]
[Graphics:Images/OpenQueue_gr_77.gif]
[Graphics:Images/OpenQueue_gr_78.gif]
[Graphics:Images/OpenQueue_gr_79.gif]
[Graphics:Images/OpenQueue_gr_80.gif]
[Graphics:Images/OpenQueue_gr_81.gif]
[Graphics:Images/OpenQueue_gr_82.gif]
[Graphics:Images/OpenQueue_gr_83.gif]
[Graphics:Images/OpenQueue_gr_84.gif]
[Graphics:Images/OpenQueue_gr_85.gif]
[Graphics:Images/OpenQueue_gr_86.gif]
[Graphics:Images/OpenQueue_gr_87.gif]
[Graphics:Images/OpenQueue_gr_88.gif]
[Graphics:Images/OpenQueue_gr_89.gif]
[Graphics:Images/OpenQueue_gr_90.gif]
[Graphics:Images/OpenQueue_gr_91.gif]
[Graphics:Images/OpenQueue_gr_92.gif]
[Graphics:Images/OpenQueue_gr_93.gif]

Thus, if we use a cache for disk B, the server response time will improve by a factor of

[Graphics:Images/OpenQueue_gr_94.gif]
[Graphics:Images/OpenQueue_gr_95.gif]
3rd case

The third question requires adjusting [Graphics:Images/OpenQueue_gr_96.gif] and [Graphics:Images/OpenQueue_gr_97.gif]. We assume that there is enough space on disk A to be able to accomodate all files on both disks The analysis is as follows:

[Graphics:Images/OpenQueue_gr_98.gif]
[Graphics:Images/OpenQueue_gr_99.gif]
[Graphics:Images/OpenQueue_gr_100.gif]
[Graphics:Images/OpenQueue_gr_101.gif]
[Graphics:Images/OpenQueue_gr_102.gif]
[Graphics:Images/OpenQueue_gr_103.gif]
[Graphics:Images/OpenQueue_gr_104.gif]
[Graphics:Images/OpenQueue_gr_105.gif]
[Graphics:Images/OpenQueue_gr_106.gif]
[Graphics:Images/OpenQueue_gr_107.gif]
[Graphics:Images/OpenQueue_gr_108.gif]
[Graphics:Images/OpenQueue_gr_109.gif]
[Graphics:Images/OpenQueue_gr_110.gif]
[Graphics:Images/OpenQueue_gr_111.gif]
[Graphics:Images/OpenQueue_gr_112.gif]
[Graphics:Images/OpenQueue_gr_113.gif]
[Graphics:Images/OpenQueue_gr_114.gif]
[Graphics:Images/OpenQueue_gr_115.gif]
[Graphics:Images/OpenQueue_gr_116.gif]
[Graphics:Images/OpenQueue_gr_117.gif]
[Graphics:Images/OpenQueue_gr_118.gif]
[Graphics:Images/OpenQueue_gr_119.gif]
[Graphics:Images/OpenQueue_gr_120.gif]
[Graphics:Images/OpenQueue_gr_121.gif]
[Graphics:Images/OpenQueue_gr_122.gif]
[Graphics:Images/OpenQueue_gr_123.gif]
[Graphics:Images/OpenQueue_gr_124.gif]
[Graphics:Images/OpenQueue_gr_125.gif]

Sensibility Analisys over the parameters [Graphics:Images/OpenQueue_gr_126.gif] (service time per visit to the ith device)

For Disk A
[Graphics:Images/OpenQueue_gr_127.gif]
[Graphics:Images/OpenQueue_gr_134.gif]
[Graphics:Images/OpenQueue_gr_135.gif]

[Graphics:Images/OpenQueue_gr_136.gif]

[Graphics:Images/OpenQueue_gr_137.gif]
[Graphics:Images/OpenQueue_gr_138.gif]
[Graphics:Images/OpenQueue_gr_139.gif]
[Graphics:Images/OpenQueue_gr_140.gif]
[Graphics:Images/OpenQueue_gr_141.gif]
[Graphics:Images/OpenQueue_gr_148.gif]
[Graphics:Images/OpenQueue_gr_149.gif]

[Graphics:Images/OpenQueue_gr_150.gif]

[Graphics:Images/OpenQueue_gr_151.gif]
For Disk B
[Graphics:Images/OpenQueue_gr_152.gif]
[Graphics:Images/OpenQueue_gr_159.gif]
[Graphics:Images/OpenQueue_gr_160.gif]

[Graphics:Images/OpenQueue_gr_161.gif]

[Graphics:Images/OpenQueue_gr_162.gif]
[Graphics:Images/OpenQueue_gr_163.gif]
[Graphics:Images/OpenQueue_gr_164.gif]
[Graphics:Images/OpenQueue_gr_165.gif]
[Graphics:Images/OpenQueue_gr_166.gif]
[Graphics:Images/OpenQueue_gr_173.gif]
[Graphics:Images/OpenQueue_gr_174.gif]

[Graphics:Images/OpenQueue_gr_175.gif]

[Graphics:Images/OpenQueue_gr_176.gif]
For CPU
[Graphics:Images/OpenQueue_gr_177.gif]
[Graphics:Images/OpenQueue_gr_184.gif]
[Graphics:Images/OpenQueue_gr_185.gif]

[Graphics:Images/OpenQueue_gr_186.gif]

[Graphics:Images/OpenQueue_gr_187.gif]
[Graphics:Images/OpenQueue_gr_188.gif]
[Graphics:Images/OpenQueue_gr_189.gif]
[Graphics:Images/OpenQueue_gr_190.gif]
[Graphics:Images/OpenQueue_gr_191.gif]
[Graphics:Images/OpenQueue_gr_198.gif]
[Graphics:Images/OpenQueue_gr_199.gif]

[Graphics:Images/OpenQueue_gr_200.gif]

[Graphics:Images/OpenQueue_gr_201.gif]

Sensibility Analisys over the parameter X (system throghput)

[Graphics:Images/OpenQueue_gr_202.gif]
[Graphics:Images/OpenQueue_gr_203.gif]
[Graphics:Images/OpenQueue_gr_204.gif]
[Graphics:Images/OpenQueue_gr_205.gif]
[Graphics:Images/OpenQueue_gr_218.gif]
[Graphics:Images/OpenQueue_gr_219.gif]

[Graphics:Images/OpenQueue_gr_220.gif]

[Graphics:Images/OpenQueue_gr_221.gif]
[Graphics:Images/OpenQueue_gr_222.gif]
[Graphics:Images/OpenQueue_gr_223.gif]
[Graphics:Images/OpenQueue_gr_224.gif]
[Graphics:Images/OpenQueue_gr_225.gif]
[Graphics:Images/OpenQueue_gr_238.gif]
[Graphics:Images/OpenQueue_gr_239.gif]

[Graphics:Images/OpenQueue_gr_240.gif]

[Graphics:Images/OpenQueue_gr_241.gif]


Converted by Mathematica      July 27, 2000