Comparing Two Dimension-Reduct

M th d f N t k Si l ti M M

eth

o

ds 

for 

N

e

twor

k Simulation 

M

o

image generated using http:/

Kevin Mills & Jim Filliben, NIST Kevin Mills

& Jim Filliben, NIST

Winter Simulation Conference – Dec. 6
Outline

• Goal – Problem – Solution• Dimension Reduction for Multivariate Respo

Dimension Reduction for Multivariate Respo

• Overview of Candidate MesoNet Response• Reduction via Correlation Analysis with Clu• Reduction via Principal Components Analys

Reduction via Principal Components Analys

• Characterization & Comparison of Dimensio

Reduction Techniques Reduction Techniques

• Findings
Goal – Problem – Solution

• Goal

– compare proposed Internet congestion 

algorithms under a wide range of controlled, 

repeatable conditions as simulated by selectirepeatable conditions, as simulated by selecticombinations of parameter values for MesoNeparameter TCP/IP network model

• Problem

– how to determine which MesoNet

responses to analyze when characterizing modb he

havior

• Solution

– apply and evaluate two techniques: 

correlation analysis with clustering & principacomponents analysis
Simulating large, fast networks across many conditions and cong

algorithms requires scale reduction in both model parameters 

Scale Reduction: Theory & Practice

y

1, ...,

yz

= f(

x1|[1,...,

l] ...,

xp|[1,...,

l]

)

ResponseState‐Space Stimulus State‐Space

(232)1000 O(109633) [ 1080 = atomsin visible universe]

Multidimensional Response Parameter 

Reduction (2 )

Discardparameters not germane to study – reduce by 944 parameters

O(10 ) [ ]

(232)56 O(10539)

20

Group related remainingparameters– reduce by 36 param

22 Responses

CorrelationAnalysis &Clusterin

g

PrincipalComponentsAnalysis

Talk on We

Use experimentdesign the

bi i 

220

(232)20 O(10192)

O(10

6)

Model Reduction

Select only 2 valuesfor each parameter

Level Reduction

g

7 Responses 4 Responses

Domain

Analysis

parameter combinationsto 

Use sensitto identity 

significant

220‐12 Experiment 2

Design Theory

Sensitivity

7 Responses Analysis

This Talk

Previous Talk

Use experimentdesign theo

parameter combinationsto 3
The Dimension-Reduction Problem 

Multivariate Responses

Fodor, I.K. 2002. A Survey of Dimension Reduction Techniques. La

“given the 

r-dimensional random variable x = (

x1,..., 

xr

)T, find a 

Livermore National Laboratory Technical Report no. UCRL-ID-1484

dimensional representation, s = (

s1,..., 

s

k)T with 

k

<

r, that capt

the content in the original data, according to some criterion.”

Fodor identifies principal components analysis (PCA) as the beterms of mean-square error) linear dimension reduction techn
We Applied & Compared 2 Different Tec

Principal

Components

A li

m responses (y

1, ...

y

m)

Analysis

m

–

d

1 responses Domain

Expertise

m responses (y

1, ...

y

m)

Analysis

m

–

d

1 responses Domain

Expertise

m responses (y

1, ...

y

m)

Analysis

m

–

d

1 responses Domain

Expertise

Correlation

m

–

d

2 responses Expertise

m

–

d

3

responses

Correlation

m

–

d

2 responses Expertise

m

–

d

3

responses

Correlation

m

–

d

2 responses Expertise

m

–

d

3

responses Analysis

DATA SCIENTIFIC SCIENTIFIC

& Clustering

DOMAIN

EXPERTISE

ANALYSIS

EXPERTISE

SCIENTIFIC

DOMAIN

EXPERTISE

ANALYSIS

EXPERTISE
Overview of (r = 22) Candidate MesoNet R

Response Definition 

y1 Active Sources – sources attempting to transfer data y2 Proportion of total sources that are active: Active Flows/All Sourcy3 Data packets entering the network per second y4 Data packets leaving the network per second Data packets leaving the network per secondy5 Packet Loss Rate: y4/(y3+y4) y6 Flows Completed per second y7 Flow Completion Rate: y6/(y6+y1) y8 Connection Failures per second y9 Connection Failure Rate: y8/(y8+y1)

y10 Retransmission Rate (ratio) y11 Average Per Flow Congestion Window (packets) y12 Average Number of Increases in Congestion Window Per Flow Pey13 Average Number of Negative Acknowledgments Per Flow Per Secy14 Average Number of Timeouts Per Flow Per Second y15 Average Round-trip Time (ms) y16 Relative Queuing Delay (y15/average propagation delay) y17 Average Throughput (packets/second) for DD Flows y18 Average Throughp Average Throughput (packets/second) for ut (packets/second) for DF Flowsy19 Average Throughput (packets/second) for DN Flows y20 Average Throughput (packets/second) for FF Flows y21 Average Throughput (packets/second) for FN Flows y22 Average Throughput (packets/second) for NN Flows 
64 x 22 Multivariate Data Set Resulting fro

211-5 Ortho

g p

onal Fractional Factorial Ex

perimen

Run y1 y2

... y21 y22

1 4680.619 0.168126

... 92.034 89.78

2 6654.512 0.239371

... 72.596 57.73

3 9431 405 9431.405 0 339259 0.339259

... 29 569 . 13 96

.

4 11565.81 0.415439

... 23.427 19.88

... ... ...... ... ...

61 10319.55 0.247471

... 87.969 41.57

62 1738.469 0.093668

... 159.298 161.60

63 1783.509 0.096094

... 148.395 161.3

64 21467.6 0.514811

... 26.159 9.98
Reduction via Correlatio

Analysis & Clustering (CA
Correlation Analysis – Par

Red 80 > |r|x100 < 100 Blue 30 > |r|x100 < 80 Green |r|x100 < 30 

Pair-wise Correlation Matrix
Correlation Analysis – Par

Hi t bi h | | 0 65 hi hli ht d i Hi

s

togram: bins w

here |r| > 

0.65 hi

ghli

ght

e

d in 
Clustering: Response Index-Index Plot where |r

Clustered into Mutual Correlations

2 responses uncorrelated

(1) throughput on DD flows

(2) flow completion rate

flow completion rate

14 correlationpairs reflectingpacket losses packet losses

3 pair-wise correlations:

(1) throughput on flows constrained by 

F-class 

(2) net ork dela net

work dela

y

(3) packets entering and leaving the network

Plot suggests MesoNet exhibits 7 distinct behavioral dimen
Correlation Analysis & Clustering Suggests MesoN

Can be Represented using only 7 Respons

CAC 

Dimension Responses 

C i on

gestion y1 2 7 11 12 19 21 , y2, y7, y11, y12, y19, y21, y22

Losses y5, y8, y9, y10, y13, y14 Delay y15, y16 F-class Throughput y18, y20D-class Throu

ghput y17 

Packet Throughput y3, y4Flows Per Second y6 

Using subjective, domain-specific reasoning, a domain analyst s

response to represent each cluster
Principp 

al Components Ana
Principal Components Analysis of 22 MesoNet Re

(a) Distribution of Variance Distribution of Variance (b) Weight Vector Matrix Weight Vector Matrix

PC Std. Dev. Cumulative % Response PC1 PC2 PC3 PC4 ... 

PC1 9.7091 0.441325 y1 0.2581 0.1421 -0.1667 0.1126 ... PC2 4.0161 0.62388 y2 0.2608 0.1768 -0.1407 0.1058 ... PC3 3.2322 0.77079 y3 0.0864 0.0218 -0.4163 -0.3909 ... PC4 2.0630 0.86457 y4 0.0435 0.0617 -0.4252 -0.4037 ... PC5 0.9716 0.90873 y5 0.2774 -0.2276 0.0363 0.0644 ... PC6 0.7585 0.94321 y6 -0.039 0.0914 -0.1246 -0.5636 ... PC7 0.4537 0.96383 y7 -0.284 -0.1358 0.1004 -0.0815 ... PC8 0.2569 0.97551 y8 0.2261 -0.2452 0.0444 0.0589 ... PC9 0.1835 0.98385 y9 0.2358 -0.2775 0.0635 0.0236 ... 

PC10 0 1254 . 0 98955 0.98955

y10 0 2706 . -0 2395 . 0 0344 . 0 0704 . ... 

PC11 0.0588 0.99222 y11 -0.245 -0.0838 -0.1081 0.0797 ... PC12 0.0504 0.99451 y12 -0.283 -0.167 -0.0036 0.0441 ... PC13 0.0360 0.99615 y13 0.2241 -0.2678 -0.0174 -0.1225 ... PC14 0.0286 0.99745 y14 0.2387 -0.2965 0.0218 -0.0815 ... PC15 0 0225 . 0 99847 0.99847 y15 0 0429 . 0 4426 . -0 0415 . 0 1868 . ... PC16 0.0113 0.99899 y16 0.0457 0.3242 -0.2348 0.3085 ... PC17 0.0099 0.99944 y17 0.0682 -0.2008 -0.3694 0.2058 ... PC18 0.0060 0.99971 y18 -0.064 -0.1636 -0.4271 0.2485 ... PC19 0.0032 0.99985 y19 -0.287 -0.1679 -0.0805 0.024 ... PC20 0.0019 0.99994

y20 -0.084 -0.1519 -0.3983 0.2356 ... 

Most response variance appears to be accounted for by the first 

4 

components (depending on the threshold selected) we highlight com

y

PC21 0.0011 0.99999 y21 -0.29 -0.1716 -0.0989 0.0413 ... PC22 0.0002 1.00000 y22 0.2581 -0.1667 -0.0332 0.0308 ... 

components (depending on the threshold selected), we highlight com

to align with the number of responses suggested by the CAC 
A

1 X = 1 PC1 1 PC2

MAX = 1

One Approach to Identify Variables to Include i

0.5

0.75

Weight| scaled MA 0.5 0.75

d Weight| scaled M

0

0.25

0 2 4 6 8 10 12 14 16 18 20 22

Response Identifier (y1-y22)

|Standardized W

0

0.25

0 2 4 6 8 10 12 14 16 18 

Response Identifier (y1-y22)

|Standardized

Response Identifier (y1 y22)

0.75

1

PC3

| scaled MAX = 1 0.75

1

t| scaled MAX = 1PC4

0

0.25

0.5

andardized Weight|

0

0.25

0.5

andardized Weight 0 2 4 6 8 10 12 14 16 18 20 22

Response Identifier (y1-y22)

|Sta

|St 0 2 4 6 8 10 12 14 16 18 a

Response Identifier (y1-y22)
Principal Components Analysis Suggests MesoNet B

be Represented using only 4 Responses

PCA 

Dimension (PC) ResponsesCongestion y1, y2, y5, y7, y8, y9, y10, y11, y12, y13, y14, y19, y21, y22 Delay y15, y16 D-class & class

&

F-class

Throughput y3, y4, y17, y18, y20 

Flows Per Second y3, y4, y6 

H h ld b d t t f th PC ?How might an analysis select responses to represent PCs?Jolliffe (2002) suggests that the number of variables to select should equal the number oaccount for the most variance (4-5 here), or perhaps a few more (6 or 7 here).How many responses

s

hould b

e used t

o account for th

e PC

s

?

How might an analysis select responses to represent PCs?

(1) MKB heuristic [Mardia, Kent and Bibby,1995]: iterates over the weight vectors from th

(PC22 here) to the most significant (PC1). When examining each weight vector, the recorresponding to the weight with the largest magnitude is discarded from further consi

process process continues until the remaining number continues until the remaining number of responses corresponds to the numbe

responses corresponds to the numbe

of variables sought.

(2) JJF heuristic inverts the MKB heuristic: iterates over the weight vectors from the m

the least significant. When examining each weight vector, the variable corresponding tthe largest magnitude is withdrawn from further consideration. This process continues 

of the set of withdrawn responses equals the number of variables sought. The set of w

constitutes the responses to be used in subsequent analyses.
Comparing Correlation & PCA Res

PC JJF Heuristic MKB Heuristic CAC Domain 

PC1 Y22 (NN flow TP) Y4 (packets output) Y22 (NN floPC2 Y15 (SRTT) Y19 (DN flow TP) Y15 (SRPC3 Y18 (DF flow TP) Y18 (DF flow TP) Y4 (packets PC4 Y6 (flows completed TP) Y6 (flows completed TP) Y6 (flows completed TP) Y6 (flows completed TP) Y6 (flows com

Y6 (flows com

PC5 Y11 (CWND) Y9 (connection failure rate) Y10 (retransmiPC6 Y17 (DD flow TP) Y17 (DD flow TP) Y20 (FF floPC7 Y16 (queuing delay) Y16 (queuing delay) Y17 (DD floPC8 Y13 (NAKs) Y13 (NAKs) N/A PC9 Y1 (act Y1 (active sources) ive sources) Y11 (CWND) Y11 (CWND) N/A

PC10 Y14 (timeouts) Y15 (SRTT) N/A PC11 Y2 (% sources active) Y7 (flow-completion rate) N/A PC12 Y9 (connection failure rate) Y2 (% sources active) N/A PC13 Y10 (retransmission rate) Y10 (retransmission rate) N/A PC14 Y8 (connection failures) Y8 (connection failures) N/A PC15 Y7 (flow-completion rate) Y14 (timeouts) N/APC16 Y12 (CWND increases) Y12 (CWND increases) N/A PC17 Y21 (

F

N flow TP) Y1 (active sources) N/A 

PC18 Y20 (FF flow TP) Y21 (

F

N flow TP) N/A 

PC19 Y19 (

D

N flow TP) Y20 (FF flow TP) N/A 

PC20 Y4 (packets output) Y4 (packets output) Y22 (NN flow TP) flow TP) N/APC21 Y5 (loss rate) Y5 (loss rate) N/A PC22 Y3 (packets input) Y3 (packets input) N/A 
Characterization & Com

pa

of 

Dimension Reduction Techn
Correlation Analysis & Clusterin

• Provided effective dimension reduction (22 

→ 7) throu

Pros

correlations that could be vetted by a domain expert

• Examining response correlations helped to validate Mes

• Uncovered nuanced differences between flow and pack

throughput rates in a network

Cons

• A second 211-5 OFF experiment with different level set

revealed some (valid) differences in correlations – thus 

l i l b d d f diff l 

Cons

correlation analyses must b

e con

ducted for different le

settings
Principal Components Analysis

Pros

• Provided greater dimension reduction (22 

→ 4 or 5) th

analysis & clustering

Cons

• There is no specific domain interpretation of even the 

principal components – in the case shown here we were 

at a reasonable interpretation at a reasonable interpretation; in other cases ; in other cases we were 

, we were 

• Principal components analysis depends on seemingly arb

threshold selections to determine which PCs to include 

responses to use to represent PCs

• Principal components proved coarser than correspondin

generated by clustering mutual correlations

• A second 2 A second 211-5 OFF experiment with different level set

11-5 OFF experiment with different level set

revealed some differences in principal components – sudifferences are difficult to understand without assistother analyses 
Correlation Analysis or PCA?

• If limited to one technique, correlation analysis provide

easier for a domain anal

y p st to com

prehend

• Principal components take on + and – values, which prese

domain analysts with difficulty assigning meaning – we hinfer meaning by comparing main effects plots of princ

components with main effects plots from responses chogroupings established by correlation analysis

• Principal components proved coarser than correspondin

groupings generated by clustering mutual correlations

• PCA provides a reasonable complement to correlation a

giving a separate view of the data, which should be conswith correlation results, thus helping to validate a mode
Findings

• We investigated correlation and PC analyses a

techniques to reduce the dimension of responfr m o MesoNet, a / n tw r mu at r TCP

/IP n

etw

o

r

k simulat

o

r

• We demonstrated that both techniques can 

significantly reduce the dimension of respons

• We found that both techniques could be used 

validate a model, but that PCA is more suited complement correlation analysis

• W f d h PC l d ff l f 

W

e found 

t

hat PC

A results are difficult for

a 

analyst to interpret without comparison to anof individual responses

• We also found that results from correlation a

analyses with one set of parameter values cannecessaril

y p ff 

 be extra

polated to a different se

values generated from different parameter s