Changes between Version 14 and Version 15 of LayoutAspect


Ignore:
Timestamp:
Sep 25, 2014 4:06:24 PM (7 years ago)
Author:
faber
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • LayoutAspect

    v14 v15  
    33= The Layout Aspect: Describing And Manipulating Experiment Topologies in DETER =
    44
    5 This page describes the model, specification and implementation of DETER's layout aspect.  The layout specifies an experiment's physcial or logical environment.  It is a description of the elements that a researcher can manipulate and a characterization of how those elements communicate.
     5This page describes the model, specification and implementation of DETER's layout aspect.  The layout specifies an experiment's physical or logical environment.  It is a description of the elements that a researcher can manipulate and a characterization of how those elements communicate.
    66
    7 Different users of a topology view it different ways. A researcher studying the propagation of a security compromise may make use of a recursive tool to create a topology.  Because the topology was generated by a recursive tool, a natural representation is in recursive chunks, which may result in a very compact specification.
     7Different users of a layout view it different ways. A researcher studying the propagation of a security compromise may make use of a recursive tool to create a layout.  Because the layout was generated by a recursive tool, a natural representation is in recursive chunks, which may result in a very compact specification.
    88
    9 The researcher has a different breakdown of the experiment than the generation tool. In their mind the topology may consist of a routing backbone, some enterprise networks, and a set of enterprise networks containing compromised computers.  This breakdown of the topology can also be characterized in terms of chunks that are defined, not by the workings of the construction algorithm, but by the semantics of the researcher's experiment.
     9The researcher has a different breakdown of the experiment than the generation tool. In their mind the layout may consist of a routing backbone, some enterprise networks, and a set of enterprise networks containing compromised computers.  This breakdown of the layout can also be characterized in terms of chunks that are defined, not by the workings of the construction algorithm, but by the semantics of the researcher's experiment.
    1010
    11 Finally, when the testbed realizes the topology, it will assign physical resources to each element and substrate.  If the topology is heavily virtualized it may be helpful for the researcher (or testbed staff) to see the topology broken into chunks that map to physical machines in the testbed.
     11Finally, when the testbed realizes the layout, it will assign physical resources to each element and substrate.  If the layout is heavily virtualized it may be helpful for the researcher (or testbed staff) to see the layout broken into chunks that map to physical machines in the testbed.
    1212
    13 We call those different descriptions of the same topology ''views'' and the testbed supports creating a topology from one view, accepting additional views from users, and synthesizing new views internally.  When viewing ore manipulating a topology, a user of the testbed can query the views available and select the one that suits their needs.
     13We call those different descriptions of the same layout ''views'' and the testbed supports creating a layout from one view, accepting additional views from users, and synthesizing new views internally.  When viewing ore manipulating a layout, a user of the testbed can query the views available and select the one that suits their needs.
    1414
    15 Inherent in a view is the definition of regions of semantic importance that can be shown, acted on, or extracted and reused by a researcher.  These regions allow the testbed to present topological information to the user only when required, enabling users to deal with the congnitive overhead and information transfer costs of manipulating large topologies.
     15Inherent in a view is the definition of regions of semantic importance that can be shown, acted on, or extracted and reused by a researcher.  These regions allow the testbed to present topological information to the user only when required, enabling users to deal with the cognitive overhead and information transfer costs of manipulating large topologies.
    1616
    17 We describe a model that suports such multi-view topologies, an API that describes how to use the model and an initial implementation in the Descartes interface.
     17We describe a model that supports such multi-view topologies, an API that describes how to use the model and an initial implementation as an aspect in the Descartes interface.
    1818
    1919== Model ==
     
    2121We describe the model in a bottom up fashion, first describing the atoms from which a view are constructed and then how to combine them into a full view.  Once we have defined the view model, we discuss specifying and manipulating multiple views through the testbed interface.
    2222
    23 The view model is not tied to the Descartes inteface, and can be used by other tools for describing and manipulating topologies.  The interfaces for creating a topology, requesting different views of it, and assigning new views are specific to Descartes.
     23The view model is not tied to the Descartes interface, and can be used by other tools for describing and manipulating topologies.  The interfaces for creating a layout, requesting different views of it, and assigning new views are specific to Descartes.
    2424
    2525
    2626=== The View Model ===
    2727
    28 Each view is a description of a topology, and we begin by explaining how to describe such a topology, from simple, explicit descriptions, to more scalable and versatile versions.
     28Each view is a description of a layout, and we begin by explaining how to describe such a layout, from simple, explicit descriptions, to more scalable and versatile versions.
    2929
    30 ==== The Fundamental Topology Model ====
     30==== The Fundamental Layout Model ====
    3131
    32 A DETER topology is a collection of experimental elements that can communicate with one another.  The topology model consists of ''elements'' that represent those experimental entities and ''substrates'' which indicate the valid commuincations scopes. An element may be specialized depending on the capabilities supplied or required.  A substrate includes limits on how the communication rate and delay when communicating through it.
     32A DETER layout is a collection of experimental elements that can communicate with one another.  The layout model consists of ''elements'' that represent those experimental entities and ''substrates'' which indicate the valid communications scopes. An element may be specialized depending on the capabilities supplied or required.  A substrate includes limits on how the communication rate and delay when communicating through it.
    3333
    34 The topology is represented as a bipartite graph where vertices are either substrates or elements.  Edges are ''interfaces''.  Each interface connects an element to a substrate, indicating that the element can communicate on the substrate.  An element may have additional communication constraints encoded in it as well.
     34The layout is represented as a bipartite graph where vertices are either substrates or elements.  Edges are ''interfaces''.  Each interface connects an element to a substrate, indicating that the element can communicate on the substrate.  An element may have additional communication constraints encoded in it as well.
    3535
    36 Each element and each substrate has a unique name in the topology.  Each interface also has a name, scoped by the element it connects to.
     36Each element and each substrate has a unique name in the layout.  Each interface also has a name, scoped by the element it connects to.
    3737
    3838We stress that these are logical descriptions.  Within DETERlab a substrate is usually realized as a virtual LAN (VLAN), but a substrate in general may capture a VLAN, a shared WDM frequency, a microwave line-of-sight or an open window across an alley.  Similarly, an interface may represent a single card in a computer or a specific radio configuration.  The mapping of interfaces or substrates to physical items is not always one-to-one.  Similarly elements are logical communicating entities.  They are specialized by the basic role they play in the experiment.  Currently the most commonly encountered element is a computer, which may be a physical machine, a virtual machine instance, or even a process.
     
    4242[[Image(Simple_topo.png)]]
    4343
    44 The image shows a simple topology encoded in our topology model.  Computers 1,2, and 3 can communicate directly because they each have an interface on Substrate A.  We omit the interface names.  Computers 2 and 3 can send as fast as 1 Gb/s but experience a 10 ms delay before the first bit transmitted arrives at the receiver.  Computer 1 is further constrained by its interface to a rate of 100 Mb/s, but sees the same delay.
     44The image shows a simple layout encoded in our layout model.  Computers 1,2, and 3 can communicate directly because they each have an interface on Substrate A.  We omit the interface names.  Computers 2 and 3 can send as fast as 1 Gb/s but experience a 10 ms delay before the first bit transmitted arrives at the receiver.  Computer 1 is further constrained by its interface to a rate of 100 Mb/s, but sees the same delay.
    4545
    4646Computers 3 & 4 can also communicate directly over Substrate B.
     
    5454The basic model specifies communication networks at a fairly high degree of abstraction while maintaining mechanisms for specialization.  However, large topologies present several problems:
    5555
    56  * Storing and transferring the entire topology can be wasteful if the researcher is only interested in manipulating or viewing parts of it
    57  * There is no effective way to annotate subgraphs of the topology, though this is a natural way for researchers to specify and manipulate complex topologies
    58  * There is no way to specify subgraphs of a topology beyond enumerating them
     56 * Storing and transferring the entire layout can be wasteful if the researcher is only interested in manipulating or viewing parts of it
     57 * There is no effective way to annotate subgraphs of the layout, though this is a natural way for researchers to specify and manipulate complex topologies
     58 * There is no way to specify subgraphs of a layout beyond enumerating them
    5959
    60 The ''region'' element addresses these shortcomings.  A region is a placeholder in a topology that stands in for a subgraph, called a ''fragment''.  The region includes a natural language description of the missing subgraph and provides enough detail on how to generate the missing fragment.  Note that fragments may also contain regions.
     60The ''region'' element addresses these shortcomings.  A region is a placeholder in a layout that stands in for a subgraph, called a ''fragment''.  The region includes a natural language description of the missing subgraph and provides enough detail on how to generate the missing fragment.  Note that fragments may also contain regions.
    6161
    62 Fragments are specified outside the topology description.  In fact, a fragment is exactly a topology description, so fragments can be combined easily. 
     62Fragments are specified outside the layout description.  In fact, a fragment is exactly a layout description, so fragments can be combined easily. 
    6363
    6464A region specifies the fragment that it is standing in for by name. That name may be a pointer into a larger data structure that includes a fragment pool or a pointer to a service that can provide the fragment.  Each region contains rules mapping the region's  interfaces to elements in the fragment (of course the region's interfaces cannot be mapped to substrates in the fragment, because that would violate the bipartite rules of the graph).
    6565
    66 In order to keep the names unique in the fully expanded topology, each region also contains rules used to rename the fragment elements and substrates when the region is expanded.  There is some complexity to this that we expand on below.
     66In order to keep the names unique in the fully expanded layout, each region also contains rules used to rename the fragment elements and substrates when the region is expanded.  There is some complexity to this that we expand on below.
    6767
    68 Here is a small topology with several regions defined:
     68Here is a small layout with several regions defined:
    6969
    7070[[Image(Unexpanded.png)]]
     
    7676[[Image(Fragment.png)]]
    7777
    78 So that when R3 is expanded the overall topology looks like this:
     78So that when R3 is expanded the overall layout looks like this:
    7979
    8080[[Image(Expanded.png)]]
     
    8282==== Recursive Regions ====
    8383
    84 Fragments can contain regions, so topology descriptions can be recursive.  These topology descriptions are used to allocate testbed resources, so the model insures that all recursions terminate.  Each region is assigned a non-negative integer valued level.  The outermost specification of topology can has region levels assigned by the user. When a region is inserted into a topology as a member of a fragment that replaces a region, we assign all regions in that replacement a level one less than the region that was expanded.
     84Fragments can contain regions, so layout descriptions can be recursive.  These layout descriptions are used to allocate testbed resources, so the model insures that all recursions terminate.  Each region is assigned a non-negative integer valued level.  The outermost specification of layout can has region levels assigned by the user. When a region is inserted into a layout as a member of a fragment that replaces a region, we assign all regions in that replacement a level one less than the region that was expanded.
    8585
    86 This is probably more intuitive with an example.  Here is a topology:
     86This is probably more intuitive with an example.  Here is a layout:
    8787
    8888[[Image(Recursion.png)]]
    8989
    90 And here is the fragment F1.  The fragment and the top level topology are exactly the same, including the fragment recursively including itself in each of the regions in it.
     90And here is the fragment F1.  The fragment and the top level layout are exactly the same, including the fragment recursively including itself in each of the regions in it.
    9191
    9292[[Image(Recursion_Frag.png)]]
    9393
    94 When the testbed (or a tool) expands the topology the first time, this topology results.  The labels are the level variable of each region.
     94When the testbed (or a tool) expands the layout the first time, this layout results.  The labels are the level variable of each region.
    9595
    9696[[Image(Recursion1.png)]]
     
    100100[[Image(Recursion2.png)]]
    101101
    102 And those last remaining level 1 regions expand into single computers just as the first one did, leaving the full topology:
     102And those last remaining level 1 regions expand into single computers just as the first one did, leaving the full layout:
    103103
    104104[[Image(Recursion3.png)]]
     
    106106==== Naming and Recursion ====
    107107
    108 We have been vague about how names are assigned to elements and substrates in recursions.  In the simplest case, where the topology specifier does not care how those names are assigned, they can be assigned by the testbed (or tool).  If the user wants a specific layout of names the pathname system can be used.
     108We have been vague about how names are assigned to elements and substrates in recursions.  In the simplest case, where the layout specifier does not care how those names are assigned, they can be assigned by the testbed (or tool).  If the user wants a specific layout of names the pathname system can be used.
    109109
    110 Each element or substrate in a topology was either named directly (at the top level) or results from an expansion of a region.  By prepending the name of an element with the name of the region from which it was expanded, each substrate or element acquires a unique path name.  That assumes that each expansion preserves the property than element and substrate names are unique, but the system can enforce this.
     110Each element or substrate in a layout was either named directly (at the top level) or results from an expansion of a region.  By prepending the name of an element with the name of the region from which it was expanded, each substrate or element acquires a unique path name.  That assumes that each expansion preserves the property than element and substrate names are unique, but the system can enforce this.
    111111
    112 Should a user need control over each name, that user must supply an an explicit map of fragment name to topology name at each region element.  The maps are bound to regions by pathname of the region.
     112Should a user need control over each name, that user must supply an an explicit map of fragment name to layout name at each region element.  The maps are bound to regions by pathname of the region.
    113113
    114 The model supports hybrid solutions, where some areas of a topology include user-specified name maps and some regions of the topology are named by the testbed (or tool).  The rule is that testbed-assigned names are provisional and can be overriden by specific user assignments.
     114The model supports hybrid solutions, where some areas of a layout include user-specified name maps and some regions of the layout are named by the testbed (or tool).  The rule is that testbed-assigned names are provisional and can be overriden by specific user assignments.
    115115
    116116=== Multiple Views ===
    117117
    118 A researcher defines a topology by presenting the testbed with a view of it.  The testbed may create other views and researchers may provide new views.  Each view is named and has an associated description.  Conventions will certainly appear for naming views with common functions. Researchers viewing or manipulating a topology can request the view that makes the most sense.
     118A researcher defines a layout by presenting the testbed with a view of it.  The testbed may create other views and researchers may provide new views.  Each view is named and has an associated description.  Conventions will certainly appear for naming views with common functions. Researchers viewing or manipulating a layout can request the view that makes the most sense.
    119119
    120120The most complex part of this is allowing researchers to provide a new view to the testbed.  This is an essential feature, because researchers can provide the domain specific views that make working with topologies effective for them.  However it is the most difficult case for the testbed,
    121121
    122 If a researcher presents a view of an existing topology and both views have names assigned to all elements and substrates, it is straightforward to confirm that the new view matches the existing view(s) of the topology. Comparing a view with no names assigned to an existing view is an instance of the [http://en.wikipedia.org/wiki/Graph_isomorphism graph isomorphism problem].  That problem is NP-hard (but not necessarily NP-complete), so confirming that the two views are isomorphic and adding the names to the new view can be computationally intensive.  Middle grounds where some nmaes have been assigned may be easier.
     122If a researcher presents a view of an existing layout and both views have names assigned to all elements and substrates, it is straightforward to confirm that the new view matches the existing view(s) of the layout. Comparing a view with no names assigned to an existing view is an instance of the [http://en.wikipedia.org/wiki/Graph_isomorphism graph isomorphism problem].  That problem is NP-hard (but not necessarily NP-complete), so confirming that the two views are isomorphic and adding the names to the new view can be computationally intensive.  Middle grounds where some names have been assigned may be easier.
    123123
    124124Implementations will support adding new views to the extent that it is possible to do so.
     
    126126== Interfaces ==
    127127
    128 This section discusses the encodeing of a view used for exchange and the interfaces to the Descartes interface that are relevant to manipulating topology views.
     128This section discusses the encoding of a view used for exchange and the interfaces to the Descartes interface that are relevant to manipulating layout views.
    129129
    130130The exact format of these interfaces - the XSD defining the exchange format and RPC calls - are still in a bit of flux.
     
    143143The substrates and elements sections are exactly as defined in [http://fedd.deterlab.net/wiki/TopDl topdl v1], except that regions are allowed as elements.  A region includes a name and the fragment name that it expands to.  The fragment name is either the name of a fragment in the fragments section, or a name that can be used to request the fragment from the testbed.
    144144
    145 The fragments section contains fragment objects that are composed of elements and substrates.  These may be referenced by region objects in the main topology or by region elements in fragements.
     145The fragments section contains fragment objects that are composed of elements and substrates.  These may be referenced by region objects in the main topology or by region elements in fragments.
    146146
    147147The name maps are a set of mappings, keyed by the pathname of a region.  Each includes
     
    169169 * The CPU element used to express the number of CPUs being described as an XML attribute rather than an element.  It was the only entity in topdl that did that, and it no longer does.  There is a count element in the CPUType definition now.
    170170
    171 === Topology Calls to the Experiment API ===
     171=== Layout Calls to the Experiment SPI ===
    172172
    173 Researchers interested in working with experiment topologies manipulate the topology aspect of an experiment.  It is possible to have multiple topology definitions for an experiment that are divided into regions differently, as long as they all are isomorphic.
     173Researchers interested in working with experiment layouts manipulate the layout aspect of an experiment.  It is possible to have multiple layouts definitions for an experiment that are divided into regions differently, as long as they all are isomorphic.
    174174
    175 When a topology aspect is added, the testbed generates aspects of type topology and the following subtypes.  This happens whether the topology aspect is added using `experimentCreate()` or `addExperimentAspect()`.
     175When a layout aspect is added, the testbed generates aspects of type layout and the following subtypes.  This happens whether the layout aspect is added using `experimentCreate()` or `addExperimentAspects()`.
    176176
    177  full_topology::
    178   The topology with all regions expanded.  The name is the topology aspect with "/full_topology" appended.
    179  minimal_topology::
    180   The topology with no regions expanded and no fragments or namemaps attached.  This is the quickest and dirtiest topology available for visualization.  The name is the topology aspect with "/minimal_topology" appended.
     177 full_layout::
     178  The layout with all regions expanded.  The name is the layout aspect with "/full_layout" appended.
     179 minimal_layout::
     180  The layout with no regions expanded and no fragments or namemaps attached.  This is the quickest and dirtiest layout available for visualization.  The name is the layout aspect with "/minimal_layout" appended.
    181181 fragment::
    182   A fragment of the given topology.  The name is the aspect name with "/" and the name of the fragment appended.  These are used to incrementally expand a minimal_topology
     182  A fragment of the given layout.  The name is the aspect name with "/" and the name of the fragment appended.  These are used to incrementally expand a minimal_layout
    183183 namemap::
    184   A namemap from the topology expansion.  The name is the aspect name with the namemap pathname appended. These are used to incrementally expand a minimal_topology
     184  A namemap from the layout expansion.  The name is the aspect name with the namemap pathname appended. These are used to incrementally expand a minimal_layout
    185185
    186 A new version of the topology can be added at any time using `addExperimentAspect()`, but the call will fail topologies that are not isomorphic to the experiment's current topology aspect.  Adding a topology to an experiment without a topology aspect always succeeds.
     186A new version of the layout can be added at any time using `addExperimentAspects()`, but the call will fail for layouts that are not isomorphic to the experiment's current layout aspects.  Adding a layout to an experiment without a layout aspect always succeeds.
    187187