The final publication is available at www.springerlink.com from http://link.springer.com/chapter/10.1007/978-3-642-37450-0_12 Algorithm 1: Selection of Replacement Sample Program Input appname), structure of the input stream application (G), transformation depth (d), number of nodes (nodes) Output : Replacement sample program (selectedLabel) Description : 1: optrunDict getLatestThreeOptrunIDs(appname, G, d, nodes) 2: for all optrun in optrunDict do /* Get sample program performance details */ 3: perfDict[optrun getPerfInfoForOptrun(optrun) 4: end for 5: labelDiffTable 6: for all optrun in perfDict do /* Aggregate throughput information for each label */ 7: for all label in optrun do 8: labelDiffTable[label].append(optrun[label]) 9: end for 10: end for 11: inputStat /* Find range, average, */ 12: labelPerfStat /* min, max throughput */ 13: for all label in labelDiffTable do: /* values for each group */ 14: labelPerfStat[label].range range(labelDiffTable[label]) 15: labelPerfStat[label].average average(labelDiffTable[label]) 16: labelPerfStat[label].min minimum(labelDiffTable[label]) 17: labelPerfStat[label].max maximum(labelDiffTable[label]) 18: if label is Input App then 19: inputStat labelPerfStat[label] 20: end if 21: end for /* Sort labels ascending order using range values */ 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41 sortByRangeAsc(labelPerfStat) selectedLabel /* Select sample program with higher average */ /* throughput compared to the Input app*/ for all label in labelPerfStat do: if label.min > inputStat.max then selectedLabel break end if end for if selectedLabel = Ø then /* If could not find a suitable app, */ for all label in labelPerfStat do: /* select using average throughput */ if label.average > inputStat.average then selectedLabel break end if end for end if if selectedLabel = Ø then /* If no suitable app found then return the input app*/ selectedLabel appname end if return selectedLabel Thousands 17:25:48 17:26:03 17:26:18 17:26:34 17:26:49 17:27:04 17:27:19 17:27:35 17:27:50 17:28:05 17:28:20 17:28:35 17:28:51 17:29:06 17:29:21 17:29:36 17:29:51 17:30:07 17:30:22 17:30:37 17:30:52 17:31:08 17:31:23 17:31:38 17:31:53 17:32:08 17:32:24 17:32:39 17:32:54 17:33:09 17:33:24 17:33:40 Throughput (B\s) Thousands 80 10 0 70 10 Change of performance for Regex and VWAP applications when two nodes were crashed in a cluster of 8 nodes 60 50 40 8 Nodes Time (Time of the day) 8 Nodes 20 Two nodes Crashed Thousands 70 6 Nodes regex VWAP 30 20 Throughput (B\s) 90 12:41:11 12:41:21 12:41:31 12:41:42 12:41:52 12:42:02 12:42:12 12:42:22 12:42:32 12:42:42 12:42:52 12:43:02 12:43:12 12:43:22 12:43:33 12:43:43 12:43:53 12:44:03 12:44:13 12:44:23 12:44:33 12:44:43 12:44:53 12:45:03 12:45:13 12:45:23 12:45:34 12:45:44 12:45:54 12:46:04 12:46:14 12:46:24 12:46:34 12:46:44 12:46:54 12:47:04 12:47:14 12:47:25 12:47:35 12:47:45 12:47:55 12:48:05 12:48:15 12:48:25 12:48:35 12:48:45 12:48:55 12:49:05 12:49:15 12:49:26 12:49:36 12:49:49 12:49:59 12:50:09 12:50:19 12:50:29 12:50:39 12:50:49 12:50:59 12:51:09 12:51:19 12:51:29 12:51:40 12:51:50 12:52:00 12:52:10 12:52:20 12:52:30 12:52:40 12:52:50 12:53:00 12:53:10 Throughput (B\s) 100 9 8 7 Throughput of sample programs generated for VWAP application over Six Calibration runs (d = 8, Nodes = 6) 6 5 4 3 Opt run 2 2 Opt run 3 1 Opt run 1 0 Two nodes crashed Opt run 4 Opt run 5 Opt run 6 (a) Sample Program Label 6 Nodes 50 30 Discharge of contents of input tuple buffer Recovery completed Time (Time of the day) (b) 90 80 Performance recovery process for Regex application during two consecutive node crashes 60 4 Nodes 40 Two nodes crashed Discharge of contents of input tuple buffer Recovery completed New Sample Program For 6 Nodes New Sample Program For 4 Nodes Initial Sample Program 0 Throughput (B\s) Thousands 2 8 Nodes 6 Two nodes crashed 4 Initial Sample Program New Sample Program Time (Time of the day) (a) Recovery completed 0 Thousands 6 Nodes Throughput (B\s) Performance recovery process for VWAP application with input tuple Discharge of contents buffering of input tuple buffer 8 100 80 60 40 20 19:52:41 19:53:12 19:53:42 19:54:12 19:54:42 19:55:13 19:55:43 19:56:13 19:56:44 19:56:59 19:57:14 19:57:29 19:57:44 19:57:59 19:58:15 19:58:30 19:58:45 19:59:00 19:59:15 19:59:30 19:59:45 20:00:01 20:00:16 20:00:31 20:00:46 20:01:01 20:01:16 20:01:32 20:01:47 20:02:03 20:02:18 20:02:33 20:02:48 20:03:03 20:03:18 20:03:34 20:03:49 20:04:04 20:04:19 20:04:34 20:04:59 20:05:15 20:05:30 20:05:45 20:06:00 20:06:15 20:06:30 20:06:45 10 16:03:22 16:03:42 16:04:02 16:04:23 16:04:43 16:05:03 16:05:24 16:05:44 16:06:04 16:06:24 16:06:45 16:07:05 16:07:25 16:07:46 16:08:06 16:08:26 16:08:47 16:09:07 16:09:35 16:09:55 16:10:15 16:10:36 16:10:56 16:11:16 16:11:37 16:11:58 16:12:18 16:12:38 16:12:58 16:13:19 16:13:39 16:13:59 16:14:20 16:14:40 16:15:00 12 140 120 Performance recovery process for Apnoea application during two consecutive node crashes Two nodes crashed 6 Nodes 8 Nodes Recovery completed 4 Nodes Two nodes crashed New Sample Program for 6 Nodes New Sample Program for 4 Nodes Initial Sample Program 0 Time (Time of the day) (b) Recovery completed