- Self-organizing overlay
which organize sets of applications in virtual peer networks, have
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
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
without central control or coordination. In a project, called HyperCast,
we pursue an approach where
network topologies are built as graphs with well-known properties. We
building an overlay network as a logical hypercube, a Delaunay
graph, or a spanning tree. We have demonstrated that our concepts can
good performance in an implementation. Measurement experiments on a
of 100 PCs showed that we can construct a stable overlay network with
nodes in less than 1 minute. Within the HyperCast project,
we develop new
abstractions and application programming
for programming overlay networks. We have developed the concept
an overlay socket as an
endpoint of communication in an overlay
Overlay Networks with Overlay Sockets”, J. Liebeherr, J. Wang, G.
Proceedings of 5th COST 264
International Workshop on Networked Group Communications (NGC 2003),
Munich, Germany. Pages 242–253, September
- “Application-Layer Multicast with Delaunay
Triangulations”, J. Liebeherr, M.
Nahas, W. Si, IEEE Journal on Selected Areas in Communications,
Issue on Network Support for Multicast Communication, 40(8):1472–1488,
<>“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
Communication, Pisa, Italy, Springer Verlag, LNCS 1736, Pages 72–89,
- Statistical Network Calculus.
on Quality-of-Service (QoS) in the 1990s has resulted in the
of a deterministic network calculus, as a new theory that provides
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
the analysis tools of the deterministic network calculus.
the deterministic view of traffic does not account for statistical
gain. This generally results in an overestimation of actual resource
and a low utilization of network resources. Since statistical
gain increases with the amount of traffic, the penalty for ignoring
multiplexing is exacerbated with increasing network capacity. This
the search for a statistical network calculus that can exploit
multiplexing, while preserving the algebraic aspects of the
calculus. We have taken an approach to a probabilistic network
calculus, where we
express statistically multiplexed arrivals of traffic in terms of
envelopes, which are bounds on aggregate traffic that hold with high
Service guarantees to traffic are either given by a scheduling
or expressed in terms of effective service curves, which are
lower bounds on service guarantees. Using these concepts, we were able
to recover several results from the deterministic calculus in a
this research is to develop a new theory and new algorithms for
the delay and throughput performance of a network. So far, our research
has provided several important insights. For compressed video traffic
showed that, at high data rates, statistical multiplexing gain
the effects of scheduling in a network. This is an indication that a
simple network design may be sufficient to provide strong service
In a recent study, we have proved statistical lower bounds for the
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
with network service providers: if a network customer can measure its
input to the network and the throughput of only a single flow, the
can determine with high certainty if the network service provider has
the resources specified in the agreement. We also managed to express
widely used concept effective bandwidth in terms of effective
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).
Service Assurances for Traffic Scheduling Algorithms, R. Boorstyn, A.
J. Liebeherr, C. Oottamakorn, IEEE Journal on Selected Areas in
Special Issue on Internet QoS, December 2000.
Per-Flow Service Bounds in a Network with Aggregate Provisioning, J.
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.
Guarantees. A significant part of my research efforts in the 1990s
addressed traffic control algorithms for networks with deterministic
guarantees. This work has included the derivation of best possible,
is, necessary and sufficient, admission control tests for the
(EDF) and Static Priority (SP) scheduling algorithms, and a proof of
of EDF for a deterministic service. Other work has included the
of new scheduling algorithms (RPQ, RPQ+), which can approximate the
EDF scheme arbitrarily closely, but with a lower implementation
than EDF. I also worked on video traffic characterization methods
video traffic, such as MPEG video. With these characterizations, and
actual MPEG video traces as benchmark traffic, it became feasible to
the maximum utilization at which deterministic service guarantees can
maintained for MPEG video traffic.
Queue Schedulers with Approximate Sorting in Output Buffered
J. Liebeherr, D. E. Wrege, IEEE Journal on Selected Areas in
Special Issue on Next Generation IP Switches and Routers, June 1999.
Admission Control in Continuous-Media Networks with Bounded Delay
J. Liebeherr, D. E. Wrege, D. Ferrari, IEEE/ACM Transactions on
Delay Bounds for VBR Video in Packet-Switching Networks: Fundamental
and Practical Tradeoffs, D.E. Wrege, E.W. Knightly, H. Zhang, J.
IEEE/ACM Transactions on Networking, June 1996.
Guarantees. Since the late 1990s, Internet researchers have
interest in class-based QoS architectures that support service
to traffic aggregates, rather than to individual flows. Class-based
trade off reduced complexity for weaker service guarantees. In his PhD
research, Nicolas Christin explored
limits of such a service and who raised the question: What are the
service guarantees that can be given in class-based service
The main contribution of this work is a new traffic control algorithm
JoBS (Joint Buffer Management and Scheduling), which makes scheduling
buffer management decisions in a single step. This is realized by
a feedback control loop at the output queue of the link level
queue. Nicolas Christin implemented JoBS in the FreeBSD Unix kernel,
showed that shown that JoBS is viable to run in modern networks.
The implementation of JoBS has been integrated into the ALTQ and KAME
Both packages are distributed with the Unix versions FreeBSD, NetBSD,
and BSDI implementations.
- A QoS
Quantitative Service Differentiation, N. Christin, J. Liebeherr, IEEE
Magazine, Special Issue on Scalability in IP-Oriented Networks,
Quantitative Assured Forwarding Service, N. Christin, J. Liebeherr, T.
Abdelzaher, Proceedings of IEEE Infocom 2002, New York, Pages 864–873,
Since my PhD thesis research, I have maintained a strong interest in
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
of these protocols. Realizing fairness and service differentiation in
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
access protocol that quickly reaches a fair distribution of bandwidth.
A follow-up study showed that in the presence of multi-priority
the IEEE 802.6 standard could not provide preemptive priorities,
and proposed a solution to overcome this problem.
The work on HFC
("cable modem networks") has had impact on the IEEE 802.14
The multi-priority media access protocol that was developed by Mark
Corner and with researchers at NIST became the
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.)
- A Priority
the IEEE 802.14 MAC Protocol for Hybrid Fiber-Coax Networks, M. D.
N. Golmie, J. Liebeherr, C. Bisdikian, D. Su, IEEE/ACM Transactions on
Networking, 8(2):200–211, April 2000.
for Pre-Emptive Priorities in Dual Bus Metropolitan Area Networks, J.
I. F. Akyildiz, A. N. Tantawi, Proceedings of ACM Sigcomm '92, August
- 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
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.
- gwTTS website
- “An Interactive Distance Learning Application with
Networking”, J. Liebeherr, S. R. Brown, R. Albertson, Multimedia Tools
11(2):211–229, June 2000.