Aurel A. Lazar

Aurel A. Lazar (IEEE Fellow'93) has been a professor of Electrical Engineering at Columbia University since 1988.

From 1981 to 2002 Professor Lazar's research interests were in communications networks. These (no longer maintained) pages provide information about some of his research activities and publications (mostly) from the 90s. A more complete list of publications is available on Google Scholar under AA Lazar.

Professor Lazar's current area of research is in silico and in vivo information representation and neural computation.

Industrial Experience

Chairman and CEO (1998-2001) of Xbind, Inc..

Academics

Department of Electrical Engineering

Columbia University

COMET

Department of Electrical Engineering

Columbia University

Department of Electrical Engineering

Columbia University

Courses Given

ELEN E6970 Resource Allocation and Networking Games (Spring 2002)
ELEN E9701 Scaling in Networks (Fall 2001)

Professional Activities

Awards

IEEE

IFIP/IEEE

Areas of Research

Shadowing and Cognitive Radio Networks

De Turck, Filip and Lazar, A.A., "Modeling Wireless Shadow Networks", Proceedings of the ACM MSWiM, Venice, Italy, October 4-6, 2004.

Networking Games

In the second half of the 90s my research focussed on networking games and pricing models. The first paper on pricing describing the Progressive Second Price (PSP) auction mechanism was published as Lazar, A.A. and Semret, N., "Auctions for Network Resource Sharing", CTR Technical Report CU/CTR/TR 468-97-02, Columbia University, 1997.

A PSP auction is a decentralized mechanism for allocating variable size shares of a resource among multiple users using a light signaling protocol. The PSP auction model for divisible resources was advanced in [1]. Under elastic demand, the PSP auction is incentive compatible and stable, in that it has a truthful epsilon-Nash equilibrium where all players bid at prices equal to their marginal valuation of the resource. PSP is efficient in that the equilibrium allocation maximizes total user value. In a dynamic setting, PSP auctions can also be employed by independent resource sellers on each element on a network with arbitrary topology.

Lazar, A.A. and Semret, N., "The PSP Auction Mechanism for Network Resource Sharing", 8th International Symposium on Dynamic Games and Applications, Maastricht, the Netherlands, July 5-8, 1998, pp. 359-365.
Semret, N., Liao, R., Campbell, A.T. and Lazar, A.A., "Market Pricing of Differentiated Internet Services", IEEE-IFIP IWQoS, June 2-4, 1999.
Semret, N., and Lazar, A. A., "Spot and Derivative Markets in Admission Control", 16th International Teletraffic Congress, Edinburgh, UK, June 7-11, 1999.
Lazar, A.A. and Semret, N., "The Design, Analysis and Simulation of the Progressive Second Price Auction Mechanism for Network Bandwidth Sharing", Telecommunications Systems, Special Issue on Network Economics, 2002, accepted for publication.
Semret, N, Liao, R., Campbell, A.T. and Lazar, A.A., "Pricing, Provisioning and Peering: Dynamic Markets for Differentiated Internet Services and Implications for Network Interconnections", IEEE Journal on Selected Areas in Communications, Vol. 18, Number 12, December 2000, pp. 2499-2513.

My research in the first half of the 90s dealt with architectural issues arising in non-cooperative networks. I coined the term "networking games" for the research area focusing on formal investigations of the throughput/time delay trade-off arising in multi-user non-cooperative networks. I also introduced the first stand alone course taught at a university on Research Allocation and Networking Games.

In noncooperative networks users make decisions that optimize their individual performance objectives. Nash equilibria characterize the operating points of such networks. Nash equilibria are inherently inefficient and exhibit suboptimal network performance. Driving Nash equilibria to a desired network operating point represents a shift of paradigm in networking games and is of outmost practical importance. In [2] it is demonstrated that a manager cognizant of the noncooperative behavior of network users can implement a routing strategy that drives the users to the best Nash equilibrium in terms of systems performance, architecting this way the flow configuration of the network. Formally, necessary and sufficient conditions are derived providing the manager with the capability for enforcing an equilibrium that coincides with the network optimum (the optimal solution of the routing problem when all of the flow in the network is centrally controlled). Thus, the manager is often able to obtain, through limited control, the same performance as in the case of centralized control.

Korilis, Y.A. and Lazar, A.A., "On the Existence of Equilibria for Noncooperative Flow Control", Journal of the Association for Computing Machinery, Vol. 42, No. 3, May 1995, pp. 584-613.
Korilis, Y. A., Lazar, A.A. and Orda, A., "Architecting Noncooperative Networks", Journal on Selected Areas in Communications, Volume 13, No. 7, September 1995, pp. 1241-1251.
Korilis, Y. A., Lazar, A.A. and Orda, A., "Achieving Network Optima Using Stackelberg Routing Games", IEEE Transactions on Networking, Vol. 5, No. 1, February 1997, pp. 161-173.
Korilis, Y. A., Lazar, A.A. and Orda, A., "Capacity Allocation under Non-Cooperative Routing", IEEE Transactions on Automatic Control, Vol. 42, No. 3, March 1997, pp.309-325.
Lazar, A.A., Orda, A. and Pendarakis, D.E., "Virtual Path Bandwidth Allocation in Multi-User Networks", IEEE Transactions on Networking, Vol. 5, No. 6, December 1997, pp. 861-871.

In 1981 I pioneered the application of formal methods of control theory to flow control in communication networks and formalized criteria quantifying the throughput/time delay trade-off in queueing systems. The first paper in a long series was: Lazar, A.A., "Optimal Control of a M/M/l Queue," Proceedings of the Nineteenth Annual Conference on Communications, Control and Computing, University of Illinois, Urbana, September 30 - October 2, 1981, pp. 279-289, later published as [1]. The first version of the key separation theorem between estimating the rate at which packets are served by the network and flow control is implicit in: Lazar, A.A., "Optimal Control of a Class of Queueing Networks", Proceedings of the Twentieth IEEE Conference on Decision and Control, San Diego, California, December 16-18, 1981, pp. 368-373, later published as [2]. The separation theorem for flow control and estimation is a structural result akin to the separation theorem between estimation and control for linear quadratic regulators, a pillar of modern control theory. The first formulation of the flow control problem as a non-cooperative game appears in Hsiao, M.-T. and Lazar, A.A., "Bottleneck Modeling and Decentralized Optimal Flow Control: II. Local Objectives", Proceedings of the Nineteenth Conference on Information Sciences and Systems, Johns Hopkins University, Baltimore, Maryland, March 27-29, 1985, pp. 558-563. The relationship between distributed computation and flow control was first established in [3]. Here are some further highlights.

Lazar, A.A., "The Throughput Time Delay Function of an M/M/1 Queue," IEEE Transactions on Information Theory, Vol. 29, pp. 914-918, November 1983.
Lazar, A.A., "Optimal Control of a Class of Queueing Networks in Equilibrium, " IEEE Transactions on Automatic Control, Vol. 28, No. 11, pp. 1001-1007, November 1983.
Bovopoulos, A.D. and Lazar, A.A., Decentralized Algorithms for Optimal Flow Control, Proceedings of the 25th Allerton Conference on Communication, Control and Computing, University of Illinois at Urbana, Urbana, IL, September 30-October 2, 1987, pp. 979-987.
Hsiao, M.-T.T. and Lazar, A.A., An Extension to Norton Equivalent, Queueing Systems: Theory and Applications, Vol. 5, 1989, pp. 401-411.
Hsiao, M.-T. T. and Lazar, A.A., "Optimal Decentralized Flow Control of Markovian Queueing Networks with Multiple Controllers,", Performance Evaluation, Vol. 13, No. 3, pp. 181-204, 1991.

Programmable Networks

Starting in the second half of 1993 I pioneered investigations into open programmable networks (I coined the name "open programmable networks", see [3]. The key ideas and the program for research was first published in: Lazar, A.A., "Challenges in Multimedia Networking", Proceedings of the International Hi-Tech Forum, Osaka'94, Osaka, Japan, February 24-25, 1994.) An open architecture must provide a set of functional programming interfaces (APIs) that abstract network resources such as switches, routers and communication links. A programmable architecture carries out the service specification and creation process via a distributed control plane.

The binding model [3] consists of a set of states (objects) and a set of binding algorithms operating on these. The objects explicitly incorporate a QOS resource model based on a set of abstractions that characterize the multiplexing capacity of networking resources under QOS requirements. Binding algorithms create services by interconnecting (binding) states of the open interfaces [4]. An example of a network service is a Virtual Private Network with QOS guarantees that is established in a shared networking environment. A formal description/ specification of the binding model is the binding architecture [4], [5]. It consists of an organized collection of interfaces, called the binding interface base (BIB), and a set of algorithms that run on top of these. BIB interfaces provide an open and uniform access to abstractions that model the local states of networking resources with QOS guarantees.

I led a group of students in the realization of the first open programmable networking environment called the xbind broadband kernel [3], [4], [5], [1]. The term kernel was deliberately used to draw a parallel between its role as a resource allocator and an extended machine, and the same roles played by a typical operating system. The first realization of the broadband kernel was deployed on a network across NY State in collaboration with NYNEX (today Verizon) and Rome Laboratory [5]. This work lead to the establishment of the IEEE P1520 standards group on Programmable Network Interfaces. See Biswas, J., Lazar, A.A., Huard, J.-F., Lim, K.S., Mahjoub, S., Pau, L.-F., Suzuki, M., Torstensson, S., Wang, W., Weinstein, S., The IEEE P1520 Standards Initiative for Programmable Network Interfaces, IEEE Communications Magazine, Vol. 36, No. 10, October 1998, pp. 64-70.

Chan, M.C. and Lazar, A.A., "Designing a CORBA-based High Performance Open Programmable Signalling System for ATM Switching Platforms", IEEE Journal on Selected Areas in Communications, Vol. 17, No. 9, September 1999, pp. 1537-1548.
Huard, J.-F., and Lazar, A.A., "A Programmable Transport Architecture with Quality of Service Guarantees", IEEE Communications Magazine, Vol. 36, No. 10, October 1998, pp. 54-62.
Lazar, A.A., "Programming Telecommunication Networks", IEEE Network, September/October 1997, pp. 8-18. This paper is a revised version of the keynote address given by the author at the International Workshop on Quality of Service, Columbia University, New York, May 21-23, 1997. Published in the workshop proceedings (pp. 3-23).
Lazar, A.A., Bhonsle, S. and Lim, K.S., "A Binding Architecture for Multimedia Networks", Journal of Parallel and Distributed Computing, Vol. 30, No. 2, November 1995, pp. 204-216.
Lazar, A.A., Lim, K.S and Marconcini, F., "Realizing a Foundation for Programmability of ATM Networks with the Binding Architecture", Journal of Selected Areas in Communications, Vol.14, No.7, September 1996, pp. 1214-1227.

Time Scales and Subexponentiality

In the mid 90s my research in broadband networking with quality of service guarantees was focussed on modeling video streams and analysing their multiplexing behavior, with emphasis on multiple time scales and subexponentiality. In [4] (what was later named) the reduced load (asymptotic) equivalence for intermediate regular varying distributions was first published.

Jelenkovic, P.R. and Lazar, A.A, "Subexponential Asymptotics of a Markov-Modulated Random Walk with Queueing Applications", Journal of Applied Probability, Vol. 35, No. 2, June 1998, pp. 325-347.
Jelenkovic, P.R. and Lazar, A.A., "Multiple Time Scales and Subexponential Asymptotic Behavior of a Network Multiplexer", invited paper, Stochastic Networks: Stability and Rare Events, Lecture Notes in Statistics #117, Editors: P. Glasserman, K. Sigman and D.D. Yao, Springer Verlag, 1996, pp. 215-235.
Jelenkovic, P.R., Lazar, A.A. and Semret, N., "The Effect of Multiple Time Scales and Subexponentiality of MPEG Video Streams on Queueing Behavior", IEEE Journal on Selected Areas in Communications, Vol. 15, No. 6, August 1997, pp. 1052-1071.
Jelenkovic, P.R. and Lazar, A.A., "Asymptotic Results for Multiplexing Subexponential On-Off Processes", Advances in Applied Probability, Vol. 31, No. 2, June 1999.
Lazar, A.A., Pacifici, G. and Pendarakis, D.E., "Modeling Video Sources for Real-Time Scheduling", ACM/Springer Verlag Multimedia Systems, Vol. 1, No. 5, 1994, pp. 253-266.

Architectures, Network Management and Control

My involvement with gigabit networking research in the early 90s lead to the first fully operational service management system on broadband networks. The system was implemented on top of AT&T's XUNET III gigabit platform spaning the continental US [1]. Furthermore, my management and control research pioneered the application of virtual reality to the management of broadband networks [3].

Aneroussis, N.G. and Lazar, A.A., "An Architecture for Managing Virtual Circuit and Virtual Path Services on ATM Networks", Journal of Network and Systems Management, Vol. 4, No. 4, December 1996, pp. 425-455.
Aneroussis, N.G. and Lazar, A.A., "Virtual Path Control for ATM Networks with Call Level Quality of Service Guarantees", IEEE Transactions on Networking, Vol. 6, No. 2, April 1998, pp. 222-236.
Crutcher, A.L. and Lazar, A.A., "Management and Control for Giant Gigabit Networks", IEEE Network, November 1993, pp. 62-71.
Chan, M.C., Lazar, A.A. and Stadler, R., "Costumer Management and Control of Broadband VPN Services", Fifth IFIP/IEEE International Symposium on Integrated Network Management, San Diego, CA, May 1997, pp. 301-314.
Mazumdar, S. and Lazar, A.A., "Objective-Driven Monitoring," IEEE Transactions on Data and Knowledge Engineering, Vol. 8, No. 3, June 1996, pp. 391-402.

Broadband Networking with Quality of Service Guarantees

In the mid to late 80s I was the chief architect of two experimental networks, generically called MAGNET. This work introduced traffic classes with explicit quality of service constraints to broadband switching and led to the concepts of schedulable [4], admissible load [5] and contract regions [7] in real-time control of broadband networks.

Amenyo, J.-T., Lazar, A.A. and Pacifici, G., "Proactive Cooperative Scheduling and Buffer Management for Multimedia Networks", ACM/Springer Verlag Multimedia Systems, Vol. 1, No.1, May 1993, pp. 37-49.
Ferrandiz, J.M. and Lazar, A.A., "Rate Conservation for Stationary Processes", Journal of Applied Probability, Vol. 28, March 1991, pp. 146-158.
Ferrandiz, J.M. and Lazar, A.A., "Monitoring the Packet Gap of Real-Time Packet Traffic," Queueing Systems: Theory and Applications, Vol. 12, 1992, pp. 231-242.
Hyman, J.M., Lazar, A.A. and Pacifici, G., "Real-Time Scheduling with Quality of Service Constraints", IEEE Journal on Selected Areas in Communications, Vol. SAC-9, No. 7, September 1991, pp. 1052-1063.
Hyman, J.M., Lazar, A.A. and Pacifici, G., "A Separation Principle between Scheduling and Admission Control for Broadband Switching", IEEE Journal on Selected Areas in Communications, Vol. 11, No. 4, May 1993, pp. 605-616.
Hyman, J.M., Lazar, A.A. and Pacifici, G., "Modeling VC, VP and VN Resource Assignment Strategies for Broadband Networks", Proceedings of the Workshop on Network and Operating Systems Support for Digital Audio and Video, Lancaster, United Kingdom, November 3-5, 1993, pp. 99-110.
Lazar, A.A. and Pacifici., G., "Control of Resources in Broadband Networks with Quality of Service Guarantees", IEEE Communications Magazine, Vol. 29, No. 10, October 1991, pp. 66-73.
Lazar, A.A., Pacifici G. and White, J.S., "Real-Time Monitoring on MAGNET II", IEEE Journal on Selected Areas in Communications, Vol. SAC-8, No. 3, April 1990, pp. 467-483.
Lazar, A.A., Temple, A. and Gidron, R., "An Architecture for Integrated Networks that Guarantees Quality of Service," International Journal of Digital and Analog Communication Systems, Vol. 3, No. 2, April-June 1990, pp. 229-238.
Lazar, A.A., Temple, A.T. and Gidron, R., "MAGNET II: A Metropolitan Area Network Based on Asynchronous Time Sharing", IEEE Journal on Selected Areas in Communications, Vol. SAC-8, No. 8, October 1990, pp. 1582-1594.