Transcript ATM based Multiservice and Multimedia Information Networking

Fuzzy logic based congestion control
Andreas Pitsillides,
Department of Computer
Science
University of Cyprus
Ahmet Sekercioglu,
Department of Informatics
Swinburne University of
Technology
Andreas Pitsillides, Department of Computer Science, University of Cyprus
1
Congestion control problem

Generally accepted that
 network congestion control remains critical issue and high priority,
especially given growing size, demand, and speed (bandwidth) of the
increasingly integrated services networks.

Despite research efforts spanning few decades and large number of
different schemes proposed,
 no universally acceptable control solutions in “fight” against congestion (a
control strategy, a control system, or a “package” of control solutions).

Current solutions in existing networks
 increasingly becoming ineffective, and
 generally accepted that these cannot easily scale up – even with various
proposed “fixes”.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
2
congestion

Definition
 network state in which performance degrades due to saturation of network
resources, (communication links, network switches, processor cycles, and
memory buffers).
 E.g. if communication link delivers packets to queue at higher rate than its service rate,
then size of queue grows. If queue space finite then in addition to delay, losses occur

Control
 refers to set of actions taken by network to minimise intensity, spread, and
duration of congestion.

optimal control of networks of queues
 well-known, much studied, and notoriously difficult problem, even for simplest of
cases. E.g. Papathemetriou and Tsitsiklis show problem of optimally controlling
simple network of queues with simple arrival and service distributions and multiple
customer classes is complete for exponential time (i.e. provably intractable).
Andreas Pitsillides, Department of Computer Science, University of Cyprus
3
Congestion control

effect of network congestion is degradation in the network performance.
 user experiences long delays in delivery of messages, perhaps with heavy losses
caused by buffer overflows.
 Thus degradation in quality of delivered service, with need for retransmissions of
packets (for services intolerant to loss). In event of retransmissions, drop in
throughput, eventually leading to network throughput collapse.

Congestion is a complex process to define.
 felt by degradation of performance.
 loss, delay and throughput deterioration good indicators of congestion.

A “good” congestion control system should be preventive, if possible.
Otherwise should react quickly and minimise spread of congestion and its
duration.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
4
Congestion can be sensed (or predicted) by:

packet loss
 sensed by the queue as an overflow,
 sensed by destination (through sequence number) and acknowledged to a user,
 sensed by sender due to lack of acknowledgment (timeout mechanism) to indicate loss

packet delay
 can be inferred by the queue size,
 observed by destination and acknowledged to user (e.g. with time stamps in packet headers)
 observed by sender, e.g. by packet probe to measure Round Trip Time (RTT)

loss of throughput
 observed by the sender queue size(waiting time in queue)

other calculated or observed event through which congestion can be inferred
 increased network queue length and its growth
 calculated from measured data, e.g queue inflow and its effect on future queue behaviour.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
5
potential problems of control:








Large scale
Distributed nature
Large geographic spread (at its limit it covers globe)
Increasingly processing delay at nodes gets smaller, in comparison to
propagation delay in links. Large-bandwidth delay product makes
control of congestion through feedback potentially difficult
Diverse nature and behaviour of carried traffic (voice, video, www, ftp,
e-mail, ….)
Unpredictable and time varying user behaviour
Lack of appropriate dynamic models for control
Expectation of the need for guaranteed levels of performance to each
user, which can be negotiated with the network
Andreas Pitsillides, Department of Computer Science, University of Cyprus
6
(lack of) modelling of network system


To design control system necessary to model input and output cause and
effect of system.
difficulty of deriving such model
» Several factors affect model, and some are time varying. Take model of traffic
behaviour as example:
– diverse user (human) behavior affects way traffic is generated (can be time varying and
different for different humans, even for same interactive services).
– inherent fuzzines, e.g, in


definition of “contract” between user and network and its policing,
in the controls (declared objectives of controls and observed behaviour of the system).
– Data generation, organisation and retrieval (long range dependance shown for both source
generation, as well as storage of data)
– Traffic aggregation process is a very complex one—studies suggest self-similarity preserved
under variety of network operations and network conditions
– Network controls (speculation that fractal features in network traffic remain even after network
controls).
– Network evolution (self-similarity appears robust to network changes, eg. upgrades).
Andreas Pitsillides, Department of Computer Science, University of Cyprus
7
control theoretic concepts

Making use of control theoretic concepts has potential benefits,
including:
» Simpler an/or more effective algorithms with more predictable properties.
» Better understanding of performance of controlled system (including
dynamic behaviour).
» Better understanding of existing non-linear algorithms, including need for
any fixes (“jacketing software”).
» Better analysis techniques for large systems of interacting algorithms.

A major difficulty in control system design is to reconcile the largescale, fuzzy, real problems with the simple well-define problems that
control theory can typically handle
» good understanding of fundamental control theory (which can be
sophisticated and complex), as well as deep understanding of system
under control (not necessarily in form of accurate mathematical model).
Andreas Pitsillides, Department of Computer Science, University of Cyprus
8
Existing approaches to congestion control and
trends

For historical reasons, and due to fundamental philosophical differences
earlier approach to congestion control, differed between TCP/IP and ATM
» However some convergence between classical TCP/IP and ATM approach
evident, (RFC2309, RFC2481, ATM Forum).

become clear that existing TCP congestion avoidance mechanisms
(RFC2001), while necessary and powerful, not sufficient.
» Basically, there is a limit as to how much control can be accomplished from
edges of network
» Some mechanisms needed in routers to complement endpoint congestion
avoidance mechanisms. (Need for gateway control realised early; e.g. see
[Jacobson, 1988], where for future work gateway side advocated as necessary).

Evolutionary, for TCP/IP and ATM we see
» progressive shift of controls from edges of network (initially open loop then edge
binary feedback) to inside network. Feedback also shifting from implicit to
explicit, from pure binary to multivalued and explicit.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
9
Network controls

network system
» large distributed complex system, with difficult often highly non-linear, time varying
and chaotic behaviour.
» inherent fuzziness in definition of controls (declared objectives and observed
behaviour).
» Dynamic or static modelling of such system for (open or closed loop) control is
extremely complex.
» Measurements on the state of the network are incomplete, often relatively poor and
time delayed.
» Its sheer numerical size and geographic spread are mind-boggling. E.g. customers
(active services) in 10s of millions, network elements in 100s of million, and global
coverage.

Computational intelligence to handle complexity and fuzziness
present in network system surely has an essential role to play here.
We should exploit tolerance for imprecision and uncertainty to achieve
tractability, robustness and low cost
Andreas Pitsillides, Department of Computer Science, University of Cyprus
10
Computational Intelligence (CI)

area of fundamental and applied research involving numerical information
processing (in contrast to symbolic information processing techniques of
Artificial Intelligence (AI)).
» Nowadays, CI research is very active and consequently its applications are
appearing in some end user products.

definition of CI can be given indirectly by observing the exhibited properties of
a system that employs CI components:
– “A system is computationally intelligent when it: deals only with numerical
(low-level) data, has a pattern recognition component, and does not use
knowledge in the AI sense; and additionally, when it (begins to) exhibit
 computational adaptivity;
 computational fault tolerance;
 speed approaching human-like turnaround;
 error rates that approximate human performance.
» The major building blocks of CI are artificial neural networks, fuzzy logic, and
evolutionary computation.”
Andreas Pitsillides, Department of Computer Science, University of Cyprus
11
Fuzzy Explicit Rate Marking (FERM) for
congestion control

Basic idea:
» measure queue length and queue growth rates (hence providing
rudimentary prediction of future behaviour) at the output buffer of a switch,
» calculate and send explicit rate control signals to traffic sources to avoid
or alleviate congestion.
» explicit rate control signals calculated periodically by fuzzy inference
engines located in switches, and sent to traffic sources in resource
management (RM) cells.

analyzed and compared performance of FERM with EPRCA in detail
regarding fairness, responsiveness, resource utilization and cell loss
in LAN and WAN environments. FERM has been further refined
(FERM2) and as an adaptive scheme which has self tuning
capabilities (A-FERM).
Andreas Pitsillides, Department of Computer Science, University of Cyprus
12
FERM2 explicit rate congestion control
scheme
Note: desired queue length is explicit, can be set by a higher level control module
to provide more dynamic resource utilization across switches utilised by VC
Andreas Pitsillides, Department of Computer Science, University of Cyprus
13
FERM 2 Operation

Overall operation compliant with ATM Forum Traffic Management
Specification, Version 4.
 Source Cell rates adjusted by Explicit Rate (ER) carried by RM cells.
 RM cells periodically generated by traffic sources, transmitted towards
destination end systems, and initial ER information is set by the ICR.
 Destination end systems bounce RM cells back to sources.
 During return path, when RM cell passes through ATM switch, its ER
value is examined and possibly modified.
 Data source, upon receiving RM cell, adjust cell rate = ER. If ER>PCR,
cell rate=PCR. Similarly, cell rate=MCR if ER<MCR.
 ER provided to all active VCs at all time so congestion and undesired
resulting behavior can be avoided.
 does not need to keep state of current VC connections sharing switch.
 Periodical ER calculations are performed by the Fuzzy Congestion
Controllers (FCCs) located in each ATM switch.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
14
implementation of FCC

Chosen most widely used and computationally lighter methods, which
are
 singleton fuzzification
 t-norm algebraic product for the mathematical representation of the
connective “and”
 Larsen's product rule of implication
 sup-product compositional rule of inference
 weighted mean of maximums defuzzification.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
15
Control surface
if queue length and queue then flow rate
too short decreasing fast
increase sharply
``
``
slowly
`` moderately
``
not changing
``
``
``
increasing slowly decrease moderately
``
``
fast
``
``
acceptable decreasing fast
increase moderately
``
``
slowly
``
``
``
not changing
no change
``
increasing slowly decrease moderately
``
increasing fast
``
``
too high decreasing fast
no change
``
``
slowly
``
``
not changing
decrease moderately
``
increasing slowly
``
sharply
``
``
fast
``
``
Set of linguistic rules defining the control surface of the FCC
Andreas Pitsillides, Department of Computer Science, University of Cyprus
16
network model for performance analysis:
simulation of ATM WAN (1500 km between switches)
backbone and LAN backbone (10 km)
Real time sources
ABR sources
3-hop
10/1500 km
ABR sources
1-hop
Andreas Pitsillides, Department of Computer Science, University of Cyprus
17
simulated ATM LAN under FERM2 congestion control:
average end-to-end ABR cell delay vs. useful throughput
Andreas Pitsillides, Department of Computer Science, University of Cyprus
18
simulated ATM WAN under FERM2 congestion control:
average end-to-end ABR cell delay vs. useful throughput
Andreas Pitsillides, Department of Computer Science, University of Cyprus
19
Time evolution of Explicit Rate for case of LAN;
calculated by the FCC
Andreas Pitsillides, Department of Computer Science, University of Cyprus
20
Time evolution of the queue length for the case of a LAN.
Note that the reference value set at 400 cell places.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
21
Time evolution of Explicit Rate for the case of the WAN;
calculated by the FCC
Andreas Pitsillides, Department of Computer Science, University of Cyprus
22
Time evolution of the queue length for the case of a WAN.
Note that the reference value is set at 400 cell places.
Andreas Pitsillides, Department of Computer Science, University of Cyprus
23
Conclusions and recommendations

congestion control in communication networks is a real challenge,
especially supporting video, voice and data applications simultaneously.
» Computational Intelligence techniques expected to play central role, especially in
large scale, geographically distributed network systems. Hybrids also expected to
supplement these techniques and prove useful, especially in optimising overall
network objectives.

challenges include:
 Agreement on structured approach to congestion control for network. Control
theoretic concepts and techniques have essential role to play.
 Engineer network system with network control system together in order to add
another degree of flexibility.
 Theoretical advances in handling large scale complex systems are required,
including decomposition and organisation of controls.
 Globally optimise overall network objectives.
 Agreement in common simulative framework and common test bed framework
for testing congestion control algorithms
Andreas Pitsillides, Department of Computer Science, University of Cyprus
24