Framework/Idea for exhaustive checking of all possible scenarios

how to generate all possible scenarios? using for loops or not?

Page 1 of 1

2 Replies - 765 Views - Last Post: 14 October 2010 - 06:32 AM Rate Topic: -----

#1 avionion   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 14-October 10

Framework/Idea for exhaustive checking of all possible scenarios

Posted 14 October 2010 - 05:37 AM

Hi everyone,

I am a PhD Student and this is my first post here. sorry if its not the right place to ask the question. I will briefly describe the problem below and would like to see input from you all:

Problem:
========
I want to generate all possible scenarios for a certain system. For example, let's suppose that we have a full duplex switched Ethernet with 6 computers. Each computer generates periodic traffic on the network and at any switch output port, packets are stored and forwarded in FIFO manner. Since these 6 computers are not globally synchronized with each other so there packets can arrive at switch output port simultaneously and hence experience a 'waiting in queue' delay which depends on traffic and instance of time when packet arrived. My aim is to find worst case possible delay at each switch output port. Now one straight forward approach is to check for all possible scenarios and find the worst case.

My question is, is there any framework in any language or some libraries which can help me in generating all possible cases? If i try to use nested 'for' loops i get roughly (128000)^6 iterations!!! (assuming period of each computer is 128ms). so is there any library or tool which can help me in improving the speed and implementation for so many iterations?

Thanks in advance!

Is This A Good Question/Topic? 0
  • +

Replies To: Framework/Idea for exhaustive checking of all possible scenarios

#2 Salem_c   User is online

  • void main'ers are DOOMED
  • member icon

Reputation: 2253
  • View blog
  • Posts: 4,343
  • Joined: 30-May 10

Re: Framework/Idea for exhaustive checking of all possible scenarios

Posted 14 October 2010 - 06:24 AM

Well you could try some maths to see how "futile" your endeavour would be.

> If i try to use nested 'for' loops i get roughly (128000)^6 iterations!!!
My calculator says 4398046511104000000000000000000

Assuming a fanciful "each solution takes 1uS to calculate" (that's only 1000 machine instructions), you're looking at 139461140 BILLION YEARS.

Most problems of "vast permutation" are solved using pen, paper and some theoretical maths.
Not trying every possible combination which would consume the universe in even attempting to find the answer.
Was This Post Helpful? 0
  • +
  • -

#3 avionion   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 14-October 10

Re: Framework/Idea for exhaustive checking of all possible scenarios

Posted 14 October 2010 - 06:32 AM

Hi thanks for the input.
yes offcourse I know how big a task this is thats why I was asking for some help. As for your suggestions, I have already done some analytic solutions using network calculus but these solutions are pessimistic upper bounds, not the exact values of these delays. I have also tried model checking approach by using UPPAAL and NuSMV but again they have same problem; they cant explore all possible cases.

The idea here, is to find a mechanism which can efficiently generate all permutations. then definitely i will use some algorithms to ignore many generated cases which are not relevant and about which i can give reasoning to be 'useless'.


View PostSalem_c, on 14 October 2010 - 05:24 AM, said:

Well you could try some maths to see how "futile" your endeavour would be.

> If i try to use nested 'for' loops i get roughly (128000)^6 iterations!!!
My calculator says 4398046511104000000000000000000

Assuming a fanciful "each solution takes 1uS to calculate" (that's only 1000 machine instructions), you're looking at 139461140 BILLION YEARS.

Most problems of "vast permutation" are solved using pen, paper and some theoretical maths.
Not trying every possible combination which would consume the universe in even attempting to find the answer.

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1