Notes
Slide Show
Outline
1
Admission Control in
Self-Aware Networks
  • Georgia Sakellari
  • Prof. Erol Gelenbe
  • Dr. Maurizio D’Arienzo
2
Admission Control

  • 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
QoS Service Levels
  • 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
Existing network QoS solutions

  • Frame Relay


  • Integrated Service (IntServ)


  • Differentiated Service (DiffServ)


  • Asynchronous Transfer Mode (ATM)


  • MultiProtocol Label Switching (MPLS)


  • Cognitive Packet Network (CPN)
5
Existing internet QoS protocols
  • 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
Existing internet QoS protocols
  • 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
Types of AC
  • 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
The proposed AC algorithm (1/5)

  • 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 proposed AC algorithm (2/5)

  • 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
The proposed AC algorithm (3/5)
  • 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
The proposed AC algorithm(4/5)
  • 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
The proposed AC algorithm(5/5)
  • 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
Computing the QoS matrices
  • 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
Generalisation of the Floyd-Warshall algorithm to non-additive QoS metrics

  • 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
Experiments – Probing Stage

  • 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
Experiments – Decision Stage
  • 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
Open issues

    • How long to probe?

    • What rate to probe at?

    • 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"
  • Thank you


  • http://san.ee.ic.ac.uk/