Topology control algorithms for rule-based routing.

摘要

In this dissertation, we introduce a new topology control problem for rule-based link-state routing in autonomous networks. In this context, topology control is a mechanism to reduce the broadcast storm problem associated with link-state broadcasts. We focus on a class of topology control mechanisms called local-pruning mechanisms. Topology control by local pruning is an interesting multi-agent graph optimization problem, where every agent/router/station has access to only its local neighborhood information. Every agent selects a subset of its incident link-state information for broadcast. This constitutes the pruned link-state information (pruned graph) for routing. The objective for every agent is to select a minimal subset of the local link-state information while guaranteeing that the pruned graph preserves desired paths for routing.;In topology control for rule-based link-state routing, the pruned link-state information must preserve desired paths that satisfy the rules of routing. The non-triviality in these problems arises from the fact that the pruning agents have access to only their local link-state information. Consequently, rules of routing must have some property, which allows specifying the global properties of the routes from the local properties of the graph. In this dissertation, we illustrate that rules described as algebraic path problem in idempotent semirings have these necessary properties.;The primary contribution of this dissertation is identifying a policy for pruning, which depends only on the local neighborhood, but guarantees that required global routing paths are preserved in the pruned graph. We show that for this local policy to ensure loop-free pruning, it is sufficient to have what is called an in atory arc composition property. To prove the sufficiency, we prove a version of Bellman's optimality principle that extends to path-sets and minimal elements of partially ordered sets.;As a motivating example, we present a stable path topology control mechanism, which ensures that the stable paths for routing are preserved after pruning. We show, using other examples, that the generic pruning works for many other rules of routing that are suitably described using idempotent semirings.