A. Performance Guarantees in Communication Networks
[A1] Cheng-Shang Chang, Performance Guarantees in Communication Networks, Springer-Verlag, 2000.
This research monograph is the essence of Prof. Chang's work for the last fifteen years. He worked with many talented researchers in the field to develop two theories for providing performance guarantees in communication networks: (i) the theory of effective bandwidth for stochastic guarantees and (ii) the filtering theory for deterministic guarantees (also known as the network calculus). The theory of effective bandwidth is built upon the mathematical theory of the large deviation principle. It provides a rough estimate for the minimum bandwidth required to meet the buffer overflow probability. The filtering theory is an algebraic theory under the min-plus algebra. It provides building blocks needed for the deterministic worst case analysis in networks. Papers written in this area turn out to be the most cited papers of Prof. Chang's. This monograph was also used by Prof. Bruce Hajek at UIUC and Prof. Ravi Mazumdar at Purdue University for graduate level courses.
[A2] Cheng-Shang Chang, ``Stability, queue length and delay of deterministic and stochastic queueing networks,'' IEEE Transactions on Automatic Control, Vol. 39, pp. 913-931, 1994.
This is the first paper that developed the general framework of the theory of effective bandwidth. This paper has been cited 126 times according to the SCI database.
[A3] George Kesidis, Jean Walrand and Cheng-Shang Chang, ``Effective bandwidths for multiclass Markov fluids and other ATM sources,'' IEEE/ACM Transactions on Networking, Vol. 1, pp. 424-428, 1993. (Team work).
Effective bandwidths for various Markov fluids were found via the large deviation principle. This paper has also been cited 142 times.
[A4] Cheng-Shang Chang, Philip Heidelberger, Sandeep Juneja and Perwez Shahabuddin, ``Effective bandwidth and fast simulation of ATM intree networks,'' Performance Evaluation, Vol. 20, pp. 45-66, 1994. (Team work).
A fast simulation method was developed using the theory of effective bandwidth. This paper has been cited 32 times.
[A5] Cheng-Shang Chang, ``Sample path large deviations and intree networks,'' Queueing Systems, Vol. 20, pp. 7-36, 1995.
The theory of effective bandwidth was extended to intree networks in this paper. This paper has been cited 24 times.
[A6] Cheng-Shang Chang and Joy A. Thomas, ``Effective bandwidth in high speed digital networks,'' IEEE Journal on Selected Areas in Communications, Vol. 13, pp. 1091-1100, 1995. (Principal author).
Physical insights of the theory of effective bandwidth and their connections to statistical mechanics were given in this paper. This paper has been cited 41 times.
[A7] Cheng-Shang Chang, Jin-Fu Chang, Kwang-Cheng Chen and Ming-Young You, ``Guaranteed quality-of-service wireless access to ATM networks,'' IEEE Journal on Selected Areas in Communications, Vol. 15, pp. 106-118, 1997. (Principal author).
A priority based polling scheme was proposed for providing deterministic quality-of-service in wireless ATM networks. This paper has been cited 33 times.
[A8] Cheng-Shang Chang, ``On deterministic traffic regulation and service guarantees: a systematic approach by filtering,'' IEEE Transactions on Information Theory, Vol. 44, pp. 1097-1110, 1998.
This is the first paper that uses the min-plus filtering theory for deterministic traffic regulation and service guarantees. This paper has been cited 26 times.
[A9] Cheng-Shang Chang, ``Matrix extensions of the filtering theory for deterministic traffic regulation and service guarantees,'' IEEE Journal on Selected Areas in Communications, Vol. 16, pp. 708-718, 1998.
The min-plus filtering theory was extended to the networks with multiple inputs and multiple outputs in this paper.
[A10] Cheng-Shang Chang, David D. Yao and Tim Zajic, ``Large deviations, moderate deviations, and queues with long range dependent input,'' Advances in Applied Probability, Vol. 31, pp. 254-278, 1999. (Team work).
The theory of effective bandwidth was extended to queues with long range dependent inputs. It is first shown that queues with long range dependent inputs build up via nonlinear paths.
[A11] Cheng-Shang Chang and Yih Haur Lin, ``A general framework for deterministic service guarantees in telecommunication networks with variable length packets,'' IEEE Transactions on Automatic Control, Vol. 46, pp. 210-221, 2001. (Principal author).
The filtering theory was extended to networks with variable length packets in this paper. This is done by using the max-plus algebra instead of the min-plus algebra.
[A12] Zhi-Ren Chang, I-Chung Lee, Cheng-Shang Chang, Chien-Hsin Li and Ben-Li Sui, ``A novel scheme using the information of departure processes for delay guarantees of distributed VBR traffic,'' IEEE/ACM Transactions on Networking, Vol. 9, pp. 452-463, 2001. (Subsidary author and leader of group).
This is an improved scheme for providing deterministic quality-of-service in wireless ATM networks. This is done by collecting information of the departure processes at the base station.
[A13] Cheng-Shang Chang, Rene Cruz, Jean-Yves Le Boudec, Patrick Thiran, ``A Min-Plus System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees,'' IEEE/ACM Transactions on Networking, Vol.10, pp. 805-817, 2002. (Team work).
The filtering theory was extended to networks with time varing constraints.
[A14] Cheng-Shang Chang and Zhen Liu, ``A bandwidth sharing theory for a large number of HTTP-like connections,'' IEEE/ACM Transactions on Networking, Vol. 12, pp. 952-962, 2004. (Principal author).
Bandwidth sharing at the TCP level is known to be a distributed optimization problem. Via the large deviation principle, it was shown that bandwidth sharing at the HTTP level is also a distributed optimization problem.
[A15] Chung Lee, Cheng-Shang Chang, and Ching-Ming Lien, ``On the throughput of multicasting with incremental forward error correction,'' IEEE Transactions on Information Theory, Vol. 51, No. 3, pp. 900-918, 2005. (Subsidary author and leader of group).
Via the large deviation principle, it was shown that there exist several strong laws of large numbers for various multicasting problems with incremental forward error correction.
B. High speed switching:
Prof. Chang and his colleagues developed switch architectures and the associate theories that could scale with the speed of fiber optics. Their architecture was used by the research team led by Prof. Nick McKeown at Stanford University to design a 100 terabits/sec optical router. As commented by Prof. J. Chao (an IEEE fellow and the co-author of the book, “Broadband Packet Switching Technologies”), their load-balanced Birkhoff-von Neumann switch architecture opened a new avenue for research in the area of high speed switching. Their works in this area have received a great deal of attentions. In particular, in the two most prestigious journals in the area of networking (IEEE/ACM Transactions on Networking and IEEE Journals on Selected Areas in Communications), half of the papers published in 2003 on electronic packet switches cited their works (4 in 8 for ToN and 5 in 10 for JSAC). In IEEE INFOCOM 2003 (the most prestigious conference in the area of networking), near half of the papers in the area of switching cited their works. In academic research, they influenced almost 50% of the top papers in the area of electronic packet switches in 2003. Their switch architectures were also taught in regular classes by several universities, including Stanford University, University of Texas, Austin, and Hong Kong University of Science and Technology. To award their outstanding breakthrough in high speed switching, NSC granted them the PPAEU-II project for the total amount of NT 35,000,000 in 2004-2008. For teaching, Prof. Chang and Prof. Duan-Shin Lee have completed the first draft of their book on ``Principles, Architectures, and Mathematical Theories of High Performance Packet Switches.’’ The book is a summary of their works and is currently used as a lecture note in a senior/graduate level course at the National Tsing Hua University.
[B1] Cheng-Shang Chang, Wen-Jyh Chen and Hsiang-Yi Huang, "Birkhoff-von Neumann input buffered crossbar switches for Guaranteed-Rate Services," IEEE Transactions on Communications, Vol. 49, pp. 1145-1147, July 2001. Conference version in IEEE INFOCOM 2000. (R.O.C. patent 145758, U.S. patent 6704312). (Principal author and leader of group).
Researchers were once puzzled by whether 100% throughput could be achieved by using input-buffered switches. In this paper, it was shown that 100% throughput can be easily achieved by using the Birkhoff-von Neumann decomposition for doubly stochastic matrices in 1946. Furthermore, it was shown that the Inukai algorithm published in IEEE Transactions on Communications in 1979 is a special case of the Birkhoff-von Neumann decomposition.
[B2] Cheng-Shang Chang, Duan-Shin Lee and Yi-Shean Jou, "Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering," Computer Communications, Vol. 25, pp. 611-622, 2002. (Principal author and leader of group).
The problem of the Birkhoff-von Neumann switch is the complexity of carrying out the Birkhoff-von Neumann decomposition. By adding a load-balancing switch in front of the Birkhoff-von Neumann switch, the complexity of the load balanced Birkhoff-von Neumann switch was greatly reduced to O(1).
[B3] Cheng-Shang Chang, Duan-Shin Lee and Ching-Ming Lien, "Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering," Computer Communications, Vol. 25, pp. 623-634, 2002. (Principal author and leader of group).
This is a refinement of [B2]. It not only corrected the resequencing problem in [B2] but also provided a deterministic delay bound when comparing with an ideal output-buffered switch. An R.O.C. patent and a mainland patent were filed jointly with Accton, a well-known networking company in Taiwan.
[B4] Cheng-Shang Chang, Duan-Shin Lee and Chi-Yao Yue, "Providing Guaranteed Rate Services in the load balanced Birkhoff-von Neumann switches," Proceedings of IEEE INFOCOM, 2003. (Team work and leader of group).
This is an extension of [B3]. It was shown that guaranteed rate services can also be provided in the load balanced Birkhoff-von Neumann switches.
[B5] Cheng-Shang Chang, Duan-Shin Lee, and Ying-Ju Shih , "Mailbox switch: a scalable two-stage switch architecture for conflict resolution of ordered packets, Proceedings of IEEE INFOCOM 2004. (Team work and leader of group).
Mailbox switches are a special class of the load balanced Birkhoff-von Neumann switches that have feedback paths from inputs to outputs. Feedbacks can then be used to keep packets in sequence.
[B6] Cheng-Shang Chang, Duan-Shin Lee, and Chao-Lin Yu, "Generalization of the Pollaczek-Khinchin formula for throughput analysis of input-buffered switches," to be presented in IEEE INFOCOM 2005. (Team work and leader of group)
The Pollaczek-Khinchin formula for M/G/1 queues is one of the most important formulas in queueing. As the formula has a closed-form expression, it is easy to compute and thus has a lot of applications. In this paper, it was shown that the Pollaczek-Khinchin formula can be extended to a much more general setting. As such, the throughputs of various input-buffered switches can be computed.
[B7] Isaac Keslassy, Cheng-Shang Chang, Nick McKeown, and Duan-Shin Lee, "Optimal load balancing," to be presented in IEEE INFOCOM 2005. (Subsidary author).
Load balancing is formulated as an optimization problem. It was shown that the load balanced Birkhoff-von Neumann switches are asymptotically optimal.
C. Optical queues:
For optical packet switching, one has to build optical queues that store optical packets. The only known way to store optical packets without converting them into other media is to direct optical packets via a set of Switches and fiber Delay Lines (SDL) so that the optical packets come out at the right place and at the right time. Due to the huge state space for the control of the switches in SDL elements, constructing optical queues via switched delay lines was once regarded as a notorious combinatoric problem. Recently, Prof. Chang and his team at the National Tsing Hua University were able to solve various construction problems by using queueing theory and switching theory.
[C1] Cheng-Shang Chang, Duan-Shin Lee and Chao-Kai Tu, ``Recursive construction of optical multiplexers with switched delay lines,'' IEEE Transactions on Information Theory, Vol. 50, pp. 3221-3233, 2004. (Team work and leader of group).
This is the first paper that provides a systematic method of constructing optical multiplexiers.
[C2] Cheng-Shang Chang, Duan-Shin Lee and Chao-Kai Tu, "Using switched delay lines for exact emulation of FIFO multiplexers with variable length bursts," conditionally accepted by IEEE Journal on Selected Areas in Communications. Conference version in Proceedings of IEEE INFOCOM, 2003. (Team work and leader of group).
The construction in [C1] was extended to the case with variable length bursts.
[C3] Cheng-Shang Chang, Yi.-Ting Chen and Duan-Shin Lee, ``Construction of optical FIFO queues and non-overtaking delay lines,'' submitted. (Principle author and leader of group).
Develop a three-stage construction of optical FIFO queues. Show that the classical switching theory can be used for constructing non-overtaking delay lines.
[C4] Cheng-Shang Chang, Yi.-Ting Chen and Duan-Shin Lee, ``Multistage constructions of linear compressors, non-overtaking Delay Lines, and flexible Delay Lines,'' first draft. (Principle author and leader of group).
Show that the theory of multistage interconnection networks, including Clos networks, Cantor networks, and Banyan networks, can be used for constructing various optical queues.
D. Stochastic majorization and its applications in parallel processing systems:
[D1] Cheng-Shang Chang, ``A new ordering for stochastic majorization: theory and applications,'' Advances in Applied Probability, Vol. 24, pp. 604-634, 1992.
In this paper, Prof. Chang developed a new stochastic majorization ordering and its associated rearrangement inequalities that can be used as a unifying framework for various scheduling problems in the literature. This paper was awarded an IBM Outstanding Innovation Award in 1992.
[D2] Cheng-Shang Chang, XiuLi Chao, Michael Pinedo and J. George Shanthikumar, ``Stochastic convexity for multidimensional processes and its applications,'' IEEE Transactions on Automatic Control, Vol. 36, pp. 1347-1355, 1991. (Principal author).
A new notion of stochastic convexity was developed in this paper. It was then used to prove that correlated inputs result in poor performance in various queueing systems.
[D3] Cheng-Shang Chang and David D. Yao, ``Rearrangement, majorization and stochastic scheduling,'' Mathematics of Operations Research, Vol. 18, pp. 658-684, 1993. (Team work).
New rearrangement inequalities were derived based on the new stochastic majorization ordering in [D1]. These inequalities were then used to unify various stochastic scheduling results in the literature.
[D4] Cheng-Shang Chang and Randolph D. Nelson, ``Bounds on the speedup and efficiency of partial synchronization in parallel processing systems,'' Journal of the Association for Computing Machinery (JACM), Vol. 42, pp. 204-231, 1995. (Principal author).
Random task graphs were used to model job execution in parallel processing systems. It was shown that non-zero throughput can be achieved as long as the parallel system has limited (partial) synchronization. Majorization ordering was used to compare the throughputs of different random task graphs.
E. list of coauthors ( excluding Prof. Chang’s students):
Jin-Fu Chang (National Chi-Nan University)
Chi-Chao Chao (National Tsing Hua University)
Xiuli Chao (North Carolina State University)
Kwang-Cheng Chen (National Taiwan University)
Rene Cruz (University of California, San Diego)
Philip Heidelberger (IBM)
Arie Hordijk (Universiteit Leiden)
Sandeep Juneja (I.I.T.)
George Kesidis (University of Waterloo)
Isaac Keslassy (Technion)
Jean-Yves Le Boudec (E.P.F.L.)
Duan-Shin Lee (National Tsing Hua University)
Zhen Liu (IBM)
Nick McKeown (Stanford University)
Randolph Nelson (OTA)
Michael Pinedo (NYU)
Rhonda Righter (Santa Clara University)
Perwez Shahabuddin (Columbia University)
J. George Shanthikumar (University of California, Berkeley)
Patrick Thiran (E.P.F.L.)
Joy Thomas (Calpurnia.com)
Jean Walrand (University of California, Berkeley)
Richard Weber (University of Cambridge)
Gideon Weiss (Technion)
David Yao (Columbia University)
Tim Zajic (University of Minnesota).
|
