Principle of Autonomous Decentralized Flow Control and Layered Structure of
Network Control with Respect to Time Scales
Masaki Aida

Chisa Takano

NTT Information Sharing Platform Laboratories
NTT Corporation
Musashino-shi 180-8585, Japanaida@m.ieice.org

Traffic Engineering Division
NTT Advanced Technology Corporation
2-4-15, Naka-cho, Musashino-shi 180-0006, Japanchisa@m.ieice.org

1 Introduction
Network control mechanisms in networks can be categorized by the time scales on which an individual control takes
effect and they form a layered structure with respect to thetime scales. In high-speed networks, the processing speedof each node is high but the propagation delay is the same as
in slower networks, because it is constrained by the speedof light. So, the framework of network control on a shorttime scale should be an autonomous decentralized system[1]. We have proposed an autonomous decentralized flow
control mechanism applicable to high-speed networks [2],and have investigated its stability and adaptability to dynamic network state [3]. In this article, to clarify the aim of
our flow control mechanism, we show supplemental explanations from the following three points of view:• Layered structure of network control with respect totime scale and the inevitability of autonomous decentralized control on a short time scale.
• The relationship between local decision making at anode and the performance of the whole network, inorder to achieve high global performance as a micromacro link.
• The principle of our flow control derived from the efficient framework of parallel computing as an actual
approach to realize appropriate global performance bycontrolling local decision making.

2 Layered Structure of Network Control andTime Sensitive Control in High-Speed Networks
Every packet in a network is either in a node or on alink. In high-speed networks, many packets are on links
compared with in nodes. Since the packets currently stored
in nodes are not being transmitted over the network, it isnecessary to maximize the number of packets on links inorder to realize high performance of the whole network.
However, the only packets we can control are those stored
in nodes. Thus, higher performance of the whole network
involves many uncontrollable packets being propagated onlinks. Therefore, inappropriate flow control cannot produce
a state that has high performance and stability.
Individual control mechanisms work well on their appropriate time scales and they cooperate with each other. For
example, increasing the link capacity and routing fall on thelong and medium time scales, respectively. Window flow
control such as TCP acts on the time scale of the round-trip
delay. In high-speed networks, since a lot of packets are being propagated on links, control delay greatly affects on theperformance. The centralized control cannot collect information about the whole network immediately. Since timesensitive control must take effect immediately, its framework is inevitably an autonomous decentralized system.
Figure 1 shows a sequence of human behavior as an analogy. When an accident occurs, we immediately act. Thisaction is time-sensitive and is achieved by a spinal reflex.
After that, essential treatment is performed through cerebration on a relatively long time scale. The aim of our control[2, 3] is to take immediate effect by autonomous decentralized control. The centralized control is effective on relatively long time scales and is compatible with our control in
the layered structure.

3 Micro-Macro Link in the Framework ofAutonomous Decentralized Flow Control
There are phenomena in nature where local interactions
on the micro scale produce symmetry on the macro scale.
For example, local interactions among water molecules leadto highly symmetrical snow flakes. By applying this mechanism, although time-sensitive control on a short time scale
can not use global information about the network, we may
be able to control the global performance through local decision making at the nodes. This framework is not always

Accident(emergency!)

Emergency measure(spinal reflex)

Medical treatment(after cerebration)

Figure 1. Layered structure of behaviors with respect to time scales
required to work effectively on a long time scale, but itshould be effective until control on a longer time scales
takes effect.
In the framework of our control [2, 3], we desire that
global performance is indirectly controlled immediately by
the predefined rule for local decision making at nodes.
Nodes at distant locations do not communicate with eachother. So, in spite of the constraint of light speed, appropriate global performance is achieved quickly. Since thecentralized control cannot achieve the performance quickly
due to the constraint of light speed, our control seems totake effect faster than the speed of light.

4 Principle of Autonomous Decentralized
Flow Control
The actual way of achieving our control mechanism issimilar to parallel computing. A typical case where parallel computing is effective is solving temporal evolution
equations of a wave or fluid which are based on local interaction, e.g., the Navier-Stokes, wave, and diffusion equations. They have the feature that the temporal evolution ofthe state at a certain point is determined only by the states atthe point and the neighborhood. Parallel computing is effective for this type of calculation because each computer cancalculate by exchanging only neighborhood information. Inaddition, the solutions of the above equations behave orderly on the macro scale. On the other hand, for the temporal evolution equations including nonlocal interactions, e.g.,
the many body problem with long-range potential, temporal evolution of the state at a certain point requires globalinformation. So, parallel computing is not good at this typeof calculation.
In our framework, by designing the appropriate local interactions as a rule of decision making at nodes, we get
the flow control mechanism to work effectively as an autonomous decentralized system. The performance of thewhole network becomes the solution of a certain temporal
evolution equation.
Our flow control [2, 3] is based on the diffusion-type
equation and we expect the congestion in the network tobe restored with time, like diffusion phenomena. Although
the behavior of each node obeys a predefined rule and its
decision is based only on local information, we can expect

the performance of the whole network to exhibit an orderlyproperty.
We show an example in a continuous approximation forsimplicity. The packet flow J(x, t) in our framework iswritten as∂n(x, t),(1)
J(x, t) = α r(x, t) − Di∂xwhere r(x, t) and n(x, t) denote the drift component of theflow and the number of packets, at position x and time t, respectively, and α and Di are constants. When each node
handles the flow, the node requires only the information
at x and its neighborhood. So, autonomous decentralized
control applies effectively to this framework. The temporalevolution of the number of packets at x is written as∂r(x, t)∂ 2 n(x, t)∂n(x, t)= −α+ Di.
(2)
∂t
∂x
∂x2
This is a diffusion-type equation and it will lead to the diffusion phenomena with respect to the number of packets.

5 Concluding Remarks
This article has shown the aims of our autonomous decentralized flow control from three different points of view.
The diffusion-type flow control we proposed exhibits appropriate performance as shown in our previous studies. Inaddition, our current results show that shortening the control delay and applying the control to an asymmetric network are probably possible if we choose appropriate valuesof α and Di . In future, we will investigate an appropriate
way to determine the values of α and Di .

References[1] M. Aida and K. Horikawa. Stability analysis for global performance of flow control in high-speed networks based on
statistical physics. IEICE Transactions on Communications,
E82-B(12):2095–2106, December 1999.
[2] M. Aida and C. Takano. Stability of autonomous decentralized flow control schemes in high-speed networks. In Proc.
of IEEE ICDCS 2002 Workshop (ADSN 2002), pages 63–68,2002.
[3] C. Takano and M. Aida. Stability and adaptability of autonomous decentralized flow control schemes in high-speed
networks. In Proc. of ISADS 2003, 2003.