Transcript Pocket Webclass - MSU CSE - Michigan State University

Adaptive Middleware for Heterogeneous
Collaborative Computing
Philip K. McKinley
Software Engineering and Network Systems Laboratory
Department of Computer Science and Engineering
Michigan State University
Outline
 SENS Lab and Communications Research Group
 Summary of prior research activities
 Issues in anytime, anywhere, anyhow computing
 Ongoing Projects
Pavilion: web-based collaborative toolkit
RAPIDware: adaptive middleware framework
Meridian: automated development of
distributed applications
 Summary
MSU SENS Laboratory
 The Software Engineering and Network Systems
Laboratory supports research in:
software engineering
distributed computing
network protocols and real-time systems
fault tolerance and security
formal methods, code generation
compilation/analysis of concurrent systems
 Six faculty members and their students
 Research sponsored by NSF, DARPA, DOE,
NASA, EPA, and several industrial partners
Communications Research Group
 A research group within the SENS Laboratory
 Much of our research addresses the design and
performance of multiparty applications,
protocols, and services. Prior research:
 Parallel processing
collective communication in MPPs and NOWs
 Distributed Computing
reliable multicast in Linux kernel and in NT
 Networking
hardware-based flooding in ATM networks
efficient leader election, routing protocols
Motivations for Current Work
 “Anytime, anywhere” data access and
communication is quickly becoming reality, due to:
development of world-wide web
large scale deployment of wireless services
advances in handheld/wearable computers
 One class of applications that will likely benefit
from this infrastructure is collaborative computing
systems
 Examples: CSCW, remote instruction, factory
management, medical diagnosis, command and
control
 Users will access services through a variety of
network connections and computing devices
Example Scenario
Remote collaboration among researchers:
Field Engineer
with Wearable
Computer
Traditional Wired LAN
Telecommunications
Network
Internet
Proxy
server(s)
Indoor Wireless LAN
Proxy
server(s)
Mobile Research
Station
High-Performance
Compute Server
Same technology will also be used for “everyday”
collaboration among family members, etc.
Pavilion Project
 A Java-based middleware framework for weboriented collaborative applications
 By default, provides collaborative browsing
 More importantly, supports development of new
applications by reusing/extending components:
Reliable Multicast Protocol (WBRM)
Web Browser Interfaces
Leadership Protocol
Extensible HTTP Proxy
Plug-ins for thin clients
etc...
Default Pavilion Operation
Proxy
Server
Browser
Interface
Multicast
Protocol
Leadership
Protocol
S
Proxy
Server
Multicast
Protocol
Leadership
Protocol
Browser
Interface
HTTP/GET
FILE DATA
URL INFO
CONTROL
WBRM Performance
 Over 8Mbps throughput on 10Mbps Ethernet and around
50Mbps on 100Mbps Ethernet, depending on processors
 Performance approaches that of our Linux kernel protocol,
H-RMC, with much less development effort
Response Time
35000
Delay (msec)
30000
Protocol (Avg)
Protocol (Max)
Protocol (Min)
HTTP (Avg)
HTTP (Max)
HTTP (Min)
25000
20000
15000
10000
5000
0
1
3
5
7
9 11 13 15 17 19
Number of Receivers
Pavilion Proxy Servers
 Proxies can be used to provide transparent
services to collaborative web-based applications
Local proxies execute on client's local host and are
typically used to enhance application functionality
Remote proxies execute on other systems and
enhance performance by tailoring data streams to
match client capabilities
 A key design principle in Pavilion (and follow-on
RAPIDware project) is to provide such services in
the form of data- and application-specific plug-ins
Building Applications with Pavilion
Pavilion may be extended by implementing
application-specific plug-ins (loaders, filters,
etc) for various proxies.
Plug-ins used to perform the following tasks:
Distill data stream to reduce bandwidth consumption or
client processing overhead
Modify the web resources according to applicationspecific needs
“Wrap” the resource in another file that is returned to the
browser (used to load associated applet). Such applets
can communicate with other participants via local
Pavilion “worker” threads.
Example: VGuide
 VGuide is a Pavilion-based synchronous virtual
reality tool
leader selects (arbitrary) VRML world and guides other
participants through that world
 Uses/extends several Pavilion components:
reliable multicast protocol to distribute VRML file and
associated applets
proxy server plug-ins to intercept file and “wrap” it in an
html file containing an application-specific applet
applets and worker threads to monitors viewpoint
changes and multicast them to other group members
VGuide Demonstration
VGuide Component Overview
Leader Browser
Client Browser
 VRML plug-in to Http proxy
EAI Applet
EAI Applet
socket
VRML Thread
Browser
Interface
socket
IP
Multicast
VRML Thread
Browser
Interface
VRML
Plug-in
Http proxy
Http proxy
Reliable
Multicast
“wraps” VRML file in html file with
embedded applet
 Http proxy distributes VRML file
and associated applet
 Applet uses External Authoring
Interface (EAI) to access the
VRML world
 Applet forwards viewpoint
updates to VRML thread using
socket
 VRML thread sends viewpoint
updates to other participants
using IP multicast
Platform Heterogeneity
The time needed to
read/modify object in a VRML
word varies on each machine.
 Time to modify an object depends
highly on video adapter
performance
 Time to read an object depends
on CPU speed.
Presence of heterogeneous
participants could lead to high
jitter and buffer overflow.
Updates filtered by proxies for
slow clients in order to improve
performance
Pocket Pavilion Subproject
 Goals:
To design a web-based application that extends
collaborative browsing to wireless handheld
computing platforms running Windows CE
To demonstrate reuse of Pavilion components in
supporting heterogeneous clients
To evaluate the performance of using a wired proxy
on behalf of wireless clients
 Key issue: accommodating limitations of
handheld PCs and the Windows CE
environment
Handheld/Palm-Sized PCs
 No disk, only
ROM and RAM
 Can be
connected to a
desktop to
synchronize
data
 Run PalmOS,
Windows CE, ...
HP 620LX/660LX Handheld PC
 75MHz RISC processors (Hitachi SH-3)
 Display
 256-color LCD
 640*240 pixels on screen
 32MB/16MB RAM
 Card Slots
 One PC card type II card slot
 One CompactFlash type I card slot
 Ports
 One RS-232C serial port
 One IrDA port
 Battery
 Rechargeable Lithium-Ion Battery
 CR2032 coin-cell backup battery
 Windows CE 2.0
Experimental Configuration
Multicast-incapable
wireless receivers
Wired receivers
Sender
Proxy with
TCPhub
Access
point
Wired receivers
Reliable multicast
connection
TCP connection
Pocket Pavilion Operation
7.
Request
for data
8. Data
3. Data
Data
Proxy
Reliable Multicast
Protocol
3. URL
Control Proxy
6. URL
Pocket
Pavilion
Client
Handheld PC
5. URL
2. Web
resources
4. URL
4. URL
TCP hub
5. Request to
Data Proxy
for data
1. Register
1. Register
H/PC
Membership
manager
Proxy Node (also a
participant in the session)
6. Data
from Data
Proxy
Sample Performance
Proxy vs. no proxy
1200
Milliseconds
1000
800
No proxy
600
Proxy
400
200
0
1k
2k
4k
6k
File size
8k
10k
RAPIDware Project
 Extends Pavilion by addressing automatic
instantiation and adaptation of the middleware
layer
 Key objectives:
Automatically accommodate heterogeneity of among
computing devices and network connections
Adapt to failures, changes in channel quality, etc.
Provide support for reuse of middleware components
Offer a unified methodology for three types of
adaptation: communication services, user interfaces,
fault tolerance
 Observers monitor system and detect changes
 Responders handle such events by instantiating
Adaptive Component Interaction
Host computer
(wired workstation)
Host computer
(wireless laptop)
Application
Application
APPLICATION
LAYER
Host computer
(wireless palmtop)
Application
observers
MIDDLEWARE
LAYER
data
paths
NETWORK
LAYER
core middleware
components
Proxy node
(e.g., desktop)
responders
Subproject: Adaptive FEC for Reliable
Multicasting on WLANs
 Forward Error Correction (FEC) can be introduced at a
WLAN proxy to mitigate potentially high packet loss rates
 Losses among multiple receivers in WLANs are often
uncorrelated, since they depend on the distance from the
access point and environmental conditions
 Objective: experimentally evaluate effectiveness of proxybased FEC on multicast data streams in WLANs, and
explore how to adapt FEC to changing conditions
 Proxy runs two instances of protocol, one tuned for wired
network, and one tuned for wireless network
Receiver Throughputs without Proxy
and with Proxy
Throughputs with Proxy
Observed Throughput (in Mbps)
50
45
Wired Receiver
40
Wireless Receiver #1
35
Wireless Receiver #2
30
25
20
15
10
5
0
1
2
3
4
Run #
5
6
7
Observed Throughput (in Mbps)
Throughputs Without Proxy
50
45
40
35
30
25
20
15
Wired Receiver
Wireless Receiver #1
Wireless Receiver #2
10
5
0
1
2
3
4
Run #
5
6
7
(n,k) Block Erasure Codes
•Divide data (audio) stream into groups of k packets
•For each group, send k data packets and n-k parity packets
•Receipt of any k packets enables reconstruction of data
FEC Proxy Design
 Reuses several classes from WBRM protocol
 Adaptive components operate as plug-in modules
Packet
Buffer
WBRM
Receiver
Dispatcher
Queue
FEC Group
Filter
Wired
LAN
Adaptive
FEC Control
FEC
Encoder
Packet
Dispatcher
Parity
Packet
Buffer
Packet Loss
Monitor
Wireless
LAN
NAK
Processor
Proactive Parity Transmission
 In the presence of high losses, it usually takes multiple
NAKs (and hence RTTs) to correct losses in a group
since the correction packets themselves are
susceptible to losses
 Sending immediate redundant information along with
the data and NAK responses may help in solving this
problem
 Can adjust proactive rate a proportionally to loss rate
 Experiments show that throughput is less affected by
an over-estimate of the proactive parameter than by
an under-estimate
Sample Results (Emulation)
5% loss
10% loss
35
35
Proactive Packets
NAK Response
Total Required Parity
20% loss
35
30
Proactive Packets
NAK Response
Total Required Parity
25
20
15
10
5
Group Number
277
254
231
208
185
162
138
115
92
69
46
23
0
0
277
254
231
208
162
138
Group Number
Group Number
No. of Packets
115
0
277
254
231
208
185
162
138
0
115
0
92
5
69
5
46
10
23
10
92
15
69
15
20
46
20
23
No. of Packets
25
0
No. of Packets
25
30
185
Pro-active Packets
Nak Response
Total Required Parity
30
Sample Results (Experimental)
adec=0.02
adec=2i(0.02)
25
1465
1353
1240
1127
1014
902
789
676
563
451
0
1361
1257
1152
1047
942
838
733
628
524
Group Number
Group Number
25
Proactive Packets
Required Parity
NAK Response
20
15
10
5
1465
1353
1240
1127
902
Group Number
1014
789
676
563
451
338
225
112
0
0
Number of Packets
419
0
314
0
210
5
0
5
338
10
225
10
15
112
15
105
Proactive Packets
Required Parity
NAK Response
20
Number of Packets
20
Number of Packets
25
Proactive Packets
Required Parity
NAK Response
adec=2i(0.02)
lower bound = 1
Subproject: Mobile Composable Filters
 Questions:
can we apply mobile agent concepts to instantiation
and population of proxies?
Can we dynamically insert filters into running
communication streams without disruption?
 Goal: identify and evaluate “glue” mechanisms
needed for dynamic construction of lightweight
proxies in which components are created,
migrated, composed as necessary to
accommodate heterogeneous and dynamic
environments
 Example proxy services: FEC, filtering, web
clipping
Proxy Framework
 Mobile Composable Filters enable proxy filters to be
uploaded and dynamically inserted into (running) data
streams
Control
Thread
PROXY
Endpoint
Endpoint
F1
DIS
F2
F3
DOS
Control
Internal Data Flow
External Data Flow
The Classes
 To facilitate the making and breaking of data flow inside
the Proxy Container – two new classes were created:
DetachableInputStream
DetachableOutputStream
 These streams have all the methods available in
PipedInputStream and PipedOutputStream classes of the
Java2 API.
 They also have additional methods that allow us to handle
diverse data streams.
 The ControlThread communicates with a ControlManager
and implements the proxy management.
 The ControlManager class serves to control the proxy
framework remotely. It can be easily integrated to a
browser.
DIS/DOS Interaction
 Similar to other Java I/O streams, except that
they can be paused, reconnected, restarted
DetachableOutputStream
DetachableInputStream
sink
Data
In
connect(dis)
write( )
flush( )
source
connect(dos)
receive( )
buffer
read( )
available( )
pause( )
reconnect(dis)
pause( )
reconnect(dos)
Data
Out
Current Status
 Presently, we are refactoring various Pavilion
proxy filters to work within the new framework
 Example: FEC insertion in video streams
Location 3
80%
80%
Percentage of Frames Delivered
100%
60%
40%
20%
FEC + NAKs
FEC Only
No Error Control
0%
60%
40%
20%
FEC + NAKs
FEC Only
No Error Control
Time (sec)
Time (sec)
58
55
52
49
46
43
40
37
34
31
28
25
22
19
16
13
7
10
4
1
58
55
52
49
46
43
40
37
34
31
28
25
22
19
16
13
10
7
4
0%
1
Percentage of Frames Delivered
Location 2
100%
Meridian
 Large multi-investigator project supported by
NSF grant
 Goal: Develop an end-to-end, integrated set of
tools that automate the development and
maintenance of interactive distributed
applications
 Case studies from several industrial partners
involving on-board control, web-based
collaboration, mobile telecommunications
Meridian Vision
IDA Models
IDA Constraints
IDA Interface
Requirements
Refined
Specifications
Requirements
Specifications
Model
Editing
Specification
Analysis
Design
Processing
IDA Reuse
Repository
Code
Feedback
User
IDA External
Parameters
Test Cases
Testing/
Simulation
Model Editor
 Supports editing of UML
models.
Incorporates reusable
IDA models.
 Generates formal
representations of the
models
 Supports automated
analysis of graphical
models
Reuse Environment
 Supports browsing/selection from
reuse repositories.
 Component-based:
 Index components by formal

specs
Search and retrieve based on
specs
Tool suite (cont’d)
 Temporal Analyzer:
 Augments UML models with

temporal constraints.
Graphical spec of timing
constraints
 Design Processor:
 Automatically refines UML



models.
Generates code and selects
reusable components
Adapts components to satisfy
interface constraints
Checks consistency between
refinements
Emulation/Simulation of Synthesized
Components
 MX simulator supports emulation of code
identical to that used in experiments, via a
socket-level system call interface
 Provides both C++ and Java APIs
Host
Application
Code
Host/Network
Configuration
File
Process
Thread
Placement
Module
Host
Socket-Level
API
Socket-Level
API
OS Module
OS Module
NIC
NIC
Network Module
(Routing Domains, Wired/Wireless Channels,
Routers, Wireless Access Points, etc.)
Meridian Contributions
 Automates end-to-end development of IDAs
 Extends visual development to encompass formal
reasoning.
 Supports reuse at many levels of abstraction using a
common notation: UML
 Integrates formal analysis and testing/simulation.
 Enables tracing of requirements from diagrams to code
 Facilitates evolution of software to accommodate new
technologies
 Holds promise of “Internet-Speed” development.
Summary
 Pavilion: (present) focuses on communication
protocols for interconnecting heterogeneous
mobile nodes and on reuse of collaborative
components
 RAPIDware: (short term) seeks to develop a
unified methodology for design of adaptive
middleware and automate its operation
 Meridian: (long term) seeks to automate many
aspects of the development of interactive
distributed applications in order to improve their
quality and maintainability
Related Work
 Groupware Toolkits
JETS, Promondia, TANGO, Habanero, DISCIPLE,
MultiTel, and others
 Adaptive Middleware Frameworks
Rover, TAO, MCF, DaCapo++, Odyssey, QuO,
Mobiware, Remulac, Sync, MOST, Limbo, ...
 Configurable Proxies
Transend, MPA, Mobiware, Alpine, Active Names, …
 FEC for multicast
 RMDP protocol (Rizzo and Vicisano, 1998
 NP (Nonnenmacher et al., 1998)
 ECSRM (Gemmell, et al. 1998)
Further Information
 Project descriptions, including related papers and
technical reports, are available at:
http://www.cse.msu.edu/~mckinley
 Email address: [email protected]
 This research was supported in part by National
Science Foundation grants DUE-9551180, CCR9503838 CDA-9617310, NCR-9706285, and CCR9912407, and EIA-0000433.