Transcript Efficient Algorithms for Large-Scale Topology Discovery

OneLab
An Open Federated Laboratory
to evaluate the possible
futures of the Internet
Serge Fdida
http://www-rp.lip6.fr/~sf/
Université Pierre et Marie Curie – Paris 6
Laboratoire LIP6 – CNRS
France
SBRC 2008, May 29, Rio de Janeiro
Remaining grand
challenges in networking:
Are there any?
Short answer!
Pick one :
YES
NO
Is there a future for the
INTERNET?
Vision
•Explore the possible Future(s) of the
Internet
•Realistic view
–
Continuous evolution and change
•The future Internet might be Polymorphic
•
•
•
Various research projects, scientists and
“people” will propose new ideas
Building blocks
Architectures
4
Vision
•Networked Systems are predominant,
with various forms
•Virtual Worlds are emerging
•Moving more from connectivity to content
•An enabler for service creation
•An enabler for competition
5
Changes
•Increased heterogeneity of devices and
networks
•Mobility and Dynamicity
•Increased management complexity
•Security and Trust
•An increasing variety of applications
•Managed and unmanaged systems
6
Economical/Social factors
•Usage and Services will become
predominant
•User-centric approach to system design
•Other factors than technology will be
instrumental
–
Economics, Social behaviors, Entry cost,
Regulation…
7
8
The Polymorphic Internet :
Some Internet Future(s)
•The Network is a Database
•The (Access) Network is Wireless
•The Network is the People
•The Network is a global Virtualized
resource
•They’re all Federated
9
Some observations on recent
evolutions
• CONTENT, who cares about Packets
–
Content distribution is the communication rationale
–
Popular content is likely to be “en route”. No need to fetch it
from a server/peer, or, at least doest not make sense to send
thousands of unicast streams
–
Shared (“Data to Many”)
–
Traffic Engineering moving from flows to services
–
DPI (Deep Packet Inspection) is becoming available
• The MEDIATION router
10
The Network is the people
•Services where infrastructure is lacking or
damaged
•Intermittent connectivity
•Multiple access opportunities
•A challenge for the Services
•Opportunistic networking
•DTN approaches
12
Mobility
•Always ON is not for the
network
•Mobility favors interest
•Mobility increases capacity
•Mobility is very context
sensitive
–
Disturbance
–
Silence, …
13
Virtualized networked systems
• Today, there is already a rationale for going to
virtualized servers in Enterprise Networks
• The networked system connects Virtualized
Resources
• Network clients are themselves less persistent
(mobile, nomadic, ambient intelligence)
• On-demand Networking
• Virtualized networks to support a Polymorphic
Internet
• Federation comes into the big picture
• Managing, Securing the virtualized environment
14
Federation concept
www.one-lab.org
• Federation is more than interconnection
• API, Policies
• Governance, Trust, Economics
• Interoperable naming system
• Service discovery
• Resource management in a Federated environment
–
A user in a single domain
–
A domain in a federation
–
Incentive for federation
•
•
Fixed contribution
Reliability, Heterogeneity, Amount of resources
–
Resource management
–
A user outside the federation
16
What are our main questions?
• How to assess the assumptions and solutions
explored by the research projects?
• Building a Facility, which affordable long-term
vision can we develop?
• What is a reasonable starting point?
• How to study different transition scenarios?
• What are the purposes to be served?
• What are the facility-specific research
challenges?
17
WARNING!
Building a testbed is not REWARDING
It requires a lot of resources and is hard to
publish
Still ….
18
OneLab 1 & 2 Vision
OneLab: An Open Federated Laboratory Supporting
Network Research for the Future Internet
• Develop and operate a large facility to support
networking research and evaluate design
solutions
• Supports current and emerging architectures
• Adopts a pragmatic approach:
19
–
Evaluates challenges and proposed solutions
–
Deploys incrementally
–
Supports the federation concept
–
Builds towards a long-term objective
OneLab History
Oct’03 March’04
ENEXT
NoE
Testbeds
PlanetLab
Europe
Initiative
May’04
Sept’05
OneLab
submitted
as IST
STREP
PlanetLab
meeting in
Cambridge
NSF GENI
Initiative
20
Sept’06
Onelab
funded as
IST project
(Strep),
2 years 3M€
Dec’07
OneLab2
accepted as
IST project
(IP),
2 years10M€
Building The Facility
• Research projects are the roots for exploring
the future(s) of the Internet
• Other proposals might be developed
independently (outside ICT)
• Develop incentives for research projects (at
large) to experiment with their ideas
• Lower the entry cost for experimentation
• An open and federated facility
–
–
–
Provide some diversity
General and dedicated resources made available
At scale, with international visibility and usage
21
The starting point
•Do not start from scratch
–
Too long to make the “utility function” high
enough in the short-medium term
•Initialize with existing testbeds
•Enforce the federation concept to expect
a convergence in the long-term
•Assess the usefulness of what is provided
regularly enabling a platform for research
projects
22
Evaluation
• Enforce the projects to evaluate their proposal with
some form of experiments
–
Proof-of-concept
• Instrument the experiments and make data public
(when possible)
• Define “Benchmarking” environments wrt target
objectives
–
even if it is hard, or at least, provide a well-defined set of
parameters to be able to reproduce the results
• Provide a repository for the data
• Liaison with other initiatives at the international level
23
Outline
•PlanetLab
•OneLab
•Services, management and operation
26
PlanetLab overview
28
PlanetLab nodes
Single PLC
located at
Princeton
• 842 machines spanning
• 416 sites
• 35 countries
29
PlanetLab in Brazil
• 5 sites and 10 nodes
–
RNP - Ceara
–
Universidade Federal de Minas Gerais
–
RNP - Rio de Janeiro
–
Federal University of ABC - Santo André
–
RNP - Rio Grande do Sul
30
Inside a node
Node
Mgr
Owner
VM
VM1
VM2
…
VMn
Virtual Machine Monitor (VMM)
Kernel
Hardware
31
VMM
• Linux
–
significant mind-share
• Vserver
–
scales to hundreds of VMs per node (12MB each)
• Scheduling
–
CPU
•
–
link bandwidth
•
•
–
fair share per slice
peak rate limit: set by each site (100Mbps default)
disk
•
–
fair share per slice (guarantees possible)
5GB quota per slice (limit run-away log files)
memory
•
no limit
32
Sliver Access
34
Zero Slice on nodes
35
Slice 1 with 9 Slivers
36
Slice 2 with 7 slivers
37
Slices
38
Sensors
•Sensors are services located on a slice.
•Used for Auditing & Monitoring
–
PlanetFlow
•
logs every outbound IP flow on every node
–
–
retrieves packet headers, timestamps, context ids (batched)
•
used to audit traffic
•
aggregated and archived at PLC
SliceStat
•
has access to kernel-level / system-wide information
–
accesses /proc via Proper
•
used by global monitoring services
•
used to performance debug services
41
Long-Running Services
• Content Distribution
–
CoDeeN: Princeton (serving > 1 TB of data per day)
• Internet Measurement
–
ScriptRoute: Washington, Maryland
• DHT
–
Chord (DHash): MIT
• DNS
–
CoDNS: Princeton
• Brokerage Services
–
Sirius: Georgia (Time and CPU priority)
• Monitoring/Discovery Services
–
CoMon: Princeton
42
User experiments
• Research and commercial experiments
–
Testing a peer-to-peer game architecture, On-demand streaming service:
CERNET
–
Measuring availability to/from multi-homed sites on the Internet:
CarnegieMellon
–
Internet topology measurements: UPMC
–
Network Security: Columbia
–
Determine reachability of Google IPs from various parts of the internet: Google
–
Distributed skype experiments: Maryland
43
Outline
•PlanetLab
•OneLab
• Services,
management and operation
44
OneLab Goals
• Extend
–
Extend PlanetLab into new environments, beyond the
traditional wired internet.
• Deepen
–
Deepen PlanetLab’s monitoring capabilities.
• Operate PlanetLab Europe
–
Provide a European administration for PlanetLab nodes in
Europe.
• Federate
–
With other PlanetLab worldwide
45
Extend OneLab to New Environments
• WiMAX (Université Catholique de Louvain)
• UMTS (Università di Napoli, Alcatel Italia)
• Wireless ad hoc networks (France Telecom)
• Emulated (Università di Pisa)
–
Based on dummynet
• Multihomed (Universidad Carlos III de Madrid)
46
Why Deepen PlanetLab?
• Problem: PlanetLab provides limited facilities
to make applications aware of the underlying
network
–
PlanetLab consists of end-hosts
–
Routing between nodes is controlled by the internet
(This will change with VINI/GENI)
–
Applications must currently make their own
measurements
47
Why Federate PlanetLab?
Federation adds diversity and scale
Federation allows each individual component to
evolve independently
Federation raises Governance issues
–What
if we want to study a particular wireless technology,
and this requires changes to the source code?
–What
if we wish to change the cost structure for small and
medium size enterprises?
49
OneLab Vision for PlanetLab
- Reveal the underlying
network
- Extend into new wired
and wireless environments
- Deploy and manage
PlanetLab-Europe
51
PlanetLab Europe
•PlanetLab Europe
Run by UPMC
– https://www.planet-lab.eu
– Create a European consortium with evolutive
Acceptable Use Policies.
– Federation with Princeton (PLC)
– Expect 195+ European nodes (58 Germany, 24
Poland,..)
– [email protected]
–
52
Welcome to PlanetLab Europe
https://www.planet-lab.eu
53
PlanetLab Europe Wireless
component
• Added wireless capabilities to the kernel
• Integration of Madwifi drivers on each
nodes:
• Open issues
–
Virtualization of Wireless!
–
« usage model »
–
Acces Policy : Assume many wireless
testbeds to be made available on PlanetLab
54
PlanetLab Europe Wireless
component (preliminary)
• The node software allow the deployment and test
application in wireless mesh multi-hop network.
• A node has to be configured with a fixed IP, OLSR,
and ad hoc routing table.
Wireless node
55
PlanetLab Europe Wireless
component
• In order to broaden the scope of devices
(PDAs, mobile phone,…), the nodes can be
PlanetLab Europe software independent if
they are connected to a gateway configured
with the node software
Gateway
56
PlanetLab Europe Wireless
component
• If no Gateway is configured the user can:
–
Access to each individual node of the wireless multi-hop
mesh network with his ssh key.
–
Use the configured wireless command.
–
Launch application (Streaming video, iperf, hping, …).
ssh
57
PlanetLab Europe Wireless
component
• If the Gateway is used:
–
A PlanetLab Europe user can have access to the
monitoring interface on the gateway node.
Network topology
Link Stability
58
PlanetLab Europe Emulation
component
• DummynetBox (DBox):
–
Based on Dummynet
•
–
(Emulation component used in EmuLab)
Individual users (slivers) can independently
and concurrently set up the characteristics
of the emulated link for their experiment.
59
PlanetLab Europe Emulation
component
• Dummynet API:
–
–
–
Configure and install the DBox on a site.
Assign node, slivers to the DBox.
Load emulation configuration file to emulate
the wireless link according to the features
requested by the users.
60
PlanetLab Europe Emulation
component
• Configuration of the DBox:
–
Add sliver/nodes on a Dbox with the
DummyNet API methods located on PLE.
AddDBox
61
PlanetLab Europe Emulation
component
• Configuration of the DBox:
–
Configuration of the emulated wireless link
(802.11g, 1Mbps, 38dB) on the Dbox with
netconfig program.
netconfig
62
PlanetLab Europe Emulation
component
• DBox monitoring :
–
The DBox continuously monitor the traffic
flowing through the interface and report on
web page dynamically.
64
Progress on Deepening
• CoMo is now OneLab-aware, has better
scripting
–
CoMo allows one to write scripts to track one’s own
packets as they pass measurement boxes within the
network
• Deploying traceroute@home, a distributed
topology-tracing system
–
Made fundamental improvements to traceroute to
correct errors introduced by network load balancing
(new tool: Paris traceroute)
65
Goal: Federate
Before: a homogeneous system
66
Goal: Federate
After: a heterogeneous set of systems
67
Federation concept
• Federation is more than interconnection
• API, Policies
• Governance, Trust, Economics
• Interoperable naming system
• Service discovery
• Resource management in a Federated environment
–
A user in a single domain
–
A domain in a federation
–
Incentive for federation
•
•
Fixed contribution
Reliability, Heterogeneity, Amount of resources
–
Resource management
–
A user outside the federation
68
Federation requirements
•
Universal agreement on minimal core (narrow waist)
•
Allow independent pieces to evolve independently
•
Identify principals and trust relationships among
them
69
Progress on Federation
• Jointly developed PlanetLab v4 with Princeton
–
Allows PLCs (PlanetLab Centrals) to federate
–
Any user is offered the illusion of a global platform
–
And can thus create slices as if it was a single testbed
–
Through a single interface
• Paradigm
–
One-to-one peering (n-square trust relationship)
–
Each PLC has its own database (nodes, users, slices..)
–
And keeps data from other PLC’s
–
Slice attributes (grant of resources) remains local: PLE decides how
to use resources from its own nodes
• Running an embryonic PlanetLab Europe
–
Peering PLE-PLC operational for about a year
70
Federation mechanism
71
Developing the Vision
• OneLab should be developed as a multi-year facility
–
Onelab2 (9/08-9/10)
• Based on three pillars
–
–
–
Platform (development, operations)
Tools (monitoring)
Customers (users and research targets)
• Liaison with “pilot” projects
–
Haggle & ANA (SAC), PSIRP (Content), 4WARD (Future
Internet)
• PlanetLab Europe (PLE) will grow over the years
–
72
Tools found mature are integrated from OneLab2 into PLE
• Cooperation with PlanetLab_US/ORBIT/VINI, PlanetLab
Japan, FEDERICA, NICTA (Australia), Plans with
GLabs
OneLab2 Innovations (partial list)
73
•
Provide embedded passive & active measurement technologies
•
Support wireless integration and develop management tools
•
Provide infrastructural support for large-scale data-centric
networking research (CDN, Pub-Sub, Routing in a slice)
•
Integrate Opportunistic Networking and DTN platforms through the
SAC Gateway
•
Establish methodology to compare networking experiments in non
controllable environments
•
Explore and implement resource management for a single domain
and the federation, as well as incentives for sharing
•
Data representation of the variety of resources
•
Of course: operations, integration and maintenance
OneLab2 Organisation
Pillar 3 - Customers
Pillar 2 - Tools
WP5
Packet
Tracking
WP0
Management
WP9
Benchmarking
WP8
SAC
Provides monitoring tools
WP4
Topology
Information
Pillar 1 - Platform
WP3
Dissemination
WP7
Content
WP6
Wireless
Provides
PlanetLab
Europe
Provides
monitoring tools
WP2
Operations
Delivers the
OneLab Build
Contributes code
74
WP1
Integration
Contribute
code
Outline
•PlanetLab
•OneLab
• Services,
management and operation
76
Welcome to PlanetLab Europe
https://www.planet-lab.eu
77
PlanetLab Europe Terminology
and Roles
• Site: Physical location where PlanetLab nodes are located
• Node: Dedicated server that runs components of PlanetLab services.
• Slice: a set of allocated resources distributed across PlanetLab. To most
users, a slice means UNIX shell access to a number of PlanetLab nodes
• Principal Investigator (PI): The PIs at each site are responsible for
managing slices and users at each site. PIs are legally responsible for the
behaviour of the slices that they create.
• Technical Contact (Tech Contact): Each site is required to have at least
one Technical Contact who is responsible for installation, maintenance, and
monitoring of the site's nodes.
• User: Anyone who develops and deploys applications on PlanetLab.
78
Joining PlanetLab Europe
81
Joining PlanetLab Europe
82
PlanetLab Europe
Creates a slice
The PI at your site should validate your slice
88
PlanetLab Europe
Manages your slice
90
PlanetLab Europe
Node creation
91
Monitoring Node trafic with
PlanetFlow
93
Monitoring Node trafic with
PlanetFlow
94
Resource allocation and
provisioning
• Problem
– Many PlanetLab nodes are down or congested
• Needed
– Incentives for infrastructure/resource contributions
(provisioning)
• Question
– How to allocate resources in case of congestion?
95
Current situation
96
Uptime
97
Avg. CPU load
98
Sites behaviour
• Determine four categories of sites behaviour:
–
Good: Site have good standing nodes and usage (green, yellow)
–
Donners: Site has working nodes but no usage (blue).
–
Leaches: Site is down, but using others' resources (Red)
–
Down: site is down, but no usage (Black)
99
Resource allocation
•Existing solutions
Provision: simple contribution rule (Min. 2
nodes)
– Allocation: (almost) unlimited consumption,
equal sharing
–
100
PlanetLab Resource monitoring
• Node Manager
–
monitor slice/node health
–
discover available resources
–
create and configure a slice
• Content Distribution Network for monitoring the health of PlanetLab
–
CoTop: activity monitoring tool for PlanetLab.
–
CoMon, a Web-based general node/slice monitor that monitors
most PlanetLab nodes.
101
A rule-based approach
•Sites with higher (effective) contribution
should be granted a higher service level
•Exploring a Differentiated service approach
– Ref:
Resource Provision and Allocation in shared Network
Testbed Infrastructures : Panayotis Antoniadis in ROADS
2008
103
European initiative
•The FIRE - Future Internet Research and
Experimentation- Initiative
•
–
7th Framework Programme ICT call 2, Objective
1.6 “New Paradigms and Experimental Facilities”.
14 Testbeds and Research projects
•
40 Meuros funding at first call
•
Starting now
•See
–
http://cordis.europa.eu/fp7/ict/fire/launch.html
–
http://www.ict-fireworks.eu
106
Messages …
•To much hope to re-invent the Internet
–
The disappearing internet
–
The Polymorphic Internet
•Designing the future
–
Back to fundamentals
–
Support experimentally-driven research
–
Tightly associated to research projects
•Explore the Federation concept
107
JOIN US!
OneLab
www.one-lab.org
PlanetLab Europe
www.planet-lab.eu
108