4.4 Buffer Memory Considerations

4.4 Buffer Memory Considerations

Most bridges and routers are modular devices whose feature selection list may contain more entries than a restaurant menu. Among the features from which you can normally select is a series of different memory modules that govern the buffer area in which frames can be queued when the frame arrival rate temporarily exceeds the service rate of the device.

Although the cost of memory has significantly declined over the past few years , a wild guess can still be costly from an operational perspective. Thus, we will conclude this chapter by examining how you can use queuing theory to make an educated estimate of the amount of buffer memory that should be installed in remote bridges and routers. It should also be mentioned that this section is applicable to LAN switches, because a related problem is the effect of buffer memory on delays through the switch.

4.4.1 Average Memory

Previously, we determined the mean length of the queue, denoted by Lq. By multiplying the value of Lq by the average frame size , you can determine the average amount of buffer memory that will be occupied. Unfortunately, this action results in the average amount of buffer memory required and means that half the time more memory will be required. Thus, to obtain a more meaningful mechanism to estimate buffer memory requirements, you must consider another method to determine the use of buffer memory. That method is obtained by computing the probability of the different numbers of frames in a queuing system.

4.4.2 Using Probability

The probability of n units (P _n ) in a single-channel, single-server system is obtained from the following formula:

The probability of k or more units (P _n>k ) in a single-channel, single-server system is given by the formula:

To illustrate the use of the preceding formulas, let us return to our prior computations in which the utilization level was determined as 0.375. Table 4.6 lists the statements of a BASIC program labeled UNITS.BAS, which you will use to compute the value of P(N) and P(N>K) as N and K vary from 0 to 20 for a single-channel, single-server system. This program, which is stored on the file UNITS.BAS in the directory BASIC at the referenced Web URL was written to accept any server utilization level which provides you with the ability to use it to satisfy the computational requirements associated with a specific situation.

 REM PROGRAM UNITS.BAS TO COMPUTE PROBABILITY OF N UNITS IN SYSTEM REM AND PROBABILITY OF K OR MORE UNITS IN SYSTEM CLS PRINT "PROGRAM TO COMPUTE PROBABILITY OF N UNITS AND K OR MORE UNITS IN SYSTEM" DIM P(20), K(20) INPUT "Enter utilization level of server"; P PRINT "PROBABILITY OF N UNITS    PROBABILITY K OR MORE UNITS" PRINT "  N     P(N)                K       P(N>K)" FOR N = 0 TO 20 P(N) = P ^ N * (1 - P) K(N) = P ^ N PRINT USING "### #.########           ###   #.########"; N; P(N); N; K(N) NEXT N END 

Table 4.7 illustrates the results obtained from the execution of the program UNITS.BAS with a server utilization level of 0.375, which is equivalent to 37.5 percent. In examining the data listed in Table 4.6, note the relationship P(N) and P(N>K). That is, P(N) provides the probability for a specific number of units or, for our example, frames in a system, while P(N>K) provides the probability that there are K or more units in the system. Thus, there is a 62.5 percent probability that there are no frames in the system (P(N = 0)), while as expected there is a probability of unity that there are 0 or more frames in the system. Although you could use either column of probabilities as a decision criterion for determining the amount of buffer space you need in your bridge or router, as you will shortly note, the second column provides a more direct value.

 PROGRAM TO COMPUTE PROBABILITY OF N UNITS AND K OR MORE UNITS IN SYSTEM Enter utilization level of server?.375 PROBABILITY OF N UNITS PROBABILITY K OR MORE UNITS   N     P(N)             K       P(N>K)   0 0.62500000           0   1.00000000   1 0.23437500           1   0.37500000   2 0.08789063           2   0.14062500   3 0.03295898           3   0.05273438   4 0.01235962           4   0.01977539   5 0.00463486           5   0.00741577   6 0.00173807           6   0.00278091   7 0.00065178           7   0.00104284   8 0.00024442           8   0.00039107   9 0.00009166           9   0.00014665  10 0.00003437          10   0.00005499  11 0.00001289          11   0.00002062  12 0.00000483          12   0.00000773  13 0.00000181          13   0.00000290  14 0.00000068          14   0.00000109  15 0.00000025          15   0.00000041  16 0.00000010          16   0.00000015  17 0.00000004          17   0.00000006  18 0.00000001          18   0.00000002  19 0.00000001          19   0.00000001  20 0.00000000          20   0.00000000 

In attempting to determine the size of the buffer space you require, the question you must answer is: How big should the buffer be to satisfy a predefined probability level of X percent? Then, once you define the probability level, you can answer the question. For example, assume you want a buffer size big enough to store 99.9 percent of the occurrences when the arrival rate exceeds the service rate. To accomplish this, you can directly use the second column listed in Table 4.7, in which the probability of K or more units was tabulated for K varying from 0 to 20. To obtain a level of 99.9 percent of the occurrences is equivalent to not being able to handle 0.1 percent of the occurrences, which would be displayed as 0.001 in the table in the second column of Table 4.7. Note that when K is 7, P(N>K) is 0.00104284, or slightly more than one tenth of 1 percent. Thus, you must select K equal to 8 to satisfy your requirement for handling 99.9 percent of the occurrences in which the frame arrival rate exceeds the service rate of the bridge or router. Thus, through the use of Table 4.7, you would want the bridge or router to be capable of storing or queuing up to eight frames. Because the frame length was defined as 1200 bytes, your memory storage requirement becomes 1200 bytes/frame * 8 frames, or 9600 bytes for this particular situation.

4.4.2.1 The Excel Model UNITS

Continuing our desire to develop Excel spreadsheet models when appropriate, Figure 4.12 shows the execution of the template stored in the Excel directory under the filename UNITS at the previously noted Web URL. This Excel template is a bit different from the Basic program of the same name . This difference results from the fact that the spreadsheet model requests the arrival rate and service rate to compute the level of utilization, providing a bit more flexibility. This additional flexibility results from the fact that you can override entering an arrival rate and service rate if you so desire and simply enter a utilization level in the appropriate cell position.

Figure 4.12: Execution of the Excel Template UNITS

4.4.3 Six-Step Approach

The steps required to determine queuing storage requirements can be summarized as follows :

1. Determine the average frame arrival and average server service rates.

2. Determine the utilization level of the server.

3. Determine the level of service you want the server to provide with respect to storing or queuing frames for transmission when the frame arrival rate exceeds the server's service rate.

4. Determine the probability of K or more units in the system for a range of values.

5. Determine the probability that N>K, where K represents the level of service you want the server to provide and locate that value in the computed range of probabilities. Then, extract the value of K that represents the number of frames that must be queued.

6. Multiply the average or maximum frame length by the number of frames that must be queued. Note that multiplying by the average frame length results in obtaining the average buffer storage required for a given level of probability, while multiplying by the maximum frame length supported by your LAN results in obtaining a buffer storage value that will satisfy all situations for the predefined probability level.

4.4.4 Considering the Maximum Frame Size

Although the first five steps are relatively self-explanatory, the sixth step may be confusing to some readers. Thus, let us take a moment prior to proceeding and focus attention on the final step.

Previously you determined that your bridge or router should have 9600 bytes of buffer storage to queue 99.9 percent of the occurrences in which the frame arrival rate exceeds the server's service rate. In actuality, the prior computation was based on an average frame length of 1200 bytes. Thus, the amount of buffer storage you computed satisfies an average of 99.9 percent of the occurrences in which the frame arrival rate exceeds the server's service rate. If you wish to obtain a buffer storage value that fully satisfies your probability requirement, you must then use the maximum frame size supported by the LAN you are using or anticipate installing. For example, if you are using an Ethernet or IEEE 802.3 LAN, its maximum frame size is 1500 bytes (excluding overhead preamble and addressing and CRC bytes), while the use of a 4-Mbps or 16-Mbps Token Ring LAN would result in a maximum frame size of 4500 or 18,000 bytes, respectively.

4.4.4.1 Program QVU.BAS

To facilitate performing another set of calculations, the program QVU.BAS was developed. Table 4.8 lists the statements contained in this program that compute the buffer requirements for Ethernet and 4- and 16-Mbps Token Ring networks based on different server utilization levels ranging up to 99.0 percent. Readers can easily modify this program to obtain buffer requirements for other server utilization levels or to slightly expand frame sizes to better reflect the overhead associated with transmitting a frame using a specific WAN protocol.

 REM PROGRAM QVU.BAS TO COMPARE QUEUE LENGTH VERSUS SERVER UTILIZATION LEVEL CLS FRAME = 1500 LPRINT "ANALYSIS OF BUFFER STORAGE REQUIREMENTS" LPRINT "MAXIMUM ETHERNET FRAME SIZE = 1500 BYTES" LPRINT "MAXIMUM 4MBPS TOKEN-RING FRAME SIZE  = 4500 BYTES" LPRINT "MAXIMUM 16MBPS TOKEN-RING FRAME SIZE =18000 BYTES" LPRINT LPRINT "UTILIZATION   LENGTH OF QUEUE     BUFFER REQUIREMENTS IN BYTES" LPRINT "  PERCENT     IN FRAMES      ETHERNET    4MBPS T-R 16MBPS T-R" FOR P = 0! TO.9 STEP.1 LQ = P ^ 2/(1 - P) B = INT(LQ * FRAME +.99) T4 = INT(LQ * 4500 +.99) T16 = INT(LQ * 18000 +.99) LPRINT USING "###.##       ####.###     ########"; P * 100; LQ; B; LPRINT USING "   ########   ########"; T4; T16 NEXT P FOR P =.91 TO.99 STEP.01 LQ = P ^ 2/(1 - P) B = INT(LQ * FRAME +.99) T4 = INT(LQ * 4500 +.99) T16 = INT(LQ * 18000 +.99) LPRINT USING "###.##       ####.###     ########"; P * 100; LQ; B; LPRINT USING "   ########   ########"; T4; T16 NEXT P END 

Table 4.9 illustrates the results obtained from the execution of QVU.BAS. In examining the data in Table 4.9, note that the length of the queue in terms of frames is relatively small until the server's utilization level exceeds 70 percent. Thereafter, it rapidly increases and will approach infinity as the utilization level approaches 100 percent. Thus, you can use the data in Table 4.9 to determine if you really need to continue further and compute P(N>K), or if you can simply estimate that at the level of server utilization the buffer requirements are so small that just about every bridge and router should have a sufficient amount of buffer memory. For example, suppose your server's utilization level was 80 percent and your organization operates an Ethernet LAN. Table 4.9 indicates an average buffer storage requirement of 4800 bytes, infinitesimally small in comparison with the 32 or 64 Kbytes of buffer storage included in most remote bridges and routers. Thus, without further analysis to compute P(N>K), you could safely conclude that a 32-Kbyte buffer area should be sufficient for P(N > 99.9).

 ANALYSIS OF BUFFER STORAGE REQUIREMENTS MAXIMUM ETHERNET FRAME SIZE = 1500 BYTES MAXIMUM 4MBPS TOKEN-RING FRAME SIZE = 4500 BYTES MAXIMUM 16MBPS TOKEN-RING FRAME SIZE = 18000 BYTES UTILIZATION   LENGTH OF QUEUE     BUFFER REQUIREMENTS IN BYTES   PERCENT       IN FRAMES        ETHERNET   4MBPS T-R  16MBPS T-R   0.00            0.000                0          0         0  10.00            0.011               17         50       200  20.00            0.050               75        225       900  30.00            0.129              193        579      2315  40.00            0.267              400       1200      4800  50.00            0.500              750       2250      9000  60.00            0.900             1350       4050     16200  70.00            1.633             2450       7350     29400  80.00            3.200             4800      14400     57601  91.00            9.201            13802      41406    165621  92.00           10.580            15870      47611    190441  93.00           12.356            18534      55601    222403  94.00           14.727            22090      66270    265080  95.00           18.050            27075      81225    324900  96.00           23.040            34560     103680    414720  97.00           31.363            47045     141135    564540  98.00           48.020            72030     216090    864359  99.00           98.009           147015     441043   1764171 

4.4.4.2 The Excel Model QVU

The Excel template QVU, which provides a computation capability similar to the Basic program file with that name, is located in the directory Excel at the previously noted Web URL. Figure 4.13 illustrates an example of the execution of this spreadsheet model, to include the display of a graph that plots queue length versus the level of utilization. As we summarize this chapter in the next section, we will reference this plot and the first two columns of tabular data shown in the Excel model.

Figure 4.13: Execution of the Excel Remplate QVU

4.4.5 Summary

Although a variety of queuing concepts were examined in this chapter, it is most important to remember several concepts that govern the application of queuing theory to networking. One concept is that as the level of utilization of a server increases, its queue length increases. A second concept worth remembering is the fact that as the level of utilization for a single-server system exceeds 50 percent, queues become more observable to whatever process you are performing. A third concept worth noting is the fact that as the level of utilization of a server approaches 100 percent, the length of a queue dramatically begins to increase and will eventually approach infinity.

The first two columns in Figure 4.13 indicate in tabular form the queue length for different utilization levels of a single-phase , single-channel system. Note that at a 50 percent utilization level, the mean queue length is 0.5; however, at a 70 percent level of utilization, the queue length more than tripled. Also note that an increase in utilization from 70 to 80 percent results in a doubling of the mean queue length, while an increase in utilization from 80 to 91 percent results in the length of the queue nearly tripling. The minichart shown at the bottom of the Excel model presented in Figure 4.13 graphically illustrates the same data. In examining Figure 4.13, it is important to remember that the mean queue length is directly related to the mean waiting time and explains why most network managers, analysts, and designers should consider modifying a network facility when its utilization level exceeds 50 percent.