4. Approaches and Recent Accomplishments
7. Publications Under the Support
Name: Jennifer C. Hou
Address: Department of Computer Science
University
of Illinois
1304 W. Springfield Avenue, Urbana, IL
61801
Phone: (217) 265-6329
Fax: (217)
244-6500
E-mail: jhou@cs.uiuc.edu
URL: http://lion.cs.uiuc.edu/perc
Grant
Number: KK0101 University of California at Santa
Barbara
Zipped powerpoints given at the MURI progress
meeting on August 18-19, 2002.
The goal of our component PERC project is
to develop and demonstrate an environment – an integrated set of QoS-aware
network protocols, network simulation tools, and network middleware and
software – for supporting QoS on an end-to-end basis in real-time, fault
tolerant environments. In the support
period of 1 July 2000 – 30 June 2002, we have
1. Laid
a general QoS framework for QoS-driven shared tree multicast routing and
devised eligibility tests for member join/leave procedures.
2. Investigated
how the long range
dependency (LRD) characteristics of Internet traffic --- existence of
non-trivial correlation structure at multiple time scales --- can be
judiciously exploited for better traffic control and measurement.
3. Completed the design and implementation of
a component-based, compositional network simulation and emulation environment, JavaSim,
and made the first formal release (after 8 pre-releases) in October 2001 (http://www.javasim.org).
4.
Laid the
software architecture for the communication middleware to be developed.
4. Approaches and Recent
Accomplishments
QoS-driven multicast routing: We have investigated the problem of QoS
provisioning in shared multicast routing protocols such as Core-Based Tree,
Simple Multicast (SM) and Protocol Independent Multicast Sparse Mode (PIM-SM),
and devised a unified QoS extension framework for this type of multicast
routing protocols. Specifically, the QoS requirement may be heterogeneous
among receivers, and is specified as either (R1) an upper/lower bound of an
additive, multiplicative, or concave QoS parameter (e.g., the end-to-end delay
bound), or (R2) an upper bound of the inter-receiver difference of a QoS
parameter (e.g., the inter-receiver delay jitter bound). We consider these QoS
requirements and devise a set of enhancements in the member join/leave and
state update/refresh procedures to facilitate the deployment of additive (e.g.,
end-to-end delay bound), multiplicative (e.g., packet loss ratio along a path)
and concave (e.g., minimum bandwidth available) QoS. In particular, we (i)
devise eligibility tests to verify whether or not a new member can join a
multicast tree at adequate QoS, without violating the existing QoS to the other
on-tree members; (ii) determine the set of states kept at each router in order
to conduct eligibility tests; (iii) devise a state update/refresh procedure
that is based on soft state and can be readily integrated with the tree
maintenance mechanism that already exists in most core based multicast
routing protocols; and (iv) implement,
based on the CBT daemon in FreeBSD (developed by British Telecom), and
empirically evaluate the performance of
the proposed QoS framework.
We have reported our evaluation results in
the Inter-domain multicast routing working group of Internet Engineering Task
Force. The presentation was very well
received.
Exploitation of LRD for resource and
traffic control: Central to exploitation of the abundant
correlation structure for traffic control and measurement is (i) prediction of
the future traffic at multiple time scales based on recent measurements and
(ii) use of the prediction results in the decision making of traffic
control/measurement. We have carried out the research along the following two
major directions: on the one hand, we investigate both fractional-model-based
and non-fractional-model-based predictors and determine which predictor(s)
render the best performance in predicting Internet traffic. The fractional
brownian motion model, the fractal ARIMA model, and the multifractal
wavelet model are representatives of the former, and the linear minimum
mean square error predictor falls in the latter. This study is conducted with performance measures of accuracy,
ease of deployment, computational complexity, and adaptability, and is based on
analytical reasoning, ns-2 simulation, and empirical experiments with the large
amount of traffic measurement and traces available at the Cooperative
Association for Internet Data Analysis (CAIDA). On the other hand, we have
investigated how we can harness traffic prediction (obtained with appropriate
choices of traffic predictors) in traffic control/measurement in the following
three research thrust areas:
(1)
Leveraging
traffic predictability in active queue management: We show that the correlation structure
present in long-range dependent traffic can be detected on-line and used to
predict the future traffic. We then
devise a novel scheme, called TCP with traffic prediction (TCP-TP), that
exploits the prediction result to infer, in the context of AIMD steady-state
dynamics, the optimal operational point at which a TCP connection should
operate. Through analytical reasoning,
we show that the impact of prediction errors on fairness is minimal. We also conduct ns-2 simulation and FreeBSD
4.1-based implementation studies to validate the design and to demonstrate the
performance improvement in terms of packet loss ratio and throughput attained
by connections.
(2)
Exploring
use of traffic predictability to improve TCP congestion control: We figure in, with the objective of
stabling the instantaneous queue length, the prediction results in the
calculation of the packet dropping probability in active queue management
(AQM). The resulting scheme is termed as predictive AQM (PAQM). Through
analytical reasoning, we show that PAQM is a generalized version of the well-known
AQM scheme, random early detection (RED) that takes the future arrival rate as
a new dimension of congestion index. By stabilizing the queue at a desirable
level with consideration of future traffic, PAQM enables the link capacity to
be fully utilized, while not incurring excessive packet loss ratio. Through
ns-2 simulation, we compare PAQM against existing AQM schemes with respect to
different performance criteria, and show that under most cases PAQM outperforms
SRED in stabilizing the instantaneous queue length, and adaptive virtual queue
(AVQ) in reducing packet loss ratio and better utilizing the link capacity.}
Design, implementation, and module
enhancement of JavaSim: We have laid a
component-based software architecture, called autonomous component
architecture (ACA), that deploys a message-passing, independent
execution model to more closely mimic hardware systems, in terms of how
components are specified and assembled and how components interact with one
another. To fully specify, implement,
and evaluate ACA, and to explore its application in building large-scale, truly
extensible network simulation/emulation environments, we have carried out tasks
along the following two thrusts of research:
1.
We have implemented a proof-of-concept version of ACA in Java. Through
the lessons we learned from the implementation and experimentation, we have
continued to refine/enrich the implementation.
For example, we have designed and implemented an execution context
management and scheduling mechanism in the ACA runtime. We have also fine-tuned
the performance of the ACA implementation to reduce the component overhead in
terms of execution time and memory usage.
2. To explore how ACA facilitates the
building of large-scale, extensible, and reusable software systems, we have
built, on top of the ACA implementation, a compositional network simulation
environment, JavaSim. Succinctly, we have devised a packet-based network
modeling framework, called extensible internetworking framework (EIF),
and implemented on top of the ACA and EIF implementation, an (almost) complete
suite of essential network protocols in the Internet best-effort service,
integrated service, and differentiated service architectures. Table 1 gives the set of protocol classes
currently supported in JavaSim.
Very recently we have also extended JavaSim to include components
in mobile wireless environments, i.e., antenna propagation models, terrain
models, IEEE 802.11 and power saving mode, ad hoc routing classes (DSR/AODV),
and will make another release in September 2002.
|
Network Architecture |
Application |
Socket Layer |
Transport |
Routing |
Traffic Model |
Tagger Marker |
Buffer Management |
NI Scheduling |
|
Best Effect Services |
FTP, FSP |
BSD 4.3 |
TCP-Reno |
RIP (DV) |
|
|
Drop-Tail |
FIFO |
|
Differentiated Services |
|
|
|
|
|
Token Bucket |
RED |
FIFO |
|
Integrated Services |
|
|
RSVP |
Unicast QoS routing |
Periodic message (CBR) |
|
|
RM |
|
FTP: file transfer protocol |
FSP: file service protocol |
|
BSD: Berkeley socket distribution |
TCP: transmission control protocol |
|
RIP: routing information protocol |
OSPF: open shortest path first |
|
DVMRP: distance vector multicast
routing protocol |
MOSPF: multicast extension to OSPF |
|
CBT: core based tree protocol |
FIFO: first in first out |
|
TSW: time sliding window |
ETSW: enhanced time sliding window |
|
RED: random early drop |
FRED: fair random early drop |
|
SRED: stable random early drop |
BRED: balanced random early drop |
|
RSVP: Resource reservation protocol |
CBR: constant bit rate |
|
RM: rate monotonic |
EDF: earliest deadline first |
|
DCTS: distance constrained task system |
LFVC: leap forward virtual clock |
|
SCFQ: self-clocked fair queueing |
PGPS: packet-by-packet generalized
processing sharing |
|
STFQ: start time fair queueing |
WF2Q: worst-case fair
weighted fair queueing |
Table 1: Protocol classes supported in
JavaSim
We have conducted extensive stress tests,
compared the performance of JavaSim against ns-2 and SSFNET, and
provided a detailed qualitative and quantitative comparison report in http://www.javasim.org/comparison.html. In spite of the overhead inherited from the
component architecture, JavaSim demonstrates better scalability (both in terms
of simulation completion time and experiment setup time_ in large simulation
scenarios (e.g., in the case that the number of nodes >= 5000) on a
dual-Pentium III-600 MHz, 256MB RAM PC.
Dependable Communication Middleware:
In order to make the multiple networking technologies transparent to the
applications, we are currently developing a communication middleware that
supports fault-tolerant and secure communication. In the middleware,
abstractions, such as dependable pipe and secure pipe, respectively are
developed. Dependable pipe will employ multiple communication mediums and
secure pipe will use encryption.
Moreover, we have
identified and developed a set of large-grained middleware services (building
blocks) with precise specifications and well-defined interfaces, and will
export a collection of modular and composable middleware services with a rich,
well-defined API. Figure 1 illustrates the components in the suite of
middleware services from the user
prospective. Each layer exports a well-defined interface to other services
or to applications that are built on top of it and supports standard protocols.
Related services are grouped together to illustrate functional dependencies
among them:
1.
QoS negotiation and adaptation: provides negotiation services of parameterized QoS at the application
level. Applications may specify and negotiate QoS in terms of quantitative
measures, and qualitative terms.
2.
QoS monitoring and notification: provides support and feedback from
lower-layer protocols to adaptive higher-layer protocols and applications. As part
of the dependability-related operations implemented in a protocol module, the
protocol module will cause an up call into each other protocol module and
application that has registered interest in such changes.
3.
Fault detection and recovery management: is closely related to fault-tolerant communication services.
Associated with each protocol module is an application-specific recovery
procedure that may be invoked when a failure is detected through timeouts or
lack of heartbeat messages.
Applications and higher-layer protocols may register specifying the
fault/error latency and the level of fault tolerance desired.
4.
Dependable communication service: exploits spatial redundancy
(edge-disjoint backup paths) or temporal redundancy (pre-allocations of both primary
and alternate transmission time intervals for a connection) to achieve fault
tolerance without sacrificing the predictability of the system. An application
may invoke the service, specifying its fault tolerance requirements in terms of
packet loss, fault tolerance latency, and the number of replicated messages
desired.
5.
Predictable unicast/multicast services: provide a collection of network services
with deterministic or statistical temporal QoS for sending messages to a single
destination or a group of destinations. The set of services to be exported
include unicast with end-to-end delay bound, unicast with inter-message delay
jitter bound, (datagram or casual) multicast with delay bound,
inter-destination delay jitter bound, or a combination thereof, and (datagram
or casual) multicast with TCP-friendly congestion control.
6.
System resource tracking and management: provides interfaces for tracking both
active and passive resources involved in a communication activity, for
determining their availability, and for supporting application-specified
management/security policies. Based on
the system resource available and the dependability/QoS required, an
application can then compose the protocol modules for admission control,
resource reservation/adaptation, and/or traffic control in a plug-and-play
fashion.
The research results on QoS-driven
multicast routing and LRD-driven traffic/resource control have direct applicability
to the development and implementation of network protocols/solutions in support
of resource management in network-centric warfare scenarios. Three journal papers that document the
research findings have been accepted for publication in two of the most
prestigious IEEE journals: IEEE Trans. on Computers and IEEE/ACM
Trans. on Networking. Several
student-coauthored papers have been presented in highly-regarded IEEE
conferences (usually with acceptance rate usually less than 20%), e.g., IEEE
INFOCOM and IEEE Int’l Conf. on Network Protocols.
Exploitation of LRD in congestion,
resource, and traffic control is still in its infancy. Tuan and Park pioneered the work of exploiting LRD in congestion control, and
used, based on the conditional expectation, a simple estimation scheme to
explore the correlation structure. We have taken the heuristic rule-of-thumb to
a rigorous plateau, where the traffic prediction is rigorously made with the
use of a LMMSE predictor, and the calculation of packet dropping probability in
AQM and/or the window adjustment in TCP congestion control is pinpointed in the
context of steady-state dynamics. Moreover, this is achieved without requiring
router support or compromising simplicity and ease of implementation. The research results have been (or will be)
reported in IEEE INFOCOM 2002 (acceptance rate < 20%) and IEEE
Int’l Conf. on Network Protocols 2002 (acceptance rate < 15%).
Figure 1: Communication middleware
JavaSim, on the other hand, provides an extensible, reusable network
simulation and emulation environments.
Since its formal release, more than one hundred groups have downloaded
the software, including NIST, Oak Ridge National Laboratory, Fujitsu Labs of
America, CMU, Univ. of Toronto, Dartmouth College, Georgia Tech, and Renesys,
Inc. We are currently collaborating
with Oak Ridge National Laboratory on laying a Grid networking layer (on top of
the transport layer) in JavaSim to support simulation of Grid
applications and with Fujitsu Labs of America on extending JavaSim for
network emulation.
Education and Student Training: The research being carried in this
component of the PERC is part of the thesis research of three of Ph.D.
students: Hung-Ying Tyan, Yuan Gao, and Guanghui He. Tyan graduated in Fall 2001 and is currently a member of
technical staff at Fujitsu Labs of America, Sunnyvale, CA. Gao has successfully
advanced to candidacy, is expected to graduate in September 2002, and will join
Lucent Technologies Bell Laboratories, Murray Hills as a member of technical
staff in traffic measurement and control. Guanghui He is expected to take his
candidacy exam in September 2002, and is working as a summer intern student (in
Summer 2002) at IBM T.J. Watson Research Center in the area of studying web
traffic patterns and user behaviors.
Other Professional Activities: Recognized by the research accomplishments (which are, in part,
results of the grant), the PI has served as the chair of the technical program
committee of IEEE Real-time Technology and Application Symposium in June
2000 and as the general chair of the same symposium in June 2001. In addition, she has served as the vice
chair of the technical program committee of IEEE Int’l Conf. on Distributed
Computing Systems in June 2002, the tutorial chair of IEEE Int’l Conf.
on Computer, Communication, and Networks in November 2002, and the session
chair for IEEE
8th Int'l Conf. on Network Protocols, November 2000, SPIE
conference on scalability and traffic control in IP networks, August 2001,
and IEEE 21st INFOCOM: The Conference on Computer Communication, June
2002. She has also served on the review
panel for NSF CAREER program in 1998-2001, NSF Information Technology
Research program in 2000-2002, NSF Strategic Technology for Internet Program
in 2001, NSF Computer and Computational Research program in 2001, and NSF
Embedded and Hybrid Systems Program in 2002.
Extension of QoS-driven multicast routing
to wireless sensor networks: Already important in
wired networks, multicast is expected to assume an important role in actively
controlled wireless networks in which a myriad of mobile sensors, actuators and
vehicles inter-connected by wireless links. Providing multicast support for
such environments is a challenging problem, for several reasons. First, the addition of mobility to the host
group model implies that multicast routing algorithm must now deal not only
with dynamic group membership, but also with dynamic member location (i.e., the
routes used to reach specific group members are themselves transient in
nature). Second, many of the algorithms
used in multicast routing protocols, such as DVMRP, MOSPF, PIM or CBT,
implicitly assume static hosts when a multicast delivery tree is set up. Reconstructing the delivery tree every time
a multicast source moves is not always a viable option, because of the overhead
involved. Last but not least, support of reliable data transport and QoS in the
existence of host mobility and low-bandwidth, unreliable wireless links
requires careful coordination, and perhaps combination, of host membership,
dynamic routing, resource management, and reliable multicast
transport. We will:
(i)
Develop multicast models of different levels of QoS in wireless
networking environments (e.g., user-viewed video streams may tolerate relaxed
reliable delivery in lieu of reduced latency).
(ii)
Develop multicast routing algorithms that take into account of host
mobility and frequent route changes. In particular, we will extend Mobile IP
(by perhaps migrating some of the functionalities of DVMRP and MOSPF to Mobile
IP) and develop multicast routing protocols in mobile wireless networks.
Exploitation of LRD for resource and
traffic control: we will investigate three theoretically
grounded methods: prediction, reconstruction and interpolation, for measuring
cross traffic on the bottleneck link of an end-to-end path. The objective is to infer cross traffic as
accurately as possible, while not injecting a significant amount of probe
packets into the network. In all these
methods, we will take advantage of the LRD characteristic of cross traffic. We
will also conduct simulation/empirical (Internet) studies to study (i) if these methods can give good mean or
instantaneous measurement of cross traffic (ii) if they are adaptive to the
dynamic change of cross traffic and are robust in the presence of multiple
bottleneck links on an end-to-end path.
We will also further improve the robustness of three methods in
the cases that probe packets may be queued before/after the bottleneck link and
that the bottleneck itself may change as a result of dynamic network traffic
changes.
Design, implementation, and module
enhancement of JavaSim: We will continue our JavaSim
efforts along the following directions:
(i)
We will
extend JavaSim to include components in other emerging network
architectures, such as wireless sensor networks.
(ii)
We will
extend JavaSim to realize network emulation. Specifically, we will develop a complete Java-compliant socket
layer on which real applications (e.g., web/ftp servers and audio/video
applications) can be readily ported. We
will also devise techniques to interface device driver components in JavaSim
with real network interface cards (NICs);
(iii)
We will
investigate use of fluid models to expedite simulation. In the fluid model
based simulation, network traffic is modeled in terms of a continuous fluid
flow, rather than discrete packet instances.
A cluster of closely spaced packets may be modeled as a single fluid
chunk with a constant fluid rate. A set
of differential equations is derived (based on the fluid model) and used to
characterize the system evolution. A
fluid-model based simulator then keeps track of the fluid rate changes at
traffic sources and at router queues.
We will investigate in which network layer (transport, routing, buffer
management, or MAC) fluid model-based simulation is most effective, and
quantify the execution time speed-up thus achieved and the approximation errors
thus incurred. We will also implement
fluid-model based simulation classes in JavaSim.
(iv)
We will
develop a real-time process-driven simulation technique (as opposed to event-driven
simulation) that naturally extends the ACA independent execution model and
characterizes the interactions in real systems more realistically.
(v)
We will
investigate whether or not, and how, the conservative and optimistic
synchronization approaches used in event-driven simulation can be applied to
real-time process-driven simulation.
Our ultimate goal is to build parallel simulation engines into the ACA
runtime.
Dependable Communication Middleware: The proposed middleware will not only significantly enhance the abstractions provided to the application developers, but will impact many other applications such as internetworking of homes (i.e., connecting home computers to the Internet). We will continue the efforts along three directions:
(i) We will continue to implement the
communication middleware in Redhat Lunix.
(ii) We will identify a set of
middleware services common to network services with dependability guarantees,
and study how to group together the building blocks (Figure 1) to realize these
services and to ensure end-to-end QoS provisioning.
(iii)
We
will implement user APIs that may be a profile
of APIs or a new API veneer that covers the APIs of the underlying middleware
services that it abstracts with a common syntax.
7. Publications Under the
Support
Journal papers
[1] Hung-Ying Tyan, Jennifer Hou, and Bin Wang, ``Many-to-many
multicast routing with temporal QoS guarantee,'' accepted for publication in IEEE
Trans. on Computers, July 2001.
[2] Yuan Gao, Jennifer Hou, and Sanjoy Paul, ``RACCOOM: a
rate-based congestion control scheme for multicasts,'' accepted for publication
in IEEE Trans. on Computers, October 2001.
[3] Hung-Ying Tyan, Jennifer Hou, and Bin Wang, “QoS extension to
core-based muticast routing,” accepted for publication in IEEE/ACM Trans. on
Networking, July 2002.
Conference papers
[4] Bin Wang, Hung-Ying Tyan, and Jennifer Hou, ``QoS-based
multicast routing for distributing layered video to heterogeneous receivers in
rate-based networks,'' IEEE 20th INFOCOM, Tel Aviv, Israel, March 2000
(11 pages).
[5] Yuan Gao, Ye Ge, and Jennifer Hou, “Reliable multicasts for
core-based multicast routing,” Proc. IEEE 8th Int’l Conf.
on Network Protocols (ICNP’00), Osaka, Japan, November 2000 (11 pages)
[6] Hung-Ying Tyan and Jennifer Hou, ``JavaSim: A
component-based compositional network simulation environment,'' Proc. of
Western Simulation Multiconference -- Communication Networks And Distributed
Systems Modeling And Simulation, January 2001 (10 pages).
[7] Yuan Gao, Jennifer Hou, and Sanjoy Paul, ``RACCOOM: a
rate-based congestion control scheme for multicasts,'' SPIE conference on
scalability and traffic control in IP networks, August 2001 (8 pages)
[8] Bin Wang and Jennifer Hou, ``An efficient QoS routing
algorithm for quorumcast communication,'' IEEE 9th Int'l Conf. on Network
Protocols (ICNP'01), November 2001 (10 pages).
[9] Hung-Ying Tyan and Jennifer Hou, ``Design, realization, and
evaluation of a component-based, compositional network simulation
environment,'' Proc. of Western Multiconference -- communication networks and distributed systems modeling and
simulation, January 2002 (8 pages).
[10] Yuan Gao, Guanghui He, and Jennifer Hou, ``On leveraging
traffic predictability in active queue management,'' Proc. IEEE INFOCOM 2002,
New York, NY, June 2002 (11 pages).
[11] Honghai Zhang and Chao-Ju Hou, "A
scheduling algorithm for variable rate coded voice in Bluetooth networks,"
to appear in The Fifth ACM International Workshop on Wireless Mobile Multimedia,
September 2002.
[12] Wei-Peng Chen and Jennifer Hou, ``Dynamic, ad-hoc source
routing with connection-aware link-state exchange and differentiation,'' Proc.
IEEE Globecom 2002, Taipei, Taiwan, November 2002 (8 pages).
[13] Guanghui He, Yuan Gao, and Jennifer Hou, ``A case for
exploiting self-similarity of Internet traffic in TCP congestion control,'' IEEE
Int'l Conf. on Network Protocols, Paris, France, November 2002 (11 pages)
Manuscripts in submission
[14] Bin Wang and Chao-Ju Hou, "QoS-based
multicast routing for distributing layered video to heterogeneous
receivers," submitted to IEEE/ACM Trans. on Networking, February
2001.
[15] Yuan Gao, Ye Ge, and Chao-Ju Hou, "Reliable
multicasts for core-based multicast routing," submitted to IEEE Trans.
on Computers, May 2002.
[16] Yuan Gao, Chao-Ju Hou, and Sanjoy Paul, "COCOON: an
alternate approach to end-host congestion management" submitted to IEEE
Trans. on Computers, April 2002.
[17] Guanghui He and
Jennifer Hou, ``On exploiting long range dependency in measuring cross
traffic,'' submitted to IEEE INFOCOM 2003, July 2002.
[18] Yuan Gao and Jennifer Hou, ``A state feedback control approach to
stabilizing AQM queues for ECN-enabled TCP connections,'' submitted to IEEE
INFOCOM 2003, July 2002.
[19] Rong Zheng, Chao-Ju Hou, and Lui Sha, ``An asynchronous
wakeup mechanism for ad hoc networks: theory and protocol design'' submitted to
IEEE INFOCOM 2003, July 2002.
[20] Hwangnam Kim and
Jennifer Hou, “Fluid model-based analysis and simulation for IEEE 80211-operated
wireless LANs,” submitted to IEEE Int’l Conf. on Communications, July
2002.
Ph.D. thesis
[21] Hung-Ying Tyan,
“Design, realization and evaluation of a component-based compositional software
architecture for network simulation,” Department of Electrical Engineering,
Ohio State University, December 2001.
[22] Yuan Gao,
“Congestion control for the next generation Internets,” Department of
Electrical Engineering, Ohio State University, September 2002.
