[brite-users] Some Bugs Fixed
Anukool Lakhina
anukool@cs.bu.edu
Sat Mar 22 19:37:01 2003
Hi Arnaud,
BRITE implements an "incremental growth" version of the Waxman
model. This means that at each step of the algorithm, a new node
surveys the existing nodes in the graph and connects to m of them with
probability given by the waxman model. Note that the parameter "m" makes
the graph more or less dense.
The rationale for an incremental-growth Waxman becomes evident once we
survey the existing graph generation algorithms that have been proposed,
principally the Barabasi-Albert flavor models. All of these are
incremental growth with some connectivity function. The Waxman
model therefore, was tailored to mimic this style of graph generation, for
comparision.
Hope this is helpful and please feel free to contact me if you have any
questions. We would be thrilled if you (or anyone!) would contribute or
extend the Waxman model in BRITE.
Thanks for bringing this up. And I'm sorry I didn't respond
earlier. Cheers,
Anukool
On Sat, 22 Mar 2003, Arnaud Legrand wrote:
> On 21/03/03 Anukool Lakhina wrote:
>
> > Hi all -
> >
> > We've just fixed a handful of bugs in BRITE. Here is the list of bugs
> > fixed (from the changelog)
> >
> > - A number of bugs in heavy tail assignment of link bandwidths.
> > (Thanks to WenHui for spotting them)
> >
> > - Minor fixes to GUI misbehavior in Win32
> > (Thanks to ZhangHao for spotting these)
> >
> > - The C++ version now compiles with GCC 3.2
>
> Hi Anukool.
>
> Two months ago, I have sent an e-mail on this list on how to find "good"
> parameters for all those models. Nobody answered but afterall, that is a
> difficult question. Nevertheless, I was also mentionning a weird behavior in
> the implementation of the Waxman algorithm.
>
> Here are the comments I had sent last time :
> ****************************************************************************
> In the Waxman model (as you explain in the documentation and as presented
> in most papers I have read), two nodes u and v are connected with a
> probability P(u,v)=\alpha e^{-d(u,v)/\beta L}, where \alpha and \beta are
> in [0,1]. Thus, the basic method for generating such a graph consist in
> considering all couples (u,v) of nodes, to generate a random number x
> between 0 and 1 and to connect u and v iff x is smaller or equal than
> P(u,v). That is why the alpha parameter controls the "density" of the
> graph, i.e. the number of edges.
>
> I have been then surprised that changing this parameters had almost no
> impact on the look of my graphs. Thus, I have check out your code (C++
> and Java). And in both sources, you proceed roughly in the following way
> (I do not take in account the m parameter which does not really change
> the problem).
>
> You pick up randomly a node v1.
> While v1 is not connected to somebody else :
> You pick up randomly a node v2 which is not already connected to v1.
> You determine whether v1 should be connected to v2 and connect it if it
> is the case.
>
> You repeat this operation until all nodes are connected.
>
> You obviously use this method to ensure that the resulting graph will be
> connected. But what if alpha is very high ? Then you're are going to
> connect v1 with the the first other node at each step and the resulting
> graph will almost look like a tree (with some more edges but not as much
> as it should). If the alpha is very small, you are going to have the same
> kind of graph because your condition for stopping the creation of new
> edges is the connectivity of the graph.
>
> I think you should use the plain method of checking all pairs of node for
> deciding whether a new edge should be created or not. Of course, when
> alpha is too low, there are some risks for the graph to be non connected.
> You should then try to generate a graph following this scheme until you
> find a connected graph.
> ****************************************************************************
>
> I have downloaded the new version of BRITE and looked at the sources. It
> seems to me that nothing has been done to correct this behavior. Can you
> just tell me whether I am wrong or not.
>
> Best regards,
>
> Arnaud Legrand
>
> --
> Arnaud Legrand tel + 33 4 72 72 85 47
> Projet ReMaP, Laboratoire LIP fax + 33 4 72 72 80 80
> UMR CNRS-INRIA-ENS NDEG5668 Arnaud.Legrand@ens-lyon.fr
> École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France
>
>
>