Information Technology Reference
In-Depth Information
F
IG
. 27. Comparison of several algorithms for retrieving objects from parallel channels.
This is especially important when a large percentage of the objects in a broadcast are
requested.
7.1.4 Simulation Results
As expected, the TSP methods provide much better results than both the Next
Object and Row Scan heuristics. Simulation results showed that the TSP heuristic
performed almost exactly as well as the optimal TSP algorithm. This is a very inter-
esting observation, because it means that one can use a fast heuristic, rather than a
slow but exact algorithm, to schedule retrievals of objects from the broadcast without
any performance degradation.
Figure 27
used 5 parallel channels and 20 pages per channel. It is also interest-
ing to note that the straightforward row scan nearly matches the performance of the
TSP-based algorithm when more than about 45% of the total number of objects is
requested. In this case, there are so many conflicts that it is virtually impossible to
avoid having to make as many passes as there are parallel channels. When this oc-
curs, it is better to do the straightforward row scan than to spend time and resources
running a TSP heuristic.
7.1.5 Number of Broadcast Channels
One of the important questions that must be answered in designing a broadcasting
system is how many parallel channels to use for broadcasting information. More
channels means shorter broadcast length and more potential for conflicts.
Figure 28
shows the number of pages of data that must be broadcast, on average, to retrieve
K
