Prev: 2^q mod (p) calculation
Next: THE HONOR OF YOUR GREAT MAHEMATICIAN PROF ESCULTURA / MATHEMATICS MONUMENT
From: atrovantes on 4 Jun 2010 11:41
Let Q denote a queue.
Let r(i) denote Q's size at time-slot i.
Let A_i be i.i.d. random Bernoulli variables.
Let B_i be i.i.d. random Bernoulli variables.

At each timeslot i:
if (A_i == 1) {
if (r(i) > 0) {remove one packet from Q;}
if (B_i == 1) {schedule one packet to enter Q in K slots from now, i.e. in slot i+K;}
}

As you can see, a "simple" Markov chain cannot be used as the event A_i affects the state change of both slots i+1 and i+K.

So; does anyone have any idea on how this can be tackled?
I'm interested in both stationary and transient analysis.

Thank you in advance.
From: Les Cargill on 4 Jun 2010 16:07
atrovantes wrote:
> Let Q denote a queue.
> Let r(i) denote Q's size at time-slot i.
> Let A_i be i.i.d. random Bernoulli variables.
> Let B_i be i.i.d. random Bernoulli variables.
>
> At each timeslot i:
> if (A_i == 1) {
> if (r(i)> 0) {remove one packet from Q;}
> if (B_i == 1) {schedule one packet to enter Q in K slots from now, i.e. in slot i+K;}
> }
>
> As you can see, a "simple" Markov chain cannot be used as the event A_i affects the state change of both slots i+1 and i+K.
>

I can't see that at all. Sorry. The operation "enter Q in K slots from
now" could mean any of a number of things. We have no picture of
what the relationships between elements - the invariants - are.

> So; does anyone have any idea on how this can be tackled?
> I'm interested in both stationary and transient analysis.
>
> Thank you in advance.


--
Les Cargill
From: Ray Vickson on 4 Jun 2010 16:47
On Jun 4, 12:41 pm, atrovantes <eba...(a)gmail.com> wrote:
> Let Q denote a queue.
> Let r(i) denote Q's size at time-slot i.
> Let A_i be i.i.d. random Bernoulli variables.
> Let B_i be i.i.d. random Bernoulli variables.
>
> At each timeslot i:
> if (A_i == 1) {
>   if (r(i) > 0) {remove one packet from Q;}
>   if (B_i == 1) {schedule one packet to enter Q in K slots from now, i.e. in slot i+K;}

What happens if A_i = 0: do you then NOT test for B_i = 1? In other
words, if you do not remove a packet at time i do you _never_ schedule
an arrival at time i+K?

R.G. Vickson

>
> }
>
> As you can see, a "simple" Markov chain cannot be used as the event A_i affects the state change of both slots i+1 and i+K.
>
> So; does anyone have any idea on how this can be tackled?
> I'm interested in both stationary and transient analysis.
>
> Thank you in advance.

From: atrovantes on 4 Jun 2010 13:53
> atrovantes wrote:
> > Let Q denote a queue.
> > Let r(i) denote Q's size at time-slot i.
> > Let A_i be i.i.d. random Bernoulli variables.
> > Let B_i be i.i.d. random Bernoulli variables.
> >
> > At each timeslot i:
> > if (A_i == 1) {
> > if (r(i)> 0) {remove one packet from Q;}
> > if (B_i == 1) {schedule one packet to enter Q in
> K slots from now, i.e. in slot i+K;}
> > }
> >
> > As you can see, a "simple" Markov chain cannot be
> used as the event A_i affects the state change of
> both slots i+1 and i+K.
> >
>
> I can't see that at all. Sorry. The operation "enter
> Q in K slots from
> now" could mean any of a number of things. We have no
> picture of
> what the relationships between elements - the
> invariants - are.

Firstly, thanx for the response.
Let me try clarify some things.

You can think of the operation "enter Q in K slots from now" as if there is a storage where the scheduled packet is placed at slot i, and then at slot i+K the packet is retrieved from this storage and placed in Q.

Moreover, it holds that if A_i == 0, no packet is scheduled for slot i+K. Thus, in slot i+K the only thing that can happen is for Q to lose one packet.

What is more, you may notice that there can be no more than K packets in Q. Let's say there is a slot i where one packet is inserted into Q and now Q has K+1 packets, this means this last packet was scheduled at slot i-K, however in order to reach K+1 packets at slot i then Q should have had at least one packet during slot i-K. Thus, r(i-K)>0, so this packet would have left the system at slot i-K. (Mind me if I'm one slot or packet up or down; with the above argument I'm trying to roughly suggest an aspect of the behavior of the system.)

Some interesting questions may be:
what is the probability distribution of the number of packets in Q, or what is the mean number of packets in Q, or something in the scope of transient analysis that resembles the conditional probabilities of A Markov chain where the states hold, at least, the number of packets in Q.
There are even more questions if you consider tracking certain packets... But this concerns a slightly more complex model but probably quite more difficult to solve.

>
> > So; does anyone have any idea on how this can be
> tackled?
> > I'm interested in both stationary and transient
> analysis.
> >
> > Thank you in advance.
>
>
> --
> Les Cargill
From: atrovantes on 4 Jun 2010 14:00
> On Jun 4, 12:41 pm, atrovantes <eba...(a)gmail.com>
> wrote:
> > Let Q denote a queue.
> > Let r(i) denote Q's size at time-slot i.
> > Let A_i be i.i.d. random Bernoulli variables.
> > Let B_i be i.i.d. random Bernoulli variables.
> >
> > At each timeslot i:
> > if (A_i == 1) {
> >   if (r(i) > 0) {remove one packet from Q;}
> >   if (B_i == 1) {schedule one packet to enter Q in
> K slots from now, i.e. in slot i+K;}
>
> What happens if A_i = 0: do you then NOT test for B_i
> = 1? In other
> words, if you do not remove a packet at time i do you
> _never_ schedule
> an arrival at time i+K?
>
> R.G. Vickson

Thank you for your response.
The answer to both of your questions is affirmative.
Moreover, at each slot, Q may receive one packet, may lose one packet, none of this may happen, or both (the latter two result in Q retaining it's size).

I also answered your question when replying to Les Cargill. I left some other notes too; you may want to see this response also.

>
> >
> > }
> >
> > As you can see, a "simple" Markov chain cannot be
> used as the event A_i affects the state change of
> both slots i+1 and i+K.
> >
> > So; does anyone have any idea on how this can be
> tackled?
> > I'm interested in both stationary and transient
> analysis.
> >
> > Thank you in advance.
>
 | 
Pages: 1
Prev: 2^q mod (p) calculation
Next: THE HONOR OF YOUR GREAT MAHEMATICIAN PROF ESCULTURA / MATHEMATICS MONUMENT