# Dynamic Programming Approach for Single-Node Optimization.

Changes in the availability, use and economics of telecommunications
services have caused companies to closely examine their calling
requirements, particularly for long distance. The PBX, used by most
organizations for their communications, generally uses automatic route
selection to complete long-distance calls in order of placement through
available costs (from the least to the most expensive), optimization of
the system can be obtained.

This article describes a dynamic programming approach to figuring the most economical trunking configuration for implementation of a single-node communication system. A dynamic programming approach is used to make a sequence of decisions so that the total cost is optimized.

We are concerned with reducing the total cost of a single-node system that has several collecting points and one branching point for the overflow traffic among the trunk groups. A collecting point is necessary to provide the first overflow trunk group for different foreign-exchange (FX) lines. A branching point is required to accommodate the traffic that overflows from one group (MCI, for example) to different WATS bands with known distributions.

To obtain otpimization, we must assume that the traffic has a constant-rate random arrival. This asusmption permits the use of the Erlang B formula in figuring the optimum trunking configuration. The Elarng B formula is used in dimensioning trunk groups. This formula assumes that traffic originates from an infinite number of traffic sources, that the number of service channels is limited, that lost calls are cleared from the system with zero holding time, and that it is valid for any distribution of call holding time. By changing a parameter such as representative hourly traffic, the optimum trunking configuration can be used to calculate minimum cost for any single-node system.

In determining the trunking configuration of a single-node system, it often occurs that the overflow traffic does not have a strictly sequential route, thereby prohibiting the direct application of a dynamic programming approach. This difficulty can be overcome by including an additional state variable. Since each stage is a trunk group, the decision is made at each stage as to how many trunks should be optimally used. Applying the Concept

Figure 1 depicts the general features of a single-node system where the dynamic programming method for optimization can be applied. There are N trunk groups with some randomly distributed, first-offered traffic for each group. The first-offered traffic of the last group, usually DDD, contributes nothing to reducing cost and is therefore excluded in this discussion. Each group has a certain number of trunks to carry the traffic. The overflow traffic is passed over to the succeeding trunk groups, which are arranged in a cost-ascending order. The last trunk group is assumed to have an unlimited capacity and absorbs all overflow traffic passed to it. The ordering of FX groups is not important as long as they overflow to the right trunk group. For example, three FX groups overflow to WATS Band 3. Although these three FX groups should be contiguous in sequencing, their ordering among themselves is not important. Branching of the overflow traffic occurs at a trunk group so that only a known fraction of the overflow traffic goes to the next group. The rest of the overflow traffic from the first group is directed to other subsequent groups with known distributions.

Each trunk group usually has a piece-wise, linear rate structure. Typical rate structures for WATS, FX and DDD groups are shown in Figure 2. Although there might be an initial installation cost, with increasing traffic per trunk per month, the incremental cost decreases. The cost of an FX trunk is usually not usage-sensitive and is represented by a horizontal line. The last trunk group has a flat rate with no installation cost and is represented in Figure 2 as a straight line through the origin. On a typical business day, traffic comes in with a random distribution. The hourly traffic rate has a bimodal distribution with one peak in the morning and one in the afternoon.

The problem is to size all groups in such a way that the system achieves the least total cost. Two-Step Procedure

The proposed dynamic programming procedure has two steps:

* Step 1--A certain constant, fraction f, is applied to the daily, first-offered traffic of every trunk group to produce representative hourly traffic. The dynamic programming approach is applied to this hourly traffic to arrive at the optimum trunking arrangement.

Each trunk group is a stage, and the number of trunks in each stage is a decision variable. There are two state variables: the allowable and the non-allowable traffic levels. Conceptually, the traffic flows through the system in a sequential fashion. Overflow traffic, which is meant to be routed to a later trunk group, is put in the non-allowable traffic and transferred from the non-allowable traffic to the allowable traffic when it reaches the trunk group to which it has been routed. Since the distribution of the overflow traffic among all the branches routed. Since the distribution of the overflow traffic among all the branches is known, only the total non-allowable traffic needs to be a state variable.

At each stage, the allowable traffic consists of three components: the traffic first offered to this group; the overflow from the allowable traffic of the previous stage if it is allowable at the present stage; and the portion of the non-allowable traffic of the other previous stages that becomes allowable for the present stage.

The non-allowable traffic of the present stage is the portion of the overflow traffic that is non-allowable for that stage. At the last stage, DDD, there is no non-allowable traffic. Cost-Function Table

A two-dimensional cost-function table is developed for each trunk group, starting with the next to last group and proceeding toward the first group. The two dimensions in the table represent the allowable and the non allowable traffic levels. These ranges are determined by the extreme cases under the given first-offered traffic to the system; the lower limit is the first-offered traffic at that stage. The range of values between the upper limit and the lower limit is divided into several intervals. Each table entry contains the optimum cost to carry the specified total traffic (allowable plus nonallowable).

For each cost-function table entry, the Erlang B formula is used to determine the overlfow traffic from the allowable traffic for different trunk sizes. The cost of the carried traffic is determined by the known cost structure of that group. The cost of the overflow traffic is taken from the cost-function table for the succeeding trunk group, which has already been developed. This may involve interpolation of values; a quadratic interpolation is recommended for keeping the overall accuracy at acceptable levels. The minimum total cost and its corresponding trunk size are entered in the new table (corresponding to the new stage).

The cost-function table of the first trunk group has only one entry, which corresponds to the group's first-offered traffic. The cost and the trunk size are optimum for the first group. The optimum trunk sizes of the succeeding groups are obtained by tracing, starting with the first group. The Erlang B formula is applied to the first table's allowable traffic and trunk sizxe; the cost for the carried traffic is calculated. Three factors determine from where in the table of the succeeding stage to select the trunk size for that sate: the amount of overflow traffic, the amount of non-allowable traffic and the first-offered traffic of the succeeding group. The cost of the carried traffic is again calculated. This is done for all subsequent trunk groups. The total cost for the system is the sum of all partial costs at all stages. Tracing Checks Accuracy

The tracing procedure determines the system's optimum trunking and the corresponding cost, which can be compared with the table cost of the first group. This provides a check on the accuracy of the interpolation. The table size (the number of intervals between the upper limit and the lower limit) can be varied until a stable, accurate solution is obtained.

* Step 2--The second step of this dynamic programming procedure varies the fraction f of Step 1. With each value of f, the cost is recalculated using the hourly traffic profile and the trunking configuration of step 1. The non-randomness of the overflow traffic is accounted for by the equivalent random theory (R.I. Wilkinson, "Theories for Toll Traffic Engineering in the USA," Bell System Technical Journal, Volume 35, Number 2, March 1956, pages 421 through 514). This theory takes advantage of the formulas for the mean and the variance of the overflow traffic when a random traffic of "a" Erlangs is offered to a trunk group of size c: Mean, m=aE(c,a) Variance, v=m(1-m+a/(c+m-a)) where m=the mean of the overflow traffic, a=the mean of the original random traffic; c=the trunk group size; E(c,a)=the probability of overflow using Erlang B formula; and v=the variance of the overflow traffic.

Steps 1 and 2 are carried out for different values off. The configuration with the lowest cost is used as the final result. How It Works

Figure 3 illustrates an example. The first group, MCI Network Services, is a branching point. The first-offered traffic is expressed in unit hours per month. A typical month has 21 business days. All other parameters are given in Figure 4.

Entries are in cost-per-hour for each group at the left of the table. Suppose Group 1 (MCI) has four trunks and carries a total of 100 hours of traffic in a month. Then, on the average, each trunk carries 25 hours. The cost for each trunk is: $85 + 15($16.33) + 10($14.52) = $475.15. The total cost for Group 1 is: 4($475.15)=$1,900.60.

As far as the total cost of the group is concerned, it does not matter how the total traffic is carried among all trunks in the group. Using a computer program developed at Northern Telecom, for f=.125, the results shown in Figure 5 are obtained in Step 1.

The table cost differs from the traced exact cost by 0.06 percent. So a table of size 10 times 10 is accurate enough, at least for this problem.

When there are only two trunk groups (for example, WATS 5 and DDD), the optimization is simple--vary the number of trunks for the WATS 5 group, calculate the total cost for each configuration and pick the best one. The dynamic programming method becomes useful when theer are more than two trunk groups. Reoptimizing gets more complicated when more and more groups are added, and the dynamic programming approach outlined here is one way to handle the added trunk groups properly. Using Another Formula

If the Erlang B overflow formula is replaced by some other suitable queuing formula, the dynamic programming method can be applied to a trunking design with queing. The two steps formulated earlier stay the same.

The above cost-reduction scheme does not produce the absolute lowest cost because the dynamic programming approach is applied only in a limited sense. To apply dynamic programming in the most general case and let the absolute minimum cost, the hourly traffic profile and the non-randomness of the overflow traffic must be taken into account when the cost-function tables are built.

to include the hourly traffic profile, the number of state variables has to be increased tremendously. Two state variables are needed for each hour, one for the allowable and one for the non allowable traffic levels, because the hourly traffic distribution determines how much traffic is carried by each group. For example, under the busy hour approach, there will be a higher level of overflow than when the traffic is assumed to be evenly distributed over all business hours; that is, "average-hour" approach. The total cost of the latter will be less since trunk groups are arranged in cost-ascending order.

From stage to stage, the hourly traffic profile is changed because different fractions of the traffic are carried for each hour. The higher the traffic in an hour, the lower the fraction that is carried. As a result, to keep the total cost accurate, one must have additional state variables. If we have only eight business hours in a day, the number of state variables increases from two to 16. This increase renders the dynamic programming approach impossible for use with present-day computers, due to both storage and computing time limitations.

Since the parameter f is varied in Step 2, the effect of the hourly traffic distribution is actually accounted for in a satisfactory fashion. This can be demonstrated in a comparison of total overflow traffic calculation for one trunk group using different approximation methods (Figure 6). Assume that there are 20 business ays in a month and nine business hours in a day. The hourly traffic distribution is shown in the table.

The monthly overflow traffic using different methods is given in Figure 7.

It can be seen that if a busy hour is used to calculate the overflow traffic, the percentage error can be as high as 7.8 percent and it always overestimates the amount of overflow traffic. If an average hour is used, it always underestimates the overflow traffic and the maximum error is minus 2.5 percent. If an f=0.118 is used, the relative error is kept to less than one percent. Since f is always varied and the best one chosen in Step 2, the error in overflow traffic calculation by using a representative hour can be expected to be less than one percent, which is accurate enough for our purposes. Worth Investigating

Developing further use of dynamic programming for optimizing single-node systems, including the non randomness of the overflow traffic in Step 1 of this approach, is not inconceivable since it only adds one additional state variable--peakedness. This means, however that a three-dimensional interpolation is needed for each table. A three-dimensional interpolation is usually less accurate than a two-dimensional interpolation. As a result, larger tables are needed to increase accuracy. The inclusion of peakedness in the dynamic programming approach appears to be a worthwhile topic for future investigation.

The required CPU time varies linearly with the number of trunk groups. The example cited earlier, with seven trunk groups, requires 14 CPU seconds on an IBM 4341.

This article describes a dynamic programming approach to figuring the most economical trunking configuration for implementation of a single-node communication system. A dynamic programming approach is used to make a sequence of decisions so that the total cost is optimized.

We are concerned with reducing the total cost of a single-node system that has several collecting points and one branching point for the overflow traffic among the trunk groups. A collecting point is necessary to provide the first overflow trunk group for different foreign-exchange (FX) lines. A branching point is required to accommodate the traffic that overflows from one group (MCI, for example) to different WATS bands with known distributions.

To obtain otpimization, we must assume that the traffic has a constant-rate random arrival. This asusmption permits the use of the Erlang B formula in figuring the optimum trunking configuration. The Elarng B formula is used in dimensioning trunk groups. This formula assumes that traffic originates from an infinite number of traffic sources, that the number of service channels is limited, that lost calls are cleared from the system with zero holding time, and that it is valid for any distribution of call holding time. By changing a parameter such as representative hourly traffic, the optimum trunking configuration can be used to calculate minimum cost for any single-node system.

In determining the trunking configuration of a single-node system, it often occurs that the overflow traffic does not have a strictly sequential route, thereby prohibiting the direct application of a dynamic programming approach. This difficulty can be overcome by including an additional state variable. Since each stage is a trunk group, the decision is made at each stage as to how many trunks should be optimally used. Applying the Concept

Figure 1 depicts the general features of a single-node system where the dynamic programming method for optimization can be applied. There are N trunk groups with some randomly distributed, first-offered traffic for each group. The first-offered traffic of the last group, usually DDD, contributes nothing to reducing cost and is therefore excluded in this discussion. Each group has a certain number of trunks to carry the traffic. The overflow traffic is passed over to the succeeding trunk groups, which are arranged in a cost-ascending order. The last trunk group is assumed to have an unlimited capacity and absorbs all overflow traffic passed to it. The ordering of FX groups is not important as long as they overflow to the right trunk group. For example, three FX groups overflow to WATS Band 3. Although these three FX groups should be contiguous in sequencing, their ordering among themselves is not important. Branching of the overflow traffic occurs at a trunk group so that only a known fraction of the overflow traffic goes to the next group. The rest of the overflow traffic from the first group is directed to other subsequent groups with known distributions.

Each trunk group usually has a piece-wise, linear rate structure. Typical rate structures for WATS, FX and DDD groups are shown in Figure 2. Although there might be an initial installation cost, with increasing traffic per trunk per month, the incremental cost decreases. The cost of an FX trunk is usually not usage-sensitive and is represented by a horizontal line. The last trunk group has a flat rate with no installation cost and is represented in Figure 2 as a straight line through the origin. On a typical business day, traffic comes in with a random distribution. The hourly traffic rate has a bimodal distribution with one peak in the morning and one in the afternoon.

The problem is to size all groups in such a way that the system achieves the least total cost. Two-Step Procedure

The proposed dynamic programming procedure has two steps:

* Step 1--A certain constant, fraction f, is applied to the daily, first-offered traffic of every trunk group to produce representative hourly traffic. The dynamic programming approach is applied to this hourly traffic to arrive at the optimum trunking arrangement.

Each trunk group is a stage, and the number of trunks in each stage is a decision variable. There are two state variables: the allowable and the non-allowable traffic levels. Conceptually, the traffic flows through the system in a sequential fashion. Overflow traffic, which is meant to be routed to a later trunk group, is put in the non-allowable traffic and transferred from the non-allowable traffic to the allowable traffic when it reaches the trunk group to which it has been routed. Since the distribution of the overflow traffic among all the branches routed. Since the distribution of the overflow traffic among all the branches is known, only the total non-allowable traffic needs to be a state variable.

At each stage, the allowable traffic consists of three components: the traffic first offered to this group; the overflow from the allowable traffic of the previous stage if it is allowable at the present stage; and the portion of the non-allowable traffic of the other previous stages that becomes allowable for the present stage.

The non-allowable traffic of the present stage is the portion of the overflow traffic that is non-allowable for that stage. At the last stage, DDD, there is no non-allowable traffic. Cost-Function Table

A two-dimensional cost-function table is developed for each trunk group, starting with the next to last group and proceeding toward the first group. The two dimensions in the table represent the allowable and the non allowable traffic levels. These ranges are determined by the extreme cases under the given first-offered traffic to the system; the lower limit is the first-offered traffic at that stage. The range of values between the upper limit and the lower limit is divided into several intervals. Each table entry contains the optimum cost to carry the specified total traffic (allowable plus nonallowable).

For each cost-function table entry, the Erlang B formula is used to determine the overlfow traffic from the allowable traffic for different trunk sizes. The cost of the carried traffic is determined by the known cost structure of that group. The cost of the overflow traffic is taken from the cost-function table for the succeeding trunk group, which has already been developed. This may involve interpolation of values; a quadratic interpolation is recommended for keeping the overall accuracy at acceptable levels. The minimum total cost and its corresponding trunk size are entered in the new table (corresponding to the new stage).

The cost-function table of the first trunk group has only one entry, which corresponds to the group's first-offered traffic. The cost and the trunk size are optimum for the first group. The optimum trunk sizes of the succeeding groups are obtained by tracing, starting with the first group. The Erlang B formula is applied to the first table's allowable traffic and trunk sizxe; the cost for the carried traffic is calculated. Three factors determine from where in the table of the succeeding stage to select the trunk size for that sate: the amount of overflow traffic, the amount of non-allowable traffic and the first-offered traffic of the succeeding group. The cost of the carried traffic is again calculated. This is done for all subsequent trunk groups. The total cost for the system is the sum of all partial costs at all stages. Tracing Checks Accuracy

The tracing procedure determines the system's optimum trunking and the corresponding cost, which can be compared with the table cost of the first group. This provides a check on the accuracy of the interpolation. The table size (the number of intervals between the upper limit and the lower limit) can be varied until a stable, accurate solution is obtained.

* Step 2--The second step of this dynamic programming procedure varies the fraction f of Step 1. With each value of f, the cost is recalculated using the hourly traffic profile and the trunking configuration of step 1. The non-randomness of the overflow traffic is accounted for by the equivalent random theory (R.I. Wilkinson, "Theories for Toll Traffic Engineering in the USA," Bell System Technical Journal, Volume 35, Number 2, March 1956, pages 421 through 514). This theory takes advantage of the formulas for the mean and the variance of the overflow traffic when a random traffic of "a" Erlangs is offered to a trunk group of size c: Mean, m=aE(c,a) Variance, v=m(1-m+a/(c+m-a)) where m=the mean of the overflow traffic, a=the mean of the original random traffic; c=the trunk group size; E(c,a)=the probability of overflow using Erlang B formula; and v=the variance of the overflow traffic.

Steps 1 and 2 are carried out for different values off. The configuration with the lowest cost is used as the final result. How It Works

Figure 3 illustrates an example. The first group, MCI Network Services, is a branching point. The first-offered traffic is expressed in unit hours per month. A typical month has 21 business days. All other parameters are given in Figure 4.

Entries are in cost-per-hour for each group at the left of the table. Suppose Group 1 (MCI) has four trunks and carries a total of 100 hours of traffic in a month. Then, on the average, each trunk carries 25 hours. The cost for each trunk is: $85 + 15($16.33) + 10($14.52) = $475.15. The total cost for Group 1 is: 4($475.15)=$1,900.60.

As far as the total cost of the group is concerned, it does not matter how the total traffic is carried among all trunks in the group. Using a computer program developed at Northern Telecom, for f=.125, the results shown in Figure 5 are obtained in Step 1.

The table cost differs from the traced exact cost by 0.06 percent. So a table of size 10 times 10 is accurate enough, at least for this problem.

When there are only two trunk groups (for example, WATS 5 and DDD), the optimization is simple--vary the number of trunks for the WATS 5 group, calculate the total cost for each configuration and pick the best one. The dynamic programming method becomes useful when theer are more than two trunk groups. Reoptimizing gets more complicated when more and more groups are added, and the dynamic programming approach outlined here is one way to handle the added trunk groups properly. Using Another Formula

If the Erlang B overflow formula is replaced by some other suitable queuing formula, the dynamic programming method can be applied to a trunking design with queing. The two steps formulated earlier stay the same.

The above cost-reduction scheme does not produce the absolute lowest cost because the dynamic programming approach is applied only in a limited sense. To apply dynamic programming in the most general case and let the absolute minimum cost, the hourly traffic profile and the non-randomness of the overflow traffic must be taken into account when the cost-function tables are built.

to include the hourly traffic profile, the number of state variables has to be increased tremendously. Two state variables are needed for each hour, one for the allowable and one for the non allowable traffic levels, because the hourly traffic distribution determines how much traffic is carried by each group. For example, under the busy hour approach, there will be a higher level of overflow than when the traffic is assumed to be evenly distributed over all business hours; that is, "average-hour" approach. The total cost of the latter will be less since trunk groups are arranged in cost-ascending order.

From stage to stage, the hourly traffic profile is changed because different fractions of the traffic are carried for each hour. The higher the traffic in an hour, the lower the fraction that is carried. As a result, to keep the total cost accurate, one must have additional state variables. If we have only eight business hours in a day, the number of state variables increases from two to 16. This increase renders the dynamic programming approach impossible for use with present-day computers, due to both storage and computing time limitations.

Since the parameter f is varied in Step 2, the effect of the hourly traffic distribution is actually accounted for in a satisfactory fashion. This can be demonstrated in a comparison of total overflow traffic calculation for one trunk group using different approximation methods (Figure 6). Assume that there are 20 business ays in a month and nine business hours in a day. The hourly traffic distribution is shown in the table.

The monthly overflow traffic using different methods is given in Figure 7.

It can be seen that if a busy hour is used to calculate the overflow traffic, the percentage error can be as high as 7.8 percent and it always overestimates the amount of overflow traffic. If an average hour is used, it always underestimates the overflow traffic and the maximum error is minus 2.5 percent. If an f=0.118 is used, the relative error is kept to less than one percent. Since f is always varied and the best one chosen in Step 2, the error in overflow traffic calculation by using a representative hour can be expected to be less than one percent, which is accurate enough for our purposes. Worth Investigating

Developing further use of dynamic programming for optimizing single-node systems, including the non randomness of the overflow traffic in Step 1 of this approach, is not inconceivable since it only adds one additional state variable--peakedness. This means, however that a three-dimensional interpolation is needed for each table. A three-dimensional interpolation is usually less accurate than a two-dimensional interpolation. As a result, larger tables are needed to increase accuracy. The inclusion of peakedness in the dynamic programming approach appears to be a worthwhile topic for future investigation.

The required CPU time varies linearly with the number of trunk groups. The example cited earlier, with seven trunk groups, requires 14 CPU seconds on an IBM 4341.

Printer friendly Cite/link Email Feedback | |

Author: | Chang, C. |
---|---|

Publication: | Communications News |

Date: | Aug 1, 1984 |

Words: | 2391 |

Previous Article: | Designing an Effective RFP for Microwave Bypass System. |

Next Article: | Europe Pushes ISDN to Achieve Parity with the United States. |

Topics: |