Review of Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks by Lixia ZhangGeneralAnalytical ResultsSimulation and Experimentation ResultsSummaryPage 1Review of Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks by Lixia ZhangGeneralThis paper describes an adaptive algorithm for traffic flow through a network switch. The author shows that a network switch using the algorithm can obtain the efficiency of a statistical multiplexer coupled with the robustness of a Time-Division Multiplexed (TDM) device. A given data channel or flow can obtain approximately 96% of its expected maximumbandwidth with the algorithm. The algorithm typically does not drop data packets from well-behaved flows, but can drop them from “misbehaving” flows (i.e., those who have exceeded their maximum bandwidth) without adversely affecting those that are well-behaved. A simulation of the algorithm is described, with fixed packet sizes generated via various schemes on a test network.I found Virtual Clock, the key definition of the paper, to be a rather strange name for the algorithm. It would seem to imply a clock that was not physically present, but actually the algorithm requires a real-time clock (presumably in hardware) for operation. I think a namelike adaptive packet sequencer would have made more intuitive sense. The other definitions and terms in the paper seemed to be more obvious, however.There were a few small typographical errors and English mistakes. None were so serious that they confused the presentation. The most serious problem is in Figure 1, where the count numbers are not aligned properly with the packet “pulses” that correspond to them.The principal claim of the author is that the Virtual Clock algorithm combines the efficiency of a statistical multiplexer with the data integrity of Time-Domain Multiplexing (TDM). Theauthor support these claims well, but only for certain types of data. The algorithm seems to work well if the input data is of fixed packet size, not “bursty”, with an upper limit of priorityand other resource requirements. In cases where these requirements do not always hold, thealgorithm may not work so well.The limitation on fixed packet sizes may not be too serious for real-world ATM networks and the like, but some of the other assumptions may be more restrictive. From the article, it appears that “bursty” data (that is, data which is not sent at rates acceptable to the algorithm) can cause the it to become unstable in certain circumstances. The author addresses this, and imposes a restriction on the source that it conform to a certain “User-Behavior Envelope” (UBE) to avoid problems. This may be unrealistic for many real-world applications.CS 740 Steve SchultheisSpring 1995 [email protected] 1 29 January, 1995Page 2The author gives some good examples showing how various data flows can have differing priorities in the network without interacting with each other. He even gives a scheme whereby the priority of a flow can be modified while running to lower (but not raise) its priority. In particular, he points out that flows with differing priorities and even pathological behavior do not affect others with his algorithm.I found the paper to be moderately interesting and well written, although not terribly significant. The proposed adaptive algorithm seems like a fairly obvious concept to me. The information is based on the author’s Ph.D. thesis work (which he references), but he doesn’t state what information in this article is new or different.Perhaps the best feature of the paper was the algorithm itself and discussion of some of the tradeoffs. In particular, the author explained some results which were not (to the author at least) intuitively obvious. One example of this is that there is no way to pick a threshold T that is guaranteed to be stable. The discussion of the simulation experiment were supportedby a concise but appropriate amount of numeric data. In particular, he generated his test data using several models (constant rate, Poisson, and packet train) to confirm that his results were independent of the input data scheme. He also compares some other well-known algorithms for network flow control, but does not specify under what conditions they may give better (or worse) performance than his own.The weakest aspect of the discussion was perhaps the rather strict data requirements for the algorithm to work effectively. This is a function of the algorithm, however, not the paper itself.Here are some additional ideas to explore that were presented in the paper: How can the Average Interval (AI) be adjusted dynamically when the source data rate requirements change? Can priority of flows be raised? (Currently, they can only be lowered). What are some proposed control methods for dealing with misbehaving, malicious, or simply defective data sources? Can maximum transmission delays be guaranteed for deterministic real-time performance? How can the switch avoid dropping packets when it gets congested? How can the AI value be dynamically tuned to optimize the network for deterministic operation versus efficiency?CS 740 Steve SchultheisSpring 1995 [email protected] 1 29 January, 1995Page 3Analytical ResultsMost of the proofs and formulas are stated in an acceptable manner, with two exceptions. First, the author does not include a complete explanation of the relationship between the Average Interval AI and the Threshold T. Instead, the author simply states that there is a need for a “user behavior envelope” that restricts the output of each flow to bounds that will not cause the algorithm to become unstable. We are referred to the author’s Ph.D. thesis, where presumably there is a better explanation of all this. If it was already stated in the thesis, surely it could be concisely summarized in this paper too.The author does not discuss this “user behavior envelope” in much detail, but instead refers to an appendix which is only four paragraphs. Presumably this is only one idea for a suitable UBE, but since it is so short I would have preferred to see it mentioned in the text at the point where it was discussed.Simulation and Experimentation ResultsThe simulation system is described reasonably well. There is probably enough information in the article to implement the virtual clock algorithm in software on some system. The author