Transcript cse311_talk_cut - University of Connecticut

Scalable Group Communications and
Systematic Group Modeling
Jun-Hong Cui
University of Connecticut
[email protected]
http://www.cse.uconn.edu/~jcui
Cool Application 1 : Teleconferencing
Cool Application 2 : Telemedicine
Cool Application 3 : Net Gaming
Multicast: What and How?

Multicast:


One to many or many to many
communications (group communications)
To achieve multicast:
Multiple unicast (one to one)
 Network multicast---IP multicast
 Overlay multicast (using proxies)


Application layer multicast (end host)
Jun-Hong Cui (c) UCONN 2004
Outline of this talk

Scalable Group Communications
--- Aggregated Multicast

Systematic Group Modeling
--- GEM Model

Research Directions
Jun-Hong Cui (c) UCONN 2004
IP Multicast
Group: IP D class
address
 Use Tree delivery
structure
 Routers: keep
forwarding entries
per-group/source
(multicast state)
 IP multicast

group NHop
g1
Domain B
Ab, A3
A2
Domain A
B1
Ab
Aa
A1
X1
A3
Y1
Domain X
C1
Domain Y
D1
Customer Networks, Domain D
Domain C
Resource efficient
 Scalable to group size

Jun-Hong Cui (c) UCONN 2004
The Problem: Not Scalable to the
Number of Groups

group NHop
g1
Ab, A3
g2
Ab, A3
More forwarding entries
 More tree maintenance
overhead
Domain B
A2

B1
Domain A
Ab

Aa
A1
X1
A3
Y1
Domain X
C1
IP multicast NOT scalable
to the number of groups
State Scalability problem
 Serious in transit domains

Domain C
Domain Y
D1
More groups  more trees

Our solution

Customer Networks, Domain D
Aggregated multicast to
improve state scalability
Jun-Hong Cui (c) UCONN 2004
Key Insight
group NHop
g1
Ab, A3
g2
Ab, A3
Domain B
A2
B1
Domain A

Ab
Aa
A1
X1
A3
Y1
Domain X
C1
There are many
overlaps among
multicast trees in
transit domains
Domain C
Domain Y
D1
Customer Networks, Domain D
Jun-Hong Cui (c) UCONN 2004
Aggregated Multicast
Tree
T1

NHop
Domain B
Ab, A3
A2
Key idea:

B1
Domain A
Ab
Aa
A1
X1
C1
Reduce state at core
routers
 Reduce tree maintenance
overhead
 Push complexity to edge
Domain C
Domain Y
D1
Benefits:

A3
Y1
Domain X

Force multiple groups
share a single delivery
tree (aggregated tree)

Target:

Multicast provisioning in
transit domains
Customer Networks, Domain D
Jun-Hong Cui (c) UCONN 2004
Aggregated Multicast (cont.)
Tree
T1
NHop
Domain B
Ab, A3
A2
B1
De-aggregation
Domain A
Ab
Aggregation
Aa
A1

Core routers:


Edge routers:

A3
De-aggregation

Keep state per-tree
Keep group state
Groups:
Aggregate at incoming
edge router
 De-aggregate at
outgoing edge routers

X1
Y1
Domain X
C1
Domain Y
Domain C
D1
Customer Networks, Domain D
Jun-Hong Cui (c) UCONN 2004
Perfect Match vs. Leaky Match
Tree
T1
NHop
Domain B
Ab, A3
A2

B1
Perfect match
 Leaky match
Domain A

Ab
Aa
A1
X1
Discard Packets
A3
Y1
Domain X
Group-Tree match
C1
Domain Y
D1

Domain C
Bandwidth waste
in leaky match

Data delivery to
non-member nodes
Customer Networks, Domain D
Jun-Hong Cui (c) UCONN 2004
Aggregation Control

Leaky match
Good for tree aggregation
 But waste bandwidth

There is a trade-off
 Static group-tree matching: NP hard
 A dynamic group-tree matching
algorithm to control the trade-off


Under a given bandwidth waste threshold
Jun-Hong Cui (c) UCONN 2004
Group-Tree Matching
Domain E
E1
Domain B
A2
B1
Domain A
A4
Ab
Aa
A3
A1
X1
Y1
Domain X
C1
Domain C
Domain Y
D1
Customer Networks, Domain D
Jun-Hong Cui (c) UCONN 2004
Group-Tree Matching
Domain E
E1
Domain B
A2
B1
Domain A
A4
Ab
Aa
A3
A1
X1
Y1
Domain X
C1
Domain C
Domain Y
D1
Customer Networks, Domain D
Jun-Hong Cui (c) UCONN 2004
Implementation Issues

Multiplex multiple groups over a shared tree
IP encapsulation
 MPLS (Multi-Protocol Label Switching)



Tree management and group-tree matching

Tree Manager (need to know group membership)

Distributed or centralized solutions
Have designed and implemented protocols:
ASSM for source specific multicast (SSM)
 BEAM for shared tree multicast (ASM)
 AQoSM for QoS multicast provisioning

Jun-Hong Cui (c) UCONN 2004
Extend to Overlay and Adhoc Net

Overlay multicast

Implement multicast in overlay net

A collection of proxies (or gateways)
Processing power, memory & bandwidth more critical
 Aggregated multicast reduces management overhead


Wireless multicast

Implement multicast in wireless adhoc net

No infrastructure, self-organized
Energy, memory, bandwidth, resilience very critical
 Aggregated trees help to improve performance

Jun-Hong Cui (c) UCONN 2004
Overlay Network
Jun-Hong Cui (c) UCONN 2004
Adhoc Network
Jun-Hong Cui (c) UCONN 2004
Outline of this talk

Scalable Group Communications
--- Aggregated Multicast

Systematic Group Modeling
--- GEM Model

Research Directions
Jun-Hong Cui (c) UCONN 2004
The Problem: Group Modeling

The locations of the group members


Given a graph, where should we place them?
Current assumptions: uniform random
model (unproven)
All members uniformly distributed
 Not realistic for many applications

Jun-Hong Cui (c) UCONN 2004
Group Modeling is Critical

Some studies have shown the locations of
members have significant effects on
Scaling properties of multicast trees
 Aggregatability of multicast state
 Performance of state reduction schemes


Realistic group models
Improve effectiveness of simulation
 Guide the design of protocols

Jun-Hong Cui (c) UCONN 2004
Our Contributions

Measure real group membership properties


MBONE (IETF/NASA) and Netgames (Quake)
Design a model to generate realistic membership
GEneralized Membership Model (GEM)
 Use Maximum Enthropy: a statistical method

Jun-Hong Cui (c) UCONN 2004
Roadmap
Membership Characteristics
 Measurement and Analysis Results
 Model Design and Validation

Jun-Hong Cui (c) UCONN 2004
Beyond Uniform Random Model
How close are the members in a
group?
 Are all the members same in group
participation?
 What are the correlations between
members in group participation?

Jun-Hong Cui (c) UCONN 2004
An Illustration (Teleconference)
Member Router
Edge Router
Seattle 0.7
Boston 0.5
Internet
1.0
Los Angeles 0.5
Atlanta 0.4
Jun-Hong Cui (c) UCONN 2004
Membership Characteristics

Member clustering
Capture proximity of group members
 Use network-aware clustering method


Group participation probability


Show difference among members/clusters
Pairwise correlation in group participation
Capture joint probability of two members/clusters
 Use correlation coefficient (normalized covariance)

Jun-Hong Cui (c) UCONN 2004
Measure Membership Properties

MBONE applications (from UCSB)
IETF-43 (Audio and Video, Dec. 1998)
 NASA Shuttle Launch (Feb. 1999)
 Cumulative data sets on MBONE (1997-1999)


Net Games (using QStat)
Quake I (query master server)
 Choose 10 most popular servers (May. 2002)


Examine three membership properties
Jun-Hong Cui (c) UCONN 2004
Member Clustering
(3, 0.64)
MBONE cumulative data sets
MBONE real data sets
Net game data sets
CDF of cluster size for MBONE and net games
Group Participation Probability
CDF of participation probability for Net Game data sets
Group Participation Probability
CDF of participation probability for MBONE applications
Pairwise Correlation in Group Participation
CDF of correlation coefficient for Net Game data sets
Pairwise Correlation in Group Participation
CDF of correlation coefficient for MBONE applications
Generalized Membership Model
--- GEM (An Overview)
Inputs
GEM
Network topology
Cluster method
Group behavior
Distr. of participation prob.
Distr. of pairwise correlation
Distr. of member cluster size
1. Create clusters in given topology
2. Select clusters as member clusters
According to input distributions
3. Choose nodes for each member clusters
Outputs
Desired number of multicast groups
that follow the given distributions
Jun-Hong Cui (c) UCONN 2004
Member Distribution Generation

Definition:
K clusters: C1 , C2 , … , Ci , … , CK
Prob. pi for any i in [1, K]
Joint prob. pi,j for any i, j in [1, K]
X=(X1 ,X2 , … , Xi , … , Xk): Xi is a binary indicator
Xi = 1 if Ci is in the group
Xi = 0 if Ci is not in the group

Objective:
Generate vectors x=(x1 , x2 , … , xk) satisfying
P(Xi = 1) = pi and P(Xi = 1 , Xj = 1) = pi,j
Jun-Hong Cui (c) UCONN 2004
Maximum Entropy Method
To calculate the distribution of (X1,X2, …, Xk)
requires O(2K) constraints
 But we only know O(K+K2) constraints
 We use Maximum Entropy Method

Entropy is a measure of randomness
*
 We construct a maximum entropy distr. p (x)

Satisfy constraints in specified dimensions
 Keep as random as possible in unconstrained dimensions
 i.e. maximize entropy while match given constraints

Jun-Hong Cui (c) UCONN 2004
Three Cases
Considering P(Xi=1)= pi and P(Xi=1, Xj=1)=pi,j
1. Uniform distr. without correlation (easy)
pi,j = pi * pj , and pi = pj
2. Non-uniform distr. without correlation (easy)
pi,j = pi * pj , but pi = pj not necessary
3. Non-uniform distr. with pairwise correlation
Neither pi,j = pi * pj nor pi = pj necessary
Need to calculate the maximum entropy distr.
p*(x)
Entropy decreases from case 1 to case 3
Jun-Hong Cui (c) UCONN 2004
Experimental Validation
Consider all membership properties
 Consider three cases
 Figures omitted …
 Our experiments show


GEM can regenerate groups satisfying
given distributions (from real
measurement)
Jun-Hong Cui (c) UCONN 2004
Summary

Uniform random model
Can capture net games approximately
 But not realistic for MBONE applications


GEM: a generalized membership model
Three cases (case 1: uniform random model)
 Realistic membership can be regenerated


Beyond multicast


Peer-to-peer network modeling
Beyond wired network
Wireless adhoc networks, sensor networks …

Jun-Hong Cui (c) UCONN 2004
Outline of this talk

Scalable Group Communications
--- Aggregated Multicast

Systematic Group Modeling
--- GEM Model

Research Directions
Jun-Hong Cui (c) UCONN 2004
Networking: Expanding Visions
(from
JimUCONN
Kurose)
Jun-Hong
Cui (c)
2004
Peer-to-Peer Networking
Peer-to-Peer Networking
Focus at the application level
Applications & Challenges

Applications
P2P file sharing (Napster, Gnutella, Freenet, etc.)
 Application-layer multicast


Characteristics
each node potentially same responsibility, functionality
 logical connectivity rather than physical connectivity


Why P2P?


High resource utilization (bandwidth, memory, CPU)
Challenges
Self-organized and large scale (routing)
 Reliability and security

Jun-Hong Cui (c) UCONN 2004
Research Directions

Overlay multicast


Multicast modeling


measurement & modeling, complex queries
Wireless adhoc networks


Systematic multicast evaluation
Peer-to-peer networks


Scalability, QoS, security, pricing, …
Mobility modeling, scalable multicast
Sensor networks
Sensor deployment and security
 Very large scale sensor network design

Jun-Hong Cui (c) UCONN 2004
Questions?
[email protected]
http://www.cse.uconn.edu/~jcui
Jun-Hong Cui (c) UCONN 2004
THANKS!!!
Jun-Hong Cui (c) UCONN 2004
Network Characteristics
No fixed infrastructure, instantly deployable
 Node portability, mobility
 Error-prone channel
 Limited resources



Heterogeneous nodes


big/small; fast/slow etc
Heterogeneous traffic


bandwidth, energy supply, memory and CPU.
voice, image, video, data
Wireless multihop connection

to save power, overcome obstacles, enhance spatial
spectrum reuse, etc
Jun-Hong Cui (c) UCONN 2004
Calculate the Maximum Entropy Distribution
The maximum entropy distr. p*(x) is the solution for:
p*  x   arg max   p x logp x dx
Subject to
 xi x j p x dx  pi, j , when i  j
and
 xi p x dx  pi
and
 p x dx  1
Use lagrange multipliers and numerical method to
construct p*(x), Then Gibbs Sampler to sample it
Jun-Hong Cui (c) UCONN 2004
Group Participation Probability
Participation probability distribution for IETF43-Video
Pairwise Correlation in Group Participation
Joint probability distribution for IETF43-Video