Re: [GLIF controlplane] RE: Network Control Architecture

[Steve Thorpe <thorpe@xxxxxxxx>]

Hi Bert,

Regarding RB's, I think we collectively should be able to support an 
arbitrary number of them.  It seems to be splitting hairs to focus on 
the rare case where different RB's could repeatedly request / be denied, 
request / be denied.... I suspect it would be pretty infrequent if ever 
this would happen to us.  They might happen but such is life, 
unfortunately we don't have infinite resources and sometimes the answer 
is going to be no.

Actually, I think you, me, and Jon MacLaren are all basically in 
agreement...

You mentioned:  "Now, although the above scenario is not very likely, in 
a complex system where a lot of reservations are made similar processes 
might and will happen, just like in the early supercomputers."

Jon mentioned:  "Also, we have so few people actually wanting to do 
reserve these resources, that this scenario is highly unlikely to occur. 
 If it did, the users would probably retry - they would have to be 
exceptionally unlucky to hit the same race condition twice in a row..."

In my opinion we should focus not on the very unlikely but on the very 
likely scenarios.  And, using a 2-phase commit protocol at the 
individual resource level, combined with (possibly multiple, 
independent) RBs using that protocol to co-allocate advanced 
reservations of multiple resources, should handle the great majority of 
scenarios.

Anyway, there are a couple more cents for the thread.  Hope you and 
everyone else on the list have a great weekend :)

Thanks,

Steve

Bert Andree wrote:
> Hello Steve,
>
> Well, it is easy to make the pre-reservation of a single resource 
> atomic. Even the reservation of multiple resources in a single domain is 
> not very hard. But in the multidomain case, the pre-reservation of all 
> resources together needs to be atomic. This can only be achieved if 
> there is some kind of RB, and only one RB is active at the same time.
>
> This process can be compared with the semaphore in parallel computing.
>
> If not *all* resources can be pre-reserved in a single atomic action the 
> following might occur:
> RB-A pre-reserves RS-1
> RB-B pre-reserves RS-2
> RB-A pre-reserves RS-2 (fail)
> RB-B pre-reserves RS-1 (fail)
> RB-A releases RS-1
> RB-B releases RS-2
> RB-A pre-reserves RS-1
> RB-B pre-reserves RS-2
> RB-A pre-reserves RS-2 (fail)
> RB-B pre-reserves RS-1 (fail)
> RB-A releases RS-1
> RB-B releases RS-2
> etc.
>
> Now, although the above scenario is not very likely, in a complex system 
>  where a lot of reservations are made similar processes might and will 
> happen, just like in the early supercomputers.
>
> Now, if there is a single RB (or at least a single queue for requests 
> from resource brokers), than it is possible to *develop* a system that 
> does not lead to deadlock or individual starvation.
>
> Of course, if we assume that resources are not scarse, the above is not 
> important, but then: why do we need reservations.
>
> Best regards,
> Bert
>
>
> Steve Thorpe wrote:
>
> > Hello Bert, everyone,
> >
> > The point Bert made "...if the pre-reservation of resources is not an 
> > atomic action..." is very important.
> >
> > My belief is the pre-reservation of resources, or Phase 1 of a 2-phase 
> > commit protocol, *must* be atomic.  That is, there must be a guarantee 
> > that at most one requestor will ever be granted a pre-reservation of a 
> > given resource.  Then, the requestor should come back with a 
> > subsequent "Yes, commit the pre-reservation", or "No, I release the 
> > pre-reservation".  In the case where the requestor does not come back 
> > within a certain amount of time, then the pre-reservation could expire 
> > and some other requestor could then begin the 2-phase commit process 
> > on the given resource.
> >
> > There may be situations where a resource broker can not get the 
> > desired resource reservation(s) booked.  But, I don't see deadlocking 
> > here - where both resources can *never* be booked.  Unless of course, 
> > a resource broker books them once and is allowed on to them forever.
> >
> > The atomicity of the pre-reservation (phase 1) stage of the 2-phase 
> > commit process is a very critical part for this to work.
> >
> > Steve
> >
> > PS I have also added Jon MacLaren to this thread, as I'm not sure he's 
> > on the GLIF email list(s).
> >
> >
> > Bert Andree wrote:
> >
> > > Hi Gigi,
> > >
> > > What exactly dou you mean with one RB per request.
> > > Suppose there are two independant RB's,RB-A and RB-B and two 
> > > resources, RS-1 and RS-2.
> > > Suppose that there is a request to RB-A to book both resources and a 
> > > request to RB-B to do the same. Now, if the pre-reservation of 
> > > resources is not an atomic action, two different strategies may 
> > > introduce specific problems.
> > >
> > > Stategy 1: an availibility request does not reserve the resource:
> > > RB-A asks for RS-1 (available)
> > > RB-B asks for RS-2 (available)
> > > RB-A asks for RS-2 (available)
> > > RB-B asks for RS-1 (available)
> > >
> > > RB-A confirms RS-1 (success)
> > > RB-B confirms RS-2 (success)
> > > RB-A confirms RS-2 (fail)
> > > RB-B confirms RS-1 (fail)
> > >
> > > The obvious solution would be to free all resources and try again. In 
> > > complex systems there is a fair chance that both resources can never 
> > > be booked (deadlock).
> > >
> > >
> > > Stategy 2: an availibility request reserves the resource:
> > > RB-A asks for RS-1 (available)
> > > RB-B asks for RS-2 (available)
> > > RB-A asks for RS-2 (not available)
> > > RB-B asks for RS-1 (not available)
> > >
> > > RB-A and RB-B free all resources and try again. In complex systems 
> > > there is a fair chance that both resources can never be booked 
> > > (deadlock).
> > >
> > > The only way to prevent is, is to have some queing of requests and 
> > > even then "individual starvation", e.g. RB-A can never book any 
> > > resources is possible in complex systems.
> > >
> > > Best regards,
> > > Bert
> > >
> > > Gigi Karmous-Edwards wrote:
> > >
> > > > Hi Admela,
> > > >
> > > > I agree, there are two phases, 1) check availability from xRM, and 
> > > > 2) If all xRMs give an ack. then go th second phase of commit, 2') 
> > > > if one or more xRM gives a nack, then do not proceed to the phase 
> > > > two commit. In the architecture sent out, the responsibility of 
> > > > coordinating and administering the two phases is in ONE RB per 
> > > > request. Each xRM will rely on the RB to tell them  whether to 
> > > > proceed to a commit or not. If they get a commit from an RB, it then 
> > > > becomes the xRM's responsibility to make the reservation and 
> > > > allocation in the actual resources. I think if  for example RB-A 
> > > > talks to an xRM in domain "B", then it may be the responsibility of 
> > > > the xRM-B to tell its own  RB-B of its interaction with RB-A. Is 
> > > > this in line with your thoughts?
> > > >
> > > > Gigi


--
Steve Thorpe
Systems Programmer/Analyst, MCNC
Email: thorpe@xxxxxxxx
Office: 919-248-1161
Mobile: 919-724-9654
Skype/AIM: thorpe682

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature