A Study of Aggregation Techniques Applications To Communication Networks Honsing Cheng May 1995 1. Introduction Aggregation, in general, is the replacement of some part of a system by a simpler part, which has external behavior like the replaced part to certain extent. This is a central idea in engineering where the technique of a top-down approach carries the essence of aggregation -- the details of some part of the system is hidden (or aggregated) into a black box and as long as the black box demonstrates the same external behavior, we can ignore whatever details is in the black box. From the point of view of stochastic optimization, aggregation can be used to help evaluate the performance of a system. Instead of running simulation of the original, potentially complicated system, we can run simulation of the aggregated, simpler equivalent system. Depending on the specific aggregation technique we choose, the performance statistics obtained from the aggregated system corresponds more or less to the statistics from the original system. This is where the concept of ordinal optimization can be used to evaluate how "good" a paritcular aggregation technique is in terms of how well it preserve the ranking of designs. We will look closer at this subject in later section. We focus our application of the various techniques and analysis on communication networks. As communication network development has been exploding in the past 10 or 20 years, the task of modeling the internet becomes extremely laborsome. We will focus on how communication networks violate assumptions of certain queueing theory models. In this paper, we will first examine briefly a model used by Kleinrock (1965) that was one of the earliest efforts to analyze communication networks using queueing model. Then, we look at the Equivalent Server technique for aggregation, which predominates the literature in this area. We examine difficulties in applying this technique multiple times to aggregating large networks, and propose solutions that ensure its applicability. An example is then given to demonstrate such solutions. Afterwards, we investigate the role of ordinal optimization in this area using different perspectives. 2. Kleinrock's Model of Communication Networks (1965) Kleinrock's model is one of the earliest efforts in modeling communication networks using queueing theory. Basically, it looks a lot like an open queueing network. However, it captures enough of the specifics of communication networks that it violates some assumptions of standard open queueing theory. Nevertheless, the model is developed ignoring the violations, and yet it still yields accurate predictions. A channel in the real network corresponds is represented by a queue. So, message waiting to use a particular channel is appended to the queue of that channel until the message ahead of it in the queue is processed. Note that a node (host or router) in the network is represented only as the junctions between queues. Although in real life, a node has a queue of incoming messages and channels are passive transmission medium that has no queues. However, in this model, we can think of the following: as soon as a node receives a message, it appends it to the queue of the edge which the message should traverse next. See . 2.1 Assumptions The following assumptions are made by the model. a) The only delay a message experience in the network comes from channel delay, i.e. the time it waits to use a channel, and also the transmission time through a channel. Nodes might perform fuunctions on the messages, but they are assumed to be of zero processing time. b) Channels are assumed to be perfectly reliable. Therefore, no data is corrupted due to transmission. As a result, complications like retransmission or acknowledgement schemes are avoided, making analytical solutions possible. c) The quesus at all channels have infinite buffer size. Otherwise, messages may get lost due to buffer overflow and messages retransmission schemes are needed. d) Routing procedures are fixed. This means all messages originating from node i to node j have to go through the same path. (A path consists of a sequence of edges.) Therefore, efficient adaptive routing procedures are not allowed. 2.2 The Model Messages enter the network at each node as a Poisson process with a node-dependent rate. Packet size follows an exponential distribution and this will determine the time it takes to traverse an edge. Since we model an edge as a server, this is just the service time the message experiences. We can compare this model with Jackson's network, which has a product-form steady-state solution. First, we realize the source of service time randomness in Jackson's network comes from the servers. However, in this model, service time at a particular channel varies because the messages it processes have different lengths. Second, in Jackson's network, the service time a message experiences at different servers (channels) are independent random variables. However, in this model, they are correlated since each of them depends on the message size which is constant for each message. 2.3 Analysis of Delay and Optimization Problem Definitions Despite the differences mentioned above, Kleinrock continued the analysis as if it was for a Jackson's network. The performance measure of concern is the average time delay a message experiences. Time delay is the time elapsed between origination of a message and its arrival at its destination. A preliminary analysis yields the following: This is already an interesting result in that we can predict the bottlemeck behavior of the network. See . Everything else fixed, if we increase throughput upto a certain threshold value, average time delay does not increase much. At the threshold throughput, one term in the above summation dominates and average time delay shoots up. Now, we got a feeling of how to model communication networks using queueing networks. Kleinrock had also used this model to solve some optimization problems. Since we are only interested in "how to model," only problem definitions are included. See . 3. The Equivalent Server Technique for Aggregation Chandy, Herzog, and Woo (1975) had discovered a version of Norton's theorem for queueing networks. It enables us to replace an arbitrary portion of a network with a load-dependent server (LDS). A load-dependent server is a server with service rate dependent on the number of customers waiting in its queue and in its service. 3.1 The Procedure Suppose we want to study what is the effect on performance if we change the value of some parameters of a device in the network. The device can be a single server or a group of servers and is referred to as the "designated subnetwork." Then, we want to aggregate the rest of the network into one server which has the same external behavior (the aggregate subnetwork). Note that we assume there is only one edge joining each end of the designated network to the aggregate network. See . To find the service rate of the load-dependent server that we will use to replace the aggregate network, we need to find the throughput of the network with device i shorted and with 1, 2, ..., N customers. See . Throughput of this shorted network is equal to the rate of customers leaving/entering the aggregate network. Finally, we can put device i back in and replace the aggregate network with a load-dependent server whose service rates are found in the previous step. See . Now, we can vary some parameters of device i and see what effect it has on some performance measure. With the aggregation, we have hidden the unconcerned details of the network in a single server. 3.2 Applicability Chandy, Herzog, and Woo has proven that for a certain kind of networks, namely the BCMP networks, the queue length distribution at the designated network (device i) is exactly the same as in the original network. Also, this is proven true for both open and closed networks. In order for networks to be BCMP, there are restrictions on the service discipline, job class change time, the arrival process, and service time dependence. In spite of these many restrictions, the BCMP networks cover a large set of interesting queueing networks. However, the BCMP restriction that service time only depends on queue length is not satisfied under the model of communication networks we defined above. Specifically, the service time in the above model is independent of queue length; it is a function of the message length. One important question to pursue then, is how "well" does the equivalent server technique apply to non-BCMP networks, like the communication networks. This can be generalized to a question of how do we evaluate arbitrary aggregation technique. This subject is handled in section 5 where ordinal optimization analysis is used. The next section focuses on difficulties we might encounter when applying the equivalent server technique to large communication networks. 4. Multiple Aggregations on the Same Network Though the communication network is not exactly BCMP, as pointed out above, from here on, we assume it did. Therefore, we can apply the equivalent server technique to it. However, if we apply to only one part of the network, we are restricted to studying the performance impact by entities within the designated subnetwork. The resultant network after the aggregation is what we will call a partially aggregated network (PAN) -- partial in the sense that some entities in the resultant network also exist in the original network. PAN's allow for study of some specified designated subnetwork, but unless a different PAN is generated, our scope of study is confined within the designated network that has given rise to the PAN at hand. Suppose now we want to study some aspects of the network that are more overall, that is different parts of the network need to be considered simultaneously. Individual PAN's cannot suffice because aggregating one part of the network but not the other means that, due to the aggregation, some part loses information while the other does not. In other words, the network is not uniformly aggregated. Evaluating global characteristics on a PAN therefore seems inappropriate. How do we carry out uniform aggregation? We propose the following procedure. First, convert all undirected edges in the graph into directed ones. The direction of an edge will be important in a later step. Second, the original network is divided into N groups. Each of these groups will be replaced by a load-dependent server. Third, for each group i, apply equivalent server technique to obtain its load-dependent server equivalent LDSi. That is, group i is the aggregate subnetwork, and the remainder is the designated. After all groups calculate their equivalent LDS, we have N LDS's. See . However, we are not finished yet because the result should be a single queueing networks, not simply a set of disjoint queues. 4.1 Problem 1: Multiple Inter-subnetwork Edges If we look at how to aggregate a group more closely, one problem may arise as is shown in . In , there are multiple edges going between each end of the designated network and the aggregate network. However, the equivalent server technique works only when there is exactly one edge between each end of the designated network and the aggregate network. To solve this problem, we propose adding one pair of nodes to each of the subnetworks and change the network as follows. If node i has an edge going out of the subnetwork containing it, construct an edge of twice capacity going from node i to the new output node. On the other hand, if node i has an edge coming from outside the subnetwork containing it, construct an edge from the new input node to node i with twice the capacity. Now we can remove all inter-subnetwork edges. Finally, add in edges with infinite capacity from the output node of a subnetwork to the input of the other. See . Now have a setup ready for equivalent server technique. We argue such construction has not done anything other than making sure there exist only two edges between the two subnetworks. Consider where a message is going from node i to j. Through the new path, the message has to suffer a delay of (b/2C) + (b/infinity) + (b/2C) = b/C which is just the delay in the original path. Therefore, as long as we modify the routing procedure specification to realize these new paths, the behavior is preserved completely. 4.2 Problem 2: Connectivity of Resultant Network After aggregating each of the N groups with respect to the rest of the network, we get N load-dependent servers, each having an input end and an output end. In order to preserve inter-group connectivity in the resultant network, we propose the following. In the new network, there exists an edge going from output of LDS i to input of LDS j if and only if there exists an edge in the original network going from a node in group i to some node in group j. We also make sure there is at most one edge between any pair of LDS's. The assignment of capacity of the inter-LDS edges depends on what aspect of the resultant network do we concern more. For example, if we want to optimize with respect to capacity assignments of inter-LDS's, then we just set the capacity assignment to that one we want to evaluate. On the other hand, we recognize the inter-LDS's serve mainly to preserve connectivity. Then we can assign all of them with infinite capacity, so inter-LDS delay becomes zero. This is reasonable approximation when the size of the groups before aggregation is large, accounting for a major part of message delay. However, whatever assignment we choose, the connectivity among the LDS's is now well-defined in the resultant network. 4.3 Example An example of the above construction is provided in . In this example, we have four groups to be aggregated. As we can perceive from the example, the larger each of the groups we are aggregating, the more the complexity of the network is cut. By construction, for an original network with N groups, number of nodes in the resultant network will be N and the maximum number of edges will be C(N,2). Keeping N fixed, cutting in complexity would be dramatic is each of the N groups is large initially. 5. The Role of Ordinal Optimization Aggregation almost by definition results in a simpler system which carries less information or fewer details than the original system. Therefore it is really a form of approximation -- approximation of complicated systems by simpler ones. Let's say we have a set of parameter values (a set of designs) which corresponds to a set of presumably true performance values obtained from long simulation of the complicated system. See . Then aggregation gives us a simpler system from which performance statistics can be obtained faster due to the simpler aggregated system. But since some information is lost due to the aggregation, this set of performance values therefore contains noise. The distribution of the noise term depends on the particular technique used and can be determined experimentally. From the point of view of stochastic optimization, aggregation provides an effieient algorithm for finding "good enough" solutions with 100% confidence. As shown in , we can run some preliminary simulations on the simple system obtained from aggregation and find the best design J*. This best observed design is then passed into a long simulation from which we find the true performance J of the observed best design, where J* = J + noise. If J is good enough, then we are finished. Otherwise, simulations of the simple system can be run again to find another J* or J* can be the second best in the last set of runs. Thus, aggregation provides a quick way to pick highly qualified designs. From the point of view of an aggregation technique designer, an important evaluation metric is the alignment probability. If S is the selected set derived from the simulation of an aggregated system, and if G is the "good enough" set, then P = P[ |S intersect G| = k ] can be used for technique evaluation. A high value of P means the technique in question must have preserved most of the critical information needed for the particular performance metric we are using. Another way to evaluate aggregation techniques is the rank stabilization speed, i.e. how long does it take for the best design to stabilize its position in the first rank. Given limited time for simulation, the technique that stabilizes faster should be of choice since we always want the ranking to have stabilized at the end of the simulation. See . 6. Conclusion The use of aggregation technique in helping analysis of large communication networks has become more important than before due to the explosion of expansion of the internet and use of local area networks. If we wnat to analyze some more global aspects of the internet instead of focusing on one or a few particular components, we can apply some uniform aggregation technique to obtain a reasonable but much simpler network for the analysis. Aggregation is a form of approximation and a better technique should be one that preserve more information from the original system. We have seen how the communication networks violate the BCMP assumptions. However, it would still be interesting to apply the equivalent server technique to them and evaluate how "good" a technique it is for cases where some of its assumptions are not satisfied. Unfortunately, we do not have time to go into that in this project.