Self-Tuning Routing Algorithms
Self adapting protocols are attractive theoretically because they converge towards optimal operation, and practically because they eliminate classes of misconfiguration error. In order to achieve self adaption, a protocol needs to gather state information upon which to base decisions. This paper begins to address these issues by investigating the trade-off surrounding the rate at which information needs to be gathered. If information is gathered too frequently, the overhead outweighs the benefit; but gathering too infrequently means that the state information is inaccurate and sub-optimal. This trade-off is investigated analytically on some simplified abstract problems. The results reveal how there are large and distinct regions where the routing strategy is degenerate (i.e. maximal or minimal state gathering).