Next: Experience with Using CANS
Up: Distributed Adaptation in CANS
Previous: Data Path Reconfiguration and
Planning and Global Reconfiguration
A plan refers to the deployment of drivers, services, and data paths
in response to a request from a client application to connect to an
end service. The key component responsible for planning in CANS is the
plan manager, which is triggered when the interception layer
detects a connect attempt on a TCP socket of interest. The plan
manager takes responsibility both for creating the original plan, as
well as changing it as required based on evolving system
conditions. Such replanning is a last resort; as stated earlier, most
changes are expected to be handled either entirely within a component
or through localized data path reconfiguration.
The planning procedure consists of two steps: route selection
where a graph of nodes and links is selected for deploying the plan,
and driver selection where appropriate drivers and services are
mapped to the selected route. Space considerations prevent us from
describing the steps in full detail, so we just highlight the overall
strategy restricting our attention to plans that involve a single
source and a single sink.
Route selection can be viewed as the shortest path problem in the node
graph, which takes into consideration bandwidth on links between nodes
in different domains and the relative loads on nodes within the same
domain.
Driver selection bridges source and sink types while (1) efficiently
using link and node capabilities along the selected route, and (2)
overcoming problems caused by link properties such as insecure
transmission and packet loss. The first subproblem amounts to
selecting type-compatible components to construct the data path such
that node and link capacities are not exceeded, and some overall path
metric (e.g., throughput) is optimized. The second subproblem imposes
restrictions on the stream type at various points in the data path;
for example, encrypted data is required in order to cross an insecure
link if the sink requires a secure stream.
Our scheme unifies these two subproblems by defining the notion of an
augmented type: each data type is extended with a set of link
properties (e.g., security, reliability, and timeliness) that can take
values from a fixed set. Network links are modeled in terms of the
same properties and have the effect of modifying, in a type-specific
fashion, values of the corresponding properties associated with
different data types. To consider an example of HTML data transmitted
over an insecure link, the data type represented by HTML(
secure=true) is modified to HTML(secure=
false) upon crossing a link with property secure=false.
As a refinement to this base scheme, some data types have the
capability to isolate others below them in the type stack
associated with a stream from having their properties be affected by a
link. For example, the Encrypted type isolates the secure
property of types that it ``wraps'', i.e., encrypted data still
remains secure after crossing insecure links.
Thus, the inputs to the driver selection process are the augmented
type at the data source, the augmented type required at the sink, and
the selected route (whose links may transform augmented types as
described earlier). We use a dynamic programming algorithm to
simultaneously select a component and map it to the route in a fashion
that optimizes overall throughput. The partial solutions that make up
the algorithm essentially look at the problem of converting the source
type to an intermediate type on a subset of the route using only a
fixed number of components. The complexity of this algorithm is
, where is the number of the components and
is the number of nodes.
Next: Experience with Using CANS
Up: Distributed Adaptation in CANS
Previous: Data Path Reconfiguration and
Weisong Shi
2001-01-08