Transcript Cognitive Packet Networks - CHIST-ERA

Self-Aware Networks: QoS & Performance
http://san.ee.ic.ac.uk
Summary in E. Gelenbe, Communications of the ACM, July 2009
Introduction in S. Dobson et al. “Autonomic Communications”,
ACM Trans. Adapt. Aut. Systems, 2006
Erol Gelenbe
Professor in the Dennis Gabor Chair
Imperial College
www.ee.ic.ac.uk/gelenbe
[email protected]
Member of Academy of Sciences of Turkey www.tuba.gov.tr
Academy of Sciences of Hungary www.mta.hu
Academie des Technologies (France) www.academie-technologies.fr
Self Awareness and Adaptation in Networked Natural Systems is our
Speculative Topic of Investigation:
Spiking Neurons, Gene Regulatory Networks, Chemistry, Digital Economy
Extension: Gene Regulatory
Networks
A Communication Network such as the Internet is a
Control System whose function is to Adaptively and
Robustly vehicule Information between Users and
offer Services to Users
 Old Goals include Quality of Service (Loss, Delay,
Jitter, Low Overhead)
 New Goals include Security, Privacy, Low Energy
Consumption, Resilience to Attacks

Computer-Communication
Networks are Robust Control
Systems
Network Control cannot be based on “set point” approaches
because such simple points do not exist
 Models are routinely used for Preliminary Design of
Topologies and Capacity Optimisation
 The use of Models for Network Control is limited because of
dimensionality, model accuracy, parameter identification,
control computation and control delays
 Self-Awareness in this Area can be based on Online Measurement and Continuous, Distributed
Adaptation

Computer-Communication
Networks  Self-Aware Systems
Self-Awareness must Address Network Security via Detection
of Attacks and Adaptive Countermeasures
 Energy Consumption by Networks and ITC represents 2% of
worldwide consumption  Self-Aware Control needs to
address this issue to limit any further increase while ITC
pervasively extends
smart homes, smart vehicles, smart grid, e-learning
 Network Self-Awareness must incorporate the
application:
digital economy, smart grid  Co-Networks
[Comms+Application]
  On-line Measurement and Continuous,
Distributed Adaptation

Co-Networks  Self-Aware
Systems
IP Core Technology also supports Mobility
Hot Stuff happens at the periphery: parasitic
and symbiotic relationships
Fixed
and Mobile Convergence
IP is obviously – for the time being – the universal solution provider for
Communications
Applications as Networks: The Family’s Private Network
The FPN is a Network User, and its is a Service for the Family
Private to the family and specific services: Home Security, Housekeeper, Parents
Fully known to itself (self-aware, self-monitoring) cheap, secure, private and
dependable
Must dynamically and economically use all available communication modalities:
Sensor Networks, IP etc., public fixed and mobile telephony, WiFi, .. You guess it ..
-
Children and Parents have PDAs and Lap-Tops
-
Children use home “learning center” based on multiple external services
-
Parents’ cars are connected
-
Infants, grand parents, teen-agers are being monitored
-
House security system, Home temperature, sound sensors & actuators are on-line
-
Home appliances, security, entertainment, heating, lighting are monitored and controlled
-
Autonomic Self-Aware Management of Connections, U[grades, Costs, QoS, Policies,
Virtual Services, Network Resources, Monitoring …
The Internet Architecture: A Historical
Perspective
- It was Invented “Against” the Telecoms Industry because of
DoD’s Dissatisfaction with Telephony for Dependable
Communications
- The Initial System was Built on top of Analog Telephony
- The Telecoms Industry Fought it for Many Years and Created
Competing Services (e.g. Minitel, Teletext) .. and so did some of
the Computer Industry (IBM’s EARN, Frame Relay, Transpac)
- The First Major Application was File Transfer .. Then E-mail ran
under FTP
- The Internet grew in a Time of Deregulation based on Loose
Standardization (e.g. IETF)
Historical Internet Protocols: OSI Layers






TCP/IP is a layered protocol stack
Application handles particular
applications, Presentation handles
compression and encryption of data,
Session controls establishment,
management, termination of sessions
Transport provides flow of data
Network handles the transmission of
packets in the network
Data-link is responsible for the
interaction of the device driver in the
operating system and the network card
in the machine
Physical defines electrical and
mechanical specifications
Application
Presentation
Session
Transport
Network
Data Link
Physical
IP Architecture in Reality:
An Assembly of Inter-dependent Protocols
- The Web is a “Standard User Interface”
- TCP the Transmission Control Protocol: Controls Packet Flow for a
Connection as a Function of Correctly Received or Lost Packets (TCP
Reno, Vegas, etc.) & Retransmits Lost Packets
- BGP: Determines Paths between Clouds of Routers belonging to
Autonomous Systems (AS)
- MPLS: Carries out fast Packet Switching based on Pre-determined
Paths within ASs using Labels, Implements Traffic Engineering within
ASs
- IP Implements Shortest Path Routing within ASs. Variants of IP
Address QoS (e.g. DiuffServ, IPV6), Weighted Fair Queueing,
Congestion Control through Packet Drop …
IP Architecture:
A Distributed System which has Evolved
through Usage and Practice
- It grew in a Time of Deregulation
- The Web was developed to store technical papers
- TCP is a Rudimentary Congestion Control
Mechanism
- BGP Allows Different ISPs to Exchange Traffic
- MPLS Exploits ATM-like Fixed Path Routing and
Reduces the Overhead of Packet Switching
- The IP (Internet Protocol) provides Router Based
Staged Decisions & Shortest Paths to Minimize
Overhead
Critique from the Founding Funders
(DARPA) in August 2004
- “Flaws in the basic building blocks of networking and computer
science are hampering reliability, limiting flexibility and creating
security vulnerabilities”
(Note that DARPA paid for most of these developments !!)
- DARPA wants to see the IP and the OSI protocol stack
revamped
- “The packet network paradigm … needs to change … we must
… have some mechanism for assigning capabilities to different
users … today’s networks are stationary and have a static
infrastructure … (mobile) nodes should be able to automatically
sign on to networks in their vicinity …
The “Historical” Need for QoS
- Exploit different technologies dynamically, for the
users’ benefit
- Identify and eliminate undesirable traffic flows, e.g.
SPAM
- Protect from Malicious Attacks: Viruses and Worms,
Denial of Service Attacks
- Identify services and charge for them
- Provide security to connections
- Demonstrable service levels and monitored
agreements
- Wireless makes it all the more urgent
The Means for Quality of Service
- Effective user interfaces & Access Control
- Pro-active monitoring of users
- On-line monitoring of flows
- Pro-active measurement
- Monitoring of QoS/QoE and Service Level
Agreements
- Technical approach that Crosses Protocol
Layers
Coordinated Measurement Based Dynamic
Adaptation
In Theory, QoS Optimisation Problems can be
defined and Solved
In Practice Optimisation is Impossible





The network is very large – for specific users,
optimization is relevant for a subset of routes at a
time
The system is large .. information delay, control delay
and combinatorial explosion: global algorithms can be
very slow and come too late
The system is highly dynamic – traffic varies
significantly over short periods of time
There are large quantities of traffic in the pipes –
congestion can occur suddenly, reaction and detours
must be very rapid
Measurements are local to subset of users, and
adaptivity is needed which is relevant to the users
most concerned by the measurements
On-Line Measurement and Adaptation
“Self-Aware Networks”
- Many applications have implicit or explicit QoS requirements
• Voice, Video conferencing, Network games and simulation,
Commerce , Banking
– QoS techniques based on “parameter setting” such as IntServ, DiffServ
and IPv6 have been unsuccessful
Our proposal:
Users and Services formulate their Needs and QoS Goals
The Network Service adaptively offers Services to Users
and the Resources to Users and Services
The Network Service Monitors the outcome and Adaptively
re-allocates Services and Resources as needed
The Approach is that of Adaptive Control in a Random
Environment
How about theory?
Sensible Routing Theorem
[Gelenbe, Computational Management Science ‘03]
Consider any decision point x at with n choices
Let q(x,i) be a r.v. representing the QoS that
results from choice i, and lrt W(x,i) = E[u(q(x,i))]
be the expected outcome of choice i
Theorem If p(k)(x,i) = [W(x,i)]-k/ Snm=1 [W(x,m)]-k
and
W(k)(x) = Snm=1 W(x,m) p(k)(x,i),
then
W(k+1)(x) < W(k)(x)
Simulation of Routing with Perfect Ignorance
Average Travel Time E[T] vs Average Time-Out 1/r
for a regular 8 neighbour grid with d=1 and D=10 (b=0,
c=1.5)
General Context






Packets go from some source S to a Destination (that may
move) that is initially at distance d
The wireless range is d << d, there are no collisions
Packets can be lost in [t,t+Dt] with probability lDt
anywhere on the path
There is a time-out R (in time or number of hops), or
timed-out in [t,t+Dt] with probability rDt with a subsequent
retransmission delay M
Packets may or not know the direction they need to go –
we do not nail down the routing scheme with any specific
assumptions
We avoid assumptions about the geography of nodes (in
some m-dimensions) but assume temporal and spatial
homogeneity and temporal and spatial independence along
the distance to the destination – each physical setting will
have a different distance ..
22/07/2015
23
Destination
Source
Simulation examples in an infinite grid: d=1
(D=6) or d=sqrt(2) (D=4)
22/07/2015
24
Simulations of Average Travel Time
vs Constant Time-Out
d=1, D=10, M=20, No Loss
Perfect Ignorance: b=0, c=1
22/07/2015
25
Brownian Motion Model
Assumes homogeneity with respect to distance to the destination
After each Loss or Time-Out, the Source waits M time units and then
retransmits the packet under identical statistical conditions
f ( x , t ) dxdt is the probabilit
y that the
x  X t  x  dx from the destinatio
- P(t) is the probabilit
destinatio
packet is at distance
n at time
[t,t  Δt[
y that a packet has reached the
n and that a new packet wil l be retransmit
ted
after unit time
- L(t) is the probabilit
y that the
most recently t ransmitted
packet is lost. S will " time - out" after a time - out of
average value R  r
1
- W(t) is the probabilit
y that S is in the wait state after a time - out;
it will send out a new copy after time
M  
1
Packets reach thei r destinatio
d at times T i  s i where E [ s i ]  1
transmitte
f
 b
t
dP ( t )
dL ( t )
dt

x
1
2
 f
2
c
x
 [  W ( t )  P ( t )] d ( x  D )
2
x 0
 l
dW ( t )
dt
f
  P ( t )  lim  [  bf 
dt
n at times T i , the process is renewed and a new packet is

 r

0

f
x
]
fdx  rL ( t )   W ( t )
P (t )  L (t )  W (t ) 


0
E[T]  P  1 obtained
-1
2
c
fdx  rL ( t )

0
1

fdx  1 ; lim  f  0 .
x 0
from the stationary
solution
22/07/2015
27
Theoretical Result: Time to Travel
to a Destination at Distance D
Average Time E[T]
 Drift b < 0 or b>0, 2nd Moment Param. c>0
 Average Time-Out 1/r , M=1/, then

1
E [T ]   2 D
b 
b
l  r
l


r
2
 2c (l  r )
22/07/2015
28
Theory: Average Travel Time for D=10, b=0, 4Neighbours and M=50 with Losses
22/07/2015
29
Theory: what happens when loss rate increases
22/07/2015
30
What happens if we send multiple copies of
each packet and accept the first one that
arrives ?
22/07/2015
31
What happens if we send multiple copies of each packet
and accept the first one that arrives ?
22/07/2015
32
Send N copies of each packet and accept the
first that arrives ..
22/07/2015
33
Summary








Mathematical model assumes exponentially distributed loss
time, time-out and re-start time after time-out
It assumes temporal and spatial homogeneity
It allows for generally distributed times between hops
Closed form expressions are obtained for E[T] from the
diffusion model with jumps for al values of D, b, c, r, l, 
If b<0 (good) the average total travel time E[T] is finite
If b>0 (bad), E[T] is finite provided that time-outs
(hara-kiri) exist and c>0
There is a single minimum of E[T] as a function of r
Additional results: Multiple Copies of Each Packet – You can
actually save on energy and improve timeliness Sufficient
conditions under which the packet gets to the destination
when the destination moves
22/07/2015
34
QoS Routing Pragmatics :
The Cognitive Packet Network
Approach
Let the Measurements and On-Line Adaptation
be under “user” or meta-user control
 Let the user make his/her own QoS and
economic decisions
 Remain compatible with the core IP protocol ..
i.e. be able to run CPN and IP simultaneously
and tunnel IP packets through CPN sub
networks

OSI Layers & CPN






TCP/IP is a layered protocol stack
Application handles particular
applications, Presentation handles
compression and encryption of data,
Session controls establishment,
management, termination of sessions
Transport provides flow of data
Network handles the transmission of
packets in the network
Data-link is responsible for the
interaction of the device driver in the
operating system and the network
card in the machine
Physical defines electrical and
mechanical specifications
Application
Presentation
Session
Transport
Network
Data Link
Physical






CPN operates seamlessly with IP and
creates a self-aware network environment
Users select QoS goals
The User’s Packets collectively learn to
achieve the goals
Learning is performed by sharing
information between packets
User Packets sharing the same goals can
be grouped into classes
Nodes (Cognitive Routers) are storage
centers, mailboxes and processing units
CPN Principles
CPN and Smart Packets
Smart Packets route themselves based on QoS
Goals, e.g.,
Minimise Delay or Loss or Combination
Minimise Jitter (for Voice)
Maximise Dispersion (for security)
Minimise Cost
Optimise Cost/Benefit
Smart Packets make observations & take
decisions
ACK Packets bring back observed data and trace
activity
Dumb Packets execute instructions, carry
payload and also may make observations
Cognitive Adaptive Routing




QoS Goals are obtained from Path
Measurements: Traffic, Delay, Loss, Cost, Power,
Security Information – this is the “Sufficient
Level of Information” for Self-Aware Networking
Smart packets collect path information and dates
ACK packets return Path, Delay & Loss
Information and deposit W(K,c,n,D), L(K,c,n,D)
at Node c on the return path, entering from Node
n in Class K
Smart packets use W(K,c,n,D) and L(K,c,n,D) for
decision making using Reinforcement Learning
Decision System: a “neural” network of networks
(neural networks embedded in each router)
Internal State of Neuron i, is an Integer xi > 0
Network State at time t is a Vector
x(t) = (x1(t), … , xi(t), … , xk(t), … , xn(t))
Is the Internal Potential of Neuron I
If xi(t)> 0, we say that Neuron i is excited and it
may fire at t+ in which case it will send out a spike
If xi(t)=0, the Neuron cannot fire at t+
When Neuron i fires: :
It sends a spike to some Neuron k, w.p. pik
Its internal state changes xi(t+) = xi(t) - 1
Rates and Weights
If xi(t)> 0, then Neuron i will fire with probability
riDt in the interval [t,t+Dt] , and as a result:
From Neuron i to Neuron m
- Excitatory Weight or Rate is wim+ = ri pim+
- Inhibitory Weight or Rate is wim- = ri pim - Total Firing Rate is ri = Snm=1 wim+ + wim–
To Neuron i, from Outside the Network
- External Excitatory Spikes arrive at rate Li
- External Inhibitory Spikes arrive at rate li
State Equations
p ( k , t )  Pr[ x ( t )  k ] where {x(t):t  0 } is a discrete

and
k ij

 k  ei  e j ,
k ij

d
p (k , t ) 
dt
k i  k  ei :
- Kolmogorov
 [ p (k

ij
 k  ei  e j

k i  k  ei ,
The Chapman
state - space Markov process,
Equations



, t )ri p ij 1[ k j ( t )  0 ]  p ( k ij , t ) ri p ij ] 
i, j
 [ p (k

i

, t )( l i  ri d i )  L i p ( k i , t )1[ k i ( t )  0 ]]
i
 p ( k , t )  [( l i  ri )1[ k i ( t )  0 ]  L i ]
i
Let :
p ( k )  lim Pr[ x ( t )  k ],
t 
Theorem
then
it
If
has
the
the
C K
and
equations
" product  form "
q i  lim Pr[ x i ( t )  0 ]
t 
have
a
stationary
solution ,
n
p ( k )   q i i (1  q i ) ,
k
i 1
where
External Arrival
Rate of Excitatory
Spikes


ji
Probability that
Neuron I is excited
0
 qi 
Li 
ri  l i
 qrp
 q r p
j
j
j

ji
j
j
j

Firing Rate of
Neuron i
External Arrival
Rate of Inhibitory
Spikes


ji

ji
1
Goal Based Reinforcement
Learning in CPN

The Goal Function to be minimized is selected by
the user, for instance G = [1-L]W + L[T+W]

On-line measurements and probing are used to
measure L and W, and this information is brought
back to the decision points



The value of G is estimated at each decision node
and used to compute the estimated reward R =
1/G
The RNN weights are updated using R stores G(u,v)
indirectly in the RNN which makes a myopic (one
step) decision
Routing with Reinforcement
Learning using the RNN





Each “neuron” corresponds
to the choice of an output
link in the node
Fully Recurrent Random
Neural Network with
Excitatory and Inhibitory
Weights
Weights are updated with RL
Existence and Uniqueness of
solution is guaranteed
Decision is made by
selecting the outgoing link
which corresponds to the
neuron whose excitation
probability is largest
Reinforcement Learning in CPN

The decision threshold is the Most Recent
Historical Value of the Reward
Tl  aT l 1  (1  a ) R l , R  G
Recent Reward Rl
If

w (i , j )
then
T
 R
1

l 1
l
w

(i, k )

w

w


(i, j )

(i , k )

Rl
Rl
n
else
w
w


(i , k )  w

(i , j )  w

(i , k ) 

, k
j
2
Rl
n  2
(i , j )  Rl

,k  j

Re-normalize all weights
n
ri 
*
 [ w ( i , m )  w ( i , m )]


1
w

(i, j )  w

(i , j )
ri
ri
w

(i , j )  w

(i , j )
ri
ri


*
*
Compute q = (q1, … , qn) from the fixed-point
Select Decision k such that qk > qi , i=1, …, n
Test-Bed Measurements
On-Line Route Discovery by Smart Packets
Route Adaptation without Obstructing Traffic
Packet Round-Trip Delay with Saturating
Obstructing Traffic at Count 30
Route Adaptation with Saturating
Obstructing Traffic at Count 30
Packet Round-Trip Delay with Link Failure at Count 40
Path Tags with Link Failure at Count 40
Average Round-Trip Packet Delay
VS
Percentage of Smart Packets
SP
All
DP
QoS vs Route Switching
Average delay of each user is computed individually, and the median is
plotted in the graph: Error bars indicate the 1st and 3rd quartile
Frequency of Oscillations vs Route
Switching
Undesirable Effect of Route Switching:
Packet Loss due to De-sequencing
The rate at which packets are dropped at the reordering
(resequencing) buffer increases with the switching probability
A QoS Driven Application
Voice over CPN
Fig. 1. Voice over CPN
Experimental Results
Voice over CPN
Fig. 4
Experimental Results
Voice over CPN
Fig. 6 : Average roundtrip delay (left) and jitter (right) for user payload when only DPs are
allowed to carry user payload
Experimental Results: Voice over CPN
Packet desequencing Probability at Receiver vs Packet Rate
Fig. 7. Probability of packet desequencing perceived by the receiver side
CPN for Traffic Engineering
Other experiments

CPN routing algorithm is used to conduct
experiments using different QoS goals:
◦ Delay [Algorithm-D]
◦ Hop count [Algorithm-H]
◦ Combination of delay and hop [Algorithm-HD]
Average path length for each algorithm
 The route usage under different traffic
rates

◦ Low Traffic Rate (LTR)
 100 packets/second
◦ Medium Traffic Rate (MTR)
 500 packets/second
◦ High Traffic Rate (HTR)
 1000 packets/second

The forward delay of each algorithm with
different background traffic is also
reported
Average path length with different
levels of background traffic
H-Algorithm Route usage with Low TR


25 routes are discovered and one of them is the
shortest path
Above 90% of DPs use this shortest path
H-Algorithm Route usage: Medium TR


20 routes are discovered and 4 of them are
the shortest path
Above 85% of DPs use these 4 shortest paths
H-Algorithm Route usage: High TR


12 routes are discovered and 4 of them are the
shortest path
Only about 51% of DPs use these 4 shortest paths
Delay with different background traffic levels
Medium
None
High background traffic
Exploit an analogy between “genotypes”
and network paths
 The fitness of the individual is the QoS of
the path
 Selection function chooses paths for
reproduction based on the QoS of paths
 The genetic operation used to create new
individuals is crossover

Another extension:
Genetic Algorithms for CPN
Populations in CPN
No background
traffic
Delay
Loss
2.4Mb background
traffic
4.0Mb background
traffic
Delay
Loss
5.6Mb background
traffic
Wireless Power-Aware Adhoc
CPN Test-Bed
Denial of Service Protection using CPN
•
•
•
•
•
•
•
1996. Panix
1998. “Analyzer” attacks the Pentagon
2000. “Mafiaboy” attacks Amazon, Yahoo etc.
2001. Port of Houston
2002. 13 Root Servers
2003. American hackers attack Al Jazeera
2007 Attacks on Estonia’s e-Government and Financial Sector
What is a DoS Attack
An attack with the
purpose of
preventing
legitimate users
from using a specific
network resource
Is it a new threat?
1985, R.T. Morris writes:
“The weakness in the Internet Protocol is that the
source host itself fills in the IP source host id, and
there is no provision in TCP/IP to discover the true
origin of a packet” .. IP Spoofing
SYN Flood Attack
Distributed DoS
Issues that we have adressed

Detection

Response
◦
◦
◦
◦
Pattern detection
Anomaly detection
Hybrid detection
Third-party detection
◦
◦
◦
◦
Agent identification
Rate-limiting
Filtering
Reconfiguration
CPN DDoS Defence Scheme





The CPN architecture traces flows using smart
and ACK packets
A DoS produces QoS degradation
The user(s) and victim(s) detect the attack and
inform nodes upstream from the victim(s)
using ACK packets
These nodes drop possible DoS packets
The detection scheme is never perfect (false
alarms & detection failures)
Mathematical model
(1)
Analyses the impact of DDoS protection
on overall network performance
 Measures traffic rates in relation to
service rates and detection probabilities

Mathematical model
j 1
I n j , n  l n j , n  (( 1  L n l )( 1  f n l , n ))
n
n
l 1
j 1
I d j , d  l d j , d  (( 1  L d l )( 1  d d l , d ))
d
d
l 1
Li  
B i 1
Bi
i

1  i
1  i
 i  s i (  I i ,n (1  f i ,n )   I i ,d (1  d i , d ) )
n
n
d
d
Illustration on an Experimental CPN Test-Bed
Predictions of the Model
Impact on the nodes
(without Defence)
Impact of the Defence on the Nodes
Experiment
2.4GHz P4 PCs, Linux kernel 2.4.26,
CPN
 Different QoS protocols for normal and
attack traffic
 Delay-based FIFO queuing
 60 sec

Trace1 --- Attack Traffic
Averaged Likelihood
False Alarms: 2.8 %
Correct Detections: 88 %
Feedforward RNN
False Alarms: 11 %
Correct Detections: 96 %
Recurrent RNN
False Alarms: 11 %
Correct Detections: 96 %
Trace2 --- Attack Traffic
Averaged Likelihood
False Alarms: 0 %
Correct Detections: 76 %
Feedforward RNN
False Alarms: 8.3 %
Correct Detections: 84 %
Recurrent RNN
False Alarms: 2.8 %
Correct Detections: 80 %
Stable Networks in the Presence of Failures: Initial Results
• A node failure is emulated by disabling some or all of the Ethernet interfaces of a
node (so that no traffic will be able to go through that node, just like in a real breakdown
of a machine) and is restored by re-enabling all the interfaces.
• Failures are considered to be similar to worm attacks and their spread is modelled
according to the AAWP (Analytical Active Worm Propagation) model. This is a discretetime and continuous state deterministic approximation model, proposed by Chen et al.
[1] to model the spread of active worms that employ random scanning.
• The AAWP is a discrete time model which is more realistic, since a node must be
completely infected before it starts infecting other node, so that the speed of the spread
is connected to the number of nodes that can be infected.
• AAWP uses the random scanning mechanism in which it is assumed that every nodes
is just as likely to infect or be infected by others. Other scanning mechanisms can be
used, such as local subnet, permutation and topological scanning.
Current Experiments
DoS on a streaming video
Math. Analysis, Simulation and Experiment
Comparison
http://san.ee.ic.ac.uk