Current Research Interests

J. Liebeherr

  • Self-organizing overlay networks. Application-layer overlay networks, which organize sets of applications in virtual peer networks, have emerged as a new direction in networking research for deploying new network services.  Our research group addresses the problems  that arise when overlay networks grow to many thousand and even millions of peers, and where the set of peers in the networks dynamically changes. We seek solutions where a large number of peers can quickly (in the matter of seconds) self-organize in an overlay network without central control or coordination. In a project, called HyperCast, we pursue an approach where overlay network topologies are built as graphs with well-known properties. We consider building an overlay network as a logical hypercube, a Delaunay triangulation graph, or a spanning tree. We have demonstrated that our concepts can yield good performance in an implementation. Measurement experiments on a cluster of 100 PCs showed that we can construct a stable overlay network with 10,000 nodes in less than 1 minute.  Within the HyperCast project,  we develop new abstractions and application programming interfaces for programming overlay networks.  We have developed the concept of an overlay socket as an endpoint of communication in an overlay network.
More Information:
Publications:
  • “Programming Overlay Networks with Overlay Sockets”, J. Liebeherr, J. Wang, G. Zhang, Proceedings of 5th COST 264 International Workshop on Networked Group Communications (NGC 2003), Munich, Germany. Pages 242–253, September 2003.
  • “Application-Layer Multicast with Delaunay Triangulations”, J. Liebeherr, M. Nahas, W. Si, IEEE Journal on Selected Areas in Communications, Special Issue on Network Support for Multicast Communication, 40(8):1472–1488, October 2002.
    • <>“HyperCast:  A Protocol for Maintaining Multicast Group Members in a Logical Hypercube Topology”, J. Liebeherr, T. K. Beam, Proceedings of First International Workshop on Networked Group Communication, Pisa, Italy, Springer Verlag, LNCS 1736, Pages 72–89, November 1999.
  • Statistical Network Calculus. Research on Quality-of-Service (QoS) in the 1990s has resulted in the development of a deterministic network calculus, as a new theory that provides powerful tools for reasoning about worst-case delays and backlogs in a network. Many traffic algorithms developed for QoS networks, such as scheduling and traffic conditioning methods, have been validated and evaluated with the analysis tools of the deterministic network calculus.   However, the deterministic view of traffic does not account for statistical multiplexing gain. This generally results in an overestimation of actual resource requirements and a low utilization of network resources. Since statistical multiplexing gain increases with the amount of traffic, the penalty for ignoring statistical multiplexing is exacerbated with increasing network capacity. This motivates the search for a statistical network calculus that can exploit statistical multiplexing, while preserving the algebraic aspects of the deterministic calculus. We have taken an approach to a probabilistic network calculus, where we express statistically multiplexed arrivals of traffic in terms of effective envelopes, which are bounds on aggregate traffic that hold with high probability. Service guarantees to traffic are either given by a scheduling algorithm or expressed in terms of effective service curves, which are probabilistic lower bounds on service guarantees. Using these concepts, we were able to recover several results from the deterministic calculus in a statistical setting. 
The long-term goal of this research is to develop a new theory and new algorithms for determining the delay and throughput performance of a network. So far, our research has provided several important insights. For compressed video traffic we showed that, at high data rates, statistical multiplexing gain dominates the effects of scheduling in a network. This is an indication that a relatively simple network design may be sufficient to provide strong service guarantees. In a recent study, we have proved statistical lower bounds for the service experienced by a single flow when resources are managed for aggregates of flows and when the scheduling algorithms used in the network are not known. This result can be applied for verifying service level agreements with network service providers: if a network customer can measure its aggregate input to the network and the throughput of only a single flow, the customer can determine with high certainty if the network service provider has provisioned the resources specified in the agreement. We also managed to express the widely used concept effective bandwidth in terms of effective envelopes. This allowed us to evaluate the delay distribution for a diverse set of traffic models (e.g., on-off traffic, fractional Brownian motion) and a variety of scheduling algorithms (GPS, EDF, Static Priority).

Publications:
  • Statistical Service Assurances for Traffic Scheduling Algorithms, R. Boorstyn, A. Burchard, J. Liebeherr, C. Oottamakorn, IEEE Journal on Selected Areas in Communications. Special Issue on Internet QoS, December 2000.
  • Statistical Per-Flow Service Bounds in a Network with Aggregate Provisioning, J. Liebeherr, S. D. Patek, and A. Burchard, Proceedings of IEEE Infocom 2003.
  •  A Calculus for End-to-end Statistical Service Guarantees, A. Burchard, J. Liebeherr, and  S. D. Patek University of Virginia, Department of Computer Science, CS-2001-19, May 2002.

Past Research

  • Deterministic Service Guarantees. A significant part of my research efforts in the 1990s addressed traffic control algorithms for networks with deterministic service guarantees. This work has included the derivation of best possible, that is, necessary and sufficient, admission control tests for the Earliest-Deadline-First (EDF) and Static Priority (SP) scheduling algorithms, and a proof of optimality of EDF for a deterministic service. Other work has included the development of new scheduling algorithms (RPQ, RPQ+), which can approximate the optimal EDF scheme arbitrarily closely, but with a lower implementation complexity than EDF.  I also worked on video traffic characterization methods for compressed video traffic, such as MPEG video. With these characterizations, and using actual MPEG video traces as benchmark traffic, it became feasible to determine the maximum utilization at which deterministic service guarantees can be maintained for MPEG video traffic.
Publications:

  • Priority Queue Schedulers with Approximate Sorting  in Output Buffered Switches, J. Liebeherr,  D. E. Wrege, IEEE Journal on Selected Areas in Communications. Special Issue on Next Generation IP Switches and Routers, June 1999.
  • Exact Admission Control in Continuous-Media Networks with Bounded Delay Services, J. Liebeherr, D. E. Wrege, D. Ferrari, IEEE/ACM Transactions on Networking, December 1996.
  • Deterministic Delay Bounds for VBR Video in Packet-Switching Networks: Fundamental Limits and Practical Tradeoffs, D.E. Wrege, E.W. Knightly, H. Zhang, J. Liebeherr, IEEE/ACM Transactions on Networking, June 1996.
  • Class-based Service Guarantees. Since the late 1990s, Internet researchers have developed interest in class-based QoS architectures that support service guarantees to traffic aggregates, rather than to individual flows. Class-based services trade off reduced complexity for weaker service guarantees. In his PhD research, Nicolas Christin explored the limits of such a service and who raised the question: What are the strongest service guarantees that can be given in class-based service architecture? The main contribution of this work is a new traffic control algorithm called JoBS (Joint Buffer Management and Scheduling), which makes scheduling and buffer management decisions in a single step. This is realized by running a feedback control loop at the output queue of the link level transmission queue. Nicolas Christin implemented JoBS in the FreeBSD Unix kernel, and showed that  shown that JoBS is viable to run in modern networks. The implementation of JoBS has been integrated into the ALTQ and KAME implementations. Both packages are distributed with the Unix versions FreeBSD, NetBSD, OpenBSD, and BSDI implementations. 

More Information:

Publications:

  • A QoS Architecture for Quantitative Service Differentiation, N. Christin, J. Liebeherr, IEEE Communications Magazine, Special Issue on Scalability in IP-Oriented Networks, 41(6):38–45, June 2003. 
  • A Quantitative Assured Forwarding Service, N. Christin, J. Liebeherr, T. Abdelzaher, Proceedings of IEEE Infocom 2002, New York, Pages 864–873, June 2002.
  • MAC Protocols. Since my PhD thesis research, I have maintained a strong interest in media access protocols (MAC) for local and metropolitan area networks. I have worked on two media access protocols, Distributed Queue Dual Bus (DQDB) and Hybrid Fiber-Coax (HFC). Particularly, I have worked on the design and evaluation of protocols to improve fairness or provide priority access of these protocols. Realizing fairness and service differentiation in MAC protocols continue to pose difficult research problems, as evidenced by the recently proposed MAC protocols Resilient Packet Ring (IEEE 802.17) and WiFi (IEEE 802.11e). In my PhD thesisI presented and analyzed a media access protocol that quickly reaches a fair distribution of bandwidth. A follow-up study showed that in the presence of multi-priority traffic, the IEEE 802.6 standard could  not provide preemptive priorities, and proposed a solution to overcome this problem.
    The work on HFC networks ("cable modem networks") has had impact on the IEEE 802.14 standardization committee. The multi-priority media access protocol that was developed by Mark Corner and with researchers at NIST became the foundation for the priority scheme of the IEEE 802.14 standard effort. (The IEEE 802.14 standard was never completed, since the competing DOCSIS effort became the de-facto standard for HFC networks.)

Publications: 

  • A Priority Scheme for the IEEE 802.14 MAC Protocol for Hybrid Fiber-Coax Networks, M. D. Corner, N. Golmie, J. Liebeherr, C. Bisdikian, D. Su, IEEE/ACM Transactions on Networking, 8(2):200–211, April 2000. 
  • An Effective Scheme for Pre-Emptive Priorities in Dual Bus Metropolitan Area Networks, J. Liebeherr, I. F. Akyildiz, A. N. Tantawi, Proceedings of ACM Sigcomm '92, August 1992.
  • Telecollaboration Tools. In the mid-1990s, we experimented a lot with MBONE tools and multimedia collaboration tools. We developed a system, called grounds-wide tele-tutoring system (gwTTS), for tele-tutoring on a campus network.The gwtts tele-tutoring software developed has been commercialized by the Virginian company Litton-Fibercom (CAMVision 7610 Distance Learning Controller). Paco Hope developed a (unfortunately unpublished)  tele-orchestra application for MIDI data over IP multicast.
    • <>
    More Information:

  • gwTTS website (1996)

    • Publication:
      • “An Interactive Distance Learning Application with Hybrid ATM/IP Networking”, J. Liebeherr, S. R. Brown, R. Albertson, Multimedia Tools and Applications, 11(2):211–229, June 2000.
8/2004