JAIST Repository
https://dspace.jaist.ac.jp/Title

Building Foundations for Dependable Systems(Preliminary Version)

Author(s)Schlichting, Rick

CitationIssue Date

2005‑03‑11

TypePresentation

Text version

publisher

URL

http://hdl.handle.net/10119/8277

RightsDescription

JAIST 21世紀COEシンポジウム2005「検証進化可能電子社会」 = JAIST 21st Century COE Symposium 2005
Verifiable and Evolvable e‑Society , 開催：2005年3月10日〜11日, 開催場所：石川ハイテク交流センター, Technical session 5 <Dependable
Infrastructure>

Japan Advanced Institute of Science and Technology

Building Foundations forDependable Systems

Work done in collaboration with:y Matti Hiltunen (AT&T)
y Former Arizona PhD student Jun He (Cisco).
y UIUC PhD student Kaustubh Joshi (AT&T VURI intern) and(Preliminary Version)faculty member Bill Sanders.

Rick Schlichting
Software Systems Research Department
AT&T Labs-Research
Florham Park, NJ 07932, USA

2Motivation© Copyright 2005 AT&T. All Rights Reserved

Next Generation Information Infrastructurey Moving towards an e-society based on information systems

y Characteristics

and networks.

– Multiple machines connected by networks.
– Spectrum of network types and technologies: wired, optical,wireless, ….
– Spectrum of distances: local-area, metro-area, widearea,….

Our Society– Spectrum of devices: from sensors to mobile units to highend machines and clusters.
– Spectrum of applications.
– Dynamic execution conditions and resource demands.
– Multiple administrative domains.

Social Infrastructure Information System

3© Copyright 2005 AT&T. All Rights Reserved

Dependability° MUST be dependable!
4System Abstractions

y Definition: The trustworthiness of a computing system such thaty System abstractions can simplify the process.
y Definition:

reliance to be justifiably placed on the service it delivers.
(Laprie, et al., Dependability: Basic Concepts and Terminology, Springer-Verlag, 1992)

y Includes many properties and attributes.
–––––– Simplified model of a real-life hardware/software component or function.

Reliability
Availability
SafetySecurity
Timeliness– Extracts essential features while omitting unnecessary detail.

y Goal: Building blocks for constructing more complex
systems.

y Non-functional or Quality of Service (QoS) attributes.

y Have long been used to as a way to simplify the design of– Focus is not on how something gets done, but rather how well.

complex systems.

y Immensely challenging to build software with these attributes!

y “Classic” examples:– Failures, intrusions….
– Concurrent and non-deterministic execution– Process, file, virtual memory,….

– Heterogeneous systems and networks– Layered operating system architectures (e.g., THE system).

– Resource constraints°Good abstractions are those that people use without
thinking about the underlying implementation.

– Multiple administrative domains– Scaley Dealing with multiple attributes makes it even harder (multidimensional QoS).
y Fundamental issue is complexity.
5© Copyright 2005 AT&T. All Rights Reserved© Copyright 2005 AT&T. All Rights Reserved

6© Copyright 2005 AT&T. All Rights Reserved1What about Dependability?
y Certainly some good dependability-related abstractions.
– Provide enhanced QoS characteristics.

y Hardware virtualization.
– Stable storage: abstract storage that never fails.
– Fail-stop processor: virtual processor whose only failure is a detectablecrash.

y Services for networked systems.
– Often focus on providing common global information across machines
despite machine and network failures (virtual shared state).
– Implemented as middleware and/or using network protocols.
– Consistent global clock: abstraction of a single system-wide clock.
– Atomic multicast: shared message queue– Distributed atomic actions (transactions): all or nothing execution acrossmachines.

y Can also be organized as layers or hierarchies.

7© Copyright 2005 AT&T. All Rights Reserved

8© Copyright 2005 AT&T. All Rights Reserved

CHANGED USERREQUIREMENTS

Challenges and Issues

Battery Power

Secure/Survivable

y Abstraction failures (leaky abstractions).
– Impossible to implement an abstraction in which QoS properties hold under
all conditions.

INTRUSIONS

Available– Inherently probabilistic.

y Composing abstractions.

Memory– Reasoning about properties of combinations of abstractions.
– Conflicts and tradeoffs between different attributes.

CPUReliable– Performance overhead.

y Unnecessary attributes.

Predictable
Adaptable– Matching attributes of abstractions to application and execution environment.
– Unnecessary attributes can mean extra execution overhead.

Maintainabley Changing QoS attributes dynamically.
– Providing ability to adapt at runtime

CHANGES IN
AVAILABLERESOURCES
9© Copyright 2005 AT&T. All Rights Reserved

CHANGED USERREQUIREMENTS

10Battery PowerINTRUSIONS

MemoryAvailable

Secure/Survivable

Middleware© Copyright 2005 AT&T. All Rights Reserved

Provide support for building system abstractions
and services that bridge the gap between network
and application.
y Support for configurable solutions

CPU– Ability to customize properties to the characteristics of the execution
environment and the needs of the application.

Adaptabley Support for adaptive behavior

Protocols

Predictable

FAILURES

Dependable Systems Research at AT&T

APPLICATION

Reliable

Network Bandwidth– Ability to change execution behavior dynamically to react to changes in theexecution environment or the application.

Maintainable

Cactus ¾ configuration and customization

OSCholla ¾ adaptation
CHANGES IN
AVAILABLERESOURCES
11© Copyright 2005 AT&T. All Rights Reserved

FAILURES

Network Bandwidth12© Copyright 2005 AT&T. All Rights Reserved2Cactus: Building Highly Configurable
SoftwareCactus Approachy Both a programming model and an implementation

Messages/ Method invocations

Composite/Traditional Protocol

framework for building customized software from collectionsof software modules.

Composite protocol

Customizable API

y Highlights:– Fine-grain configuration and customization.
– Multiple types of attributes and properties, each implemented by a collectionof alternative modules.
– Combination of hierarchical and non-hierarchical composition.

y Focus:– Communication-oriented services in networks, i.e., protocol stacks anddistributed services (but more general).

Shared data Micro-protocols
structures
Reliability
Messages

EventsMsg from above
Msg from below

Total order
Hash tables etc.

Site failure

Integrity

Msg timeout

Event handlers– Highly customizable Quality of Service (QoS) attributes related to fault
tolerance, timeliness, security, etc. (but useful for other reasons).

Customizable API
Messages/ Method invocations

y Addresses challenge of module interaction in highlyconfigurable software.
13

QoS requests/Notifications

QoS requests/Notifications

Composite/Traditional Protocol© Copyright 2005 AT&T. All Rights Reserved

14

Cactus Model© Copyright 2005 AT&T. All Rights Reserved

Example Protocols and Services
y Configurable Transport Protocol (CTP)y Protocol/service = composite protocol.

– Ordering, reliability, flow/congestion control, security.

– Provides service-specific API.

y Secure and Survivable Communication (SecComm)y Property/QoS attribute = micro-protocol (MP).

– Privacy, authenticity, integrity, replay prevention, combinations.

y Configurable Quality of Service (CQoS)– MPs interact using an events, shared data, and dynamic messages.
– Mechanisms provide decoupling of MPs ⇒ configurability.

– Adding transparent multi-dimensional QoS customization to distributed object systems.

y Service customization = choose appropriate MPs.

y Distributed System Monitoring Service (CDSMon)y Dynamic adaptation = load/activate/deactivate MPs at

y Location-Based Services (LBS)– Function to be monitored.

– Functionality based on location for mobile services.

runtime.

y Ad-Hoc Networking (AHN)

y Two implementations of Cactus 3.0.

– Dynamic QoS

y AT&T Enterprise Messaging Network (EMN)– C version running on different variants of Unix.
– Java version.

– Per request QoS for mobile service platforms

y Others– RTD channels, group RPC, membership, configurable DSM,….
15© Copyright 2005 AT&T. All Rights Reserved

16

Adaptive Systems

CQoS Architecture (Jun He)
Client Application

Server Application

CQoS

CQoS

Dynamically changing system behavior.

CQoS
CQoS
Interceptor

CQoS
ServiceCactus

y CQoS consists of two components:– Application and platform-specific CQoS interceptor generated from IDL.

Motivation:y Short term ⇒ react to changes in the environment: failures, spam/virus/worm attacks,flash crowds, change in wireless connectivity, intrusions

Middlewarey Long term ⇒ system evolution: updating hardware, software, configuration over time

Adaptive actions:y Micro-protocols include:• Fault tolerance: ActiveRep, PassiveRep, TotalOrder, MajorityVote,Membership, StateRecovery… .
• Security: DESPrivacy, Authentication, AccessControl …
• Timeliness: PrioritySched, QueueSched, TimedSched.

configuration, video frame rate,spam definitions (valueadaptations)y Change software modules: videoencoder, caching (algorithmicadaptations)

Action 1...

...
AlertsMonitoring
infoAction mMonitor nCommands

Adaptation Control SystemTraining

y Change resource allocation:
bandwidth, CPUs (resourceadaptations)y Semantically different combinations of micro-protocols
provide semantically different variations of multidimensional QoS.
© Copyright 2005 AT&T. All Rights Reserved

Monitor 1

y Change parameters: router– Generic CQoS service component implements customizable QoS usingCactus.

17© Copyright 2005 AT&T. All Rights Reserved

18© Copyright 2005 AT&T. All Rights Reserved3Cholla Adaptation Architecture

Execution Control Feedback Loop
Each phase can be complex inlarge networked systems:yMonitoring involves data acrossMonitory

Adapt

Analyzey Support for value and/or algorithmic
adaptations.

multiple hosts and multiple
sources.
Analyzing may involve heuristics orevaluation over time.

yDecision may involve evaluating
tradeoffs or distributed algorithms.

yAdaptation may involve distributed
coordination across multiple hosts.

y Challenges:– Decoupling control from regular functionality.
– Coordinating adaptations» Inter-component coordination on a single host» Inter-host coordination for distributed services– Composition of adaptation policies.
All must be done in arunning system and anenvironment that continues
to change.

Decide– Developing appropriate adaptation policies.
– Efficient realization of policies.

y Solution: Cholla adaptationarchitecture

Adaptation mechanisms versus policies:••
19

Mechanisms provide hooks for monitoring and effecting changes as well as
protocols for data collection, analysis, and adaptation coordination.
Policy encapsulates tradeoff analysis and “business logic”.

– Uses Cactus as underlying platform for
implementing adaptive mechanisms and protocols.

© Copyright 2005 AT&T. All Rights Reserved

20

Power
Availability

CPU
Availability© Copyright 2005 AT&T. All Rights Reserved

Software Architecture

VideoSender

Video
DisplayVideo
Display

Transport
ProtocolTransport
ProtocolTransport
ProtocolSessionProtocolAdaptation
Controller

IP

IP

IP

Network
DeviceNetwork
DeviceNetwork
DeviceAdaptation
Controller

Operating System
Network
Congestion
21© Copyright 2005 AT&T. All Rights Reserved

22

Adaptation Controller

Adaptation Controller
Control and inter-component coordination

Vid Sender
MetaController© Copyright 2005 AT&T. All Rights ReservedVideoSendery Implements execution feedback control loop:– Monitors system state and controls adaptation.

y Monitoring:Controller– Input variables from controlled components.

Trans ProtController– Input from external monitoring.

y Control:– Generates outputs based on inputs plus adaptation policies.

Agreement

SecureAdap.Fastmp
Adap. mp
Graceful
Adap prot– Changes execution parameters in controlled components (valueadaptations).
– Orchestrates module changeovers (algorithmic adaptations).

y Implementations:TransportProtocol– FLAC: Fuzzy logic based adaptation controller. Focuses on value
adaptations and inter-component coordination.

Inter-host coordination– CAC: Cactus based adaptation controller. Focuses on algorithmic
adaptations and inter-host coordination.
– Others possible….

IP
23© Copyright 2005 AT&T. All Rights Reserved

24© Copyright 2005 AT&T. All Rights Reserved

4Policy Generation

Conclusions and Future Work

(Kaustubh Joshi, Bill Sanders)y Goal: Use stochastic models of system and environment toy Useful system abstractions are the key to building a highly
dependable information infrastructure for e-society.

generate optimal policies for selecting adaptive actions.
Policycomputation

StatePolicy
Lookup
TableController

Model

Parameter
Estimation

Systemy Our research is addressing issues related to building such
abstractions:

AdaptiveAction– Cactus: flexible fine grain configuration based on two-level composition model.
– Cholla: Control and coordinated adaptation.

Measurement

Off-line Model
Specification Tooly Future work
– Using Cactus and protocols/services built using Cactus.
Human Designer– New protocols for cross-host coordination.
– Policies, policies, policies!

y Formulation of the problem as a Markov Decision Process– Must deal with state space explosion: state aggregation, model decompositiony Currently applying to AT&T EMN system.
25© Copyright 2005 AT&T. All Rights Reserved

26© Copyright 2005 AT&T. All Rights Reserved

For More Information
Bhatti, Hiltunen, Schlichting, and Chiu. Coyote: A System for Constructing Fine-Grain
Configurable Communication Services. ACM Trans. on Computer Systems 16, 4 (Nov.
1998), 321-366.
Chen, Hiltunen, and Schlichting, Constructing Adaptive Software in Distributed Systems.
Proc. 21st Conf. on Distributed Computing Systems (ICDCS), (April 2001), 635-643.
Wong, Hiltunen, and Schlichting. A Configurable and Extensible Transport Protocol. Proc.
Infocom 2001, (April 2001), 319-328.
Hiltunen, Schlichting, and Ugarte. Building Survivable Services using Redundancy andAdaptation, IEEE Trans. on Computers (February 2003), 181-194.
He, Hiltunen, Rajagopalan, and Schlichting. Providing QoS Customization in Distributed
Object Systems, Software-Practice and Experience 33,4 (April 2003), 295-320.
He, Hiltunen, Schlichting. Customized Dependability Attributes for Mobile Service
Platforms. Proc. DSN-2004 Dependable Computing and Communication Symp. (June2004), 574-583.
Joshi, Hiltunen, Sanders, Schlichting, and Agbaria. Online Model-Based Adaptation for
Optimizing Performance and Dependability. Proc. WOSS ‘04 (Oct 2004).
Hiltunen, Schlichting. The Lost Art of Abstraction. Proc. DSN Workshop on Architecting
Dependable Systems, Springer-Verlag LNCS, 2005, to appear.

27© Copyright 2005 AT&T. All Rights Reserved5