Transcript Slide 1

Networked Systems Research Projects
@ McGill
Muthucumaru Maheswaran
Advanced Networking Research Lab
School of Computer Science
McGill University
Montreal, QC H3A 2A7
Outline
• Ongoing Projects
– Galaxy: A Quality of Service Aware Public Computing
Utility
– RAN: Resource Addressable Network
– Trusted Gossip
– GINI: A Toolkit for User-Level Networks
• Future Projects:
– RASAN: Resource and Service Addressable Network
– ALVIN: Application Layer Virtual Internetworking
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
2
Motivation for RASAN
RASAN: Resource and Service Addressable Network
• New technology trends:
– Radio frequency IDs (RFIDs)
– Pervasive wireless access
– Very low cost/power sensors
• Creating new resource and service discovery problems.
• Examples of such discovery problems:
– Locating the best doctors and nurses who should be brought into a
team to respond to particular emergency situations,
– Locating and allocating resources and services that are necessary
for conducting disaster relief
– Logistical scheduling of different types
• New “discovery” problems enabled by the evolution of
network beyond a system that merely interconnects
clients and servers via a packet switched network
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
3
What is RASAN?
• RASAN is a real-time large-scale directory service
that is targeted to include heterogeneous
resources (wired, wireless, sensors, people, etc)
• RASAN Goal:
–
–
–
–
Flexible search (multiple search dimensions)
Minimal overhead
Fast response times
Late binding to determine real-time scenarios
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
4
What is RASAN…
• RASAN architecture:
– Organized in a P2P manner that self-organizes with
resource arrival and departure events
– Allows searches along multiple attribute spaces for
locating resources and services
– Uses space filling curves (SFC) to reduce multidimensional search to single dimensional problem
(used in RAN with success on the Internet for
locations)
– Instead of a single SFC, it uses a hierarchy of SFCs
– Enables multi-resolution searches to reduce error
accumulation
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
5
RASAN Design Requirements
• Scalable system: Obvious scalability dimension is
the number of devices. Others include number
of search attributes and resource classes.
• Dynamic system support: Resources and services
can attach and detach from the directory
services without prior notice.
• Heterogeneous and multi-resolution search:
RASAN is meant to search along multiple
attribute dimensions. One way to make the
search efficient is to perform the search in
progressively increasing resolutions.
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
6
RASAN Design Req…
• Resource efficient implementation: Due to its P2P
nature, a RASAN kernel would run on each resource. To
include resource challenged sensors into RASAN, the
implementation should be able to run with limited
memory and processing capacities. Further, resources
with restrictive battery capacities should be able to
participate in “stub” configurations with minimal transit
traffic.
• Operation with localized trust: Resource should have
some credential to establish it identity. Localized
reputation should be used to evaluate “behavior trust”
• Shared fate: A resource or service that does not exist
need not be indexed by the directory
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
7
Resource Addressable Network
• RAN: middle layer between services and
resources.
• Attribute-based and location-based discovery.
ODC Service
RAN discovery substrate
Profile-based discovery
Profile-based naming
Naming the resources
based on their attributes
Location-based discovery
Landmark-aided positioning
Physical Resources
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
Network positioning mechanism,
assigning coordinates for each node
in the network delay space
8
RAN Overlay
Location ID
Node
(x,y)
Hilbert
indexing
Node
(LID)
decides the location
Neighborhood pointers
connect the rings
LAP
decides the ring
Node
PBN/Hilbert
indexing
Node
(PID)
Profile ID
Type rings
Resources with the same
profile ID form a ring
Route pointers in the nodes
creates the overlay structure
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
9
Network Positioning
• Network positioning: assigning coordinates for
the nodes in a virtual Cartesian space, from
which real network delay can be predicted.
Internet
l12
Distance prediction:
l12 ≈ √[(x1-x2)2+(y1-y2)2]
y
(x2, y2)
(x1, y1)
Cartesian space
x
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
10
Landmark Aided Positioning
• Landmark aided positioning (LAP): the network
positioning scheme for RAN.
– Using a set of landmarks.
– Normal nodes:
• Select a subset of the total landmarks and ping them.
• Run optimization algorithm to position themselves to minimize
the total error in distance prediction.
• Two phases of LAP:
– Landmark positioning: positioning the landmarks.
– Node positioning: positioning the normal nodes.
• Simplex and Spring algorithms.
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
11
Location-based Discovery
• Finding a resource at specific coordinate/range:
– Multidimensional search.
– Chose Hilbert curve as the data structure.
• Hilbert curve:
– A space filling curve.
– Preserving proximity.
– Hierarchical Hilbert index  location ID (LID).
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
12
Location-based Discovery (cont…)
Routing table at node with LID = 2.3.3.1.0
• Routing table for location-based discovery.
– Non-zero error in pings justifies fixed length LIDs.
– Ring pointers ensuring connectivity; jump pointers enhancing
route complexity.
• Average search hop complexity = h (approx. level)  O(1).
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
13
Profile-based Discovery
• Discovery systems implements naming schemes:
– Label-based naming (LBN): DNS, IP Address.
• Scalable, but not flexible.
– Description-based naming (DBN): LDAP.
• Flexible, but with high overhead due to information
maintenance, complex matching algorithms.
• Introducing profile based naming (PBN):
– Labels popular attribute-value combinations.
• Combines the goods of LBN and DBN.
• Can not discover all the attribute-value combinations.
• Trading off flexibility (performance) for scalability.
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
14
Profile-based Discovery (cont…)
Profile-based naming:
profiles
profile space
description
1
2
3
description space
Profile IDs
Profile 1: {Intel/AMD, ≤ 512MB} : 0.*
Profile 2: {Intel with 1GB}
: 1.0
Profile 3: {Intel/AMD, > 1GB} : [1.1,1.2]
• Profile-based routing table is very similar to location-based routing table.
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
15
The Galaxy Architecture
• The following diagram shows a proposal for
Galaxy architecture:
Galaxy Services
Resource
Broker
...
Resource
Broker
Galaxy Resource Management System
Security
Galaxy Middleware
Galaxy Applications
Service Level, Trust,
Incentive Management
Resource Broker
Resource Addressable Network (RAN)
Resource Pool (RP)
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
16
Trust and Incentive Management
• Public resources remain under control of local
agents whose behavior may change randomly
• resource sharing in hostile and friendly environments
• Challenges in trust management in a PCU
– Internet-scale
• manage vast pool of distributed resources
– cross boundary; autonomous
•
•
•
•
span across administrative domains
handle localized policies; varied level of trust requirement
reliable exchange of peer behavior
ensure fair resource exchange; resource participation
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
17
GRMS Trust Management Model
Resource Brokers (RBs)
RB1A
RB2
A
RB1B
Resource Peers (RPs)
RP2B
RP1B
RP1A
RP2A
Domain A
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
RP3A
Domain B
18
Trust Hierarchy
• Hierarchy: local, global trust
RB1B
• Helps to reduce
overhead needed for
computing trust
local trust
– scalable; flexible;
localized policing
RP1A
RP1B
global trust
domains are not
connected in
hierarchy
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
19
PCU Operations for Allocation
4. resource negotiation
RB1A
1. resource
request
RB1B
3. resource
reply
2. resource discovery
(via RAN)
6. resource
rewarding
RP1B
RP1A
Provider
Requestor
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
20
Negotiation: Trust Evaluation
4. resource negotiation
RB1A computes RP1B ’s global trust
GT_ RP1B = LT_RP1B x REP_DBA
RB1A
REP_DBA = reputation of
Domain B as measured
by Domain A
RB1B
RB1B recommends RP1B
to RB1A based on RP1B ’s
B
local trust LT_ RP
Domain
C
1
RP1B
RP1A
Provider
Resource access is authorized
A
B
if RB
1 considers GT_RP1
Requestor
value as trustworthy
Domain A
Advanced Networking Research Laboratory,
School of Computer Science,
McGill University, Montreal, QC, Canada.
Security/fairness mechanisms
Domain B
ensure that RBs and RPs do
not collude or lie to each other
21