A control-theoretic view of layering and decomposition in complex
Download
Report
Transcript A control-theoretic view of layering and decomposition in complex
Complex
Network
Architecture
Reactions
Flow
Protein level
Reactions
Application
Error/flow control
Global
John Doyle
Flow
RNA level
Relay/MUX
John G Braun Professor
Control and Dynamical Systems
E/F control
E/F control
Local
Relay/MUX
Reactions
BioEngineering, Electrical Engineering
Caltech
Relay/MUX
Flow
DNA level
Physical
Doyle
Architecture of
complex networks
Theory
• First principles
• Rigorous math
• Algorithms
• Proofs
Data
Analysis
• Correct
statistics
• Only as good
as underlying
data
Lab
Numerical
Experiments Experiments
• Simulation
• Synthetic,
clean data
• Stylized
• Controlled
• Clean,
real-world
data
Field
Exercises
Real-World
Operations
• SemiControlled
• Messy,
real-world
data
• Unpredictable
• After action
reports in lieu
of data
Essential ideas: Architecture
Robust
yet
fragile
Question
Constraints
that
deconstrain
Answer
A Layered View of HFN Architecture
Robust
Constraints
HUMAN / COGNITIVE
LAYER
Conversation
Organizational
Politicalthat
yet Social/Cultural The
fragile?
deconstrain?
VOICE
- Push-to-talk
- Cellular
- VoIP
- Sat Phone
- Land Line
VIDEO/IMAGERY
- VTC
- GIS
- Layered Maps
WIRED
- DSL
- Cable
WIRELESS LOCAL
- WiFi
- PAN
- MAN
WIRELESS LONG
HAUL
- WiMAX
- Microwave
- HF over IP
POWER
- Fossil Fuel
- Renewable
HUMAN NEEDS
- Shelter
- Water
- Fuel
- Food
PHYSICAL SECURITY
- Force Protection
- Access
Authorization
TEXT
“APPLICATION
LAYER”
“NETWORK
LAYER”
“PHYSICAL
LAYER”
- email
- chat
- SMS
Economic
SPECIALIZED
- Collaboration
- Sit Awareness
- Command/Control
- Integration/Fusion
REACHBACK
- Satellite
Broadband
- VSAT
- BGAN
OPERATIONS
CENTER
- NetSec
- Command/Control
- Leadership
Infrastructure networks?
•
•
•
•
•
•
•
Water
Waste
Food
Power
Transportation
Healthcare
Finance
All examples of
“bad” architectures:
• Unsustainable
• Hard to fix
Where do we look for “good” examples?
Essential ideas: Architecture
Robust
yet
fragile
Question
Constraints
that
deconstrain
Answer
Simplest case studies
Internet
Bacteria
•
•
•
•
•
•
•
Successful architectures
Robust, evolvable
Universal, foundational
Accessible, familiar
Unresolved challenges
New theoretical frameworks
Boringly retro?
Simplest case studies
Internet
Bacteria
• Universal, foundational
Technosphere
Biosphere
Internet
Bacteria
• Universal, foundational
Technosphere
Spam
Viruses
Internet
Biosphere
Bacteria
Two lines of research:
1. Patch the existing Internet architecture
so it handles its new roles
Technosphere
•
•
•
•
•
Internet
Real time
Control over (not just of)
networks
Action in the physical world
Human collaborators and
adversaries
Net-centric everything
Two lines of research:
1. Patch the existing Internet architecture
2. Fundamentally rethink network architecture
Technosphere
•
•
•
•
•
Internet
Real time
Control over (not just of)
networks
Action in the physical world
Human collaborators and
adversaries
Net-centric everything
Two lines of research:
1. Patch the existing Internet architecture
2. Fundamentally rethink network architecture
Technosphere
Biosphere
Case studies
Internet
Bacteria
Essential ideas: Architecture
Robust
yet
fragile*
Question
* Carlson
Precursors
Catabolism
Systems requirements:
functional, efficient,
robust, evolvable
Co-factors
Constraints
DNA
replication
Trans*
Proteins
Hard constraints:
Thermo (Carnot)
Info (Shannon)
Control (Bode)
Compute (Turing)
Genes
Carriers
Diverse
Universal
Control
Diverse
Components and materials:
Energy, moieties
Protocols
Hard limits.
No networks
Hard constraints:
Thermo (Carnot)
Info (Shannon)
Control (Bode)
Compute (Turing)
Assume
different
architectures
a priori.
New unifications are encouraging,
but not yet accessible
Cyber
•
•
•
•
Physical
Thermodynamics
Communications
Control
Computation
•
•
•
•
Thermodynamics
Communications
Control
Computation
Internet
Bacteria
Case studies
Robust Yet Fragile (RYF)
[a system] can have
[a property] robust for
[a set of perturbations]
Yet be fragile for
[a different property]
Or [a different perturbation]
Fragile
Robust
Proposition :
The RYF tradeoff is a hard limit
that cannot be overcome.
Cyber
•
•
•
•
Thermodynamics
Communications
Control
Computation
Physical
Physical
•
•
•
•
Thermodynamics
Communications
Control
Computation
Fragile
Robust
Theorems :
RYF tradeoffs are
hard limits
Robust yet fragile
Biology and advanced tech nets show extremes
• Robust Yet Fragile
• Simplicity and complexity
• Unity and diversity
• Evolvable and frozen
What makes this possible and/ or inevitable?
Architecture (= constraints)
Let’s dig deeper.
Essential ideas: Architecture
Constraints
that
deconstrain*
Answer
* Gerhart and Kirschner
Essential ideas: Architecture
Constraints
that
deconstrain*
Answer
Bad architecture:
Things are broken and you can’t fix it
Good architecture:
Things work and you don’t even notice
Systems requirements:
functional, efficient,
robust, evolvable
Are there universal
architectures?
Components and materials:
Energy, moieties
Protocols
Layers (Net)
Ancient network
architecture:
“Bell-heads versus
Net-heads”
Operating
systems
Pathways (Bell)
Phone systems
my
computer
Wireless
router
web
server
Optical
router
HTTP
TCP
IP
MAC
Switch
MAC
MAC
Pt to Pt
Pt to Pt
Physical
my
computer
Applications
HTTP
Browsing the web
web
server
The physical pathway
my
computer
Wireless
router
Optical
router
Physical
web
server
my
computer
web
server
Applications
HTTP
Wireless
router
Optical
router
Physical
my
computer
web
server
Applications
Diverse Applications
HTTP
Share?
Wireless
router
Optical
router
Diverse Resources
Physical
Applications
Error/flow control
TCP
IP
Relaying/Multiplexing
(Routing)
Resources
Error/flow control
TCP
IP
Relaying/Multiplexing
(Routing)
Applications
Control
Error/flow
Relay/MUX
Resources
max
x0
U ( x )
i
i
i
subj to Rx c( p )
x X
Applications
diverse
and
changing
Resources
Fixed and universal
Control
Error/flow
Relay/MUX
max
x0
U ( x )
i
i
i
subj to Rx c( p )
x X
Applications
Deconstrained
U i ( xi )
Constraints max
x0
i
that
subj to Rx c( p )
deconstrain
x X
Resources
Deconstrained
Gerhart
and
Kirschner
my
computer
Wireless
router
TCP
IP
Physical
my
computer
Wireless
router
TCP
IP
MAC
Switch
Physical
my
computer
Wireless
router
MAC
Switch
Error/flow control
Relaying/Multiplexing
Physical
Wireless
router
Applications
MAC
Switch
Resources
Error/flow control
Local
Relaying/Multiplexing
my
computer
Wireless
router
TCP
IP
MAC
Switch
Differ in
• Details
• Scope
Error/flow control
Global
Relaying/Multiplexing
Error/flow control
Local
Relaying/Multiplexing
Physical
Wireless
router
web
server
Optical
router
TCP
IP
Physical
Wireless
router
web
server
Optical
router
TCP
IP
MAC
Pt to Pt
Physical
Wireless
router
Error/flow control
Global
Relay/MUX
web
server
Optical
router
TCP
IP
Error/flow control
MAC
Local
Pt to Pt
Relay/MUX
Physical
my
computer
Wireless
router
web
server
Optical
router
HTTP
TCP
IP
MAC
Switch
MAC
MAC
Pt to Pt
Pt to Pt
Physical
Recursive control structure
Application
Global
Local
Local
Physical
Local
Recursive control structure
Application
Error/flow control
Relay/MUX
Physical
Recursive control structure
Application
Error/flow control
Global
Relay/MUX
E/F
control
Relay/MUX
Local
Physical
E/F
control
Relay/MUX
Architecture
is not graph
topology.
Application
TCP
IP
Architecture
facilitates
arbitrary
graphs.
Physical
Constraints that deconstrain
Applications
Deconstrained
min
x
Rx c Rx c
2
2
dt
x arg max L v, p , p Rx c
v
xs arg max Ls v, p
v
Resources
Deconstrained
Generalizations
• Optimization
• Optimal control
• Robust control
• Game theory
• Network coding
Layering as optimization decomposition
• Each layer is abstracted as an optimization
problem
• Operation of a layer is a distributed solution
• Results of one problem (layer) are parameters of
others
• Operate at different timescales
Application: utility
application
transport
network
link
physical
max
x0
U ( x )
i
i
i
Phy: power
subj to Rx c( p )
x X
IP: routing
Link: scheduling
Layering and optimization*
Each layer is abstracted as an optimization problem
Operation of a layer is a distributed solution
Results of one problem (layer) are parameters of others
Operate at different timescales
Application
TCP/AQM
Minimize response time, …
Maximize utility
Minimize path cost
IP
Link/MAC
Physical
Maximize throughput, …
Minimize SINR, maximize capacities, …
*Review from Lijun Chen and Javad Lavaei
Protocol decomposition: TCP/AQM
my PC
router
TCP
source algorithm (TCP)
iterates on rates
Primal:
Dual
max
x 0
s.t.
U
s
( xs )
s
Rx c
min
p 0
AQM
link algorithm (AQM)
iterates on prices
U
(
x
)
x
R
p
p
c
s max
s
s
s ls l
l l
xs 0
l
l
horizontal decomposition
TCP/AQM as distributed primal-dual algorithm over the network
to maximize aggregate utility (Kelly ’98 , Low ’99, ’03)
Generalized utility maximization
Objective function: user application needs and network cost
Constraints: restrictions on resource allocation (could be
physical or economic)
Variables: Under the control of this design
Constants: Beyond the control of this design
Network cost
Application utility
max
x , R ,c , p
T
U
(
x
)
λ
Rx
i i
i
subj to Rx c
c X ( p)
IP: routing
Phy: power
Link: scheduling
Layering as optimization
decomposition
Network
generalized NUM
sub-problems
functions of primal/dual variables
decomposition methods
Layers
Interface
Layering
Application
TCP/AQM
IP
Link/MAC
Physical
•
Vertical decomposition: into
functional modules of different layers
•
Horizontal decomposition: into
distributed computation and control
Case study I: Cross-layer
congestion/routing/scheduling design
Rate constraint
U
Primal : max
x, f
s
Schedulability constraint
( x s ) s.t. H ( x) A( f ), f
s
Dual : min {max (U s ( x s ) p T H ( x)) max p T A( f )}
p 0
x
f
s
Rate control
Routing
Scheduling
Cross-layer implementation
Dual: min{max
(U s ( xs ) pT H ( x)) max pT A( f )}
p 0
x
f
s
Rate control
Routing
Scheduling
Application
Transport
Rate control:
x(t ) x( p(t )) arg max U s ( x s ) p T (t ) H ( x)
x
Network
Link/MAC
s
Routing:
solved with rate control or scheduling
Scheduling:
f (t ) f ( p(t )) arg max p T (t ) A( f )
f
Physical
A Wi-Fi implementation by Warrier, Le and Rhee shows
significantly better performance than the current system.
Case study II: Integrating network
coding
Optimization based model for rate control: back-
pressure based scheme
max
x, g , f
s.t.
m
U
(
x
m )
m
md
g
i, j
j:( i , j )L
g
md
i, j
md
m
g
x
j ,i i , i d
f
m
i, j
(1,1,1)
(1,0,1)
(1,1,0)
ci , j
(1,1,0)
m
information
flow
(1,1,1)
j:( j ,i )L
f ,
m
i, j
S
physical
flow
Constraint from NC
(1,1,1)
(1,1,0)
(1,0,1)
(1,0,1)
d1
d2
( f i , j , g id,1j , g id, 2j )
coding subgraph
Case study II: Integrating network
coding
Optimization based model for rate control: back-
pressure based scheme
Rate control
xm U
' 1
m
( p smdm )
dDm
mi , j arg max
m
Session scheduling
g imd, j
Congestion price update
Backpressure
in congestion
md
md
[
p
p
i j]
dDm
ci , j if m mi , j & pimd p md
j 0
otherwise
0
pimd [ pimd ( ximd g imd, j g md
)]
j ,i
j
j
Other case studies
wireless scheduling
correlated data gathering in senor networks
0.5
f(t) arg max p (t)f
T
f Π
0.9
throughput-optimal scheduling
' 1
x s (U s ) (p s )
coded data
p s (t )
compression/link aware
opportunistic routing
0.2
coding matrix
input data
s(t)=arg max{ps(t)cs(t)}
LZ coder
BS
MS
dual scheduling algorithm
distributed source coding (LZ+NC)
a new optimization approach to
inter-session network coding
physical network coding
A
1
b1
S1
2
b1+b2
S2
B
A
d1
b2
three sessions: (s1;d1), (s2;d2), (s1,s2;d1,d2)
3
forwarding
2
b1+b2
b2
2
B
d2
b1+b2
b1
A
1
B
2
A+B
network coding
3
Dual dynamics: TCP/AQM
my PC
router
TCP
source algorithm (TCP)
iterates on rates
Primal:
Dual
max
x 0
s.t.
U
s
( xs )
s
Rx c
min
p 0
AQM
link algorithm (AQM)
iterates on prices
U
(
x
)
x
R
p
p
c
s max
s
s
s ls l
l l
xs 0
l
l
horizontal decomposition
Dual dynamics
• Controller is fully decentralized
• Globally stable to optimal equilibrium
• Generalizations to delays, other controllers
pl Rls xs cl
s
xs arg max Ls v, p
v
Vector
notation
p Rx c
x arg max L( v, p)
v
L(x, p) U (x) pT Rx c
U (x) pT Rx pT c
What else is this good for?
• Controller is fully decentralized
• Globally stable to optimal equilibrium
• Generalizations to delays, other controllers
• Views TCP as solving an
p Rx c
optimization problem
x arg max L( v, p)
• Clarifies tradeoff at
v
equilibrium
• Generalizes to other
strategies, other layers
• Framework for cross layering
But are the dynamics optimal?
• Controller is fully decentralized
• Globally stable to optimal equilibrium
• Generalizations to delays, other controllers
•
•
•
•
p Rx c
x arg max L( v, p)
Optimal controller?
Dynamic tradeoffs?
Routing, other layers?
Framework for cross layering?
v
Inverse optimality toy example
What is this controller optimal for?
px
x kp
dynamics
controller
State
weight
min
x
Optimal control
Control
weight
kp x dt
2
2
x kp
dynamics
px
Inverse optimality review
What is this controller optimal for?
• Integral quadratic penalty
• Deviation from equilibrium
• Balance state versus control penalty
• Well-known and “ancient” literature
State
weight
min
x
Optimal control
Control
weight
kp x dt
2
2
x kp
dynamics
px
min
x
p c x c dt
2
2
p xc
x p
Simple change
px
x kp
State
weight
min
x
Optimal control
Control
weight
kp x dt
2
2
x kp
p xc
x p
dynamics
px
min
x
p c x c dt
2
2
p xc
x p
What is this controller optimal for?
• IQ penalty on deviation from equilibrium
• Balance state versus control penalty
min
x
p c x c dt
2
2
p xc
x p
Simple change
p xc
p xc
x p
x arg max L v, p
v
min arg max L v, p c
x
v
2
x c dt p x c
2
x arg max L v, p
v
What is this controller optimal for?
• IQ penalty on deviation from equilibrium
• Balance state versus control penalty
Control
weight
State
weight
min arg max L v, p c
x
v
2
dynamics
x c dt p x c
2
x arg max L v, p
v
min
x
2
2
l s Rls xs cl s Rls xs cl dt
pl Rls xs cl
xs arg max Ls v, p ,
v
s
xs arg max Ls v, p
v
Network
min arg max L v, p c
x
v
2
x c dt p x c
2
x arg max L v, p
v
min
x
2
2
l s Rls xs cl s Rls xs cl dt
pl Rls xs cl
xs arg max Ls v, p ,
v
s
xs arg max Ls v, p
v
min
x
Rx c
2
Rx c
2
dt
x arg max L v, p , p Rx c
v
xs arg max Ls v, p
v
Vector
notation
What is this controller optimal for?
• IQ penalty on deviation from equilibrium
• Balance state versus control penalty
• Optimal controller is decentralized
State
weight
min
x
Rx c
Control
weight
2
Rx c
2
dt
x arg max L v, p , p Rx c
v
xs arg max Ls v, p
v
dynamics
What else is this result good for?
• Elegant proofs of stability
• Clarifies the tradeoff in dynamics
• Insights about joint congestion control
and routing
• Can derive more general control laws
min
x
Rx c
2
Rx c
2
dt
x arg max L v, p , p Rx c
v
xs arg max Ls v, p
v
• Finite horizon version
• Terminal cost is lagrangian
min
x
T
Rx c Rx c
2
2
0
dt arg max L v, p(T )
v
x arg max L v, p , p Rx c
v
xs arg max Ls v, p
v
An additional constraint: energy
aware design
Energy has become a key issue in systems design
Tradeoff between energy usage and traditional
performance metrics such as throughput and delay
Challenges:
How to leverage existing energy aware technologies such
as speed scaling
What are fundamental limits on various tradeoffs
The impact of energy aware design on the system
architecture
Our current focus is on wireless networks
74
Case study: wireless downlink
scheduling
n1
p1
1
“natural” speed scaling
c ln( 1 hi pi )
B
pN
nN
min
wT
i ik
w0 E
N
Developed an online algorithm with a
competitive ratio of 1 max{wi } / min{wi }
Extending to other scenarios such as
weighted sum of response
time-varying channels and finite
time and energy
energy budget, etc.
i
75
Generalization to game theory
Player i payoff function
maximize
Pi ( xi ; x i )
subject to
xi C i
Player i strategy space
Player i strategy
Developed to study strategic interactions
Provides a series of equilibrium solution concepts
Considers informational constraints explicitly
Equilibria arise as a result of adaptation and learning, subject
to informational constraint
Provides a basis for designing systems to achieve the given
desired goals (e.g., mechanism design)
76
Game theory: Engineering perspective
Network agents are willing to cooperate, but only
have limited information about the network state
E.g., may not have access to the information/signaling
required by an optimization-based design
The best is to optimize some local or private objective
and adjust its action based on limited information
about the network state
Non-cooperative game can be used to model such a
situation
Let network agents behave 'selfishly' according to the
game that is designed to guide individual agents to
seek an equilibrium achieving the systemwide objective
77
Game theory based decomposition
system-wide performance objective
design agent utility
and define game
look for distributed
converging algorithm
must respect
informational
constraints
protocol design:
protocols as distributed update
algorithms to achieve equilibira
78
Eco vs. Eng
Economic (traditional perspective): incentive is a hard
constraint that must be taken into account in the
design
The agent utility is given
Some possibility results exist
• Mechanism design
• Cooperative game
Engineering: the focus is on the implementation in
practical systems
Respect informational constraint of the system
The challenge: to what extend we can program network
agents to achieve desired systemwide objectives
Tradeoff among computational, informational, and
incentive issues
79
Case study: Throughput optimal
channel access scheme
to achieve maximum throughput under weighted
T
fairness constraint T , 1 l , m L.
U l ( pl ) (1
e
l
*
l
l
m
m
utility
) pl e (1
*
1
l
can be seen as an
axiomatic approach
) ln( 1 pl )
distributed converging algorithm
pi (t 1) [ pi (t ) i (t )(U i' ( pi (t )) qi ( p (t )))] si
80
Biology versus the Internet
Similarities
Differences
•
•
•
•
•
•
•
•
•
•
•
•
Evolvable architecture
Robust yet fragile
Layering, modularity
Hourglass with bowties
Dynamics
Feedback
Distributed/decentralized
• Not scale-free, edge-of-chaos, selforganized criticality, etc
Metabolism
Materials and energy
Autocatalytic feedback
Feedback complexity
Development and
regeneration
• >3B years of evolution
>4B
Biology versus the Internet
Similarities
Differences
•
•
•
•
•
•
•
•
•
•
•
•
Evolvable architecture
Robust yet fragile
Layering, modularity
Hourglass with bowties
Dynamics
Feedback
Distributed/decentralized
• Not scale-free, edge-of-chaos, selforganized criticality, etc
Metabolism
Materials and energy
Autocatalytic feedback
Feedback complexity
Development and
regeneration
• >3B years of evolution
Control of the Internet
Packets
source
receiver
control
packets
signaling
gene expression
metabolism
lineage
source
receiver
Biological
pathways
signaling
gene expression
metabolism
lineage
source
receiver
control
energy
materials
More
complex
feedback
source
receiver
control
energy
materials
Autocatalytic feedback
signaling
gene expression
metabolism
lineage
What theory is relevant to receiver
source
these more complex
feedback systems?
control
energy
materials
More
complex
feedback
Network
architecture?
Layers?
Pathways
“Central dogma”
DNA
RNA
Protein
Metabolic
pathways
Catabolism
Precursors
Metabolism
Nucleotides
Carriers
energy
materials
Catabolism
Precursors
Core
metabolism
Carriers
Inside every
cell (1030)
Nucleotides
Bacterial cell
Autocatalytic feedback
Precursors
Catabolism
Environment
Environment
Co-factors
Genes
Carriers
DNA
replication
Huge
Variety
Trans*
Proteins
Nutrients
Core metabolism
Huge
Variety
Catabolism
Precursors
Nutrients
Taxis and
transport
Same
12
in all
Core metabolism
cells
Nucleotides
Carriers
Same
8
in all
cells
Taxis and
transport
Autocatalytic feedback
12
Polymerization
and complex
assembly
Precursors
Catabolism
Co-factors
Genes
Carriers
DNA
replication
Huge
Variety
8
100
Trans*
Proteins
Nutrients
Core metabolism
104 to ∞
in one
organisms
Autocatalytic feedback
Polymerization
and complex
assembly
Huge
Variety
Proteins
Genes
DNA
replication
Trans*
104 to ∞
in one
organisms
The
Taxis and
transport
bowtie
Polymerization
and complex
assembly
Autocatalytic feedback
Proteins
architectu
re ofCatabolism
the
cell.
Carriers
Precursors
Nutrients
Core metabolism
Nucleotides
Trans*
Regulation
& control
Genes
DNA
replication
Regulation & control
Reactions
Flow/error
Carriers
Need a more
coherent
cartoon to
visualize how
these fit
together.
The
hourglass
architectur
e of the
cell.
Proteins
Reactions
Flow/error
RNA level
Reactions
Flow/error
DNA level
Precursors
Catabolism
Carriers
Gly
G1P
G6P
Catabolism
F6P
F1-6BP
Gly3p
ATP
13BPG
3PG
2PG
NADH
Oxa
PEP
Pyr
ACA
TCA
Cit
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
Cit
Gly
Precursors
G1P
G6P
F6P
metabolites
F1-6BP
Gly3p
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
Cit
Gly
G1P
G6P
Enzymatically
catalyzed reactions
F6P
F1-6BP
Gly3p
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
Cit
Autocatalytic
G1P
G6P
F6P
Precursors
Gly
F1-6BP
Gly3p
Carriers
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
Autocatalytic
G1P
G6P
Rest of cell
F6P
consumed
F1-6BP
Gly3p
ATP
13BPG
produced
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
G1P
Reactions
G6P
Control?
F6P
F1-6BP
Carriers
Gly3p
Proteins
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
G1P
G6P
Control
F6P
F1-6BP
Gly3p
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
Cit
If we drew the feedback loops the
diagram would be unreadable.
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
dx
S
Sv( x)
dt
Mass &
Reaction
Energy
flux
Balance
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
ATP
Stoichiometry
matrix
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
dx
Sv( x)
dt
Mass &
Reaction
Energy
flux
Balance
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
Regulation of enzyme levels by
transcription/translation/degradation
13BPG
3PG
2PG
Oxa
PEP
level
Pyr
ACA
TCA
Cit
dx
Sv( x)
dt
Mass &
Reaction
Energy
flux
Balance
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
Error/flow
ATP
13BPG
Allosteric regulation
of enzymes
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Mass &
Reaction
dx
Sv( x) Energy
flux
dt
Balance
Gly
G1P
G6P
Reaction
F6P
Error/flow
F1-6BP
Gly3p
Level
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
G1P
Reactions
G6P
Flow/error
F6P
F1-6BP
Protein level
Gly3p
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
G1P
Reactions
G6P
Flow/error
F6P
Layered
F1-6BP
architecture
Gly3p
Protein level
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Reactions
Flow/error
Protein level
Reactions
Flow/error
RNA level
Reactions
Flow/error
DNA level
Protein
Reactions
Flow/error
Protein level
RNA
Reactions
Flow/error
RNA level
DNA
Reactions
Flow/error
DNA level
Reactions
Flow/error
Protein level
Translation
Flow/error
RNA level
Transcription
Flow/erro
DNArlevel
Reactions
Flow/error
Protein level
RNA
React
Flow
DNA
React
Flow
DNA
React
Flow
DNA
Diverse Reactions
DNA
DNA
Diverse Genomes
DNA
Diverse Reactions
Flow/error
Protein level
Conserved
core
control
Reactions
Flow/error
RNA level
Reactions
Flow/error
DNA
DNA
Diverse Genomes
DNA
Flow/error
Protein level
Reactions
Flow/error
RNA level
Reactions
Flow/error
Reactions
Flow/error
Protein level
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
ATP
13BPG
3PG
2PG
NADH
Oxa
PEP
Pyr
ACA
TCA
Cit
Reactions
Flow/err
or
Protein level
Reactions
Gly
Layering
revisited
G1P
G6P
F6P
Flow/err
Carriersor Proteins
F1-6BP
Gly3p
ATP
More complete picture
13BPG
3PG
2PG
NADH
Oxa
PEP
Pyr
ACA
TCA
Cit
Precursors
Catabolism
Nucleotides
Carriers
Flow/error
Protein level
RNA
DNA
Precursors
Biosynthesis
Nucleotides
RNA
DNA
Precursors
Biosynthesis
Co-factors
RNA Transc.
xRNA RNA level/
Transcription rate
RNAp
Gene
DNA level
Precursors
Catabolism
AA
RNA Transc.
Gene
xRNA
RNAp
Precursors
Catabolism
AA
transl.
tRNA
Enzymes
Ribosome
ncRNA
mRNA
RNA Transc.
Gene
xRNA
RNAp
“Central dogma”
Protein
AA
transl.
Protein
RNA
Ribosome
Transc.
Flow
DNA
RNA Transc.
Gene
mRNA
RNAp
Precursors
Catabolism
Autocatalysis
everywhere
AA
transl.
Proteins
tRNA
All the enzymes
are made from
(mostly) proteins
and (some) RNA.
Ribosome
RNA transc. xRNA
RNAp
This is just charging and discharging
G6P
consumption Rest of cell
= discharging
F6P
F1-6BP
Gly3p
ATP
13BPG
charging
3PG
2PG
PEP
Pyr
ATP supplies
energy to all
layers
Rest of cell
G6P
F6P
F1-6BP
ATP
Gly3p
13BPG
3PG
2PG
A*P
PEP
Pyr
Flow/error
AMP level
Protein level
RNA
DNA
RNA
DNA
ATP
A*P
Flow/error
AMP level
Lots of
ways to
draw this.
Protein level
RNA
DNA
cell
Precursors
Catabolism
AA
transl.
Enzymes
tRNA
Layered
RNA transc. xRNA
S
reactions
P
Enz1 reaction3
tRNA
ncRNA
AA
trans.
Reaction rate
Enz2
Enzymes
Enzyme form/activity
Enzyme level/
Translation rate
RNA form/activity
mRNA
RNA Transc.
Gene
RNAp
xRNA
RNA level/
Transcription rate
Ribosome
reactions
products
reaction3
Control?
Proteins
trans.
Transc.
All products
feedback everywhere
ncRNA
Recursive
control
structure
Reactions
Flow
Protein level
Reactions
Application
Error/flow control
Global
RNA level
Relay/MUX
E/F control
E/F control
Reactions
Relay/MUX
Flow
Local
Relay/MUX
Flow
DNA level
Physical
Fragility example: Viruses
Reactions
Flow
Viral
proteins
Protein level
Reactions
Viruses exploit the universal
bowtie/hourglass structure to
hijack the cell machinery.
Flow
RNA level
Reactions
Viral
genes
Flow
DNA level
Reactions
Reactions
Flow/err
Carriersor Proteins
Flow/err
or
Protein level
Gly
Layering
revisited
G1P
G6P
F6P
F1-6BP
Gly3p
ATP
More complete picture ?
13BPG
3PG
2PG
NADH
Oxa
PEP
Pyr
ACA
TCA
Cit
Carriers
Reactions
Flow/err
or
Proteins
Reactions
Flow/error
RNA level
Reactions
Flow/error
DNA level
Applications
Operating
System
router
my
computer
server
application
TCP
IP
Hardware
Instructions
Logical
MAC
Switch
CircuitCircuitCircuit
Physical
MAC
Pt
to Pt
Reactions
Flow/erro
r
Carriers
Proteins
Physical
Reactions
?
What are the additional layers?
?
• Where is the
power supply?
?
• Where are the designs and
processes that produce the
chips, PCs, routers, etc?
Flow/erro
r
RNA level
Reactions
Flow/erro
r
DNA level
fan-in
of diverse
inputs
Diverse
function
Universal
Control
Diverse
components
universal
carriers
Bowties: flows
within layers
fan-out
of diverse
outputs
Essential ideas
Robust
yet
fragile
Constraints
that
deconstrain
fan-in
of diverse
inputs
Diverse
function
Diverse
components
fan-out
of diverse
outputs
Highly robust
• Diverse
• Evolvable
• Deconstrained
Robust
yet fragile
Constraints that
deconstrain
universal
carriers
Universal
Control
Highly fragile
• Universal
• Frozen
• Constrained
Robust
yet fragile
Constraints that
deconstrain
fan-in
of diverse
inputs
Diverse
function
Universal
Control
Diverse
components
universal
carriers
Bowties: flows
within layers
fan-out
of diverse
outputs
Essential ideas
Robust
yet
fragile
Constraints
that
deconstrain
What theory is relevant to
these more complex
feedback systems?
z
z p
ln S j signaling
d ln
2
2
0
z
z p
gene expression
1
source
metabolism
lineage
control
materials
energy
receiver
More
complex
feedback
[a system] can have
[a property] robust for
[a set of perturbations]
Fragile
Yet be fragile for
[a different property]
Robust
Or [a different perturbation]
Robust yet fragile = fragile robustness
[a system] can have
[a property] robust for
[a set of perturbations]
Apply recursively
[ property] = robust for
[one set of perturbations]
fragile for
[another property] or
[another set of perturbations]
Robust yet fragile = fragile robustness
[a system] can have
[a property] robust for
[a set of perturbations]
• Some fragilities are inevitable
in robust complex systems.
Fragile
Robust
• But if robustness/fragility are conserved, what does it
mean for a system to be robust or fragile?
Emergent
Fragile
• Some fragilities are inevitable
in robust complex systems.
Robust
• But if robustness/fragility are conserved, what does it
mean for a system to be robust or fragile?
• Robust systems systematically manage this tradeoff.
• Fragile systems waste robustness.
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Gly
G1P
G6P
F6P
F1-6BP
Gly3p
ATP
ATP
13BPG
3PG
2PG
Oxa
PEP
Pyr
ACA
TCA
NADH
Cit
Autocatalytic
x
1
0 kx x
Control
q Vx q
1 1 xh
F6P
F1-6BP
Gly3p
ATP
13BPG
3PG
y
1 q
1 k y y
Autocatalytic
x
1
0 kx x
Control
q Vx q
1 1 xh
F6P
F1-6BP
Gly3p
13BPG
3PG
ATP
y
1 q
1 k y y
Autocatalytic
x
q Vx q
1 1 xh
Control
y
1
0 (1 )
1 q
1 k y y
Autocatalytic
q
x
q
Vx 1 q
1
y 1 1 x h 1 ky 0 (1 )
Control
Control theory cartoon
x
S j
u
output=x
Controller
+
input
x
q Vx q
1 1 xh
Caution: mixed cartoon
y
1
0 1
1 q
1 k y y
u
X j
S j
U j
1
Hard limits
output=x
ln S j d 0
C
0
X j
ln S j d ln U j d
ln X j d ln U j d
Entropy rates
Plant
+
u
[ATP]
1.05
Ideal
1
h >>1
0.95
Time response
0.9
Sh = F( x) h
0.85
h=1
Fourier
Transform
0
5
10
15
20
Time (minutes)
0.8
h >>1
0.6
Log(|Sn/S0|)
of error
0.8
0.4
0.2
Spectrum
h=1
0
log S h log S1
-0.2
-0.4
-0.6
-0.8
0
2
4
Frequency
6
8
10
[ATP]
1.05
1
h >> 1
0.95
Time response
0.9
0.85
Yet
fragile
h=1
0.8
0
5
10
15
20
Time (minutes)
0.8
h >>1
Robust
Log(Sn/S0)
0.6
0.4
0.2
Spectrum
h=1
0
-0.2
ln Sh j ln S0 j
-0.4
-0.6
-0.8
0
2
4
Frequency
6
8
10
ln S j d 0
0
Yet
fragile
0.8
h=3
Robust
Log(Sn/S0)
0.6
0.4
0.2
h=0
0
-0.2
-0.4
-0.6
-0.8
0
2
4
Frequency
6
8
10
[a system] can have
[a property] robust for
[a set of perturbations]
Fragile
Yet be fragile for
[a different property]
Robust
Or [a different perturbation]
Robust yet fragile = fragile robustness
X j
S j
U j
1
Hard limits
output=x
ln S j d 0
C
0
X j
ln S j d ln U j d
ln X j d ln U j d
Entropy rates
Plant
+
u
[ATP]
1.05
1
h >> 1
0.95
Time response
0.9
0.85
Yet
fragile
h=1
0.8
0
5
10
15
20
Time (minutes)
0.8
h >>1
Robust
Log(Sn/S0)
0.6
0.4
0.2
Spectrum
h=1
0
-0.2
ln Sh j ln S0 j
-0.4
-0.6
-0.8
0
2
4
Frequency
6
8
10
X j
S j
U j
1
ln S j d 0
output=x
C
0
+
The plant can make
this tradeoff worse.
Plant
z
z p
ln S j 2
d ln
2
0
z
z p
1
u
X j
S j
U j
1
ln S j d 0
C
0
All controllers:
Biological cells: =
z
k
q
p RHPzero s 2 q k s k
+
Plant
z
z p
ln S j 2
d ln
2
0
z
z p
1
output=x
u
X j
S j
U j
1
ln S j d 0
C
0
Small z is bad.
+
Plant
z
z p
ln S j 2
d ln
2
0
z
z p
1
output=x
u
z
k
q
p RHPzero s 2 q k s k
Small z is bad
(oscillations and crashes)
z
z p
ln S j 2
d ln
2
0
z
z p
1
Small z =
• small k and/or
• large q
k
z
q
Efficiency =
• small k and/or
• large q
Correctly predicts conditions
with “glycolytic oscillations”
X j
S j
U j
1
Hard limits
output=x
ln S j d 0
C
0
X j
ln S j d ln U j d
ln X j d ln U j d
Entropy rates
Plant
+
u
1
ln S j d 0
output=x
0
Plant
+
Controller
u
1
ln S j d 0
output=x
0
Channel
Plant
+
Sensor+
Channel
u
Controller
1
ln S j d C
FB
Hurts
0
1
output=x
ln S j d C
sensor
Helps
0
Channel
Plant
+
Controller
Sensor+
Channel
u
Robust
Small
Simple
Fragile Chaocritical
•
•
•
•
Large
Organized
Irreducible
Taxonomy covers standard usages
Unified picture
Can make the definitions more precise
Have “hand crafted” theorems in every major complexity
class (but lack a unified theory)
Academic stovepipes
EE, CS, ME, MS, APh, ChE, Bio, Geo, Eco, …
Apps
Tools/
tech
Apps
Apps
Apps
Tools/
tech
Tools/
tech
Apps
Tools/
tech
Tools/
tech
Diverse applications
Funding
twine
Apps
Apps Apps
Apps
Apps
Tools/
Tools/Tools/
tech Tools/
Tools/
tech tech
tech tech
“Multidisciplinary cross-sterilization”
Diverse applications
Layering
academia?
?????
Diverse resources
Apps Apps Apps
Apps
Tools/ Tools/ Tools/ Apps
Tools/
tech tech tech
tech
Tools/
tech
End
What follows are additional details on
the glycolysis fragility example.
Autocatalytic
x
q Vx q
1 1 xh
Control
y
1
0 (1 )
1 q
1 k y y
Autocatalytic
q
x
q
Vx 1 q
1
y 1 1 x h 1 ky 0 (1 )
Control
x
produced
ky y
y
consumed
k y ( y)
y
x
rate
ky y
y
ky y
k y ( y)
y
x
rate
ky y
y
level
ky y
k y ( y)
y
More enzyme
Autocatalytic
x
Control
k1 ( x)
y
consumed
produced
k1 ( x)
x
Autocatalytic
x
Control
k1 ( x)
y
rate
form/activity
k1 ( x)
x
Autocatalytic
x
Control
k1 ( x)
y
Layered control
rate
form/activity
level
k1 ( x)
x
Autocatalytic
x
Control
k1 ( x)
y
Layered control
rate
form/activity
level
k1 ( x)
x
x
1
0 (1 )
consumed
x q
1 q
1
y 1 k x x 1 ky 0 (1 )
stable
w
k ()
kw w
1
0 (1 )
x
y
ky y
Autocatalytic
q Vx q
1 1 xh
k ()
x
y
1
0 (1 )
1 q
1 k y y
Autocatalytic
q Vx q
1 1 xh
x
Control
y
1
0 (1 )
1 q
1 k y y
k y ( y)
k1 ( x)
Autocatalytic
q Vx q
1 1 xh
1
0 (1 )
x
Control
y
Robust
Strong inhibition
1 q
1 k y y
Yet Fragile
Enzyme complexity,
Oscillations
Low autocatalysis
Inefficiency,
High reaction rates
metabolic load