Transcript slides - Sigcomm

The Evolution of Layered Protocol Stacks
Leads to
an Hourglass-Shaped Architecture
Saamer Akhshabi
Constantine Dovrolis
Georgia Institute of Technology
s.akhshabi,[email protected]
1
My co-author, Saamer Akhshabi
(2nd year PhD student,
he could not travel to Toronto)
2
Outline
•
•
•
•
Motivation
Model description
Results
Concluding remarks
3
Where does this work come from?
Silver
light
Firefox
HTTP
Thunder
bird
SMTP
TCP
…
MPlayer
…
RTP
UDP
IPv4
PPP
Optical
Fiber
…
Ethernet
Twisted
Pair
Coaxial
Cable
…
4
Why is it an hourglass?
Silver
light
Firefox
HTTP
Thunder
bird
SMTP
TCP
…
MPlayer
…
RTP
UDP
IPv4
PPP
Optical
Fiber
…
Ethernet
Twisted
Pair
Coaxial
Cable
…
5
What happens at the “waist”
compared to other layers?
Silver
light
Firefox
HTTP
Thunder
bird
SMTP
TCP
…
MPlayer
…
RTP
UDP
IPv4
PPP
Optical
Fiber
…
Ethernet
Twisted
Pair
Coaxial
Cable
…
6
How can a new protocol
survive at the waist?
Silver
light
Firefox
HTTP
Thunder
bird
SMTP
TCP
…
RTP
UDP
ATM
IPv4
PPP
Optical
Fiber
…
MPlayer
X.25
IPv6
…
Ethernet
Twisted
Pair
SNA
Coaxial
Cable
…
7
What about “Future Internet”
those architectures?
• Will these architectures
also evolve to an
hourglass in few years?
• How to make them more
“evolvable”?
NDN
XIA
Mpb
ilityF
irst
Neb
ula
– So that they can better
accommodate innovation?
– So that no single protocol
at the waist “kills” all
competitors
8
Outline
•
•
•
•
Motivation
Model: EvoArch
Results
Conclusions
9
Two Disclaimers
• EvoArch is only an abstraction of protocol
stacks
– EvoArch does not capture many practical aspects and
protocol-specific or layer-specific semantics
• EvoArch is certainly not the only model, or “the
correct model”, for the emergence of
hourglass-shaped network architectures
– Models should be judged based on their assumptions,
parsimony and predictions
10
Model description
L
Protocol
dependencies
as edges
…
4
3
Protocols
as nodes
2
Products: P(u)
u
Layer of u: l(u)
Substrates:S(u)
1
Layered acyclic network
Every layer provides a service
11
The value of a protocol
• The value of a protocol depends on the value
of its products
• Protocols with valuable products are more
valuable
– example TCP, HTTP
1
1
1
1
1
1
1
3
2
5
5
1
12
The generality of a layer
As we go higher in the
stack:
• Protocols become less
general – they offer
more specialized
services
• The probability that a
protocol is used by
next-layer’s protocols
decreases
Firefox
Silverlight
HTTP
Thunder
bird
RTP
SMTP
TCP
MPlayer
UDP
IPv4
PPP
Optical
Fiber
Ethernet
Twisted
Pair
Coaxial
Cable
13
Generality as a probability
• We introduce a
parameter called
generality vector s
• s(l) : probability that
new node at layer l+1
chooses each node at
layer l as substrate
• s(l) decreases as we
go higher in protocol
stack
s(L-1) = 0.1
s(3) = 0.5
s(1) = 0.9
14
Competition between protocols
• Two protocols at the same layer compete if
they offer similar services
– i.e., if they have large overlap in their products
• HTTP competes with FTP due to several
overlapping products
HTTP
FTP
• TCP does not compete with UDP because they
have minimal service overlap
TCP
UDP
15
Modeling competition
• Let C(u) be set of competitors of u
• Node w competes with u if
• c: competition threshold
• If c = 3/5
• u competes with
q and w
• q does not
compete with w
q
u
w
16
When does a protocol “die”?
• Protocols can become extinct due to
competition with other protocols
• For example, HTTP services cover the set of
services provided by FTP
HTTP
FTP
• Competition from HTTP has led to FTP’s
demise
17
Modeling protocol deaths
• A node u dies if its value is significantly less than the value of
its strongest (i.e., maximum value) competitor.
• z: mortality parameter
18
Cascade deaths
• u is w’s competitor
• Suppose that w dies due to competition with u
(r=3/7)
1
1
2
1
1
1
1
4
1
2
7
1
1
3
1
2
If a node w dies,
its products also
die if their only
substrate is w.
This can lead to
cascade deaths.
19
Protocol births
• Basic birth process
Number of new nodes at given time is a
small fraction of total number of nodes in
network at that time.
New nodes assigned randomly to layers
• Death-regulated birth process
The birth rate at a layer is regulated by
the death rate in that layer
Discussed later
20
Summary of EvoArch
• Discrete-time model
– Time advances in rounds
• Each round includes
birth of new nodes
competition among nodes at the same layer
potentially, death of some nodes
• Key parameters
– Generality vector s
– Competition threshold c
– Mortality parameter z
21
Outline
• Motivation
• Model Description
• Results
– Emergence of hourglass structures
– Controlling the location/width of the
waist
– Evolutionary kernels
– Protocol differences
• Conclusions
22
Hourglass shape
L = 10
c = 3/5
z=1
s(l) = 1-l/L
• The network forms an hourglass structure over time
• The waist usually occurs at layer 5 or 6.
23
 w(l) : width of layer l
 Minimum occurs at layer b
 X = {w(l), l = 1, . . . b}
 Y = {w(l), l = b, . . .L}
 Mann-Kendall statistic for
monotonic trend on the
sequences X and Y:
coefficients τX and τY
 H = (τY – τX)/2
• H=1 when widths first
decrease and then
increase (monotonically)
W(L)
…
w(b+1)
w(b)
…
w(1)
Layer number
Hourglass Resemblance Metric
w(2)
Width
24
Robustness
• High hourglass scores under a wide range of
parameters
25
Why does EvoArch generate
hourglass-shaped networks?
Small generality
Low competition (local)
Few deaths
Generality close to 50%
Few protocols with many products
Most other protocols die
Large generality
High competition
Protocols have similar products
-similar values
Few deaths
26
How can we get a wider waist?
• γ is the layer
at which the
generality is
50%
s(l)
• As γ increases
0.5
γ
Layer number
– Location of the waist
moves to higher layers
– Width of waist increases
27
Evolutionary kernels
28
How can a kernel die?
• Normalized value of a node: value divided by maximum
possible value at that round
• If several nodes appear at the next higher layer, and
kernel fails to quickly acquire those new possible products,
someone else may do so..
29
Death-regulated birth process?
• What if the birth probability in a layer is regulated
by the death probability in that layer?
• It becomes practically impossible to replace kernels
30
What if protocols differ
in term of a “quality factor”?
• The “quality factor” can be interpreted broadly





Performance,
Extent of deployment,
Reliability or security,
Incremental improvements,
etc
31
Effects of quality factor
• We still get an hourglass
• Slower network growth
• Lower part of hourglass is smaller in size
– only high quality nodes survive at the lower part
• Kernels are often NOT the highest quality protocols
32
Outline
•
•
•
•
Motivation
Model Description
Results
Concluding remarks
33
What does this mean for the
Internet architecture?
• New way to think about (and teach) Internet’s
hourglass architecture
• New way to think about “ossification” of
protocols at the waist
• Parameterized model for TCP/IP stack:
– Two protocols compete when their service overlap
is more than 70%
– A protocol survives only if its value is more than
90% of its strongest competitor’s value
– Death-regulated births
34
What does this mean for
IPv4 vs IPv6?
• IPv6 has same products but lower extent of
deployment (i.e., lower “quality factor”)
• IPv6 would find it easier to compete w IPv4
if:
– It had some distinct products that IPv4 does not
have
– Unfortunately, it only offers more addresses
• IPv6 would face easier adoption if it was not
presented as “IPv4 replacement” but as “the
second network-layer protocol”
35
What does this mean for future
Internet architectures?
• Hourglass structures should be expected if
these new architectures evolve/compete
• Designers should strive for wider waist
– More diverse waist -> more evolvable architecture
• EvoArch: as the waist moves higher, it also
becomes wider
– How to push the waist to a higher layer?
– See highly relevant paper:
• L. Popa, A. Ghodsi, and I. Stoica. HTTP as the Narrow
Waist of the Future Internet. In ACM SIGCOMM
HotNets, 2010
36
From Networking
to Network Science
• Hourglass effect in development of embryos
• Hourglass effect in organization structures
• Hourglass effect in innate immune system
37