[Simgrid-user] Ordering of flows

Martin Quinson martin.quinson at loria.fr
Thu Jul 3 12:34:39 CEST 2008


Hello there,

On Wed, Jul 02, 2008 at 09:52:45AM +0200, Arnaud Legrand wrote:

> Kurt Vanmechelen wrote:
>
>> I have a new question though. As our tests show, there is no flow 
>> "ordering" in SURF. Suppose we have two hosts A and B,  and A starts 
>> two communication flows X and Y to B. Flow X is started at time U and 
>> flow Y at time V with U < V. Now it appears that Y can finish before X, 
>> i.e. there is no (packet/flow) ordering to ensure that X finishes 
>> before Y. 
>
> Well in the setting you describe, flow Y can finish before X only if it  
> conveys less data than X. If you send 10 Gb in X and 1Kb in Y, Y may  
> obviously finish earlier (depending on U and V). Otherwise, if X and Y  
> convey the same amount of data and both are from A to B, X has to finish  
> earlier than Y. I would be very surprised if you experimented otherwise.  
> But if you did, it is a huge bug and I would be happy to look at it.
>
>> If I am not mistaken the TCP protocol prevents such reorderings from 
>> happening by using sequence numbers. I also know that SURF is not 
>> supposed to do packet level simulation. 

The difference between TCP and surf is that the latter has no notion
of channel. Everything as if you opened a new TCP connexion for each
flow. Then, of course, the transfer on flow Y can finish before flow X.

If I understand well, you want surf to model a system where a unique
TCP connexion is used to send several flows in //, and you want them
to finish in the right order. But how could you send several flows in
// in the first place? Unless I'm drunk or something, BSD sockets do
not allow parallel transfers: you have to open several of them (and
then reordering is admitted) or wait for the first flow to be done
before begining the second flow (and then, reordering becomes
obviously impossible), right?

I guess that what you really want is some sort of abstraction, which
is close enough to what you could implement in real life without
getting into the difficulties of BSD sockets.

>> I was wondering however whether you came across this issue before and 
>> how you deal with this in message-based programs (i.e. programs that 
>> used your MPI layer for example). In such programs it is important for 
>> this ordering to be correct in order to assure a semantically sound 
>> execution of an RPC based program.
>
> You are directly on top of SURF. So any action entered in SURF starts as  
> soon as it is created: all flows run in parallel. If you want to express  
> some sequential dependencies between these flows (actually it comes from  
> the dependency between your messages), then you have to queue them and  
> delay their creation. This is how MSG, GRAS and SMPI work. Each process  
> has a queue of pending communication and the corresponding action is  
> created when needed (e.g. the sender and the receiver are ready). Thus  
> many flows can run in parallel but we respect the message orders for  
> each process... I hope this is more clear now.

All these interfaces are based on the SIMIX layer, which takes care of
this kind of issue. As Arnaud explained, we take the second approach
wrt what I said earlier: a communication cannot begin before the
receiver is ready to get it. And during the communication, it is
unavailable to any other incomming communication. So, the
synchronization at the SIMIX layer enforce that one given chanel
linking one sender to a receiver is FIFO while the ordering of
messages comming from several senders is not specified. That's exactly
what TCP ensures.

Bye, Mt.

-- 
All models are wrong. Some are useful.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.gforge.inria.fr/pipermail/simgrid-user/attachments/20080703/38daade4/attachment-0002.pgp 


More information about the Simgrid-user mailing list