Transcript Optimization-Based Reverse Engineering of Network Structure and

Optimization-Based Reverse Engineering
for Complex Networks
David Alderson
Operations Research
Naval Postgraduate School
Kick-off Meeting, July 28, 2008
ONR MURI: NexGeNetSci
David Alderson
Research Agenda: management and operation of network
infrastructure systems, so as to ensure efficient and reliable
performance while protecting these infrastructures from largescale disruptions resulting from accidents, failures, or attacks.
• Operations Research Dept, NPS
Assistant Professor, arrived September 2006
• Caltech: Postdoctoral Scholar, 2003-2006
– “complex yet fragile” nature of the Internet
• Stanford University
PhD (2003) Management Science & Engineering
Advisors: William J. Perry and Nicholas Bambos
• Diverse professional and research experience: Goldman Sachs, Xerox PARC,
IPAM (UCLA), Santa Fe Institute
• Princeton University
BSE (1993) Civil Eng & Operations Research
ONR MURI: NexGeNetSci
challenges in studying complex network systems
• the term “network” is ambiguous
– a Rorschach test
– a discrete approximation to any continuous relationship
• “graph”  mathematical definition
e.g., G = (N, A)
• “network” = graph + data (annotation)
• network dynamics are fundamental to many systems:
dynamics
ON networks
behavior on top of a
(fixed) graph structure
dynamics
OF networks
evolution of the graph
structure itself
Many systems of interest involve the interaction of the two
ONR MURI: NexGeNetSci
NETWORK SCIENCE
January, 2006
Some Basic Questions
Q1. To what extent does there exist a “network structure” that is responsible
for large-scale properties in complex systems?
Q2. To what extent are there “universal laws” governing the structure (and
resulting behavior) of complex networks? To what extent is selforganization responsible for the emergence of system features not
explained from a traditional (i.e., reductionist) viewpoint?
Q3. How can one assess the vulnerabilities or fragilities inherent in these
complex networks in order to avoid “rare, yet catastrophic” disasters?
More practically, how should one design, organize, build, and manage
complex networks?
ONR MURI: NexGeNetSci
a fundamental question in the study of complex systems
STRUCTURE
• components • constraints
• interactions • uncertainties
?
FUNCTION
purposeful behavior of
interacting components
• one approach: study the system of interest as an artifact
–
–
–
–
assume no prior knowledge about system
Q1: What is the system structure?
Q2: What is the system function?
Q3: How does structure support function?
• hard to know what “matters” from outside looking in
– modeling choices: affect the outcome
– different assumptions lead to different (opposite!) results
• a view incompatible with traditional engineering design
– design of components/interactions to ensure system function
– assumes knowledge of relationship: structure and function
ONR MURI: NexGeNetSci
a fundamental question in the study of complex systems
STRUCTURE
• components • constraints
• interactions • uncertainties
?
FUNCTION
purposeful behavior of
interacting components
Network Science Approach (current):
• large data samples, uncertainty
• a graph theoretic foundation
 random ensembles
• descriptive models
• dynamics, statistical properties
– graph connectivity (structure)
 statistical mechanics
– graph evolution (dynamics)
• null hypothesis: random graphs • emphasis: “likely” configurations
Common theme:
•self-organization and “emergent” structure (i.e., “emergent complexity”)
ONR MURI: NexGeNetSci
ONR MURI: NexGeNetSci
an “engineering view” of complex systems
Forward engineering = Design of components/interactions to insure
system function
STRUCTURE
• components • constraints
• interactions • uncertainties
?
FUNCTION
purposeful behavior of
interacting components
Reverse engineering = Model the structure to explain observed function
what “matters” for the given system under study?
ONR MURI: NexGeNetSci
an alternate approach to complex network research
Null hypothesis: the structure of the network has been “designed” to
achieve the existing function
STRUCTURE
• components • constraints
• interactions • uncertainties
?
FUNCTION
purposeful behavior of
interacting components
Basic idea: use an optimization-based framework to reverse-engineer
the objectives, constraints, tradeoffs shaping the system design
Solving this type of inverse problem is highly underconstrained.
Key question: what else to bring into the model?
ONR MURI: NexGeNetSci
Examples
1. Internet topology modeling
•
reverse engineering the (implicit, ad hoc) design of a
single, centralized decision maker (i.e., the ISP)
2. the behavior of TCP/AQM
•
reverse engineering a theory (i.e., primal-dual
optimization algorithm) to explain the successes and
failures of a decentralized, asynchronous protocol
3. network formation games
•
exploring the collective behavior of self-interested
agents who cooperate and/or compete
ONR MURI: NexGeNetSci
Example: Internet Topology Modeling
• Who builds real router-level topologies?
the “decision makers” are individual ISPs
• How do technology and cost influence deployment?
they provide CONSTRAINTS on what the ISP can do
• How does one evaluate a “good” design?
network PERFORMANCE can be measured in terms of traffic
• What drives their structure?
some form of an (implicit) OPTIMIZATION problem, although
actual “design” may be decentralized and heuristic
• What about power laws?
to the first order, they should be a non-issue
ONR MURI: NexGeNetSci
example: Internet topology modeling
Existing router-level topology: a solution to a DESIGN problem
• customer demands
– geographic dispersion
– variations in size
– primary source of uncertainty
• physical constraints on components
– distance/delay, capacity
• functional constraints on the system as a whole
– throughput, delay, cost
– robustness to input uncertainty, component loss
modeling approach: constrained optimization
• not the language of random graphs
• problem driven by graph annotations, not graph connectivity
• domain-specific, not generic
• transforms network modeling from an exercise in data fitting to an
exercise in reverse-engineering
ONR MURI: NexGeNetSci
Toy Example: Evaluating Network Throughput
Given realistic technology constraints on routers, how well
is the network able to carry traffic?
Step 1: Constrain to
be feasible
Step 2: Compute traffic demand
Bj
xij  Bi B j
xij
Bi
Step 3: Compute max flow
max  xij  max  Bi B j

tradeoff: number of connections
(degree) vs connection speed
i, j
s.t.
ONR MURI: NexGeNetSci
i, j
x
i , j:krij
ij
 Bk , k
Reverse-Engineering via Optimization
(example: a simple linear program)
(Forward) Optimization
Given
Inverse Optimization
Given
cost vector c
feasible region
X= { x: Ax = b, x  0 }
Solve
feasible point x0  X
Solve
Minimize ĉ – c 
subject to
x0 = argmin{ ĉ x: x  X }
Minimize c x
subject to x X
Result
Result
x* = minimum cost solution
ĉ* = cost vector minimized by x0
Reference:
R.K. Ahuja and J.B. Orlin. 2001. Inverse Optimization. Operations Research 49(5): 771-783.
ONR MURI: NexGeNetSci
Reverse-Engineering via Optimization
(example: a general mathematical program)
“Inverse Optimization”
(Forward) Optimization
Given
Given
system performance f(x)
feasible region
X= {x: g(x)  0, h(x) = 0}
Solve
feasible point x0
Solve
Maximize f(x)
subject to x X
Find f, X
subject to
x0 is a “good” solution to
Max f(x) s.t. x  X
Result
Result
x* = best system “design”
a design problem solved by x0
ONR MURI: NexGeNetSci
Reverse-Engineering via Optimization
(case study: the router-level Internet)
“Inverse Optimization”
Given
Empirical evidence
(measurement studies)
feasible point x0
Solve
Use of “first principles”
Heuristically optimal
Find f, X
subject to
x0 is a “good” solution to
Max f(x) s.t. x  X
Result
a design problem solved by x0
ONR MURI: NexGeNetSci
Heuristically Optimal Topology
Sparse, mesh-like core of fast, low-degree routers.
Relatively uniform
connectivity within core.
Core
Edges
Hosts
High degree nodes are at the edges.
ONR MURI: NexGeNetSci
High cost of links
drives traffic
aggregation at
network edge
Possibly high
variability in
connectivity at edge.
alternate approaches yield OPPOSITES in terms of engineering
Optimization-based:
• Focus: engineering design
• Uses domain-specific details
• Sparse network core
• High performance and
robustness
Degree-based:
• Focus: matching statistics
• Ignores domain-specific details
• High degree central “hubs”
• Poor performance and
robustness
These stark differences are independent of the actual statistics
ONR MURI: NexGeNetSci
reverse engineering: transport layer protocol
web
server
my
computer
TCP
router
router
AQM
AQM
ONR MURI: NexGeNetSci
TCP
reverse engineering: transport layer protocol
web
server
my
computer
TCP
router
router
AQM
AQM
ONR MURI: NexGeNetSci
TCP
reverse engineering: transport layer protocol
Kelly/Low Formulation: TCP/AQM as a Primal-Dual Algorithm
my
computer
Ref: S. Low. A Duality Model of TCP and Queue Management Algorithms.
IEEE/ACM Trans. on Networking 11(4):525-536, 2003.
router
TCP
source algorithm (TCP)
iterates on rates
Primal:
AQM
link algorithm (AQM)
iterates on prices
Dual:
Major TCP schemes
Reverse-Engineering:
• Maximize aggregate source utility
• With different utility functions
• Theoretical support for existing protocols
• Insight for new/improved protocols
ONR MURI: NexGeNetSci
reverse engineering: the Internet protocol stack
my
computer
router
APP
TCP/AQM
IP
PHY/LINK
General Approach:
An engineering design perspective
to understand, explain
the complex structure observed.
Take a single layer in isolation
and assume that the other layers
are handled near optimally.
ONR MURI: NexGeNetSci
reverse engineering: the Internet protocol stack
my
computer
router
APP
TCP/AQM
IP
?
PHY/LINK
If the current router-level
Internet is the answer,
what is the question?
ONR MURI: NexGeNetSci
reverse engineering: the Internet protocol stack
my
computer
router
APP
?
TCP/AQM
If TCP/AQM is the answer,
what is the question?
IP
PHY/LINK
ONR MURI: NexGeNetSci
reverse engineering: the Internet protocol stack
my The entire protocol stack as a decentralized, asynchronous,
computerlayered solution to a global resource allocation problem?
router
APP
TCP/AQM
IP
PHY/LINK
Network Utility Maximization
(NUM)
as a unifying framework for
design of network protocols
Ref: Chiang, Low, Calderbank, and Doyle.
Layering as Optimization Decomposition.
Proc. of the IEEE 95:255–312, 2007.
ONR MURI: NexGeNetSci
network formation games
• Let N denote the set of players, |N|=n.
• Each player i=1,2,…n chooses a strategy si which defines
the connections to build to other players (nodes).
– connection “cost” is borne by one/both of the players
• Let s=(s1,s2,…sn) denote the collective player strategies
• Let A(s) be the set of all edges resulting from strategy s;
G(s)=(N,A(s)) is the resulting graph
– Unilateral Connection Game (UCG)
UCG : A( s )  {(i, j ) : i  j, sij  1  s ji  1}
– Bilateral Connection Game (BCG)
BCG : A( s )  {(i, j ) : i  j, sij  1  s ji  1}
• Each player optimizes local utility (combines connection
cost with benefit of being connected to network)
ONR MURI: NexGeNetSci
AS-topology as a hybrid network formation game
Two types of business relationships among ASes:
• customer-provider relationship
– unilateral: customer as price taker pays provider
• peering relationship
– bilateral: both ASes agree to share traffic at low cost
How do the collective decisions of selfish players
lead to a global network structure
– stability
– sustainable economics
– compare with social optimum: “price of anarchy”
ONR MURI: NexGeNetSci
common themes
• many complex networks can be understood in terms of
design problems:
– tradeoffs: what is desirable vs. what is feasible
• modeling: constrained optimization
• reverse engineering: identify the key objectives and
constraints shaping design and operation
• Internet as a canonical case study
• new mathematics:
– inverse optimization
– decentralized, asynchronous, myopic decisions
– integrated controls, communication, computation
• successful reverse engineering invites new (and
important) forward engineering problems
ONR MURI: NexGeNetSci
Optimization-Based Reverse Engineering
for Complex Networks
David Alderson
[email protected]
831.656.1814
Kick-off Meeting, July 28, 2008
ONR MURI: NexGeNetSci