Transcript A Framework for Developing Mobile Active Services

Autonomic Networks
Customisable
Identifiers
Jan 03 - 06
Schloss Dagstuhl
Manolis Sifalakis
[email protected]
Dagstuhl Seminar 06011
Lancaster University
Abstract
• In this presentation the idea of generating customised identifiers is
promoted. Whether the identifiers are used to identify nodes, code
modules, or other functional elements, the identifier space used can
be optimised to include semantics that will assist and better the
routing and network processing within the design space. In this
presentation we consider one possible way of integrating the
wanted semantics in the identifiers.
• One example where this is partly realised is IPv6 address format
where the site local part of the address is left to the address space
owner to customise, whilst the TLD and SLD semantics remain "hard
coded" in it. Algebraic operations like the one proposed here can be
used to intcorporate site specific semantics. Then, these semantics
(be it device type, geo location, link type, etc) can be easily taken
into account by custom intra-site routing/forwarding algorithms to
optimise their performance.
Dagstuhl Seminar 06011
Lancaster University
Overview
• Properties of a potentially Autonomic Network
• Customisability is of key importance for Autonomic Networks
• Lessons and realisations from the Internet experience
 That we may want to keep in mind when designing Aut. Networks.
• Need for an Identifier Abstraction Framework (?)
• The S-Identifier framework: Idea
• Example case study
• Applications
• 2DO List
Dagstuhl Seminar 06011
Lancaster University
Properties of an Autonomic network
• Autonomic as a “living being” or a control system that can recover
from instability ?
• Self-configurability
 From zero initial state (bootstrap)
 Driven by policies/heuristics/high level goals
• Capacity for Adaptability
 Flexible/extensible/open design to adapt or extend functionality
• Reactiveness
 Sense/measure->react cycle, based on built-in/learned knowledge
• Customisability
 Modify its operational semantics and properties
 To always satisfy the goals and policies of its design space
• Self-management
 Act in response to external conditions/policies/internal state and
customise the self, w/o human intervention
Dagstuhl Seminar 06011
Lancaster University
Autonomic Nets = f (Customisability)
• At the network layer customise:




Identifier semantics
Location semantics
Topology
Routing/forwarding functions
• What drives customisability
 Physical environment, mission, app/service requirements, policies
• Examples (how can these aspects be optimised)




A wired structured IP network
An mobile adhoc flat addressed IP-less network
A set of ICs on a PCI Express network
A structured fixed low-power sensor network
Dagstuhl Seminar 06011
Lancaster University
Lessons learned so far
• Addressing and the address space structure influence
the routing topology
 in structured networks
• Proximity in the address space does not always imply
routing/path proximity
 however it often does in the case for hierarchical address spaces
• Locality is important when mapping one address space
on another
 to avoid unnecessary traffic and routing overhead
• Uniform/universal identifiers are good for
 abstracting from underlying technology dependencies
 providing a common abstraction for all overlying functions/apps
Dagstuhl Seminar 06011
Lancaster University
More lessons learned
• However, universal does not mean global. Global
identifiers are no good
 Rigid, non adaptive
•
A change/modification can take years/decades to employ
 Hard to (re-)define or change an allocation strategy
•
Think of classfull allocation versus CIDR and hierarchical versus flat
allocation
 Often Inefficient
•
Think of the number of bits required/wasted in IPv6 to make it
global so as to accommodate different semantics (TLD hierarchy,
flat link layer addresses)
 Hard to tailor its semantics to problem/environment/function
requirements
Semantics determine the algorithms for routing etc.
Different problems have different semantics.
• Global semantics sacrifice efficiency/effectiveness of the routing and
other functions to be generic
•
•
Dagstuhl Seminar 06011
Lancaster University
An Identifier Abstraction Framework
• Help abstract applications and services from the routing
infrastructure semantics
 Not isolate though (we don’t want to restrict interactions)
• Below any custom routing/switching technology provides
a network transport
• Universal identifiers
• Not Global identifiers!
 Just namespaces
 And locally scoped IDs
• Customisable semantics
Dagstuhl Seminar 06011
Lancaster University
The idea
• An internetwork comprises by a set of custom routing infras
(compartments, turfs, clusters, domains)
 Network transport, topology, structure, connectivity patterns
• Within each domain IDs are generated by algebraic functions that
combine various amortisable semantics: S(emantic)-functions
 Interdomain semantics  Intradomain semantics
 Interdomain: AS-num, physical coordinates, subnet, device type, …
 Intradomain: hash key, LL address, IP address, …
• Addressing across domains uses namespace specifiers (as in C++)
 Again routing is left undefined at this level
 “Dynamic binding” principles can attach a specific forwarding or packet
processing function within a domain or across domains
• Seen before in IPv6 but not quite the same (address scopes, opt hdrs)
 The semantics (even the intradomain ones) are fixed
 IPv6 defines global functions for routing.
Dagstuhl Seminar 06011
Lancaster University
Start simple: case study
• Include locality semantics:
(S-function): S (x) = a  N(x)  (1 - a)  H(x), 0 ≤ a ≤ 1
x: network transport address
N(x): Normalizing function
a: amortizing coefficient
H(x): Randomizing function
: mul/add/concat/etc
• Advantages
 Universal identifier space for any overlay system
 Apps always perceive the same interface for addressing and
identifying nodes or clusters of nodes
 Controls locality and removes dependency from p2p adhoc
mechanisms, and potentially small-worldiness
Dagstuhl Seminar 06011
Lancaster University
How does it work ?
• S-IDs map to transport addresses: N(x)
• S-IDs map to other semantics: H(x)
 location, domain info, AS-num, transport type
• Amortising coefficient “a” regulates the
effects of the two contradicting factors
• Identifiers can identify nodes or groups of
nodes
Dagstuhl Seminar 06011
Lancaster University
S-IDs Example
• IPv4 network transport, : arithmetic addition, H(x): returns a
random number from an IP address, N(x): masks IP address to its
/28 netmask.
• x-axis:
continuous
block of IP
addresses
Dagstuhl Seminar 06011
Lancaster University
S-IDs Example: Varying “a”
a = nx px (1-p)
(Binomial cumulative function)
n-x
1.2
1
s-ID .
0.8
0.6
0.4
0.2
0
0
10
20
30
address range .
40
50
60
Dagstuhl Seminar 06011
Lancaster University
S-IDs Example: Varying “a”
a = x/n + λe-λx (Exponential function)
1. 2
1
s-IDs
0. 8
0. 6
0. 4
0. 2
0
0
10
20
30
IP Address Range
40
50
60
Dagstuhl Seminar 06011
Lancaster University
S-IDs Example: Varying “a”
a = 1-(2/σ(2π)) e-(x-μ)
2 / 2σ2
(Inv. Gaussian based function)
1. 2
1
s-ID .
0. 8
0. 6
0. 4
0. 2
0
0
10
20
30
IP Address Range
40
50
60
Dagstuhl Seminar 06011
Lancaster University
Effects
• Per-domain customisation of locality
 Responsibility offloaded from the routing system (overlay, p2p or
other protocol)
 Can improve proximity estimation in structured overlays w/o
requiring landmarks, additional signalling traffic or long
convergence periods
• Promotes per-domain selection of custom data transport
• Independence of network transport identifiers
• In case of structured transport ID-spaces may influence
“Small World” effect
 In a way that maps to the network topology (unlike most overlay
systems currently)
Dagstuhl Seminar 06011
Lancaster University
Application in SAND
• Directory service for discovering active resources
 Scalable, Customisable, Distributed, Dynamic
• Why
 What can the network do for me (my flow) ?
•
Enable/better the e3e service provisioning
 What can I do for the network ?
Virtualise my network role/identity – integrate new functions
• Support the self-association process
• Leverage the formation of autonomic topologies
•
• Where
 Along a data path
 Along-side a data path
 Within a neighbourhood
Dagstuhl Seminar 06011
Lancaster University
SAND Client Interface
ResourceList FindResources (<P>, <FilterSpec>)
ResourceList :
ResType1 : Hostm, Hostn…
<P> : <L1 , L2 , … Ln>, (n > 0)
AS-num, NPS Coordinates, Transport IDs
<FilterSpec> : description of information requested
• Along the data path
 FindResources ((L1, L2, L3), FilterSpec(EE=Java))
• Along all possible data paths between endnodes
 FindResources ((L1, *, L3), FilterSpec(EE=Java))
• Along side the data path
 FindResources ((L1, *, L3), FilterSpec(EE=Java && DistHop=5))
• Within a network neighborhood
 FindResources ((L1), FilterSpec(Function=MIPv6 HA))
 FindResources ((L1), FilterSpec(Function=MIPv6 HA))
Dagstuhl Seminar 06011
Lancaster University
Breaking down the problem
Resource
Discovery
Resource
Specification
(WHAT)
Location
Specification
(WHERE)
<P>
<FilterSpec>
SAND Arch.
Directory Layer
S-ID Abstraction Layer
Dagstuhl Seminar 06011
Lancaster University
Other applications
• Aspect of customisation in p2p systems
• Unified addressing/interfacing between
heterogeneous networks
 Imagine an IP node communicating with an
IC on a PCI express board
• Improve routing resilience (?)
 Promote small worlds
Dagstuhl Seminar 06011
Lancaster University
Current 2Do List
• Effect on locality (routing and traffic overhead)
 Pastry
 Compare with previous work on locality
• Impact on the small-world effect
 Generate some topologies
 Use pastry or other overlay systems with S-IDs
 Measure using Watt-Strogatz’s(1) metrics the impact
on overlay topology creation
(1)
D. J. Watts, S. H. Strogatz, "Collective dynamics of 'small-world'
networks", Nature 393, 1998
Thanks for the patience
…
Autonomic Networks
Jan 03 - 06
Schloss Dagstuhl