Posts Tagged ‘QoS

Shortest Path Algorithm for Multicast Routing in Multimedia Applications

A new heuristic algorithm is proposed for constructing multicast tree for multimedia and real-time applications. The tree is used to concurrently transmit packets from source to multiple destinations such that exactly one copy of any packet traverses the links of the multicast tree. Since multimedia applications require some Quality of Service, QoS, a multicast tree is needed to satisfy two main goals, the minimum path cost from source to each destination (Shortest Path Tree) and a certain end-to-end delay constraint from source to each destination. This problem is known to be NP-Complete. The proposed heuristic algorithm solves this problem in polynomial time and gives near optimal tree. We first mention some related work in this area then we formalize the problem and introduce the new algorithm with its pseudo code and the proof of its complexity and its correctness by showing that it always finds a feasible tree if one exists. Other heuristic algorithms are examined and compared with the proposed algorithm via simulation.

Handling group communication is a key requirement for numerous applications that have one source sends the same information concurrently to multiple destinations. Multicast routing refers to the construction of a tree rooted at the source and spanning all destinations. Generally, there are two types of such a tree, the Steiner tree and the shortest path tree. Steiner tree or group-shared tree tends to minimize the total cost of the resulting tree, this is an NP-Complete problem. Shortest path tree or source-based trees tends to minimize the cost of each path from source to any destination, this can be achieved in polynomial time by using one of the two famous algorithms of Bellman and Dijkstra and pruning the undesired links. Recently, with the rapid evolution of multimedia and real-time applications like audio/video conferencing, interactive distributed games and real-time remote control system, certain QoS need to be guaranteed in the resulted tree. One such QoS, and the most important one is the end-to-end delay between source and each destination, where the information must be sent within a certain delay constraint D. By adding this constraint to the
original problem of multicast routing, the problem is reformulated and the multicast tree should be either delay constrained Steiner tree, or delay-constrained shortest path tree. Delay constrained Steiner tree is an NP-Complete problem, several heuristics are introduced for this problem each trying to get near optimal tree cost, without regarding to the cost of each individual path for each destination. Delay constrained shortest path tree is also an NP-Complete problem. An optimal algorithm for this problem is presented, but its execution time is exponential and used only for comparison with other algorithms. Heuristic for this problem is presented, which tries to get a near optimal tree from the point of view of each destination without regarding the total cost of the tree. An exhaustive comparison between the previous heuristics for the two problems can be found. We investigate the problem of delay constrained shortest path tree since it is appropriate in some applications like Video on Demand (VoD), where the multicast group has a frequent change, and every user wants to get his information in the lowest possible cost for him without regarding the total cost of the routing tree. Also shortest path tree always gives average cost per destination less than Steiner tree. We present a new heuristic algorithm that finds the required tree in polynomial time.

Tags : , , , , , , , ,

Market Oriented Cloud Architecture

As consumers rely on Cloud providers to supply all their computing needs, they will require specific QoS to be maintained by their providers in order to meet their objectives and sustain their operations. Cloud providers will need to consider and meet different QoS parameters of each individual consumer as negotiated in specific SLAs. To achieve this, Cloud providers can no longer continue to deploy traditional system-centric resource management architecture that do not provide incentives for them to share their resources and still regard all service requests to be of equal importance.Instead, market-oriented resource management is necessary to regulate the supply and demand of Cloud resources at market equilibrium, provide feedback interms of economic incentives for both Cloud consumers and providers, and promote QoS-based resource allocation mechanisms that differentiate service requests based on their utility.

Figure 1 shows the high-level architecture for supporting market-oriented resource allocation in Data Centers and Clouds. There are basically four main entities involved:

Figure 1: High-level market-oriented cloud architecture.

  1. Service Request Examiner and Admission Control: When a service request is first submitted, the Service Request Examiner and Admission Control mechanism interprets the submitted request for QoS requirements before determining whether to accept or reject the request. Thus, it ensures that there is no overloading of resources whereby many service requests cannot be fulfilled successfully due to limited resources available. It also needs the latest status information regarding resource availability (from VM Monitor mechanism) and workload processing (from Service Request Monitor mechanism) in order tomake resource allocation decisions effectively. Then, it assigns requests to VMs and determines resource entitlements for allocated VMs.
  2. Pricing: The Pricing mechanism decides how service requests are charged. For instance, requests can be charged based on submission time(peak/off-peak), pricing rates(fixed/changing) or availability of resources (supply/demand). Pricing serves as a basis for managing the supply and demand of computing resources within the Data Center and facilitates in prioritizing resource allocations effectively.
  3. Accounting: The Accounting mechanism maintains the actual usage of resources by requests so that the final cost can be computed and charged to the users. In addition, the maintained historical usage information can be utilized by the Service Request Examiner and Admission Control mechanism to improve resource allocation decisions.
  4. VM Monitor: The VM Monitor mechanism keeps track of the availability of VMs and their resource entitlements.
  5. Dispatcher: The Dispatcher mechanism starts the execution of accepted service requests on allocated VMs.
  6. Service Request Monitor: TheService Request Monitor mechanism keeps track of the execution progress of service requests.

In the case of a Cloud as a commercial offering to enable crucial business operations of companies, there are critical QoS parameters to consider in a service request, such as time, cost, reliability and trust/security. In particular, QoS requirements cannot be static and need to be dynamically updated over time due to continuing changes in business operations and operating environments. In short, there should be greater importance on customers since they pay for accessing services in Clouds. In addition, the state-of the-art in Cloud computing has no or limited support for dynamic negotiation of SLAs between participants and mechanisms for automatic allocation of resources to multiple competing requests. Recently, we have developed negotiation mechanisms based on alternate offers protocol for establishing SLAs. These have high potential for their adoption in Cloud computing systems built using VMs.

Commercial offerings of market-oriented Clouds must be able to:

  1. support customer-driven service management based on customer profiles and requested service requirements,
  2. define computational risk management tactics to identify, assess, and manage risks involved in the execution of applications with regards to service requirements and customer needs,
  3. derive appropriate market-based resource management strategies that encompass both customer-driven service management and computational risk management to sustain SLA-oriented resource allocation,
  4. incorporate autonomic resource management models that effectively self-manage changes in service requirements to satisfy both new service demands and existing service obligations, and
  5. leverage VM technology to dynamically assign resource shares according to service requirements.

Tags : , , , , , , , , , , , , , , , , , ,

Technical Challenges & Solution Approaches for DRE

Some of the most challenging requirements for new and planned DRE (Distributed Real-time and Embedded) systems can be characterized as follows:

  1. Multiple QoS properties must be satisfied in real-time
  2. Different levels of service are appropriate under different configurations, environmental conditions, and costs
  3. The levels of service in one dimension must becoordinated with and/or traded off against the levels of service in other dimensions to meet mission needs
  4. The need for autonomous and time-critical application behavior necessitates a flexible distributed system substrate that can adapt robustly to dynamic changes in mission requirements and environmental conditions.

Although conventional COTS (commercial-off-the-shelf) software cannot meet all of these requirements, today’s economic and organizational constraints—along with increasingly complex requirements and competitive pressures—are making it infeasible to built complex DRE system software entirely from scratch. Thus, there is a pressing need to develop, validate, and ultimately standardize a new generation of adaptive and reflective middleware technologies that can support stringent DRE system functionality and QoS requirements.

Middleware is reusable systems software that functionally bridges the gap between,

Middleware therefore provides capabilities whose quality and QoS are critical to DRE systems. Adaptive middleware is software whose functional and QoS-related properties can be modified.

In mission-critical DRE systems, adaptive middleware must make these modifications dependably, i.e., while meeting stringent end-to-end QoS requirements. Reflective middleware goes a step further to permit automated examination of the capabilities it offers, and to permit automated adjustment to optimize those capabilities. Reflective middleware therefore supports more advanced adaptations that can be performed autonomously based on conditions within the system, in the system’s environment, or in DRE system policies defined by operators and administrators.

Tags : , , , , , , , , , , , , , , , , , , , ,

Constrained Shortest Path Algorithm for Multicast Routing in Multimedia Applications

A  new  heuristic  algorithm  is  proposed  for  constructing multicast  tree  for multimedia  and  real-time  applications. The  tree  is  used  to  concurrently  transmit  packets  from source to multiple destinations such that exactly one copy of  any  packet  traverses  the  links  of  the  multicast  tree. Since  multimedia  applications  require  some  Quality  of Service,  QoS,  a  multicast  tree  is  needed  to  satisfy  two main  goals,  the minimum  path  cost  from  source  to  each destination (Shortest Path Tree) and a certain end-to-end delay  constraint  from  source  to  each  destination.  This problem  is  known  to  be  NP-Complete.  The  proposed heuristic algorithm solves this problem in polynomial time and gives near optimal tree. We first mention some related work  in  this  area  then  we  formalize  the  problem  and introduce the new algorithm with its pseudo code and the proof of its complexity and its correctness by showing that it always finds a feasible tree if one exists. Other heuristic algorithms are examined and compared with the proposed algorithm via simulation.

Shortest  path  tree  or source-based trees tends to minimize the cost of each path from  source  to  any  destination,  this  can  be  achieved  in polynomial  time  by  using  one  of  the  two  famous algorithms of  Bellman  and Dijkstra  and pruning the undesired  links.  Recently,  with  the  rapid  evolution  of multimedia  and  real-time  applications  like  audio / video conferencing,  interactive  distributed  games  and  real-time remote control system, certain QoS need to be guaranteed in the resulted tree. One such QoS, and the most important one,  is  the  end-to-end  delay  between  source  and  each destination, where  the  information must  be  sent within  a certain delay constraint D. By adding this constraint to the original  problem  of  multicast  routing,  the  problem  is reformulated and the multicast tree should be either delayconstrained Steiner tree, or delay-constrained shortest path tree.  Delay  constrained  Steiner  tree  is  an  NP-Complete problem,  several  heuristics  are  introduced  for  this problem each trying to get near optimal tree cost, without regarding to the cost of each individual path for  each  destination. Delay-constrained  shortest  path  tree is  also  an  NP-Complete  problem.  An  optimal algorithm  for  this  problem  is  presented  at,  but  its execution  time  is  exponential  and  used  only  for comparison  with  other  algorithms.  Heuristic  for  this problem  is  presented  in, which  tries  to  get  a  near optimal  tree  from  the  point  of  view  of  each  destination without regarding the total cost of the tree. An exhaustive comparison  between  the  previous  heuristics  for  the  two problems  can  be  found  in.  We investigate  the problem of delay constrained  shortest path tree since it is appropriate in some applications like Video on  Demand  (VoD),  where  the  multicast  group  has  a frequent  change,  and  every  user  wants  to  get  his information  in  the  lowest  possible  cost  for  him  without regarding  the  total  cost  of  the  routing  tree. Also  shortest path  tree  always  gives  average  cost  per  destination  less than  Steiner  tree.


Tags : , , , , , , , , , , , , , , ,