| 1 | package de.uka.ipd.sdq.reliability.solver.pcm2markov; |
| 2 | |
| 3 | import java.util.ArrayList; |
| 4 | import java.util.List; |
| 5 | |
| 6 | import de.uka.ipd.sdq.markov.Label; |
| 7 | import de.uka.ipd.sdq.markov.MarkovChain; |
| 8 | import de.uka.ipd.sdq.markov.MarkovFactory; |
| 9 | import de.uka.ipd.sdq.markov.State; |
| 10 | import de.uka.ipd.sdq.markov.StateType; |
| 11 | import de.uka.ipd.sdq.markov.Transition; |
| 12 | import de.uka.ipd.sdq.pcm.seff.AbstractAction; |
| 13 | import de.uka.ipd.sdq.pcm.seff.ForkedBehaviour; |
| 14 | import de.uka.ipd.sdq.probfunction.Sample; |
| 15 | import de.uka.ipd.sdq.probfunction.math.ManagedPMF; |
| 16 | |
| 17 | /** |
| 18 | * This class provides methods for building Markov Chains. |
| 19 | * |
| 20 | * @author brosch |
| 21 | * |
| 22 | */ |
| 23 | public class MarkovBuilder { |
| 24 | |
| 25 | /** |
| 26 | * Key to identify a Markov label as holding a failure type id. |
| 27 | */ |
| 28 | private static final String FAILURETYPEID = "FailureTypeId"; |
| 29 | |
| 30 | /** |
| 31 | * Key to identify a Markov label as holding a failure type name. |
| 32 | */ |
| 33 | private static final String FAILURETYPENAME = "FailureTypeName"; |
| 34 | |
| 35 | /** |
| 36 | * The Markov Factory is used to create the Elements of the Markov Chain |
| 37 | * Model resulting from the transformation. |
| 38 | */ |
| 39 | private MarkovFactory markovFactory = MarkovFactory.eINSTANCE; |
| 40 | |
| 41 | /** |
| 42 | * Indicates if the resulting Makov model shall be augmented with tracing |
| 43 | * information for diagnostic purposes. |
| 44 | */ |
| 45 | private boolean recordTraces; |
| 46 | |
| 47 | /** |
| 48 | * The constructor. |
| 49 | * |
| 50 | * @param recordTraces |
| 51 | * controls if traces shall be recorded during transformation |
| 52 | */ |
| 53 | public MarkovBuilder(final boolean recordTraces) { |
| 54 | this.recordTraces = recordTraces; |
| 55 | } |
| 56 | |
| 57 | /** |
| 58 | * Adds a state of a given type and with a given name to a Markov chain. |
| 59 | * |
| 60 | * @param chain |
| 61 | * the Markov chain |
| 62 | * @param type |
| 63 | * the type of state to add |
| 64 | * @param stateName |
| 65 | * the name for the state to add |
| 66 | * @param prefixes |
| 67 | * the prefixes to add to the state name |
| 68 | * @return the new state |
| 69 | */ |
| 70 | private State addState(final MarkovChain chain, final StateType type, |
| 71 | final String stateName, final List<String> prefixes) { |
| 72 | State state = markovFactory.createState(); |
| 73 | state.setType(type); |
| 74 | state.setName(getStateName(stateName, prefixes)); |
| 75 | state.getTraces().addAll(getStateTraces(stateName, prefixes)); |
| 76 | chain.getStates().add(state); |
| 77 | return state; |
| 78 | } |
| 79 | |
| 80 | /** |
| 81 | * Adds a failure state to a given Markov chain. |
| 82 | * |
| 83 | * @param chain |
| 84 | * the Markov chain |
| 85 | * @param prefixes |
| 86 | * the prefixes of the state name |
| 87 | * @param description |
| 88 | * the description of the failure type |
| 89 | * @return the new failure state |
| 90 | */ |
| 91 | private State addStateForFailureDescription(final MarkovChain chain, |
| 92 | final List<String> prefixes, final FailureDescription description) { |
| 93 | |
| 94 | // Create the new failure state and add it to the chain: |
| 95 | State failureState = addState(chain, StateType.FAILURE, |
| 96 | StateType.FAILURE.toString() + "(" |
| 97 | + description.getFailureType().getName() + ")", |
| 98 | prefixes); |
| 99 | |
| 100 | // Add a label to the state for the failure id: |
| 101 | Label failureIdLabel = markovFactory.createLabel(); |
| 102 | failureIdLabel.setKey(FAILURETYPEID); |
| 103 | failureIdLabel.setValue(description.getFailureType().getId()); |
| 104 | failureState.getLabels().add(failureIdLabel); |
| 105 | |
| 106 | // Add a label to the state for the failure name: |
| 107 | Label failureNameLabel = markovFactory.createLabel(); |
| 108 | failureNameLabel.setKey(FAILURETYPENAME); |
| 109 | failureNameLabel.setValue(description.getFailureType().getName()); |
| 110 | failureState.getLabels().add(failureNameLabel); |
| 111 | |
| 112 | // Return the new Failure state: |
| 113 | return failureState; |
| 114 | } |
| 115 | |
| 116 | /** |
| 117 | * Incorporates one Markov chain into another to replace a failure state |
| 118 | * with a new behavior. |
| 119 | * |
| 120 | * @param aggregateChain |
| 121 | * the outer Markov chain |
| 122 | * @param handlingChain |
| 123 | * the inner Markov chain to replace the failure state |
| 124 | * @param failureState |
| 125 | * the failure state to replace |
| 126 | * @param optimize |
| 127 | * indicates if Markov Chain reduction shall be performed during |
| 128 | * the transformation |
| 129 | */ |
| 130 | private void appendFailureHandlingChain(final MarkovChain aggregateChain, |
| 131 | final MarkovChain handlingChain, final State failureState, |
| 132 | final boolean optimize) { |
| 133 | |
| 134 | // First validate both chains: |
| 135 | this.validateChain(aggregateChain); |
| 136 | this.validateChain(handlingChain); |
| 137 | |
| 138 | // Create a copy of the specific Markov Chain to prevent reuse of any |
| 139 | // States or Transitions of the specific Markov Chain within the |
| 140 | // aggregate Markov Chain (this could lead to problems when one specific |
| 141 | // Markov Chain is incorporated several times into the same aggregate |
| 142 | // Markov Chain): |
| 143 | MarkovChain handlingChainCopy = copyMarkovChain(handlingChain); |
| 144 | |
| 145 | // Find the relevant states: |
| 146 | State aggregateChainSuccessState = getSuccessState(aggregateChain); |
| 147 | List<State> aggregateChainFailureStates = getFailureStates(aggregateChain); |
| 148 | |
| 149 | State handlingChainStartState = getStartState(handlingChainCopy); |
| 150 | State handlingChainSuccessState = getSuccessState(handlingChainCopy); |
| 151 | |
| 152 | // Take over the specific Markov Chain into the aggregate Markov Chain: |
| 153 | aggregateChain.getStates().addAll(handlingChainCopy.getStates()); |
| 154 | aggregateChain.getTransitions().addAll( |
| 155 | handlingChainCopy.getTransitions()); |
| 156 | |
| 157 | delegateIncommingTransitions(aggregateChain, failureState, |
| 158 | handlingChainStartState); |
| 159 | handlingChainStartState.setType(StateType.DEFAULT); |
| 160 | aggregateChain.getStates().remove(failureState); |
| 161 | aggregateChainFailureStates.remove(failureState); |
| 162 | |
| 163 | connectStates(aggregateChain, handlingChainSuccessState, |
| 164 | aggregateChainSuccessState, 1.0); |
| 165 | handlingChainSuccessState.setType(StateType.DEFAULT); |
| 166 | |
| 167 | // Optimize the aggregate MarkovChain: |
| 168 | if (optimize) { |
| 169 | reduceState(aggregateChain, handlingChainStartState); |
| 170 | reduceState(aggregateChain, handlingChainSuccessState); |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | /** |
| 175 | * Incorporates one Markov Chain into another. The specific Markov Chain is |
| 176 | * inserted into the aggregate Markov Chain replacing the failure state. |
| 177 | * |
| 178 | * @param aggregateChain |
| 179 | * the Markov Chain which will incorporate the other chain |
| 180 | * @param aggregateFailureStates |
| 181 | * the failure states of the aggregate chain that shall be |
| 182 | * considered |
| 183 | * @param handlingChain |
| 184 | * the Markov Chain which will be incorporated into the other |
| 185 | * chain |
| 186 | * @param handledFailureTypeIds |
| 187 | * the list of handled failure types |
| 188 | * @param removeDuplicateFailureStates |
| 189 | * indicates if duplicateFailureStates shall be removed at the |
| 190 | * end of the procedure |
| 191 | * @param optimize |
| 192 | * indicates if Markov Chain reduction shall be performed during |
| 193 | * the transformation |
| 194 | */ |
| 195 | private void appendFailureHandlingMarkovChain( |
| 196 | final MarkovChain aggregateChain, |
| 197 | final List<State> aggregateFailureStates, |
| 198 | final MarkovChain handlingChain, |
| 199 | final List<String> handledFailureTypeIds, final boolean optimize) { |
| 200 | for (State failureState : aggregateFailureStates) { |
| 201 | String failureTypeLabelValue = getFailureTypeId(failureState); |
| 202 | if (isFailureTypeHandled(handledFailureTypeIds, |
| 203 | failureTypeLabelValue)) { |
| 204 | appendFailureHandlingChain(aggregateChain, handlingChain, |
| 205 | failureState, optimize); |
| 206 | } |
| 207 | } |
| 208 | } |
| 209 | |
| 210 | /** |
| 211 | * Incorporates one Markov Chain into another. The specific Markov Chain is |
| 212 | * inserted into the aggregate Markov Chain replacing the failure state. |
| 213 | * |
| 214 | * @param aggregateChain |
| 215 | * the Markov Chain which will incorporate the other chain |
| 216 | * @param handlingChain |
| 217 | * the Markov Chain which will be incorporated into the other |
| 218 | * chain |
| 219 | * @param handledFailureTypeIds |
| 220 | * the list of handled failure types |
| 221 | * @param optimize |
| 222 | * indicates if Markov Chain reduction shall be performed during |
| 223 | * the transformation |
| 224 | */ |
| 225 | public void appendFailureHandlingMarkovChain( |
| 226 | final MarkovChain aggregateChain, final MarkovChain handlingChain, |
| 227 | final List<String> handledFailureTypeIds, final boolean optimize) { |
| 228 | appendFailureHandlingMarkovChain(aggregateChain, |
| 229 | getFailureStates(aggregateChain), handlingChain, |
| 230 | handledFailureTypeIds, optimize); |
| 231 | removeDuplicateFailureStates(aggregateChain, optimize); |
| 232 | } |
| 233 | |
| 234 | /** |
| 235 | * Incorporates multiple Markov Chains into one aggregate chain. The |
| 236 | * specific Markov Chains are inserted into the aggregate Markov Chain |
| 237 | * replacing the failure states. |
| 238 | * |
| 239 | * @param aggregateChain |
| 240 | * the Markov Chain which will incorporate the other chains |
| 241 | * @param handlingChains |
| 242 | * the Markov Chains which will be incorporated into the other |
| 243 | * chain |
| 244 | * @param handledFailureTypeIdLists |
| 245 | * the list of handled failure types per chain |
| 246 | * @param optimize |
| 247 | * indicates if Markov Chain reduction shall be performed during |
| 248 | * the transformation |
| 249 | */ |
| 250 | public void appendFailureHandlingMarkovChains( |
| 251 | final MarkovChain aggregateChain, |
| 252 | final List<MarkovChain> handlingChains, |
| 253 | final List<List<String>> handledFailureTypeIdLists, |
| 254 | final boolean optimize) { |
| 255 | List<State> aggregateFailureStates = getFailureStates(aggregateChain); |
| 256 | for (int i = 0; i < handlingChains.size(); i++) { |
| 257 | aggregateFailureStates = findStates(aggregateFailureStates, |
| 258 | StateType.FAILURE); |
| 259 | appendFailureHandlingMarkovChain(aggregateChain, |
| 260 | aggregateFailureStates, handlingChains.get(i), |
| 261 | handledFailureTypeIdLists.get(i), optimize); |
| 262 | } |
| 263 | removeDuplicateFailureStates(aggregateChain, optimize); |
| 264 | } |
| 265 | |
| 266 | /** |
| 267 | * Adds a new transition to a given Markov chain. |
| 268 | * |
| 269 | * @param chain |
| 270 | * the Markov chain |
| 271 | * @param from |
| 272 | * the source state |
| 273 | * @param to |
| 274 | * the target state |
| 275 | * @param probability |
| 276 | * the probability to annotate the new transition |
| 277 | */ |
| 278 | private void connectStates(final MarkovChain chain, final State from, |
| 279 | final State to, final double probability) { |
| 280 | Transition transition = markovFactory.createTransition(); |
| 281 | transition.setFromState(from); |
| 282 | transition.setToState(to); |
| 283 | transition.setProbability(probability); |
| 284 | nameTransition(transition); |
| 285 | chain.getTransitions().add(transition); |
| 286 | } |
| 287 | |
| 288 | /** |
| 289 | * Adds the given Transition to the given Markov Chain. If the given Markov |
| 290 | * Chain already has a Transition between the same source and target States, |
| 291 | * the already existing Transition is merged with the new one by summing up |
| 292 | * the probabilities of the two Transitions. |
| 293 | * |
| 294 | * @param markovChain |
| 295 | * the Markov Chain |
| 296 | * @param transitionToContribute |
| 297 | * the Transition |
| 298 | */ |
| 299 | private void contributeTransition(final MarkovChain markovChain, |
| 300 | final Transition transitionToContribute) { |
| 301 | |
| 302 | // Go through the Transitions of the Markov Chain to find an already |
| 303 | // existing Transition that corresponds to the new one: |
| 304 | Transition transitionCorresponding = null; |
| 305 | for (int i = 0; i < markovChain.getTransitions().size(); i++) { |
| 306 | if ((markovChain.getTransitions().get(i).getFromState() == transitionToContribute |
| 307 | .getFromState()) |
| 308 | && (markovChain.getTransitions().get(i).getToState() == transitionToContribute |
| 309 | .getToState())) { |
| 310 | transitionCorresponding = markovChain.getTransitions().get(i); |
| 311 | break; |
| 312 | } |
| 313 | } |
| 314 | |
| 315 | // Does a corresponding Transition already exist? |
| 316 | if (transitionCorresponding != null) { |
| 317 | |
| 318 | // Add the probability of the new Transition to that of the already |
| 319 | // existing one: |
| 320 | transitionCorresponding.setProbability(transitionCorresponding |
| 321 | .getProbability() |
| 322 | + transitionToContribute.getProbability()); |
| 323 | } else { |
| 324 | |
| 325 | // Simply add the new Transition to the Markov Chain: |
| 326 | markovChain.getTransitions().add(transitionToContribute); |
| 327 | } |
| 328 | } |
| 329 | |
| 330 | /** |
| 331 | * Creates a copy of a Markov Chain. All States and Transitions of the |
| 332 | * original Markov Chain are copied into the new one. |
| 333 | * |
| 334 | * @param originalMarkovChain |
| 335 | * the original Markov Chain |
| 336 | * @return the new Markov Chain |
| 337 | */ |
| 338 | public MarkovChain copyMarkovChain(final MarkovChain originalMarkovChain) { |
| 339 | |
| 340 | // Create a new Markov Chain instance: |
| 341 | MarkovChain newMarkovChain = markovFactory.createMarkovChain(); |
| 342 | newMarkovChain.setName(originalMarkovChain.getName()); |
| 343 | |
| 344 | // Copy all States from the original Markov Chain into the new one: |
| 345 | for (int i = 0; i < originalMarkovChain.getStates().size(); i++) { |
| 346 | |
| 347 | State originalState = originalMarkovChain.getStates().get(i); |
| 348 | // Create a new Markov State: |
| 349 | State newState = markovFactory.createState(); |
| 350 | newState.setName(originalState.getName()); |
| 351 | newState.setType(originalState.getType()); |
| 352 | |
| 353 | for (Label originalLabel : originalState.getLabels()) { |
| 354 | Label newLabel = markovFactory.createLabel(); |
| 355 | newLabel.setKey(originalLabel.getKey()); |
| 356 | newLabel.setValue(originalLabel.getValue()); |
| 357 | newState.getLabels().add(newLabel); |
| 358 | } |
| 359 | |
| 360 | // Add Traces information: |
| 361 | newState.getTraces().addAll(originalState.getTraces()); |
| 362 | |
| 363 | // Add the new State to the new Markov Chain: |
| 364 | newMarkovChain.getStates().add(newState); |
| 365 | } |
| 366 | |
| 367 | // Copy all Transitions from the originial Markov Chain into the new |
| 368 | // one: |
| 369 | for (int i = 0; i < originalMarkovChain.getTransitions().size(); i++) { |
| 370 | |
| 371 | // Create a new Transition: |
| 372 | Transition newTransition = markovFactory.createTransition(); |
| 373 | newTransition.setName(originalMarkovChain.getTransitions().get(i) |
| 374 | .getName()); |
| 375 | newTransition.setProbability(originalMarkovChain.getTransitions() |
| 376 | .get(i).getProbability()); |
| 377 | |
| 378 | // Determine the source and target States of the new Transition: |
| 379 | State fromState = newMarkovChain.getStates().get( |
| 380 | originalMarkovChain.getStates().indexOf( |
| 381 | originalMarkovChain.getTransitions().get(i) |
| 382 | .getFromState())); |
| 383 | State toState = newMarkovChain.getStates().get( |
| 384 | originalMarkovChain.getStates().indexOf( |
| 385 | originalMarkovChain.getTransitions().get(i) |
| 386 | .getToState())); |
| 387 | newTransition.setFromState(fromState); |
| 388 | newTransition.setToState(toState); |
| 389 | |
| 390 | // Add the new Transition to the new Markov Chain: |
| 391 | newMarkovChain.getTransitions().add(newTransition); |
| 392 | } |
| 393 | |
| 394 | // Return the resulting Markov Chain: |
| 395 | return newMarkovChain; |
| 396 | } |
| 397 | |
| 398 | /** |
| 399 | * Delegates incoming transitions from an original state to a new state. |
| 400 | * |
| 401 | * @param chain |
| 402 | * the Markov chain |
| 403 | * @param originalState |
| 404 | * the original state |
| 405 | * @param newState |
| 406 | * the new state |
| 407 | */ |
| 408 | private void delegateIncommingTransitions(final MarkovChain chain, |
| 409 | final State originalState, final State newState) { |
| 410 | ArrayList<Transition> transitions = findTransitionsToState(chain, |
| 411 | originalState); |
| 412 | for (Transition transition : transitions) { |
| 413 | transition.setToState(newState); |
| 414 | } |
| 415 | } |
| 416 | |
| 417 | /** |
| 418 | * Delegates outgoing transitions from an original state to a new state. |
| 419 | * |
| 420 | * @param chain |
| 421 | * the Markov chain |
| 422 | * @param originalState |
| 423 | * the original state |
| 424 | * @param newState |
| 425 | * the new state |
| 426 | */ |
| 427 | private void delegateOutgoingTransitions(final MarkovChain chain, |
| 428 | final State originalState, final State newState) { |
| 429 | ArrayList<Transition> transitions = findTransitionsFromState(chain, |
| 430 | originalState); |
| 431 | for (Transition transition : transitions) { |
| 432 | transition.setFromState(newState); |
| 433 | } |
| 434 | } |
| 435 | |
| 436 | /** |
| 437 | * Deletes all Transitions from the given Markov Model which are part of the |
| 438 | * given transitions list. |
| 439 | * |
| 440 | * @param markovChain |
| 441 | * the Markov Chain |
| 442 | * @param transitionsToDelete |
| 443 | * the transition list |
| 444 | */ |
| 445 | private void deleteTransitions(final MarkovChain markovChain, |
| 446 | final ArrayList<Transition> transitionsToDelete) { |
| 447 | |
| 448 | // Go through all transitions of the given list: |
| 449 | for (int i = 0; i < transitionsToDelete.size(); i++) { |
| 450 | |
| 451 | // Remove this transition from the Markov Chain: |
| 452 | markovChain.getTransitions().remove(transitionsToDelete.get(i)); |
| 453 | } |
| 454 | } |
| 455 | |
| 456 | /** |
| 457 | * Finds a failure state out of a given list of states. |
| 458 | * |
| 459 | * @param states |
| 460 | * the list of states |
| 461 | * @param failureTypeLabelValue |
| 462 | * the type of failure state to find |
| 463 | * @return the failure state; NULL if no corresponding failure state could |
| 464 | * be found |
| 465 | */ |
| 466 | private State findFailureState(final List<State> states, |
| 467 | final String failureTypeLabelValue) { |
| 468 | for (State state : states) { |
| 469 | if (!state.getType().equals(StateType.FAILURE)) { |
| 470 | continue; |
| 471 | } |
| 472 | for (Label label : state.getLabels()) { |
| 473 | // TODO: this is linear search inside an outer loop! improve |
| 474 | // performance |
| 475 | if ((label.getKey().equals(FAILURETYPEID)) |
| 476 | && (label.getValue().equals(failureTypeLabelValue))) { |
| 477 | return state; |
| 478 | } |
| 479 | } |
| 480 | } |
| 481 | return null; |
| 482 | } |
| 483 | |
| 484 | /** |
| 485 | * Finds the failure states out of a given list of states. |
| 486 | * |
| 487 | * @param states |
| 488 | * the list of states |
| 489 | * @param failureTypeLabelValue |
| 490 | * the type of failure state to find |
| 491 | * @return the failure states; NULL if no corresponding failure state could |
| 492 | * be found |
| 493 | */ |
| 494 | private List<State> findFailureStates(final List<State> states, |
| 495 | final String failureTypeLabelValue) { |
| 496 | List<State> resultList = new ArrayList<State>(); |
| 497 | for (State state : states) { |
| 498 | if (!state.getType().equals(StateType.FAILURE)) { |
| 499 | continue; |
| 500 | } |
| 501 | for (Label label : state.getLabels()) { |
| 502 | // TODO: this is linear search inside an outer loop! improve |
| 503 | // performance |
| 504 | if ((label.getKey().equals(FAILURETYPEID)) |
| 505 | && (label.getValue().equals(failureTypeLabelValue))) { |
| 506 | resultList.add(state); |
| 507 | } |
| 508 | } |
| 509 | } |
| 510 | return resultList; |
| 511 | } |
| 512 | |
| 513 | /** |
| 514 | * Finds a failure state out of a given list of states. |
| 515 | * |
| 516 | * @param states |
| 517 | * the list of states |
| 518 | * @param failureState |
| 519 | * the failure state to match |
| 520 | * @return the failure state; NULL if no corresponding failure state could |
| 521 | * be found |
| 522 | */ |
| 523 | private State findMatchingFailureState(final List<State> states, |
| 524 | final State failureState) { |
| 525 | String failureTypeLabelValue = getFailureTypeId(failureState); |
| 526 | return findFailureState(states, failureTypeLabelValue); |
| 527 | } |
| 528 | |
| 529 | /** |
| 530 | * Finds the failure states out of a given list of states. |
| 531 | * |
| 532 | * @param states |
| 533 | * the list of states |
| 534 | * @param failureState |
| 535 | * the failure state to match |
| 536 | * @return the failure states |
| 537 | */ |
| 538 | private List<State> findMatchingFailureStates(final List<State> states, |
| 539 | final State failureState) { |
| 540 | String failureTypeLabelValue = getFailureTypeId(failureState); |
| 541 | return findFailureStates(states, failureTypeLabelValue); |
| 542 | } |
| 543 | |
| 544 | /** |
| 545 | * Retrieves all Markov states of a given type from a given state list. |
| 546 | * |
| 547 | * @param states |
| 548 | * the list of states to search through |
| 549 | * @param type |
| 550 | * the requested state type |
| 551 | * @return the sub list if states of the requested type |
| 552 | */ |
| 553 | private List<State> findStates(final List<State> states, |
| 554 | final StateType type) { |
| 555 | List<State> resultList = new ArrayList<State>(); |
| 556 | for (State state : states) { |
| 557 | if (state.getType().equals(type)) { |
| 558 | resultList.add(state); |
| 559 | } |
| 560 | } |
| 561 | return resultList; |
| 562 | } |
| 563 | |
| 564 | /** |
| 565 | * Creates a list of all Transitions in a Markov Chain that start from a |
| 566 | * given source state. |
| 567 | * |
| 568 | * @param markovChain |
| 569 | * the Markov Chain |
| 570 | * @param sourceState |
| 571 | * the source state |
| 572 | * @return the list of transitions |
| 573 | */ |
| 574 | private ArrayList<Transition> findTransitionsFromState( |
| 575 | final MarkovChain markovChain, final State sourceState) { |
| 576 | |
| 577 | // Initialize the resulting List: |
| 578 | ArrayList<Transition> resultList = new ArrayList<Transition>(); |
| 579 | |
| 580 | // Go through all transitions of the Markov Chain: |
| 581 | for (int i = 0; i < markovChain.getTransitions().size(); i++) { |
| 582 | if (markovChain.getTransitions().get(i).getFromState() == sourceState) { |
| 583 | resultList.add(markovChain.getTransitions().get(i)); |
| 584 | } |
| 585 | } |
| 586 | |
| 587 | // Return the result: |
| 588 | return resultList; |
| 589 | } |
| 590 | |
| 591 | /** |
| 592 | * Creates a list of all Transitions in a Markov Chain that lead to a given |
| 593 | * target state. |
| 594 | * |
| 595 | * @param markovChain |
| 596 | * the Markov Chain |
| 597 | * @param targetState |
| 598 | * the target state |
| 599 | * @return the list of transitions |
| 600 | */ |
| 601 | private ArrayList<Transition> findTransitionsToState( |
| 602 | final MarkovChain markovChain, final State targetState) { |
| 603 | |
| 604 | // Initialize the resulting List: |
| 605 | ArrayList<Transition> resultList = new ArrayList<Transition>(); |
| 606 | |
| 607 | // Go through all transitions of the Markov Chain: |
| 608 | for (int i = 0; i < markovChain.getTransitions().size(); i++) { |
| 609 | if (markovChain.getTransitions().get(i).getToState() == targetState) { |
| 610 | resultList.add(markovChain.getTransitions().get(i)); |
| 611 | } |
| 612 | } |
| 613 | |
| 614 | // Return the result: |
| 615 | return resultList; |
| 616 | } |
| 617 | |
| 618 | /** |
| 619 | * Gets all failure states out of a given Markov chain. |
| 620 | * |
| 621 | * @param markovChain |
| 622 | * the Markov chain |
| 623 | * @return the list of failure states |
| 624 | */ |
| 625 | public List<State> getFailureStates(final MarkovChain markovChain) { |
| 626 | |
| 627 | // Initialize the resulting list: |
| 628 | List<State> failureStates = new ArrayList<State>(); |
| 629 | |
| 630 | // Go through all states of the Markov Chain: |
| 631 | for (int i = 0; i < markovChain.getStates().size(); i++) { |
| 632 | if (markovChain.getStates().get(i).getType().equals( |
| 633 | StateType.FAILURE)) { |
| 634 | failureStates.add(markovChain.getStates().get(i)); |
| 635 | } |
| 636 | } |
| 637 | |
| 638 | // Return the result: |
| 639 | return failureStates; |
| 640 | } |
| 641 | |
| 642 | /** |
| 643 | * Gets the failure type annotation of a Markov failure state. |
| 644 | * |
| 645 | * @param state |
| 646 | * the state to examine |
| 647 | * @return the failure type annotation of the state |
| 648 | */ |
| 649 | public String getFailureTypeId(final State state) { |
| 650 | for (Label label : state.getLabels()) { |
| 651 | if (label.getKey().equals(FAILURETYPEID)) { |
| 652 | return label.getValue(); |
| 653 | } |
| 654 | } |
| 655 | return null; |
| 656 | } |
| 657 | |
| 658 | /** |
| 659 | * Gets the failure type annotation of a Markov failure state. |
| 660 | * |
| 661 | * @param state |
| 662 | * the state to examine |
| 663 | * @return the failure type annotation of the state |
| 664 | */ |
| 665 | public String getFailureTypeName(final State state) { |
| 666 | for (Label label : state.getLabels()) { |
| 667 | if (label.getKey().equals(FAILURETYPENAME)) { |
| 668 | return label.getValue(); |
| 669 | } |
| 670 | } |
| 671 | return null; |
| 672 | } |
| 673 | |
| 674 | /** |
| 675 | * Retrieves a name from a given list of prefixes. |
| 676 | * |
| 677 | * @param prefixes |
| 678 | * the list of prefixes |
| 679 | * @return the resulting name |
| 680 | */ |
| 681 | private String getName(final List<String> prefixes) { |
| 682 | String result = ""; |
| 683 | for (int i = 0; i < prefixes.size(); i++) { |
| 684 | result += prefixes.get(i); |
| 685 | if (i < prefixes.size() - 1) { |
| 686 | result += "::"; |
| 687 | } |
| 688 | } |
| 689 | return result; |
| 690 | } |
| 691 | |
| 692 | /** |
| 693 | * Gets the start state out of a given Markov chain. |
| 694 | * |
| 695 | * @param markovChain |
| 696 | * the Markov chain |
| 697 | * @return the start state |
| 698 | */ |
| 699 | public State getStartState(final MarkovChain markovChain) { |
| 700 | |
| 701 | // Go through all states of the Markov Chain: |
| 702 | for (int i = 0; i < markovChain.getStates().size(); i++) { |
| 703 | if (markovChain.getStates().get(i).getType() |
| 704 | .equals(StateType.START)) { |
| 705 | return markovChain.getStates().get(i); |
| 706 | } |
| 707 | } |
| 708 | |
| 709 | // No start state found: |
| 710 | throw new MarkovException("Markov Chain has no start state."); |
| 711 | } |
| 712 | |
| 713 | /** |
| 714 | * Determines the composed name of a Markov state. |
| 715 | * |
| 716 | * @param stateName |
| 717 | * the state name |
| 718 | * @param prefixes |
| 719 | * the prefixes of the state name |
| 720 | * @return the composed name |
| 721 | */ |
| 722 | private String getStateName(final String stateName, |
| 723 | final List<String> prefixes) { |
| 724 | if (prefixes.isEmpty()) { |
| 725 | return stateName; |
| 726 | } else { |
| 727 | return prefixes.get(prefixes.size() - 1) + "::" + stateName; |
| 728 | } |
| 729 | } |
| 730 | |
| 731 | /** |
| 732 | * Determines the traces of a Markov state. |
| 733 | * |
| 734 | * @param stateName |
| 735 | * the state name |
| 736 | * @param prefixes |
| 737 | * the prefixes of the state name |
| 738 | * @return the trace list of the state |
| 739 | */ |
| 740 | private List<String> getStateTraces(final String stateName, |
| 741 | final List<String> prefixes) { |
| 742 | ArrayList<String> resultList = new ArrayList<String>(); |
| 743 | if (recordTraces) { |
| 744 | resultList.addAll(prefixes); |
| 745 | resultList.add(stateName); |
| 746 | } |
| 747 | return resultList; |
| 748 | } |
| 749 | |
| 750 | /** |
| 751 | * Gets the success state out of a given Markov chain. |
| 752 | * |
| 753 | * @param markovChain |
| 754 | * the Markov Chain |
| 755 | * @return the Success State |
| 756 | */ |
| 757 | public State getSuccessState(final MarkovChain markovChain) { |
| 758 | |
| 759 | // Go through all states of the Markov Chain: |
| 760 | for (int i = 0; i < markovChain.getStates().size(); i++) { |
| 761 | if (markovChain.getStates().get(i).getType().equals( |
| 762 | StateType.SUCCESS)) { |
| 763 | return markovChain.getStates().get(i); |
| 764 | } |
| 765 | } |
| 766 | |
| 767 | // No success state found: |
| 768 | throw new MarkovException("Markov Chain has no success state."); |
| 769 | } |
| 770 | |
| 771 | /** |
| 772 | * Incorporates one Markov Chain into another. The specific Markov Chain is |
| 773 | * inserted into the aggregate Markov Chain replacing the given aggregate |
| 774 | * Markov State. |
| 775 | * |
| 776 | * @param parentChain |
| 777 | * the Markov Chain which will incorporate the other chain |
| 778 | * @param specificMarkovChain |
| 779 | * the Markov Chain which will be incorporated into the other |
| 780 | * chain |
| 781 | * @param aggregateState |
| 782 | * the Markov State in the aggregate Markov Chain which will be |
| 783 | * replaced by the specific Markov Chain |
| 784 | * @param optimize |
| 785 | * indicates if Markov Chain reduction shall be performed during |
| 786 | * the transformation |
| 787 | * @param appendPrefixes |
| 788 | * indicates if prefixes of specific chain shall be appended to |
| 789 | * prefixes of aggregateChain |
| 790 | */ |
| 791 | public void incorporateMarkovChain(final MarkovChain parentChain, |
| 792 | final MarkovChain specificMarkovChain, final State aggregateState, |
| 793 | final boolean optimize, final boolean appendPrefixes) { |
| 794 | |
| 795 | // Assure that the replaceable Markov State is contained in the |
| 796 | // aggregate Markov Chain: |
| 797 | if (!parentChain.getStates().contains(aggregateState)) { |
| 798 | throw new MarkovException("State '" + aggregateState |
| 799 | + "' is not contained in the markov chain '" |
| 800 | + parentChain.getName() + "'."); |
| 801 | } |
| 802 | |
| 803 | // Assure that the replaceable Markov State is not a Start, Success or |
| 804 | // Failure State: |
| 805 | if (!aggregateState.getType().equals(StateType.DEFAULT)) { |
| 806 | throw new MarkovException( |
| 807 | "Only default states can be incorporated. '" |
| 808 | + aggregateState.getName() + "' is of type '" |
| 809 | + aggregateState.getType() + "'."); |
| 810 | } |
| 811 | |
| 812 | // Create a copy of the specific Markov Chain to prevent reuse of any |
| 813 | // States or Transitions of the specific Markov Chain within the |
| 814 | // aggregate Markov Chain (this could lead to problems when one specific |
| 815 | // Markov Chain is incorporated several times into the same aggregate |
| 816 | // Markov Chain): |
| 817 | MarkovChain copiedSpecificMarkovChain = copyMarkovChain(specificMarkovChain); |
| 818 | |
| 819 | // Find the Start, Success and Failure States of the aggregate Markov |
| 820 | // Chain: |
| 821 | List<State> stateAggregateFailures = getFailureStates(parentChain); |
| 822 | |
| 823 | // Find the Start, Success and Failure States of the specific Markov |
| 824 | // Chain: |
| 825 | State stateSpecificStart = getStartState(copiedSpecificMarkovChain); |
| 826 | State stateSpecificSuccess = getSuccessState(copiedSpecificMarkovChain); |
| 827 | List<State> stateSpecificFailures = getFailureStates(copiedSpecificMarkovChain); |
| 828 | |
| 829 | // Augment specific Makov traces with the aggregate state trace: |
| 830 | if (recordTraces && appendPrefixes) { |
| 831 | for (State specificState : copiedSpecificMarkovChain.getStates()) { |
| 832 | specificState.getTraces().addAll(0, aggregateState.getTraces()); |
| 833 | specificState.setName(getStateName(specificState.getTraces() |
| 834 | .get(specificState.getTraces().size() - 1), |
| 835 | specificState.getTraces().subList(0, |
| 836 | specificState.getTraces().size() - 1))); |
| 837 | } |
| 838 | } |
| 839 | |
| 840 | // Take over the specific Markov Chain into the aggregate Markov Chain: |
| 841 | parentChain.getStates().addAll(copiedSpecificMarkovChain.getStates()); |
| 842 | parentChain.getTransitions().addAll( |
| 843 | copiedSpecificMarkovChain.getTransitions()); |
| 844 | |
| 845 | // all transitions to the replaceable state are delegated to the inner |
| 846 | // start state |
| 847 | delegateIncommingTransitions(parentChain, aggregateState, |
| 848 | stateSpecificStart); |
| 849 | stateSpecificStart.setType(StateType.DEFAULT); |
| 850 | |
| 851 | // absorb failure states. for already existing failure type states |
| 852 | // delegate transitions |
| 853 | // from inner duplicates. |
| 854 | List<State> duplicateFailureStates = new ArrayList<State>(); |
| 855 | for (State failureState : stateSpecificFailures) { |
| 856 | // check if this is a duplicate |
| 857 | State existingFailureState = findMatchingFailureState( |
| 858 | stateAggregateFailures, failureState); |
| 859 | if (existingFailureState != null) { // duplicate found |
| 860 | // delegate from duplicate to existing state |
| 861 | connectStates(parentChain, failureState, existingFailureState, |
| 862 | 1.0); |
| 863 | // remove duplicate |
| 864 | failureState.setType(StateType.DEFAULT); |
| 865 | duplicateFailureStates.add(failureState); |
| 866 | } |
| 867 | } |
| 868 | |
| 869 | // |
| 870 | delegateOutgoingTransitions(parentChain, aggregateState, |
| 871 | stateSpecificSuccess); |
| 872 | stateSpecificSuccess.setType(StateType.DEFAULT); |
| 873 | |
| 874 | // remove the |
| 875 | parentChain.getStates().remove(aggregateState); |
| 876 | |
| 877 | // Optimize the aggregate MarkovChain: |
| 878 | if (optimize) { |
| 879 | reduceState(parentChain, stateSpecificStart); |
| 880 | reduceState(parentChain, stateSpecificSuccess); |
| 881 | for (State failureState : duplicateFailureStates) { |
| 882 | reduceState(parentChain, failureState); |
| 883 | } |
| 884 | } |
| 885 | } |
| 886 | |
| 887 | /** |
| 888 | * Retrieves the index of a given State within a given Markov Chain. |
| 889 | * |
| 890 | * @param markovChain |
| 891 | * the Markov Chain |
| 892 | * @param state |
| 893 | * the state to find |
| 894 | * @return the required index |
| 895 | */ |
| 896 | public int indexOf(final MarkovChain markovChain, final State state) { |
| 897 | |
| 898 | // Go through all states of the Markov Chain: |
| 899 | for (int i = 0; i < markovChain.getStates().size(); i++) { |
| 900 | if (markovChain.getStates().get(i) == state) { |
| 901 | return i; |
| 902 | } |
| 903 | } |
| 904 | |
| 905 | // Nothing found? |
| 906 | throw new MarkovException("State not found in Markov chain."); |
| 907 | } |
| 908 | |
| 909 | /** |
| 910 | * Initializes a new Markov Chain. The new Markov Chain has only three |
| 911 | * states: a start state, a success state and a failure state. A single |
| 912 | * transition goes from start to success with probability 1. |
| 913 | * |
| 914 | * @param prefixes |
| 915 | * the prefixes of the chain name |
| 916 | * @return the new Markov Chain |
| 917 | */ |
| 918 | public MarkovChain initBasicMarkovChain(final List<String> prefixes) { |
| 919 | |
| 920 | // Create the Markov Chain Entity: |
| 921 | MarkovChain markovChain = markovFactory.createMarkovChain(); |
| 922 | markovChain.setName(getName(prefixes)); |
| 923 | |
| 924 | // Create the Start and Success States: |
| 925 | State startState = addState(markovChain, StateType.START, |
| 926 | StateType.START.toString(), prefixes); |
| 927 | State successSate = addState(markovChain, StateType.SUCCESS, |
| 928 | StateType.SUCCESS.toString(), prefixes); |
| 929 | connectStates(markovChain, startState, successSate, 1.0); |
| 930 | |
| 931 | // Return the result: |
| 932 | return markovChain; |
| 933 | } |
| 934 | |
| 935 | /** |
| 936 | * Creates a basic Markov chain with a start, success and multiple failure |
| 937 | * nodes for a given list of failure descriptions. Such a chain can be used |
| 938 | * to represent an internal action with its application failure |
| 939 | * probabilities, or the sending of a message over a communication link. All |
| 940 | * failure probabilities must sum up to at most 1.0. |
| 941 | * |
| 942 | * @param prefixes |
| 943 | * the prefixes of the chain name |
| 944 | * @param failureDescriptions |
| 945 | * a list of failure descriptions |
| 946 | * @return the resulting Markov Chain |
| 947 | */ |
| 948 | public MarkovChain initBasicMarkovChainWithFailures( |
| 949 | final List<String> prefixes, |
| 950 | final List<FailureDescription> failureDescriptions) { |
| 951 | |
| 952 | // Create the Markov Chain Entity: |
| 953 | MarkovChain markovChain = markovFactory.createMarkovChain(); |
| 954 | markovChain.setName(getName(prefixes)); |
| 955 | |
| 956 | // Create the Start and Success States: |
| 957 | State startState = addState(markovChain, StateType.START, |
| 958 | StateType.START.toString(), prefixes); |
| 959 | State successState = addState(markovChain, StateType.SUCCESS, |
| 960 | StateType.SUCCESS.toString(), prefixes); |
| 961 | |
| 962 | // Start with the assumption of total reliability: |
| 963 | double successProbability = 1.0; |
| 964 | |
| 965 | // Create failure states and connecting transitions: |
| 966 | for (FailureDescription description : failureDescriptions) { |
| 967 | State failureState = addStateForFailureDescription(markovChain, |
| 968 | prefixes, description); |
| 969 | connectStates(markovChain, startState, failureState, description |
| 970 | .getFailureProbability()); |
| 971 | successProbability -= description.getFailureProbability(); |
| 972 | } |
| 973 | |
| 974 | // Assure that the reliability has not decreased below zero: |
| 975 | if (successProbability < 0) { |
| 976 | throw new MarkovException( |
| 977 | "Total failure probability of basic Chain \"" |
| 978 | + getName(prefixes) + "\" is greater than 1.0."); |
| 979 | } |
| 980 | |
| 981 | // Create the Transition from Start State to Success State: |
| 982 | connectStates(markovChain, startState, successState, successProbability); |
| 983 | |
| 984 | // Return the result: |
| 985 | return markovChain; |
| 986 | } |
| 987 | |
| 988 | /** |
| 989 | * Creates a Markov Chain that represents an execution of a |
| 990 | * ScenarioBehaviour or ResourceDemandingBehaviour. |
| 991 | * |
| 992 | * @param prefixes |
| 993 | * the prefixes of the Markov Chain name |
| 994 | * @param actions |
| 995 | * the actions of the Behaviour |
| 996 | * @param statesOut |
| 997 | * the list of states created within the method that corresponds |
| 998 | * to the given list of actions |
| 999 | * @return the resulting Markov Chain |
| 1000 | */ |
| 1001 | public MarkovChain initBehaviourMarkovChainByAction( |
| 1002 | final List<String> prefixes, final List<AbstractAction> actions, |
| 1003 | final List<State> statesOut) { |
| 1004 | |
| 1005 | // Collect the action names: |
| 1006 | ArrayList<String> actionNames = new ArrayList<String>(); |
| 1007 | for (int i = 0; i < actions.size(); i++) { |
| 1008 | actionNames.add(actions.get(i).getEntityName() + "[" |
| 1009 | + actions.get(i).getId() + "]"); |
| 1010 | } |
| 1011 | |
| 1012 | // Build the Markov Chain: |
| 1013 | return initSequentialMarkovChain(prefixes, actionNames, statesOut); |
| 1014 | } |
| 1015 | |
| 1016 | /** |
| 1017 | * Creates a Markov Chain for a branch with solved branch probabilities. |
| 1018 | * |
| 1019 | * @param prefixes |
| 1020 | * the prefixes of the branch name |
| 1021 | * @param branchProbabilities |
| 1022 | * the branch probabilities |
| 1023 | * @return the resulting Markov Chain |
| 1024 | */ |
| 1025 | public MarkovChain initBranchMarkovChain(final List<String> prefixes, |
| 1026 | final ArrayList<Double> branchProbabilities) { |
| 1027 | |
| 1028 | // Create the Markov Chain Entity: |
| 1029 | MarkovChain markovChain = markovFactory.createMarkovChain(); |
| 1030 | markovChain.setName(getName(prefixes)); |
| 1031 | |
| 1032 | // Create the Start and Success States: |
| 1033 | State startState = addState(markovChain, StateType.START, |
| 1034 | StateType.START.toString(), prefixes); |
| 1035 | State successState = addState(markovChain, StateType.SUCCESS, |
| 1036 | StateType.SUCCESS.toString(), prefixes); |
| 1037 | |
| 1038 | // Go through the given branch probabilities: |
| 1039 | for (int i = 0; i < branchProbabilities.size(); i++) { |
| 1040 | |
| 1041 | // Check for a positive branch probability: |
| 1042 | if (branchProbabilities.get(i) <= 0.0) { |
| 1043 | continue; |
| 1044 | } |
| 1045 | |
| 1046 | // Create a new State: |
| 1047 | State stateBranch = addState(markovChain, StateType.DEFAULT, |
| 1048 | "Alternative(" + (i + 1) + ")", prefixes); |
| 1049 | |
| 1050 | // Create a transition from the Start State to the new one: |
| 1051 | connectStates(markovChain, startState, stateBranch, |
| 1052 | branchProbabilities.get(i)); |
| 1053 | |
| 1054 | // Create a transition from new state to the success state |
| 1055 | connectStates(markovChain, stateBranch, successState, 1.0); |
| 1056 | } |
| 1057 | |
| 1058 | // Return the result: |
| 1059 | return markovChain; |
| 1060 | } |
| 1061 | |
| 1062 | /** |
| 1063 | * Creates a Markov Chain for a fork action with a list of forked |
| 1064 | * behaviours. |
| 1065 | * |
| 1066 | * @param prefixes |
| 1067 | * the prefixes of the fork name |
| 1068 | * @param behaviours |
| 1069 | * the list of forked behaviours |
| 1070 | * @param statesOut |
| 1071 | * the list of states created within the method |
| 1072 | * @return the resulting Markov chain |
| 1073 | */ |
| 1074 | public MarkovChain initForkMarkovChain(List<String> prefixes, |
| 1075 | ArrayList<ForkedBehaviour> behaviours, ArrayList<State> statesOut) { |
| 1076 | |
| 1077 | // Collect the action names: |
| 1078 | ArrayList<String> behaviourNames = new ArrayList<String>(); |
| 1079 | for (int i = 0; i < behaviours.size(); i++) { |
| 1080 | behaviourNames.add("ForkBehaviour(" + (i + 1) + ")"); |
| 1081 | } |
| 1082 | |
| 1083 | // Build the Markov Chain: |
| 1084 | return initSequentialMarkovChain(prefixes, behaviourNames, statesOut); |
| 1085 | } |
| 1086 | |
| 1087 | /** |
| 1088 | * Creates a Markov Chain for a loop with solved probability mass function. |
| 1089 | * |
| 1090 | * @param prefixes |
| 1091 | * the prefixes of the loop name |
| 1092 | * @param pmf |
| 1093 | * the probability mass function of the loop |
| 1094 | * @return the resulting Markov Chain |
| 1095 | */ |
| 1096 | public MarkovChain initLoopMarkovChain(final List<String> prefixes, |
| 1097 | final ManagedPMF pmf) { |
| 1098 | |
| 1099 | // Create the Markov Chain Entity: |
| 1100 | MarkovChain markovChain = markovFactory.createMarkovChain(); |
| 1101 | markovChain.setName(getName(prefixes)); |
| 1102 | |
| 1103 | // Create the Start and Success States: |
| 1104 | State startState = addState(markovChain, StateType.START, |
| 1105 | StateType.START.toString(), prefixes); |
| 1106 | State successState = addState(markovChain, StateType.SUCCESS, |
| 1107 | StateType.SUCCESS.toString(), prefixes); |
| 1108 | |
| 1109 | // Go through the samples of the probability mass function: |
| 1110 | for (int i = 0; i < pmf.getModelPmf().getSamples().size(); i++) { |
| 1111 | Sample sample = pmf.getModelPmf().getSamples().get(i); |
| 1112 | if (!(sample.getValue() instanceof Integer)) { |
| 1113 | throw new MarkovException("Invalid Sample value " |
| 1114 | + sample.getValue().toString() + " in " |
| 1115 | + pmf.getModelPmf().toString()); |
| 1116 | } |
| 1117 | |
| 1118 | int sampleValue = (Integer) sample.getValue(); |
| 1119 | |
| 1120 | // Mark the State that will lead to the Success State: |
| 1121 | State stateToSuccess = startState; |
| 1122 | double transitionProbability = sample.getProbability(); |
| 1123 | |
| 1124 | // Go through the iterations of this sample: |
| 1125 | for (int j = 0; j < sampleValue; j++) { |
| 1126 | |
| 1127 | // Create a new State: |
| 1128 | State stateSample = addState(markovChain, StateType.DEFAULT, |
| 1129 | "Alternative(" + (i + 1) + ")-Iteration(" + (j + 1) |
| 1130 | + ")", prefixes); |
| 1131 | connectStates(markovChain, stateToSuccess, stateSample, |
| 1132 | transitionProbability); |
| 1133 | |
| 1134 | // Update State and probability: |
| 1135 | stateToSuccess = stateSample; |
| 1136 | transitionProbability = 1; |
| 1137 | } |
| 1138 | |
| 1139 | connectStates(markovChain, stateToSuccess, successState, |
| 1140 | transitionProbability); |
| 1141 | } |
| 1142 | |
| 1143 | // Return the result: |
| 1144 | return markovChain; |
| 1145 | } |
| 1146 | |
| 1147 | /** |
| 1148 | * Creates a Markov chain for an internal action failing with probability |
| 1149 | * 1.0 because of unavailable hardware resources. The failure probability is |
| 1150 | * divided between all unavailable resources. |
| 1151 | * |
| 1152 | * @param prefixes |
| 1153 | * the prefixes of the chain name |
| 1154 | * @param failureDescriptions |
| 1155 | * a list of failure descriptions for hardware resources |
| 1156 | * @return the resulting Markov Chain |
| 1157 | */ |
| 1158 | public MarkovChain initResourceFailureMarkovChain( |
| 1159 | final List<String> prefixes, |
| 1160 | final List<FailureDescription> failureDescriptions) { |
| 1161 | |
| 1162 | // Create the Markov Chain Entity: |
| 1163 | MarkovChain markovChain = markovFactory.createMarkovChain(); |
| 1164 | markovChain.setName(getName(prefixes)); |
| 1165 | |
| 1166 | // Create the Start states: |
| 1167 | State startState = addState(markovChain, StateType.START, |
| 1168 | StateType.START.toString(), prefixes); |
| 1169 | addState(markovChain, StateType.SUCCESS, StateType.SUCCESS.toString(), |
| 1170 | prefixes); |
| 1171 | |
| 1172 | // Determine the failure probability for all unavailable resources: |
| 1173 | double failureProbability = 1.0 / failureDescriptions.size(); |
| 1174 | |
| 1175 | // Create failure states and connecting transitions: |
| 1176 | for (FailureDescription description : failureDescriptions) { |
| 1177 | State failureState = addStateForFailureDescription(markovChain, |
| 1178 | prefixes, description); |
| 1179 | connectStates(markovChain, startState, failureState, |
| 1180 | failureProbability); |
| 1181 | } |
| 1182 | |
| 1183 | // Return the result: |
| 1184 | return markovChain; |
| 1185 | } |
| 1186 | |
| 1187 | /** |
| 1188 | * Creates a Markov Chain that represents a sequential execution path. |
| 1189 | * |
| 1190 | * @param prefixes |
| 1191 | * the prefixes of the Markov Chain name |
| 1192 | * @param stateNames |
| 1193 | * the names of the states to create |
| 1194 | * @param statesOut |
| 1195 | * the list of states created within the method that corresponds |
| 1196 | * to the given list of state names |
| 1197 | * @return the resulting Markov Chain |
| 1198 | */ |
| 1199 | public MarkovChain initSequentialMarkovChain(final List<String> prefixes, |
| 1200 | final List<String> stateNames, final List<State> statesOut) { |
| 1201 | |
| 1202 | // Create the Markov Chain Entity: |
| 1203 | MarkovChain markovChain = markovFactory.createMarkovChain(); |
| 1204 | markovChain.setName(getName(prefixes)); |
| 1205 | |
| 1206 | // Create the Start and Success States: |
| 1207 | State startState = addState(markovChain, StateType.START, |
| 1208 | StateType.START.toString(), prefixes); |
| 1209 | State successState = addState(markovChain, StateType.SUCCESS, |
| 1210 | StateType.SUCCESS.toString(), prefixes); |
| 1211 | |
| 1212 | // Mark the State that will later lead directly to the Success State: |
| 1213 | State stateToSuccess = startState; |
| 1214 | |
| 1215 | // Go through the chain of state names: |
| 1216 | for (int i = 0; i < stateNames.size(); i++) { |
| 1217 | |
| 1218 | // Create a Markov State for this Action: |
| 1219 | State state = addState(markovChain, StateType.DEFAULT, stateNames |
| 1220 | .get(i), prefixes); |
| 1221 | statesOut.add(state); |
| 1222 | |
| 1223 | connectStates(markovChain, stateToSuccess, state, 1.0); |
| 1224 | |
| 1225 | // Update the State leading to Success: |
| 1226 | stateToSuccess = state; |
| 1227 | } |
| 1228 | |
| 1229 | // Create the Transition leading to the Success State: |
| 1230 | connectStates(markovChain, stateToSuccess, successState, 1.0); |
| 1231 | |
| 1232 | // Return the result: |
| 1233 | return markovChain; |
| 1234 | } |
| 1235 | |
| 1236 | /** |
| 1237 | * Checks if a failure-on-demand occurrence is contained in a given list of |
| 1238 | * handled failure types. |
| 1239 | * |
| 1240 | * @param handledFailureTypeIds |
| 1241 | * the list of handled failure types |
| 1242 | * @param occurredFailureTypeId |
| 1243 | * the occurred failure type |
| 1244 | * @return true if the occurred failure type is included in the list of |
| 1245 | * handled types |
| 1246 | */ |
| 1247 | private boolean isFailureTypeHandled( |
| 1248 | final List<String> handledFailureTypeIds, |
| 1249 | final String occurredFailureTypeId) { |
| 1250 | for (String handledId : handledFailureTypeIds) { |
| 1251 | if (occurredFailureTypeId.contains(handledId)) { |
| 1252 | return true; |
| 1253 | } |
| 1254 | } |
| 1255 | return false; |
| 1256 | } |
| 1257 | |
| 1258 | /** |
| 1259 | * Names a Transition. |
| 1260 | * |
| 1261 | * @param transition |
| 1262 | * the transition to name |
| 1263 | */ |
| 1264 | private void nameTransition(final Transition transition) { |
| 1265 | transition.setName(transition.getFromState().getName() + " --> " |
| 1266 | + transition.getToState().getName()); |
| 1267 | } |
| 1268 | |
| 1269 | /** |
| 1270 | * Reduces the given Markov State in the given Markov Chain. The State is |
| 1271 | * deleted and all transitions leading to or starting from the State are |
| 1272 | * re-calculated so that the failure and success probabilities of the |
| 1273 | * overall Markov Chain are preserved. |
| 1274 | * |
| 1275 | * @param markovChain |
| 1276 | * the Markov Chain |
| 1277 | * @param stateToReduce |
| 1278 | * the state which will be reduced |
| 1279 | */ |
| 1280 | private void reduceState(final MarkovChain markovChain, |
| 1281 | final State stateToReduce) { |
| 1282 | |
| 1283 | // Assure that the State which will be reduced is contained in the given |
| 1284 | // Markov Chain: |
| 1285 | if (!markovChain.getStates().contains(stateToReduce)) { |
| 1286 | throw new MarkovException( |
| 1287 | "Cannot reduce Markov State. The Markov Chain does not contain that state."); |
| 1288 | } |
| 1289 | |
| 1290 | // Assure that the State which will be reduced is not the Start, Success |
| 1291 | // or Failure State: |
| 1292 | if (!stateToReduce.getType().equals(StateType.DEFAULT)) { |
| 1293 | throw new MarkovException( |
| 1294 | "Cannot reduce Markov State. Only intermediate states can be reduced."); |
| 1295 | } |
| 1296 | |
| 1297 | // Find and delete all transitions in the Markov Chain that lead to the |
| 1298 | // reduceable State: |
| 1299 | ArrayList<Transition> transitionsToReduceState = findTransitionsToState( |
| 1300 | markovChain, stateToReduce); |
| 1301 | deleteTransitions(markovChain, transitionsToReduceState); |
| 1302 | |
| 1303 | // Find and delete all transitions in the Markov Chain that start from |
| 1304 | // the reduceable State: |
| 1305 | ArrayList<Transition> transitionsFromReduceState = findTransitionsFromState( |
| 1306 | markovChain, stateToReduce); |
| 1307 | deleteTransitions(markovChain, transitionsFromReduceState); |
| 1308 | |
| 1309 | // Delete the reduceable State: |
| 1310 | markovChain.getStates().remove(stateToReduce); |
| 1311 | |
| 1312 | // Build new transitions to replace the deleted ones: |
| 1313 | for (int i = 0; i < transitionsToReduceState.size(); i++) { |
| 1314 | for (int j = 0; j < transitionsFromReduceState.size(); j++) { |
| 1315 | |
| 1316 | // Create a new transition: |
| 1317 | Transition transition = markovFactory.createTransition(); |
| 1318 | |
| 1319 | // Set the source and target States: |
| 1320 | transition.setFromState(transitionsToReduceState.get(i) |
| 1321 | .getFromState()); |
| 1322 | transition.setToState(transitionsFromReduceState.get(j) |
| 1323 | .getToState()); |
| 1324 | |
| 1325 | // Calculate the transition probability: |
| 1326 | transition.setProbability(transitionsToReduceState.get(i) |
| 1327 | .getProbability() |
| 1328 | * transitionsFromReduceState.get(j).getProbability()); |
| 1329 | |
| 1330 | // Set the name of the transition: |
| 1331 | nameTransition(transition); |
| 1332 | |
| 1333 | // Add the new Transition to the Markov Chain: |
| 1334 | contributeTransition(markovChain, transition); |
| 1335 | } |
| 1336 | } |
| 1337 | } |
| 1338 | |
| 1339 | /** |
| 1340 | * Removes duplicate failure states from the given Markov chain. |
| 1341 | * |
| 1342 | * @param aggregateChain |
| 1343 | * the chain to reduce |
| 1344 | * @param optimize |
| 1345 | * indicates if Markov Chain reduction shall be performed during |
| 1346 | * the transformation |
| 1347 | */ |
| 1348 | private void removeDuplicateFailureStates(final MarkovChain markovChain, |
| 1349 | final boolean optimize) { |
| 1350 | |
| 1351 | // Iterate over the failure states of the chain: |
| 1352 | List<State> failureStates = getFailureStates(markovChain); |
| 1353 | List<State> duplicateFailureStates = new ArrayList<State>(); |
| 1354 | for (State failureState : failureStates) { |
| 1355 | if (duplicateFailureStates.contains(failureState)) { |
| 1356 | continue; |
| 1357 | } |
| 1358 | List<State> matchingFailureStates = findMatchingFailureStates( |
| 1359 | failureStates, failureState); |
| 1360 | matchingFailureStates.remove(failureState); |
| 1361 | for (State matchingState : matchingFailureStates) { |
| 1362 | connectStates(markovChain, matchingState, failureState, 1.0); |
| 1363 | matchingState.setType(StateType.DEFAULT); |
| 1364 | duplicateFailureStates.add(matchingState); |
| 1365 | } |
| 1366 | } |
| 1367 | |
| 1368 | // Optimize the aggregate MarkovChain: |
| 1369 | if (optimize) { |
| 1370 | for (State duplicateState : duplicateFailureStates) { |
| 1371 | reduceState(markovChain, duplicateState); |
| 1372 | } |
| 1373 | } |
| 1374 | } |
| 1375 | |
| 1376 | /** |
| 1377 | * Checks if a Markov chain is valid. The chain is judged to be valid if |
| 1378 | * each transition has a source state and a target state, and if exactly one |
| 1379 | * start and success state exist. If a chain is not valid, a Markov |
| 1380 | * exception is thrown. |
| 1381 | * |
| 1382 | * @param chain |
| 1383 | * the Markov chain to check |
| 1384 | */ |
| 1385 | private void validateChain(final MarkovChain chain) { |
| 1386 | |
| 1387 | // Check if each transition has a source and a target node: |
| 1388 | for (Transition t : chain.getTransitions()) { |
| 1389 | if ((t.getFromState() == null) || (t.getToState() == null)) { |
| 1390 | throw new MarkovException("Invalid transiton in Markov Chain."); |
| 1391 | } |
| 1392 | } |
| 1393 | |
| 1394 | // Check if exactly one start and one success state are present: |
| 1395 | boolean hasStart = false; |
| 1396 | boolean hasSuccess = false; |
| 1397 | for (State s : chain.getStates()) { |
| 1398 | if (s.getType() == StateType.START) { |
| 1399 | if (hasStart) { |
| 1400 | throw new MarkovException( |
| 1401 | "Multiple start states in Markov Chain."); |
| 1402 | } else { |
| 1403 | hasStart = true; |
| 1404 | } |
| 1405 | } else if (s.getType() == StateType.SUCCESS) { |
| 1406 | if (hasSuccess) { |
| 1407 | throw new MarkovException( |
| 1408 | "Multiple success states in Markov Chain."); |
| 1409 | } else { |
| 1410 | hasSuccess = true; |
| 1411 | } |
| 1412 | } |
| 1413 | } |
| 1414 | |
| 1415 | if (!hasStart) { |
| 1416 | throw new MarkovException("No start state in Markov Chain."); |
| 1417 | } |
| 1418 | |
| 1419 | if (!hasSuccess) { |
| 1420 | throw new MarkovException("No success state in Markov Chain."); |
| 1421 | } |
| 1422 | |
| 1423 | // TODO: Check for transitions leading to dead ends |
| 1424 | // TODO: Check for cycles |
| 1425 | } |
| 1426 | } |