1
|
- Georgia Sakellari
- Prof. Erol Gelenbe
- Dr. Maurizio D’Arienzo
|
2
|
- Admission control is the process which determines whether a connection
request in a network should be accepted or rejected.
- AC estimates the level of QoS that a new user session will need, checks
whether there are enough resources to service that session and the
affect that the entrance of the new session will have in the existing
ones.
- AC decides whether it should accept the new client or not by
characterizing the requirements of the new flow and estimating the
network’s state after it is admitted.
- Contributes to sustaining QoS
|
3
|
- A network’s capability to deliver the service requested by a client can
be characterised according to the end-to-end QoS strictness as:
- Best-effort service or “lack of QoS” (basic connectivity with no
guarantees).
- Differentiated service or “qualitative QoS” or “soft QoS” (some traffic
is treated better than the rest, and service is provided by
distinguishing different classes of traffic).
- Guaranteed service also known as “quantitative QoS” or “hard QoS”
(absolute reservation of network resources and cannot tolerate any
violation of QoS guarantees).
|
4
|
- Frame Relay
- Integrated Service (IntServ)
- Differentiated Service (DiffServ)
- Asynchronous Transfer Mode (ATM)
- MultiProtocol Label Switching (MPLS)
- Cognitive Packet Network (CPN)
|
5
|
- Cognitive Packet Network (CPN)
- Packet routing protocol which addresses QoS using adaptive techniques
based on on-line measurements.
- The users declare their QoS requirements (QoS Goals) such as minimum
delay, maximum bandwidth, minimum cost, etc.
- Three types of packets:
- smart packets (SP) for discovery,
- source routed dumb packets (DP) to carry payload, and
- acknowledgements (ACK) to bring back information that has been
discovered by SPs which are used in nodes to train neural networks.
- SPs discover routes by using random neural networks (RNN) with
reinforcement learning (RL).
- All packets have a life-time constraint based on the number of nodes
visited, to avoid overburdening the system with unsuccessful requests
or packets which are in effect lost.
- A node in the CPN acts as a storage area for packets and mailboxes
(MBs). It also stores and executes the code used to route smart
packets.
|
6
|
- Cognitive Packet Network (CPN) (continued)
- The decisional weights of a RNN are increased or decreased based on the
observed success or failure of subsequent SPs to achieve the Goal.
- Given a goal G, reward R is: R = 1/G and RNN weights updates are based
on a threshold T:
- where Rk, k = 1, 2, ... are successive measured values of
reward R and α is some constant (0 < α < 1) that is
used to tune the responsiveness of the algorithm: for instance α =
0.8 means that on the average five past values of R are being taken
into account.
- Neurons are rewarded or punished based on the difference between Rk,
the current reward, and Tk-1, the last
threshold.
- In CPN QoS metrics can be combined, e.g. the hop count metric can be
combined with the forward delay, so that the goal takes into account
both the length H and the delay D of the path.
|
7
|
- Parameter based AC
- Estimates the amount of network resources required to support the
entrance of new flows given a priori flow characteristics (user
specified connection's parameters).
- Parameter-based AC algorithms can be further classified as:
- Non-statistical
- Statistical
- Equivalent Bandwidth, Diffusion based statistical CAC
- Measurement based AC
- Relies on measurements of actual traffic load in making admission
decisions.
- It has no prior knowledge of the traffic statistics and makes admission
decisions based only on the current network state.
- Endpoint Admission Control
|
8
|
- We propose a measurement-based AC algorithm that constantly gathers data
on the ongoing users QoS in the network by exploiting the network’s Self
Awareness. This data is available in one or more locations in the
network where the decision is taken.
- This does not require any special mechanism since the CPN already
collects QoS information on all links and paths that the SPs have
explored and on all paths that any user is using in the network.
- It is a multiple criterion AC algorithm in which the QoS criteria are
specified by the user.
|
9
|
- The AC decision of our proposed scheme consists of two stages.
- Probing stage
- The AC estimates the impact of the new flow by probing the network.
- Decision stage
- The AC searches whether there is a feasible path which can accommodate
the new call by considering the impact of that new flow on the network
without affecting the quality of formerly accepted flows.
|
10
|
- Probing Stage – Estimation of the impact of a new flow
- Every QoS metric can be considered as a value which increases as the
“traffic load” increases. The addition of a new connection will
increase the load of the paths it may be using, and therefore it is
assumed that the value taken by the QoS metrics will increase.
- Let us consider some link (i,j). A small increase x in the load that is
obtained in a controlled manner, generates an estimate of the manner in
which the QoS metric q varies around the current load point Y.
- The impact of a new flow with total traffic rate X can then be
evaluated by using the measured derivative without having to know the
initial load Y.
|
11
|
- Decision Stage
- Consider the network graph G(N,E) with nodes N, n=|N|, and the set E of
directional links (i,j), where i,j Є N.
- The CPN algorithm explores G(N,E) and collects QoS data about the parts
of the network that are being currently used, or which have been
explored by SPs. This data is available in one or more locations in the
form of nxn link QoS matrices Qv with elements:
- Qv(i,j)=r where r≥0 is a real number representing the
QoS of link (i,j) which has been measured at some recent enough time,
and
- Qv(i,j)=unknown if a SP has not explored the link for QoS
metric v or if this happened so long ago that the value could be
inaccurate.
- From the link matrices Qv we can compute:
- The set of known (explored) paths P(i,j) from i to j, and
- The path QoS matrices Kv, where Kv(i,j) is the
known best value of the QoS metric v for any path going from i to j if
such a path exists and if the links on the path have known entries in
the link QoS matrices. Other entries in Kv are set to the
value unknown.
|
12
|
- Let u be a new user requesting admission for a connection from source s
to destination d carrying a traffic rate X and with QoS constraint qv(u).
Suppose also that the network is currently carrying other users z, any
one of which will be generically represented by some QoS constraint qw(z).
- Find the set of known paths P(s,d). If it is empty, send SPs to
discover paths. If unsuccessful, reject the request. Otherwise send
probe traffic at rate x along the network.
- Use the probe traffic to obtain for each QoS metric w
of interest, including w=v, and for all concerned links (i,j). Some
links will not be concerned by the probe traffic so for that links we
take .
- Then compute
for all concerned links and all QoS metrics. For unconcerned
links we take .
- Compute from (to be detailed below) for all
the QoS metrics of interest, including v.
- If
for all other current users z with source-destination pair (s',d')
and QoS metric qv, then accept u; else reject the request.
|
13
|
- The well known ``Warshall's algorithm'‘ determines for each i, j ⊂
N whether there is a path from node i to node j by computing a Boolean
matrix, the transitive closure of the graph's adjacency matrix, in less
than n3 Boolean operations.
- or
- Floyd's algorithm extends Warshall's algorithm to obtain the cost of the
``smallest cost path'' between any pair of vertices in the form of a
real-valued matrix.
- or
- If the QoS metric is additive then we can use the Floyd-Warshall
algorithm to get the smallest value of the QoS metric among all known
paths from any node i to any node j.
- For non-additive metrics we have developed a generalisation of the
Floyd-Warshall, which is described next.
|
14
|
- Consider the matrix Qv, whose entries are the measured QoS
values r≥0 over links (i,j) whenever such a link exists, or
otherwise have an initial value, e.g. +∞ for delay and variance or
0 for bandwidth.
- The matrix Kv provides us with the ``best QoS value'' for
every path between every pair of vertices (i,j).
- or
- Where the operator between
two real valued matrices B, C is defined as
- The operator between two
QoS parameters depends on the QoS metric that is being considered and
can be the addition (+) for delay and variance, the minimum (min) for
bandwidth etc. The is also
an operator that depends on the specific QoS metric q, and selects the
``best value'' among the elements on which it operates, e.g. in case of
the delay, loss or variance metric it will obtain the minimum value,
while for bandwidth it will select the maximum value, for all paths
going from i to j.
|
15
|
- One request is generated from node S1 (with destination D1) every 30sec,
it is always accepted and then it stays at the network until the end of
the experiment.
- The rate of each new flow is 1Mbps.
- The probe packets were sent with rate 10% to 100% of the requested rate.
- Every combination was repeated 5 times and the values presented in the
graphs are the average values of those repeats for each case.
- 2000 experiments, 50 sec each
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
|
21
|
|
22
|
- Network monitoring by exploiting the existing CPN capabilities of
keeping online measurements.
- Current QoS metrics: avg delay, jitter, loss rate, and the available
bandwidth.
- Requested Delay=120 μsec.
- Requested Jitter=25 μsec.
- Requested Loss Rate=5%.
- Requested path bandwidth=10Mbps.
- Data are collected every 20 seconds.
- Duration of an accepted call=150sec.
- Rate of an accepted call=10 Mbps.
- After making a request then the user will wait for a random time W and
then make a request again. W is chosen to be uniformly distributed in a
range of values which is [0,120] seconds, [0,90] seconds, and [0,70]
seconds. Thus the load on the system is increased in each of the
successive experiments.
|
23
|
|
24
|
|
25
|
|
26
|
- Would our scheme work if more than one calls are requesting admission
at exactly the same time?
- How can we maximise the number of the accepted users by using all the
available resources of the network as best as possible (reorganising
the existing users, resource management).
|
27
|
- Thank you
- http://san.ee.ic.ac.uk/
|