A Program of Work for Understanding E

A Program of Work for Understanding E

Behavior in Global Grid System

Behavior in Global Grid System

Chris Dabrowski & Kevin Mills 

National Institute of Standards and Technolo

February 13, 2006
March/2006 

 What are emergent behaviors? Why are emergent behaviors likely in global grids Can emergent behaviors be elicited or controlled? How are NIST researchers investigating these qu Case study: denial-of-service (DoS) attack on sim

Outline
March/2006 

What are emergent behaviors

Emergent behaviors are

coherent system-wide properties

that cannot be deduced directly from

analyzing behavior of individual component

Emergent behaviors typically arise in

dynamic open complex adaptive systems

where system-wide behavior derives from

self-organizing interactions among myriad comp
March/2006 

Some Dynamic Open Complex Adaptive 

http://www.sover.net/~kenandeb/fire/hotshot.html http://autoinfo.smartlink.net/quake/quake.htm http://www.wtopnews.com/

http://www.avalanche.org/

http://www.ics.uci.edu/relations/develop/rs2001/teitelbaum/sld012.htm

http://www.english.uiuc.edu/maps/depression/photoessay.htm

© http://www.nationalgeographic.com/ ©http://www.waag.org/realtime/
March/2006 

How might a complex system be detec

fractal patterns

http://www.mbfractals.com/usergal/dougowen.html

self-similarity

http://www.physionet.org/tutorials/fmnc/node3.html

ON = ParetoOFF = expone

linear w

ON = ParetoOFF = exponeON = ParetoOFF = expone

linear w

1/f noise

© J. Davidsenand H.G. Shuster 2000

http://complexity. orcon.net.nz/powerlaw.html http://heseweb.nrl.navy.mil/ga

power laws

Other ideas include: decrease in entropy or changes in statistica
March/2006 

What characteristics might lead to a complex 

 System Scale – order emerges from many interactio

space and time

 Communications Locality – inability to know globa Element Simplicity – inability to process all possible  Feedback – elements can sense environment and es

global state

 Element Autonomy – each element can vary its be

based on feedback
March/2006 

Why are emergent behaviors likely in globa

 Scale: large number of clients and services interacting vi

coupling arising through use of shared resources

 Communications Locality: clients cannot obtain complete 

timely state of all resources – decisions must be made on information

 Element Simplicity: clients possess limited processing po

decisions must be made with heuristics

 Feedback: clients learn fate of resource requests and ad

subsequent requests based on updated information

 Element Autonomy: clients decide how to proceed with n

control or direction
March/2006 

Can emergent behaviors be elicited or co

Remains an open research question, for example:

– NASA exploring emergent programming to increase adaptability 

survivability of future spacecraft (see Kenneth N. Lodding, 

“Hitchhikers Guide to Biomorphic Software”, ACM Queue vol. 2, 

– MIT exploring amorphous computing where systems structure a

specialize themselves from a common set of components

(http://www.swiss.csail.mit.edu/projects/amorphous)

– Radhika Nagpal (Harvard) studying how to engineer and unders

organizing systems (http://www.eecs.harvard.edu/~rad)

– Several researchers exploring application of economic mechan

as markets, auctions, and present-value calculations, as means effective behavior in distributed systems
March/2006

How are NIST researchers investigating these qu

1

51

101

151

201

251

301

351

401

451

501

551

601

651

701

751

801

851

901

951

1001

1051

1101

1151

1201

1251

1301

1351

1401

1451

S1

S7

S13

S19

S2

0

5

10

15

20

25

30

35

40

45

50

No. Get Template Requests

Time DSF

NSS 90 % Load

Goals

• Understand self-organizing properties 

in service-oriented architectures (SOA)

• Investigate mechanisms to shape

emergent behavior in SOA

• Improve related consortia specifications 

w.r.t. robustness, reliability, performance

Technical Approach

• Apply modeling and an

techniques from the phy

• Exploit exploratory data 

and visualization metho

• Investigate control tech

biology and economics

Space-Ti

me-State

Evo

l

ution

Project Phases

• Micro-model: 10

3 to 104 

based on selected indu

• Macro-model: 10

4 to 10

model containing selectvalidated against micro
March/2006 

Architecture of Global Compute Grid

1. PUBLISH PROVIDER DESCRIPTION

 2. DISCOVER PROVIDERS

PROVIDER

SITE

CLUSTER

SERVER

SCHEDULER JOB MANAGER

LOCAL

DIRECTORY

3. GET AVAILABILITY

4. NEGOTIATE USAGE

5. TRANSFER INPUT DATA

6. MONITOR

 EXECUTION

CLIENT

GLOBAL DIRECTORY

INTERNET
March/2006 

Micro-model conception

Layered Component Architecture

Network Layer: sites located in (x,y,z)-space used to compute d

and simulate transmission delays;TCP-like simulated transport model CPU delays, buffer & port capacity

Basic Web Services: WS- Addressing and Messaging

WSRF: WS- Resource Property, Lifetime, Notification, Topics, SGrid Services: MDS v4, WS-Agreement, and DRMAA

Major Grid Entities

Service Providers: negotiate, schedule, execute, and monitor cli

vector or cluster computers maintained at a related site 

Clients: discover providers, rank discoveries by earliest availabi

agreements, submit & monitor jobs

Client Grid Applications 

Application types: workflows of n sequential tasks, each with pa

computations – dependent tasks may not start until preceding ta

Tasks: types defined by tuple (required code, task parallelism, c

and matched to processor component with suitable code and pa

Workload: represented as a percentage of system capacity – re

assignment of applications to clients
March/2006 

Schematic showing operation of simulate

Scheduler

Task

Control

Negotiation

Control

DSI

Grid Processor

Service 

Negotiator

Agreement

Grid Processor Grid 

DSI

Service 

Negotiator

Agreement

Execution 

Control

CLIENT

Application

Client 

Negotiator

Task 1

Discovery

Control

Task 2

Grid Processor

DSI

Service 

Negotiator

Agreement

Client 

Negotiator

Task 3

Task

Control

Negotiation

Control

Application

Task 1

Discovery

Control

Task 2

Scheduler

DRMS 

Front-End

F

DRMS 

Front-End

DRMS 

Front-End

DSF

spawns

spawns

negotiates

negotiates

monitors

monitors

requests 

reservation

spawns

Supervisory Process Supervisory Process

spawns

GIIS

GRISGIIS

ProviderSite

ClientSite
March/2006 

Case Study: DoS Attack on Simulate

• Deploy simulated topology: 200 nodes covering 30 provid

12 clients, where each client uses one of two negotiation 

• Negotiation strategies: serial reservation requests (SRR) 

concurrent reservation requests (CRR)

• Run baseline: 50% workload for 200,000 simulated seco

measure the distribution of job completion times

• Repeat run: inject service-provider spoofing with probabi

effectively reduces system capacity by half on average

• Repeat run: identical spoofing but introduce a strategy to 

spoofing: identify spoofers and do not repeat interactions 

1. Which negotiation strategy is more effective under norma2. Does the outcome change under attack?3. Does the outcome change when resisting attack?

Three Questions of Interest
March/2006 

Bottom Line

1. CRR performs slightly better than SRR under normal co2. CRR performs significantly better than SRR under attac3. Surprise: both CRR and SRR perform worse when resis

and the performance of CRR deteriorates more than SR

The surprise arises because scheduling and execution of j

the global grid is an emergent behavior arising from a self-or

property of distributed resource-management algorithm
March/2006 

0.000.100.200.30

100002000030000400005000060000700008000090000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 >200000

Time

Probability

Comparative distribution of application completion times for two negoti

(over 200+ repetitions)

Serial Reservation Requests (SRR) vs. Concurrent R

Requests (CRR) with No Spoofing

Concurrent Reservation Requests

Serial Reservation Requests
March/2006 

Performance Degradation caused by Spoofing in G

50% clients use SRR and 50% use CRR

0.000.100.200.30

100002000030000400005000060000700008000090000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 >200000

Time

Probability

(a) No Spoofing

(b) Spoofing without Resistance 

(c) Spoofing with Resistance

(SURPRISE)

Comparative distribution of application completion times: (a) No Spoofi

without Resistance, and (c) Spoofing with Resistance (200+ rep
March/2006 

Decomposing performance degradation caused by 

0.000.100.200.30

100002000030000400005000060000700008000090000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 >2000

Time

Probability

Spoofing without Resistance for CRR 

Spoofing without Resistance for SRR

Spoofing with Resistance for CRR

Spoofing with Resistance for S
March/2006 

0

50

100150200250300

17

13

19

25

31

37

43

49

55

61

67

73

79

85

91

97

103

109

115

121

127

133

139

145

151

157

163

169

175

181

187

Time

Amplitude

Two Time Series: (a) Reservations Created without Resistanc

(b) Reservations Created with Resistance – 50% clients SRR and 

Aggregate Reservations Created over Tim

under Spoofing with and without Resistanc

(a) Without 

Resistance

(b) With Resistance
March/2006 

Time Series for Application/Task Completions: Two 

Types without Resistance (lower blue) vs. with Resistan

Time

Amplitudes

Time

Amplitudes

Serial Reservation Requests (SRR) Concurrent Reservation R

Application 1 Application 2 Task2 Task1 Task3 Task2

Task1

Tim e

Amplitudes

Task2

Task1

Application 1

Tim e

Amplitudes

Task3

Task2

Application 2 Task1 Earlier

Earlier

Later

Later

La

La
March/2006 

Conclusions

 Global Grids will be dynamic open complex adapt

systems with self-organizing properties leading to behaviors

 Changes made to behavior in individual compone

have pervasive and unexpected effects on global 

 We need to develop a science of complex informa

systems in order to predict and control macroscopbehavior