Check out the new USENIX Web site. next up previous
Next: Discussion Up: Evaluation Previous: Testbed


We have made a set of extensive tests, in which we have always varied one of four parameters for the subscriptions. These are namely, (1) the fraction of positive matches for a subscriber 1/c, (2) the total number of subscribers s, (3) the maximum nesting level of invocations for queries a, and (4) the number of different query methods d at each nesting level.

Varying 1/c:
From n produced messages, an average of n/c messages matched a given subscribers pattern. Figure 20(a) shows the effect of varying c. It confirms the intuition that the cost of sending messages with UDP does not depend on the matching scheme, and can be seen as fixed. With c > 100 in this scenario, the pure cost of matching is measured. In order to accentuate the differences between the matching schemes without contradicting our concrete applications, we have chosen c = 10 for the next figures.
Varying s:
Similarly to the scenario in Figure 18, we have chosen one basic condition per subscriber. Figure 20(b) reports the effect of scaling up s, conveying that the two optimizations are almost equivalent with a large s.[*] As shown in the previous figure, UDP is a limiting factor with an increasing number of sends (here due to a large s). Performance drops faster with static filters, since every additional subscriber involves a full pattern evaluation. In contrast, the optimized dynamic scheme is less sensitive since redundant queries are avoided.

Figure 20: Matching Rate and Number of Subscriptions


Varying a:
The probability of having i (in [0..a]) nested invocations was chosen as pa = 1/(a+1). Increasing a reduces throughput with static invocations (Figure 21(a)), since static accessors comprise more invocations. Similarly, the optimized dynamic scheme is less efficient with an increasing a, since the total number of performed methods increases with the depth of the tree.
Varying d:
One of d methods was chosen at each nesting level with a probability of pd = 1/d. Varying d obviously does not influence static filter evaluation. On the other hand, increasing d might lead to increasing the potential number of edges leaving from any node in the invocation tree. The resulting performance loss is directly visible in Figure 21(b). The optimized dynamic scheme is however more penalized by increasing a, as shown in the previous figure. This is due to the fact that increasing a by 1 might result in up to d new edges in every former leaf of the invocation tree.

Interestingly the optimized dynamic matching scheme never overperforms the static scheme, even if the speedups become close with a large number of message sends. One could believe that with a strong redundancy between patterns and a large number of subscribers the dynamic scheme would become more efficient. Even with extreme parameter values, we have however never encountered such a scenario.

Figure 21: Expressiveness and Redundancy of Subscriptions


next up previous
Next: Discussion Up: Evaluation Previous: Testbed
Patrick Eugster