Research on
Layered Models of
Network Control Mechanisms
with Respect toTime Scales of Their Operations
Masaki Aida
Tokyo Metrolopitan University

December 5, 2009

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20091 / 20Introduction

Background of My Research• Information networks are required to be highly reliable as social
infrastructure.
• On the other hand, in larger-scale and/or higher-speed networks, it
is difficult to control the networks by collecting detailed information ofwhole networks.
• To solve this problem, we consider a layered model of NW control
mechanisms with respect to time-scales of control operations.
Its characteristics are:Simplicity of control, simplicity of NW design. (We want to make asystem which is controllable by human intellect)
The layers are loosely coupled, details in a layer does not strongly affectto other layers.
Action in a layer is autonomously determined in its time scale.
Consider from clean slate.
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20092 / 20Introduction

Example of Layered Model w.r.t Time Scales

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20093 / 20Introduction

Three Main Issues in Our First Step

To clarify the principle of NW control that has layered structure withrespect to the time scales, we start from the following issues:• Framework of autonomous decentralized control as operations ofeach layer.
• Performance evaluation model describing interaction betweenlayers. In particular, we consider quasi-static approach for analyzing
interactions between networks and users based on decomposition oftimescales (like a non-equilibrium statistical physics).
• Analyses of structure of social networks and user dynamics. And
feedback of them to network design.

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20094 / 20Structure of Social NWs and User Dynamics

Structure of Social Networks andUser Dynamics
Revealed by Communication Services

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20095 / 20Structure of Social NWs and User Dynamics

Introduction

Strategy of Our Analysis• Nobody can observe the true social networks directly.
• Different aspects of the social network are observed throughdifferent services. They are partial information of the true socialnetworks.
• We construct a self-consistent model of the true social networks thatis behind each service.
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20096 / 20Structure of Social NWs and User Dynamics

Power Laws Appeared in Communication Services# of i-mode Users v.s. Volume of Traffic

Web traffic

E-mail traffic

At the initial stage of i-mode service, the volume of web traffic of i-mode is
proportional to the number of i-mode users n. On the other hand, the volumeof e-mail traffic of i-mode is proportional to n1+↵ , where ↵ ' 2/3．
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20097 / 20Structure of Social NWs and User Dynamics

Analysis of i-mode & mixi Data

Volume of e-mail Traffic and Human Relations

web traffice-mail traffic• If the volume of traffic per user is invariant, then the volume of e-mailtraffic should be proportional to n.
• The fact that email traffic is proportional to n1+↵ (↵ ' 2/3) suggeststhat the number of friends in i-mode users increases.
• Therefore, ↵ ' 2/3 tells us something about the strength of humanrelations in social networks.
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20098 / 20Structure of Social NWs and User Dynamics

Analysis of i-mode & mixi Data

Results from i-mode & mixi
From analyses of i-mode and mixi services, the social networks havethe following properties:• As the characteristic of node degree, the social networks are
scale-free networks and their degree distribution satisfies p(k) / kwith=11↵(1)+ 1 ' 4.

• As a topological characteristic of the social networks, a certain
opportunity of links connecting two nodes is not biased by nodedegree.
• As a characteristic of user dynamics, users tend to join popularservices in descending order of node degree.

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 20099 / 20Structure of Social NWs and User Dynamics

Verification of Degree Distribution

Degree Distribution of KDDI’s Cellular Phone

area 1

area ２

area ３area ４area ５area ６
Degree distribution of KDDI’s cellular phone service.

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200910 / 20

Framework of Autonomous Decentralized Control Based

Framework ofAutonomous Decentralized Control
Based on Local Interaction Model

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200911 / 20

Framework of Autonomous Decentralized Control Based

Framework of Our Autonomous Decentralized Control

Diffusion Phenomena(as an Example of Local Interaction Model)• Let us heat a point on a cold iron bar at a moment.

• Heat diffuses to the entire iron bar, and the temperature distribution
is smoothed.
• The temperature distribution exhibits orderly behavior even thougheach point interacts only with its neighborhood by the predefinedrule.
) A sort of Autonomous Decentralized Control.
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200912 / 20

Framework of Autonomous Decentralized Control Based

Framework of Our Autonomous Decentralized Control

Local Interaction Model & Autonomous
Decentralized Control• Let p(x, t) be the density function of heat at position x and time t.
• In diffusion, heat flow J(x, t) is given byJ(x, t) =@p(x, t),@x(2)where  is a positive constant.
• The temporal evolution equation of p(x, t) is the diffusion equation,@p(x, t)@ 2 p(x, t)
=.
@t
@x2

(3)

• Local action of J(x, t) at each point reproduces the orderly behaviorof p(x, t).
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200913 / 20

Framework of Autonomous Decentralized Control Based

Framework of Our Autonomous Decentralized Control

Recipe of Our Autonomous Decentralized Control
The recipe of the framework of autonomous decentralized control
based on local interaction theory is summarized as follows [1]:• Let us think about a behavior of state that the whole system have tohave. And then let us find the partial differential equation that has
the solution that provides such a behavior ((3) corresponds).
• Let us identify the local interaction that the partial differential
equation describes ((2) corresponds). And then we design thebehavior of subsystem as the local interaction.
• As a result, even though autonomous action of each subsystem isbased only on its local information that is available to it, the state of
the whole system exhibits the desired behavior as a solution of thedifferential equation.
The concept of our autonomous decentralized control is “By designing
the behavior of subsystems in a micro-scale properly, we indirectly
control the behavior of the whole system in a macro-scale”.
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200914 / 20

Framework of Autonomous Decentralized Control Based

Characrerustics of Diffusion-type Flow Control (DFC)

Temporal Evolution of the Number of Stored
Packets at Each Node• the horizontal axis denotes node IDs, and the vertical axis denotes
the number of packets stored in the node.
• Nodes mutually cooperate and avoid the congestion of packets.

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200915 / 20

Framework of Autonomous Decentralized Control Based

New Control Based on Renormalization Transformation

Feasibility of Other Type of Our Control• The aforementioned example is based on diffusion in order togenerate a smoothing effect. We would like to find other possibilities.
• In diffusion phenomena, the distribution is uniformized with time andapproaches the normal distribution independent of the initialdistribution.
• Let us consider a new type of control using this characteristic [4].

Asympototic behavior of diffusion phenomena

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200916 / 20

Framework of Autonomous Decentralized Control Based

New Control Based on Renormalization Transformation

Renormalization Transformation of Diffusion• We define the following distributionp2⌧q(x, t) :=pp2⌧

x, ⌧!

(4)

,

where is a positive constant, and ⌧ = t or e2ct .
• This distribution is obtained by scaling the x axis, along with thetemporal evolution. In other words, it is a sort of “renormalizationtransformation.”(consider behavior of state that the whole system have to have.)
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200917 / 20

Framework of Autonomous Decentralized Control Based

New Control Based on Renormalization Transformation

Autonomous Local Decision• The temporal evolution equation of q(x, t)✓◆
2@@
2 @q(x, t) = c 1 + x+q(x, t).
@t
@x
@x2

(5)

(find the partial differential equation.)• The flow Jq (x, t) is obtained as
Jq (x, t) =c x q(x, t)

c2@q(x, t).
@x(6)(identify the local interaction.)• Local action Jq (x, t) at each point can reproduce the orderly
distribution with a finite variance of 2 .
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200918 / 20

Framework of Autonomous Decentralized Control Based

New Control Based on Renormalization Transformation

Application to Domain Decomposition• Example of applications to domain decomposition for layered
structure of ad hoc NWs.
• Clusters are autonomously configured by autonomous action ofeach node.
Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200919 / 20

Summary

Summary and Future Study• We have shown issues in the layered architecture of the network
control according to the time scales.
• As a part of issues, we have shown the framework of autonomous
decentralized control based on local interaction model, and analysesof the structure of social networks.
• If I have chance to talk in this WS, I would like to discuss the residual
research, Quasi-Static Approach in a break-out session.
• In the future, the whole system of the layered architecture of NW
control mechanism with respect to the time scales should beclarified.

Masaki Aida (Tokyo Metrolopitan Univ.)

2nd NSF-NICT WS

December 5, 200920 / 20