Subject: Re: [PCN] A Simple Analytical Model of PCN - Revised version

From: "Raj Jain" <[email-masked]>
Date: Mon, 10 Mar 2008 10:26:23 -0500

We have now posted a revised version of our presentation on "A Simple
Analytical Model of PCN" at:
 
http://www.cse.wustl.edu/~jain/ietf/pcn0803.htm

As indicated earlier, this version examines the issue of thrashing - when
some flows are terminated while new ones are also accepted. We define a
thrasing index and show how to minimize thrasing. Sensitivity of thrashing
to termination threshold, probability of a flow being on (or off), and the
link speed (which effects total number of flows) is examined. 

The results indicate that for small number of flows, the termination
threshold should be significantly higher than the rejection threshold. For
large number of flows (very high speed links), the two thresholds can be
closer together.

Thanks.

-Raj Jain

-----Original Message-----
From: Raj Jain [mailto:[email-masked]] 
Sent: Saturday, March 08, 2008 9:04 AM
To: [email-masked]'
Cc: 'Jinjing Jiang'; 'Jinjing Jiang'
Subject: A Simple Analytical Model of PCN

Analytical models often require simplifications but they provide good
insights in to the effects of various parameters. With this view point, we
have developed a simple model of PCN. We model n flows going through a
single bottleneck where the packets are marked using a token bucket. The
egress measures the rate of marked packets and sends it to the ingress point
which makes a decision to reject new flows or to terminate existing flows.

Currently the model assumes instantaneous feedback and infinite buffering
(therefore no loss). The sources are modeled with exponentially distributed
on/off period. We are able to get close form expressions for the rejection
and termination probabilities for single marking case.

An inital set of slides presenting the model are available at:

http://www.cse.wustl.edu/~jain/ietf/pcn0803.htm

We are still working on the presentation and, in the next few days, hope to
add sensitivity analysis and the effect of various parameters on thrashing
(when some flows are accepted while other flows are terminated).

Comments are welcome.

Thanks.

-Jinjing Jiang and Raj Jain
-----------------------------------------------------
Raj Jain, Ph.D., Fellow of IEEE, Fellow of ACM                      
Professor of Computer Science and Engineering                   
Washington University in St. Louis
Campus Box 1045, One Brookings Drive
St. Louis, MO 63130
Phone: +1 314 322 8092
Email: [email-masked]
URL: http://www.cse.wustl.edu/~jain
Author of: "High Performance TCP/IP Networking" and "The Art of Computer
Systems Performance Analysis"
------------------------------------------------------  

_______________________________________________
PCN mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/pcn

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 10 Mar 2008 16:55:25 +0000

Raj,

>large number of flows (very high speed links), the two thresholds can be

I've had a quick scan - but in my acrobat reader a lot of the maths 
symbols come out rendered oddly - big greek letters and new paragraph 
symbols out of place in the middle of the slide. Do others get the same?

I understand you'll be presenting this on Thur, so I'll defer comment 
until I understand better.

Just a quick question: is the "no of flows" per edge-edge aggregate 
or per link? I think you are talking per aggregate, but just to be sure.

Cheers

Bob

>-Jinjing Jiang and Raj Jain

____________________________________________________________________________
Bob Briscoe, <[email-masked]>      Networks Research Centre, BT Research
B54/77 Adastral Park,Martlesham Heath,Ipswich,IP5 3RE,UK.    +44 1473 645196

---

From: "Lachlan Andrew" <[email-masked]>
Date: Mon, 10 Mar 2008 10:17:05 -0700

On 10/03/2008, Bob Briscoe <[email-masked]> wrote:
>
> In my acrobat reader a lot of the maths

Yes.

Lachlan

-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Ph: +1 (626) 395-8820    Fax: +1 (626) 568-3603
http://netlab.caltech.edu/lachlan
_______________________________________________
PCN mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/pcn

---

From: Steven Blake <[email-masked]>
Date: Mon, 10 Mar 2008 13:33:44 -0400

> >  symbols out of place in the middle of the slide. Do others get the same?

It looks fine to me, using both acrobat and evince on Linux.

For the purposes of an IETF meeting, having the math look like garbage
might be better.  :)

Regards,

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Steven Blake                <[email-masked]>
Ericsson/Redback Networks               +1 919-472-9913

---

From: "Raj Jain" <[email-masked]>
Date: Mon, 10 Mar 2008 20:06:49 -0500

Lachlan and Bob,

Thanks for pointing out the issues with pdf.

I have now replaced the pdfs with a different version.

Same URL:

No change in contents.

If anyone finds problems with the symbols and equations in this version,
please do let me know.

Thanks.

-Raj Jain

-----Original Message-----
From: Lachlan Andrew [mailto:[email-masked]] 
Sent: Monday, March 10, 2008 12:17 PM
To: Bob Briscoe
Cc: [email-masked]; Jinjing Jiang; [email-masked]; Jinjing Jiang
Subject: Re: [PCN] A Simple Analytical Model of PCN - Revised version

On 10/03/2008, Bob Briscoe <[email-masked]> wrote:
>
> In my acrobat reader a lot of the maths  symbols come out rendered 
> oddly - big greek letters and new paragraph  symbols out of place in 
> the middle of the slide. Do others get the same?

Yes.

Lachlan

--
Lachlan Andrew  Dept of Computer Science, Caltech 1200 E California Blvd,
Mail Code 256-80, Pasadena CA 91125, USA
Ph: +1 (626) 395-8820    Fax: +1 (626) 568-3603
http://netlab.caltech.edu/lachlan

---

From: "Geib, Ruediger" <[email-masked]>
Date: Tue, 11 Mar 2008 08:47:46 +0100

Hi Raj, hi Lachlan,

if I understood the presentation right, you propose single codepoint marking 
combined with excess marking. The admission stop and termination decisions 
are based on rate measurements. The PCN architecture document suggests to 
smooth rate counts in egress nodes by working with an exponentially 
weighted moving average. Did you apply EWMA?

Regards,

Rudiger

| -----Original Message-----
| From: [email-masked] [mailto:[email-masked]] On 
| Behalf Of Raj Jain
| Sent: Tuesday, March 11, 2008 2:07 AM
| To: 'Lachlan Andrew'; 'Bob Briscoe'
| Cc: 'Jinjing Jiang'; [email-masked]
| Subject: Re: [PCN] A Simple Analytical Model of PCN - Revised version
| 
| Lachlan and Bob,
| 
| Thanks for pointing out the issues with pdf.
| 
| I have now replaced the pdfs with a different version.
| 
| Same URL:
| http://www.cse.wustl.edu/~jain/ietf/pcn0803.htm
| 
| No change in contents.
| 
| If anyone finds problems with the symbols and equations in 
| this version, please do let me know.
| 
| Thanks.
| 
| -Raj Jain
| 
|  
| 
| -----Original Message-----
| From: Lachlan Andrew [mailto:[email-masked]]
| Sent: Monday, March 10, 2008 12:17 PM
| To: Bob Briscoe
| Cc: [email-masked]; Jinjing Jiang; [email-masked]; Jinjing Jiang
| Subject: Re: [PCN] A Simple Analytical Model of PCN - Revised version
| 
| On 10/03/2008, Bob Briscoe <[email-masked]> wrote:
| >
| > In my acrobat reader a lot of the maths  symbols come out rendered 
| > oddly - big greek letters and new paragraph  symbols out of 
| place in 
| > the middle of the slide. Do others get the same?
| 
| Yes.
| 
| Lachlan
| 
| 
| --
| Lachlan Andrew  Dept of Computer Science, Caltech 1200 E 
| California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
| Ph: +1 (626) 395-8820    Fax: +1 (626) 568-3603
| http://netlab.caltech.edu/lachlan
| 
| _______________________________________________
| PCN mailing list
| [email-masked]
| https://www.ietf.org/mailman/listinfo/pcn
| 
_______________________________________________
PCN mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/pcn

---

From: "Raj Jain" <[email-masked]>
Date: Tue, 11 Mar 2008 18:09:00 -0500

Hi Ruediger,
We use the mean rate, which is what  exponentially weighted moving average
is trying to estimate and so the answer would be "yes." 
Thanks.
-Raj

-----Original Message-----
From: Geib, Ruediger [mailto:[email-masked]] 
Sent: Tuesday, March 11, 2008 2:48 AM
To: [email-masked]; [email-masked]
Cc: [email-masked]
Subject: RE: [PCN] A Simple Analytical Model of PCN - Revised version

Hi Raj, hi Lachlan,

if I understood the presentation right, you propose single codepoint marking
combined with excess marking. The admission stop and termination decisions
are based on rate measurements. The PCN architecture document suggests to
smooth rate counts in egress nodes by working with an exponentially weighted
moving average. Did you apply EWMA?

Regards,

Rudiger

| -----Original Message-----
| From: [email-masked] [mailto:[email-masked]] On Behalf Of 
| Raj Jain
| Sent: Tuesday, March 11, 2008 2:07 AM
| To: 'Lachlan Andrew'; 'Bob Briscoe'
| Cc: 'Jinjing Jiang'; [email-masked]
| Subject: Re: [PCN] A Simple Analytical Model of PCN - Revised version
| 
| Lachlan and Bob,
| 
| Thanks for pointing out the issues with pdf.
| 
| I have now replaced the pdfs with a different version.
| 
| Same URL:
| http://www.cse.wustl.edu/~jain/ietf/pcn0803.htm
| 
| No change in contents.
| 
| If anyone finds problems with the symbols and equations in this 
| version, please do let me know.
| 
| Thanks.
| 
| -Raj Jain
| 
|  
| 
| -----Original Message-----
| From: Lachlan Andrew [mailto:[email-masked]]
| Sent: Monday, March 10, 2008 12:17 PM
| To: Bob Briscoe
| Cc: [email-masked]; Jinjing Jiang; [email-masked]; Jinjing Jiang
| Subject: Re: [PCN] A Simple Analytical Model of PCN - Revised version
| 
| On 10/03/2008, Bob Briscoe <[email-masked]> wrote:
| >
| > In my acrobat reader a lot of the maths  symbols come out rendered 
| > oddly - big greek letters and new paragraph  symbols out of
| place in
| > the middle of the slide. Do others get the same?
| 
| Yes.
| 
| Lachlan
| 
| 
| --
| Lachlan Andrew  Dept of Computer Science, Caltech 1200 E California 
| Blvd, Mail Code 256-80, Pasadena CA 91125, USA
| Ph: +1 (626) 395-8820    Fax: +1 (626) 568-3603
| http://netlab.caltech.edu/lachlan
| 
| _______________________________________________
| PCN mailing list
| [email-masked]
| https://www.ietf.org/mailman/listinfo/pcn
|

---

From: <[email-masked]>
Date: Wed, 12 Mar 2008 10:05:55 -0000

Hi Rudiger, Raj

To be pedantic, Raj's model is a sort of "infinite" EWMA limit. He
assumes that the EWMA can produce a good estimate of rate on the time
scale over which rate is (in his model) roughly constant.  This depends
on the level of aggregation at the bottleneck but also on the edge-edge
aggregates through that bottleneck: an egress seeing only a few packets
through a bottleneck may have trouble making a good estimation of rate.

Modelling how a real EWMA behaves probabilistically is quite hard.

Ben

> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Raj Jain
> Sent: 11 March 2008 23:09
> To: 'Geib, Ruediger'; [email-masked]
> Cc: [email-masked]
> We use the mean rate, which is what  exponentially weighted 
> moving average is trying to estimate and so the answer would 
> be "yes." 
> Thanks.
> -Raj
> 
> if I understood the presentation right, you propose single 
> codepoint marking combined with excess marking. The admission 
> stop and termination decisions are based on rate 
> measurements. The PCN architecture document suggests to 
> smooth rate counts in egress nodes by working with an 
> exponentially weighted moving average. Did you apply EWMA?
> 
> Regards,
> 
> Rudiger
> 
> Behalf Of