Subject: [PCN] new description of LC-PCN algorithm

From: "Georgios Karagiannis" <[email-masked]>
Date: Fri, 09 Nov 2007 12:44:45 +0000

Hi Anna, Hi Phil, Hi all

Based on the comments that I have got so far I have tried to modify the
LC-PCN algorithm.

The main changes are:
* PCN_affected_marking is only used during flow termination. In this way
the ECMP solution during flow termination can be completely solved.

* Probing is changed:
Regarding probe generation, it is important to note that probe
packets are generated by the PCN_ingress_nodes in the following way.
A probe packet belonging to a certain micro-flow is generated using the
same 5 touple (source, destination IP address, source, destination ports,
protocol number)
as the packets belonging to the same micro-flow. In addition to this
the PCN_ingress_node has to set the Router Alert IP option on the probe
packet. In this way all
the PCN_interior_node will have to observe the received probe packets.

Thus if a PCN_interior_node receives a probe packet then, due to the
Router Alert option it has to handle it differently then the user packets.
The PCN_interior_node has to PCN_mark the probe packet if it is operating
in admission control
state (or flow termination state). Otherwise the probe packet remains
unmarked.

* The PCN_egress_node changes to flow termination state if it recieves
at least one PCN_Affected_marked packet.

Below I am describing the new proposed LC-PCN operation:

* Setting the thresholds at PCN_interior_nodes:
-----------------------------------------------
In order to calculate the PCN_upper_rate we use two parameters:
Maximum PHB capacity: that is the maximum capacity that can be supported
by a PCN_interior_node
Termination_offset_rate: that is an absolute rate value that should be set
equal into all PCN_interior_nodes. Note that this value is used by
PCN_interior_nodes to calculate their PCN_upper_rate and also during
the situation that a PCN_interior_node is in flow termination state
 and it receives PCN_marked packets. Please see pseudo code on page 20.
This value must be set equal into all PCN_interior_nodes such that all
these nodes will know when to take into account the incoming
PCN_marked packets and when not. The Termination_offset_rate is needed
due to the following fact.
Consider the fact that when the measured PHB rate exceeds the
"Maximum PHB capacity" than the packets belonging to the
given PHB will be either dropped or set to another PHB.
In the situation of multiple severe congestion situations solving the
severe congestion on a severe congestion point, further away than the
PCN_egress_node, say severe_congestion_point_1, it could cause the
situation
that the severe congestion on a node located on the same path and
closer to the PCN_egress_node, say severe_congestion_point_2,
will be solved without marking the excess rate measured at
severe_congestion_point_2. This is however true only if
the measured PHB rate on severe_congestion_point_1 does not
exceed the "Maximum PHB capacity".
This is due to the fact that before the severe_congestion_point_1 goes
into
flow termination it generates a maximum PHB rate that it does not exceed
its "Maximum PHB capacity" - termination_offset_rate and after severe
congestion it generates a
maximum PHB rate not higher than "Maximum PHB capacity".
Thus if the excess rate on severe_congestion_point_1 is higher
than "Maximum PHB capacity" is not seen by severe_congestion_point_2
but, due to the principle of marking, it will be seen by the
PCN_egress_nodes.
Therefore, the severe_congestion_point_2 has to consider the
incoming_PCN_marked_rate from severe_congestion_point_1
in its marking algorithm only for the rate equal to "Maximum PHB
capaciy" - PCN_upper_rate (associated with
severe_congestion_point_1). Note that "Maximum PHB capacity" -
PCN_upper_rate
is equal to Termination_offset_rate.
Note that the severe_congestion_point_2 can know the
termination_offset_rate used by the previous severe congestion point
by using a variable that is equal into whole the PCN domain. Note that
the Termination_offset_rate can also be equal to 0.

The PCN_upper_rate is then found as:
PCN_upper_rate = "Maximum PHB capacity" - Termination_offset_rate

The PCN_lower_rate is configured in all PCN_interior-nodes and it can be
calculated in the following way:
PCN_lower_rate = PCN_upper_rate - Admission_offset_rate

The Admission_offset_rate is an absolute rate value and it is equal in
all PCN_interior_nodes and PCN_egress_nodes. Note that this value is
used by

PCN_interior_nodes to calculate their PCN_lower_rate and the
PCN_egress_nodes to calculate their PCN_upper_rate_egress. Furthermore,
this value is used by

the PCN_interior_nodes also during the situation that a PCN_interior_node
is in admission control state and it receives PCN_marked packets. Please
see pseudo

code on page 13.
This value must be set equal into all PCN_interior_nodes such that all
these nodes will know when to take into account the incoming PCN_marked
packets and when not. Note that a PCN_interior_node can PCN_mark packets
up to an excess rate equal to the Admission_offset_rate. If the exess rate
in an PCN_interior_node is higher than the Admission_offset_rate, then the
PCN_interior_node changes state from admission control state to
flow termination state.

* Setting the thresholds at PCN_egress_nodes:
---------------------------------------------
The question is how to calculate the threshold that defines when a
PCN_egress_node goes into the admission control state.
One way to do that is to consider that when the PCN_egress_node receives a
PCN_marked packet it will mean that at least one PCN_interior_node
started to be admission control congested and therefore it will go
from Normal state to admission control state. Of course this will
somehow might provide some errors, because there might be situations
that this consideration might be to conservative.
Therefore, we use a factor of received PCN_marking encoded packets.

PCN_lower_rate_egress: is equal to a fraction of the
Admission_offset_rate, say
fraction A * Admission_offset_rate, where 0<A<1 and it is preconfigured.
Thus: PCN_lower_rate_egress = A * Admission_offset_rate.

Thus we can say that a PCN_egress_node changes from Normal state to
admission control state when incoming_PCN_marking_rate >
PCN_lower_rate_egress.

where, incoming_PCN_marking_rate = N * input_PCN_marking_bytes/T
Where, input_PCN_marking_bytes = received number of "PCN_marking"
encoded
packets during measurement period T.

Now we defined the condition that the PCN_egress_node changes state from
Normal state to admission control state.

But how will the PCN_egress_node change state from admission control state
to flow termination state.

There are two solutions for this:
First solution: if the PCN_interior_nodes use the PCN_Affected_marking
encoding only during flow termination for the packets that are passing
through
the severe congested node, but without being PCN_marked,
then the PCN_egress_node can change to flow termination state when it
receives
PCN_Affected_marked packets and change from flow termnation state to
normal state
when it does not receive PCN_Affected_marked packets.

Second solution:
In order to explain this, it is important to note that each
PCN_interior_node
that is in admission control state it can PCN_mark packets up to a value
equal to the Admission_offset_rate.

Furthermore, if a PCN_interior_node receives incoming PCN_marked packets
and is in the addmission control state, it will not remark any packets if
the excess rate is equal or lower than the incoming_PCN_marking_rate,
see page 13.
Furthermore, if we will consider as normal situations the situations that
no ECMP occurs and that all flows belonging to the same ingress-egress
aggregate will use the same path from PCN_ingress to PCN_egress,
this will mean that when the PCN_egress_node receives, for the given
ingress-egress aggregate an excess rate equal to a fraction of the
Admission_offset_rate, say fraction F * Admission_offset_rate, where
A>F>=1,
it will have to change from admission control state to flow termination
state.
Note that F can be preconfigured and depends on
the network topology.
Thus in this case the second threshold, can be calculated as follows:
PCN_upper_egress_rate = PCN_lower_egress_rate + F*Admission_offset_rate.
However, there are some corner cases, that mainly occur when the
different congestion points (admission control congested
PCN_interior_nodes) on the same path are not simulataneously starting to
be congested. Therefore we use the multicongestion_error parameter to
identify the error bound that ocurs due to these corner cases. Note that
this error bound can be e.g., predefined ones off line by the
operator, by studying the network topology and/or studying how
often such corner cases could occur and/or doing off line measurements.
Therefore we use:
PCN_upper_rate_egress = PCN_lower_rate_egress + F*Admission_offset_rate
+/- multicongestion_error

I prefer to use the first solution, because then the PCN_egress_node can
solve completely the
ECMP issue and the F factor and the multicongestion_error factor do not
have
to be preconfigured anymore.
* How the states of operation in PCN_interior_nodes are being changed?
---------------------------------------------------------------------
This is explained on page 17, 18, by using Figure 4.

Change from Normal state to Admission control state: event A Occurs when:
Measured PHB rate > PCN_lower_rate

Change from Admission control state to Flow Termination  state: event B
Occurs when:
Measured PHB rate > PCN_upper_rate

* How the states of operation in PCN_egress_nodes are being changed?
---------------------------------------------------------------------
This is explained on page 21, 22, but they have to be modified.

Change from Normal state to Admission control state: event A Occurs when:
incoming_PCN_marking_rate > PCN_lower_rate_egress

Change from Admission control state to flow termination state:
Using First solution mentioned above event B Occurs when the
PCN_egress_node receives
at least one PCN_Affected_marked packet.

Using second solution:
incoming_PCN_marking_rate > PCN_upper_rate_egress

It is important to note that also the explanation of event C on page 21,
has to be modified,
see explanation given above:
Change from Admission control state to Normal state:
Occurs when:

incoming_PCN_marking_rate =< PCN_lower_rate

Change from flow termination to Normal state:
Uisng first solution:
The PCN_egress_node does not receive any PCN_Affected_marked packets

Using second solution:

* Generated excess rate by an PCN_interior_node operating in admission
control state.
-------------------------------------------------------------

The excess rate = signaled_overload_rate.
The maximum excess rate that a PCN_interior_node can calculate
in admission control state is equal to Admission_offset_rate,
see explanation above.
The number of bytes that are remarked, signaled_remarked_bytes
depend on the value of calculated excess rate (signaled_overload_rate),
the value of the Admission_offset_rate and the value of the
incoming_PCN_marking_rate, see pseudo code on page 13.

Regarding probes, and based on the received commenst by Phil and Anna
I modified the operation of probes.

Regarding probe generation, it is important to note that probe
packets are generated by the PCN_ingress_nodes in the following way.
A probe packet belonging to a certain micro-flow is generated using the
same 5 touple (source, destination IP address, source, destination ports,
protocol number)
as the packets belonging to the same micro-flow. In addition to this
the PCN_ingress_node has to set the Router Alert IP option on the probe
packet. In this way all
the PCN_interior_node will have to observe the received probe packets.

Thus if a PCN_interior_node receives a probe packet then, due to the
Router Alert option it has to handle it differently then the user packets.
The PCN_interior_node has to PCN_mark the probe packet if it is operating
in admission control
state (or flow termination state). Otherwise the probe packet remains
unmarked.

* Generating excess rate by an PCN_interior_node operating in flow
termination state:
----------------------------------------------------------------
The excess rate = signaled_overload_rate.
Note that the calculation of the signaled_overload_rate is different than
in the situation that the PCN_Interior_node operates in admission control
state, see page 19 and 20. This is due to the fact that a sliding window
is used to solve an undershooting problem, see discussion on page 19.
The number of bytes that are remarked, signaled_remarked_bytes depend on
the value of calculated excess rate (signaled_overload_rate), the value of
the Termination_offset_rate and the value of the
incoming_PCN_marking_rate,
and the see pseudo code on page 20.

Note that all packets that are passing through a congested
PCN_interior_node
 and are not being PCN_marked by the PCN_interior_node have to be remarked
using the PCN_Affected_marking.

* Providing admission control at PCN_egress_nodes:
--------------------------------------------------
 When the PCN_egress_node is operating in admission control state
than a flow that is requesting admission into the PCN domain can be
treated
in the following way:

If no probing is used, the request for admission can be accomplished by
using an external to PCN signaling protocol. In this case when the
request arrives at a PCN_egress_node that operates in
admission control state then the request is rejected.
If it operates in Normal state is accepted.

If probing is used, the request for admission is accomplished by
using probe packets. In this case when the probe arrives at
a PCN_egress_node and it is PCN_marking encoded is rejected.
Otherwise is accepted.

* Providing flow termination at PCN_egress_nodes:
--------------------------------------------------

When a PCN_egress_node operates on flow termination it calculates
the incoming excess rate (incoming_PCN_marking_rate).
By using the excess rate the PCN_egress_node calclates the number of
flows that have to be terminated using the pseudo code given on page 23.
Note that the PCN_egress_node has to maintain per flow reservation states.
The information contained in the per flow states is used for the
calculation of the flow that have to be terminated, see pseudocode
on page 23. Note also that this pseudo code uses priority clases,
but it operates when also no priority clases are used by setting
Maximum_priority = 0 Where, 0 =< priority_class =< Maximum_priority

Best regards,
Georgios

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

---

From: <[email-masked]>
Date: Fri, 9 Nov 2007 17:28:29 -0000

Thanks Georgios

Rather than be swamped by detail on a Friday evening, I wanted to make
some high level points.

- the PCN-affected-marking change is (I think) sensible. I think this
idea could be added (perhaps as an option for operator) to any of the
other 3 schemes. So it might be valuable to have a short email /draft
that only talked about this idea? an analysis of the benefit, so can
judge whether it's worth the pain (the extra encoding point required).
The benefit may also depend on what marking behaviour is standardised? 

- at a high level your proposal seems gradually to be looking more
similar to the single marking idea, ie rate based marking behaviour for
any rate above PCN-lower-rate ("adm marking" & "termination marking")
(yes I know your algorithm changes above PCN-upper-rate, but only
slightly). Of course there are differences. However, I wonder how much
they matter at the moment; we have to either select which high level
approach to standardise or else standardise in a way that allows more
than one approach through configurable parameters (see draft anna sent
yesterday). 

- I wonder if it would be worth looking at the differences one at a time
and seeing if single marking could be improved by adding it? For
example, one difference is that you swap back & forth between rates in
bit/s and rates as % capacity (of PHB) - I admit I can't really see the
benefit and the downside is that you have extra globally fixed
parameters (eg {PCN-upper-rate = PCN-lower-rate}). There are some
differences (I think fairly minor ones) in terms of handling already
marked pkts that are worth looking at. The idea about adjusting the
marking behaviour to account for some flows already being in the middle
of being terminated - we should discuss in a wider context (not just
applicable to lc-pcn) (personally at the moment I don't like the idea,
as I said in previous email I think it's better adjusting at the
PCN-boundary-node than at the PCN-interior-node). Especially important
are any differences in the PCN-interior-node marking behaviour.

Have a good weekend,
Phil/

> -----Original Message-----
> From: Georgios Karagiannis [mailto:[email-masked]]
> Sent: 09 November 2007 12:45
> To: [email-masked]
> Subject: [PCN] new description of LC-PCN algorithm
> 
> Hi Anna, Hi Phil, Hi all
> 
PCN_marked

---

From: "Georgios Karagiannis" <[email-masked]>
Date: Thu, 15 Nov 2007 16:06:09 +0100

Hi Phil

Regarding your comments please note that I will be happy to participate in
the algorithm 
comparison draft!
I think that your questions (which are not related to LC-PCN but also to
other 
proposals) can be asnwered within this algorithm comparison draft!

Best regards,
Georgios

> From: [email-masked] [mailto:[email-masked]] 
> Sent: vrijdag 9 november 2007 18:28
> To: [email-masked]; [email-masked]
> Subject: RE: [PCN] new description of LC-PCN algorithm
> 
> Thanks Georgios
> 
> Rather than be swamped by detail on a Friday evening, I 
> wanted to make some high level points.
> 
> - the PCN-affected-marking change is (I think) sensible. I 
> think this idea could be added (perhaps as an option for 
> operator) to any of the other 3 schemes. So it might be 
> valuable to have a short email /draft that only talked about 
> this idea? an analysis of the benefit, so can judge whether 
> it's worth the pain (the extra encoding point required).
> - at a high level your proposal seems gradually to be looking 
> more similar to the single marking idea, ie rate based 
> marking behaviour for any rate above PCN-lower-rate ("adm 
> marking" & "termination marking") (yes I know your algorithm 
> changes above PCN-upper-rate, but only slightly). Of course 
> there are differences. However, I wonder how much they matter 
> at the moment; we have to either select which high level 
> approach to standardise or else standardise in a way that 
> allows more than one approach through configurable parameters 
> (see draft anna sent yesterday). 
> 
> - I wonder if it would be worth looking at the differences 
> one at a time and seeing if single marking could be improved 
> by adding it? For example, one difference is that you swap 
> back & forth between rates in bit/s and rates as % capacity 
> (of PHB) - I admit I can't really see the benefit and the 
> downside is that you have extra globally fixed parameters (eg 
> {PCN-upper-rate = PCN-lower-rate}). There are some 
> differences (I think fairly minor ones) in terms of handling 
> already marked pkts that are worth looking at. The idea about 
> adjusting the marking behaviour to account for some flows 
> already being in the middle of being terminated - we should 
> discuss in a wider context (not just applicable to lc-pcn) 
> (personally at the moment I don't like the idea, as I said in 
> previous email I think it's better adjusting at the 
> PCN-boundary-node than at the PCN-interior-node). Especially 
> important are any differences in the PCN-interior-node 
> marking behaviour.
> 
> Have a good weekend,
> Phil/
> 
> > Regarding probe generation, it is important to note that 
> probe packets 
> > are generated by the PCN_ingress_nodes in the following way.
> > Termination_offset_rate: that is an absolute rate value 
> that should be
> set
> > Consider the fact that when the measured PHB rate exceeds 
> the "Maximum 
> > PHB capacity" than the packets belonging to the given PHB will be 
> > either dropped or set to another PHB.
> > situation that the severe congestion on a node located on the same 
> > path and closer to the PCN_egress_node, say 
> severe_congestion_point_2, 
> > severe_congestion_point_2. This is however true only if the 
> measured 
> > PHB rate on severe_congestion_point_1 does not exceed the 
> "Maximum PHB 
> > capacity".
> > into flow termination it generates a maximum PHB rate that 
> it does not
> exceed
> > congestion it generates a maximum PHB rate not higher than "Maximum 
> > PHB capacity".
> > Thus if the excess rate on severe_congestion_point_1 is higher than 
> > "Maximum PHB capacity" is not seen by 
> severe_congestion_point_2 but, 
> > due to the principle of marking, it will be seen by the 
> > PCN_egress_nodes.
> > incoming_PCN_marked_rate from severe_congestion_point_1 in 
> its marking 
> > algorithm only for the rate equal to "Maximum PHB capaciy" - 
> > PCN_upper_rate (associated with severe_congestion_point_1). 
> Note that 
> > "Maximum PHB capacity" - PCN_upper_rate is equal to 
> > Termination_offset_rate.
> > The PCN_lower_rate is configured in all PCN_interior-nodes 
> and it can
> be
> > up to an excess rate equal to the Admission_offset_rate. If 
> the exess
> rate
> > in an PCN_interior_node is higher than the 
> Admission_offset_rate, then
> the
> > PCN_interior_node changes state from admission control 
> state to flow 
> > termination state.
> > 
> > Admission_offset_rate, say fraction A * 
> Admission_offset_rate, where 
> > 0<A<1 and it is
> preconfigured.
> > through the severe congested node, but without being 
> PCN_marked, then 
> > the PCN_egress_node can change to flow termination state when it 
> > receives PCN_Affected_marked packets and change from flow 
> termnation 
> > state to normal state when it does not receive PCN_Affected_marked 
> > packets.
> > 
> > Second solution:
> > PCN_interior_node that is in admission control state it can 
> PCN_mark 
> > packets up to a
> value
> > and is in the addmission control state, it will not remark 
> any packets
> if
> > aggregate will use the same path from PCN_ingress to 
> PCN_egress, this 
> > will mean that when the PCN_egress_node receives, for the given 
> > Note that F can be preconfigured and depends on the network 
> topology.
> > PCN_interior_nodes) on the same path are not 
> simulataneously starting
> to
> > operator, by studying the network topology and/or studying 
> how often 
> > such corner cases could occur and/or doing off line
> measurements.
> > Therefore we use:
> > Change from Admission control state to Flow Termination  
> state: event
> B
> > Occurs when:
> > PCN_egress_node receives at least one PCN_Affected_marked packet.
> > 
> > Using second solution:
> > The maximum excess rate that a PCN_interior_node can calculate in 
> > admission control state is equal to Admission_offset_rate, see 
> > explanation above.
> > The number of bytes that are remarked, 
> signaled_remarked_bytes depend 
> > on the value of calculated excess rate
> (signaled_overload_rate),
> > Regarding probe generation, it is important to note that 
> probe packets 
> > are generated by the PCN_ingress_nodes in the following way.
> > The number of bytes that are remarked, 
> signaled_remarked_bytes depend
> on
> > incoming_PCN_marking_rate, and the see pseudo code on page 20.
> > 
> > PCN_interior_node  and are not being PCN_marked by the 
> > PCN_interior_node have to be
> remarked
> >  When the PCN_egress_node is operating in admission control 
> state than 
> > a flow that is requesting admission into the PCN domain can 
> be treated 
> > in the following way:
> > 
> > request arrives at a PCN_egress_node that operates in admission 
> > control state then the request is rejected.
> > If probing is used, the request for admission is 
> accomplished by using 
> > probe packets. In this case when the probe arrives at a 
> > PCN_egress_node and it is PCN_marking encoded is rejected.
> > Otherwise is accepted.
> > 
> > When a PCN_egress_node operates on flow termination it 
> calculates the 
> > incoming excess rate (incoming_PCN_marking_rate).
> > calculation of the flow that have to be terminated, see 
> pseudocode on 
> > page 23. Note also that this pseudo code uses priority 
> clases, but it 
> > operates when also no priority clases are used by setting