[cadynce] How Many Configurations Is Enough?

Wed May 23 09:59:05 CDT 2007

To all,

Let me see if I can clear up some of the hearsay on the PoR.  There was a
recent review of the Resource Manager Ensemble Software Design Description
for release 4 that covered how resources are allocated upon service
deployment.   Let me summarize the steps here:

Step 1: Get the list of potential hardware on which to deploy the software
      This is based on a deployment file that lists the nodes on which the
      software may be deployed or by comparing the info from the SW and HW
      profiles (required processor, RAM, CPU utilization, network bandwidth
      and operating system).  The software profile also defines the number
      of replicas needed.  Default is 1, but could be more (e.g.
      master/slave) up to every node.

        Step 2: Filter out the nodes that do not have enough resources
(RAM, CPU utilization and bandwidth) to support the software.

Step 3: Determine where to deploy the software.  This is based on:
         Co-location dependency - must be deployed on same node as other
         software
         Replication scheme - Master/slave - deploy master replicas on same
         nodes as dependent software masters
         Survivability with respect to fire zones - if a replica already
         exists, attempt to deploy  a new replica in a different firezone.
         Survivability with respect to nodes - if a replica exists on one
         node, attempt to deploy a new replica on a different node. The
         resource manager will attempt to evenly distribute replicas across
         different fire zones.
         Bin Packing - if the above does not result in a list of zero
         candidate nodes, then use bin packing to select the node.  The
         resource manager will attempt to deploy the software in the node
         with the most RAM first, then CPU utilization then network
         bandwidth that meets the software needs.  The attempt is to deploy
         1 copy of all software needed for an operational string before
         deploying additional replicas.

Step 4:  If there is not enough room on any node to deploy the software,
then the resource manager will examine the existing software on candidate
nodes for an operational string(s) that can be preempted.  This is based on
criticality, resource utilization, effect of previous preemptions and
replicas.

With all of this said, in the next phase, we will need to narrow down to
the critical strings that must be operational and the configurations that
will meet the critical needs.

Gerry

             Raj Rajkumar                                                  
             <raj at ece.cmu.edu>                                             
             Sent by:                                                   To 
             cadynce-bounces at l         Raj Rajkumar <raj at ece.cmu.edu>      
             ist.isis.vanderbi                                          cc 
             lt.edu                    cadynce at list.isis.vanderbilt.edu,   
                                       "Cross, Joseph"                     
                                       <Joseph.Cross at darpa.mil>            
             05/23/2007 12:34                                      Subject 
             AM                        Re: [cadynce] How Many              
                                       Configurations Is Enough?           

I hasten to add that some dimensions (like CPU cycles and memory
requirements, perhaps FLASH and DRAM needs)  in the PoR discussions will
certainly be dimensions in the mathematical bin-packing sense.

---
Raj

Raj Rajkumar wrote:
> Joe and Gautam:
>
> Based on little more than hearsay, I suspect that the word 'dimension'
> may be overloaded in PoR discussions.  In multi-dimensional
> bin-packing,  an object to be packed has a size attribute in k
> orthogonal dimensions, and bins have a unit size in each of these
> dimensions.    In PoR, attributes like security class, OS used, etc.
> may have been discussed as dimensions but are probably just
> classifiers which simplify the bin-packing problem.  As an example, if
> a software module can run only on Windows and another module runs only
> on (say) Linux, it would follow that there are Windows and (say) Linux
> bins.   Windows modules can only be allocated to Windows machines,
> etc.   This in turn would segment the larger bin-packing problem into
> two smaller but distinct problems.
> I agree that a longer discussion must be had.
>
> ---
> Raj
>
> Gautam Thaker wrote:
>> Raj Rajkumar wrote:
>>> Dear Joe, Gautam and Patrick:
>>>
>>> On a somewhat different note, the current configuration generator
>>> uses single-dimensional bin-packing.   ARMS-2 results indicated that
>>> relatively simple multi-dimensional variants of classical heuristics
>>> tend to work pretty well.   At CMU, a small group of us (including a
>>> former PhD student of mine named Dr. Dio DeNiz who is now at the
>>> SEI) has been spending some time reading and studying the worst-case
>>> behaviors of multi-dimensional bin-packing. There are some
>>> surprising (i.e. negative) performance bounds out there on
>>> multi-dimensional bin-packing.   Briefly, if we have k dimensions, a
>>> polynomial-time heuristic may require as many (k+1) times as many
>>> processors as required by the optimal packing.   The lower bound is
>>> 150% (i.e. 50% more processors than the optimal).    Initially, we
>>> thought that the upper bound was perhaps pessimistic, but after
>>> playing around with some numbers, we found one case with k=3
>>> dimensions, the optimal requires two bins while a fairly smart
>>> heuristic (the one that Gaurav used in ARMS-2) required 4
>>> processors.  In other words, we required (k-1) times more processors
>>> than the optimal.   Please note that these are worst-case
>>> (pathological) scenarios.   We continue to believe that in practice,
>>> multi-dimensional packing heuristics will do well in general and an
>>> ensemble will do incredibly better.  For example, for the above
>>> case, WFD solved it quickly to get the optimal! It may stumble on
>>> other cases however - encouraging the use of ensembles.
>>>
>>> Two takeaways:
>>>
>>> 1. With multi-dimensional bin-packing, there may be scenarios where
>>> the number of processors required can be significantly higher than
>>> what one might have come to expect.
>>> 2. An ensemble of multi-dimensional bin-packing heuristics will do
>>> well.
>>
>> Hi Raj:
>>
>> When I met with Carol Galloway and others at NSWC Dahlgren on May 2nd
>> one of the points Paul Werme asked me about was this exact issues. He
>> worried that PoR may have as many as 10 dimensions to pack and he
>> worried if that presented problems to allocators. I had replied that
>> more the dimensions more difficult things will be but that I will
>> discuss this point within the cadynce community. Glad this has come
>> up. I had also said that this being "Box 2", meaning off line
>> analysis, we did not mind spending lots of CPU time to generate
>> candidate allocations.
>>
>> I think we can address this point in coming weeks but nothing much
>> can be done this week. Perhaps we can talk about this in depth if and
>> when we convene the cadynce team for the next face to face meeting. I
>> remain of hope that for most practical cases we can find solutions
>> given that this is offline (box 2).
>>
>> Gautam
>>
>>>
>>> ---
>>> Raj
>>>
>>> _______________________________________________
>>> Cadynce mailing list
>>> Cadynce at list.isis.vanderbilt.edu
>>> http://list.isis.vanderbilt.edu/mailman/listinfo/cadynce
>>
>
> _______________________________________________
> Cadynce mailing list
> Cadynce at list.isis.vanderbilt.edu
> http://list.isis.vanderbilt.edu/mailman/listinfo/cadynce

_______________________________________________
Cadynce mailing list
Cadynce at list.isis.vanderbilt.edu
http://list.isis.vanderbilt.edu/mailman/listinfo/cadynce