Subject: Differentiated Routing, not only plain rambo-SPF

From: Hummel Heinrich <[email-masked]>
Date: Mon, 22 Jul 2002 18:40:02 +0200

In normal, state-less IP routing we cannot do QoS-Routing, nor sneak-around the conjestion-area routing, nor traffic balanced routing. Instead, all of this is left to MPLS, where multiple states and multiple LSPs and multiple signalling is required.

However, I am pretty sure that normal state-less IP routing could do all of it much better and like to launch a discussion
on, well, Differentiated Routing. 

Additional reasons for doing it:

As far as I know, all multicast models build their delivery channels based on SPF-results. By accomplishing
QoS-routing for normal IP, QoS-routed Multicast delivery channels might consequently  come for free (or almost for free).
Also: It would prevent that further thoughts are given to Equal-Cost Multipath (ECMP) which I think is not worth the effort.

Differentiated Routing would certainly stress Differentiated Services and I think that the reason why it hasn't been 
introduced together with DiffServ is that IETF folks are only seeing the advantages of SPF routing but not its disadvantages, i.e. were therefore blocked.

2 Examples, i.e 2 analogies well-known from our roads and highways:

1) QoS Routing
Right now, there are many Europeans going on vacation by driving southbound who are willing to pay the fees for using the highways of whichever country they pass (Germany excepted) while others aren't willing. So each group has a different set of roads available to use. As a result each one will find the optimal route in accordance with what he/she likes to spend on money. 

2)
On the way south there are several hot spots which are famous for being points of conjestion. A vacationer is well advised to pull off the highway and follow the posted signs that mark asneak-around detour as to reenter further south.  
Now let's have a look at our famous rambo-zambo SPF routing paradigma. You pull off the highway.At the first junction you cry for the shortest path to your destination.Because the answer is "crankback to the highway, this option drops out, and you choose randomly any other direction. This behavior repeats at each junction. This rambo will start looping and will soon  run out of gas before he reaches the Alpes, so that the Time-To-Live is over. The smart driver however follows the detour signs, and while he is on the detouring route, he forgets about the final destination. Instead his intermediate destination is the point where he will reenter the highway. As soon as the detouring route has been done, the focus will be again on the original destination.
Isn't  this a perfect routing tunnel? the outer dest address is the re-entrance point of the autobahn,while the route to it is computed based on the fee-less set of roads.The inner destination is somewhere south at the beach and the respective forwarding may be based on computations which takes all roads and all paid highways into consideration.

So my initial question is: why can't we go after Differentiated Routing ?!
And also: why can't we go after better routing paradigmas (with respective algorithms) than SPF-routing ?!

Heinrich 

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

---

From: "Naidu, Venkata" <[email-masked]>
Date: Mon, 22 Jul 2002 13:56:52 -0400

Hummel,

  Very interesting topic. Let me give my view.

  First of all, let me put what you described in a different way.

  Different types of services (call them ToS, CoS, GoS what ever)
  exists and support for those are well defined in the IP history
  since its existence (thanks for those who envisioned & reserved
  few bits in IP header). Those are TOS bits, and almost all
  of the IP routing protocols (at least OSPF) supports TOS.

  In other words, OSPF has different metrics for different
  TOS (min delay, max throughput, max reliability, min cost etc)
  You can (if you would like to) do SPF based on specific TOS
  metrics advertised into OSPF. That solves your first problem
  based on roads & highways.

  TOS and TOS-Routing has been deprecated in the Internet
  because of some historical & deployment reasons. 
  TOS has been changed to support DiffServ. But unfortunately
  TOS-Routing is not changed to Diff-Routing. I really
  don't know why? Pioneers can answer this question.
  But in my opinion, Yes! Diff-Routing solves some of the
  know problems you described.

  MPLS-TE on the other hand is based on Source Routing (atleast
  for now). The envisioned extensions will eventually lead to 
  Diff-Routing (and even better). For example, multiple metrics 
  for DiffServ have been proposed to IETF.
  (see draft-fedyk-isis-ospf-te-metrics-01.txt)
  
  I thought of proposing use of OSPF TOS metrics for DiffServ
  Routing (instead of above extensions) but I don't know
  how war this will be useful...

--
Venkata.

-> -----Original Message-----
-> From: Hummel Heinrich [mailto:[email-masked]]
-> Sent: Monday, July 22, 2002 12:40 PM
-> To: [email-masked]
-> Subject: Differentiated Routing, not only plain rambo-SPF
-> 
-> 
-> In normal, state-less IP routing we cannot do QoS-Routing, 
-> nor sneak-around the conjestion-area routing, nor traffic 
-> balanced routing. Instead, all of this is left to MPLS, 
-> where multiple states and multiple LSPs and multiple 
-> signalling is required.
-> 
-> However, I am pretty sure that normal state-less IP routing 
-> could do all of it much better and like to launch a discussion
-> on, well, Differentiated Routing. 
-> 
-> Additional reasons for doing it:
-> 
-> As far as I know, all multicast models build their delivery 
-> channels based on SPF-results. By accomplishing
-> QoS-routing for normal IP, QoS-routed Multicast delivery 
-> channels might consequently  come for free (or almost for free).
-> Also: It would prevent that further thoughts are given to 
-> Equal-Cost Multipath (ECMP) which I think is not worth the effort.
-> 
-> Differentiated Routing would certainly stress Differentiated 
-> Services and I think that the reason why it hasn't been 
-> introduced together with DiffServ is that IETF folks are 
-> only seeing the advantages of SPF routing but not its 
-> disadvantages, i.e. were therefore blocked.
-> 
-> 2 Examples, i.e 2 analogies well-known from our roads and highways:
-> 
-> 1) QoS Routing
-> Right now, there are many Europeans going on vacation by 
-> driving southbound who are willing to pay the fees for using 
-> the highways of whichever country they pass (Germany 
-> excepted) while others aren't willing. So each group has a 
-> different set of roads available to use. As a result each 
-> one will find the optimal route in accordance with what 
-> he/she likes to spend on money. 
-> 
-> 2)
-> On the way south there are several hot spots which are 
-> famous for being points of conjestion. A vacationer is well 
-> advised to pull off the highway and follow the posted signs 
-> that mark asneak-around detour as to reenter further south.  
-> Now let's have a look at our famous rambo-zambo SPF routing 
-> paradigma. You pull off the highway.At the first junction 
-> you cry for the shortest path to your destination.Because 
-> the answer is "crankback to the highway, this option drops 
-> out, and you choose randomly any other direction. This 
-> behavior repeats at each junction. This rambo will start 
-> looping and will soon  run out of gas before he reaches the 
-> Alpes, so that the Time-To-Live is over. The smart driver 
-> however follows the detour signs, and while he is on the 
-> detouring route, he forgets about the final destination. 
-> Instead his intermediate destination is the point where he 
-> will reenter the highway. As soon as the detouring route has 
-> been done, the focus will be again on the original destination.
-> Isn't  this a perfect routing tunnel? the outer dest address 
-> is the re-entrance point of the autobahn,while the route to 
-> it is computed based on the fee-less set of roads.The inner 
-> destination is somewhere south at the beach and the 
-> respective forwarding may be based on computations which 
-> takes all roads and all paid highways into consideration.
-> 
-> So my initial question is: why can't we go after 
-> Differentiated Routing ?!
-> And also: why can't we go after better routing paradigmas 
-> (with respective algorithms) than SPF-routing ?!
-> 
-> 
-> Heinrich 
-> 
-> _______________________________________________
-> routing-discussion mailing list
-> [email-masked]
-> https://www1.ietf.org/mailman/listinfo/routing-discussion
->

---

From: "Naidu, Venkata" <[email-masked]>
Date: Mon, 22 Jul 2002 13:56:52 -0400

Hummel,

  

--
Venkata.

---

From: "Naidu, Venkata" <[email-masked]>
Date: Mon, 22 Jul 2002 14:43:04 -0400

Fred,

  I have more questions on the future Internet QoS
  Routing (answer/correct me if any of my views are
  impractical).

  As I answered before, my worry is not DiffServ 
  Routing. The on-going extensions will eventually
  lead to better routing.

  But that is very limited to an Area (a small fraction
  in the Internet). Using all these QoS routing extensions
  confined to these small areas will not buy us (an end
  users) anything in the long run. I am speaking
  in the interest of end-to-end Internet world.

  We have an IGP/EGP split and the interoperation
  of these to carry QoS requirements are not at all 
  triggered. The current signaling protocols are also
  very stringent and won't extend end-to-end (not even
  an AS). With out these:

  "How can we deliver a future real-time services 
   (given a SIP call) end-to-end with some guarantee
   over the Internet?"

  "Do you think that there is no need for such 
   Hierarchical QoS Routing?"
  
  I know that, NSIS is trying to solve signaling part 
  of the problem. But signaling follows what routing
  dictates. How are we going to solve the problem?

  If we worry about scalability & aggregation of
  hierarchical QoS routing, we can search for other
  possibilities. For example, "LSP stitching" from
  source AS till destination address AS. This does
  not require any enhancements to IGPs but requires
  some way of communications of the QoS parameters
  across EGP boundaries. Do you agree?

  PS: I am speaking as an individual. No prejudices
      towards any union/task/forum. I just would like
      to evaluate evolution :)
  
--
Venkata.

-> >So my initial question is: why can't we go after 
-> Differentiated Routing ?!
-> >And also: why can't we go after better routing paradigmas 
-> (with respective 
-> >algorithms) than SPF-routing ?!
-> 
-> I should think this is largely a matter of market 
-> requirement. Demonstrate 
-> a market, and we can probably design something to meet its 
-> requirements. 
-> Absent a way to turn it into money, you might have 
-> difficulty drumming up 
-> commercial interest.

---

From: "Naidu, Venkata" <[email-masked]>
Date: Mon, 22 Jul 2002 14:43:04 -0400

Fred,

  

  
--
Venkata.

---

From: Fred Baker <[email-masked]>
Date: Mon, 22 Jul 2002 12:31:40 -0700

>PS: I am speaking as an individual.

This is an IETF list. We are all individuals in this forum. Frankly, if 
your opinion would be different if you posted from a different email 
address, it's not actually your opinion, and I'm not particularly 
interested in it.

>I know that, NSIS is trying to solve signaling part of the problem. But 
>signaling follows what routing dictates. How are we going to solve the problem?

I guess my question is "please state the problem". You and Hummel would 
like for the solution to include scalable QoS routing, for some definition 
of that term, and Hummel's not happy with distributed SPF as an algorithm. 
He comments that it should be related to routing at the network layer; your 
answer suggests that it should be routing at a circuit layer, and should 
include some concept of routing (SIP) calls. What is most interesting, at 
least to me, is "please spell out the problem that this solution is 
intended to solve?"

I mentioned destination+DSCP routing. The issues that is intended to be a 
solution to come from two general categories of user requests -

         "I would like to route my voice traffic differently than my data 
traffic in a
          converged network"
and
         "My network is composed of a large number of very low bandwidth 
high delay
          facilities. I would like to use them all simultaneously to best 
advantage
          if at all possible."

Note that neither is a complaint about delays or bandwidth per se. The 
former is more a policy question - "I have specific links for that traffic 
and I want to use them". The latter might be restated "do what I mean", so 
any approach to it is likely to partially succeed and partially fail. What 
the target audience really needs to do is get more bandwidth, but it's not 
something readily done.

I'm also interested in routing that uses measured delay as a metric, in 
OSPF or BGP. The problem statement as put by a variety of companies such as 
Sockeye or NetVMG might be stated "in a multihomed situation, select the 
service provider that will give you the best round trip time on a request." 
The problem statement as put by Akamai and friends might be "select a route 
or server that will give you the highest delivery rate using TCP." But 
again, I don't see anything related to that in either your extended LSPs or 
Hummel's issues with SPF, though.

What is the problem you want to solve, that your proposal might be a 
solution to?

---

From: Fred Baker <[email-masked]>
Date: Mon, 22 Jul 2002 12:31:40 -0700

---

From: "Ayyasamy, Senthilkumar (UMKC-Student)" <[email-masked]>
Date: Mon, 22 Jul 2002 16:17:20 -0500

>Differentiated Routing would certainly stress Differentiated Services 
>and I think that the reason why it hasn't been
>introduced together with DiffServ is that IETF folks are only 
>seeing the advantages of SPF routing but not its 
>disadvantages, i.e. were therefore blocked.
I have studied something reverse in some cases
(with particular reference to premium service in diffserv)
An excerpt from a recent infcomm paper,
* Originally, the DiffServ scheme is decoupled from IP routing 
intentionally, meaning that all traffic 
between each source-destination pair follows the same path no 
matter which service class it belongs to and DiffServ itself has no
effect on IP routing decisions. Due to premium traffic’s high priority
this could lead to some problems for the low-priority traffic when the
 volume of premium class traffic is high. That is to say,without taking 
routing into consideration, the premium class traffic imposes very 
negative influences on other classes of traffic, especially when the 
network is highly loaded.*
The authors modify SPF algo for avoiding problems in diffserv networks.
http://www.ieee-infocom.org/2002/papers/675.pdf
Though the paper tries to find solution for something which have been
done already (inter-class effects are discussed in the orginal EF 
RFC itself,) the authors have come up with good algebra and routing
problem analysis in diffserv networks which will help further research
in coupling IP routing and diffserv.
 
>And also: why can't we go after better routing paradigmas (with respective >algorithms) than SPF-routing ?!
 
As said, recent interest is using OSPF metric optimization for network planning.
People tweak around OSPF weights for managing their network. Hence there 
should be a strong reason for moving from the present routing paradigm. I am 
wary of many stateful routing schemes deployment.

---

From: "Ayyasamy, Senthilkumar (UMKC-Student)" <[email-masked]>
Date: Mon, 22 Jul 2002 16:17:20 -0500

---

From: "Ayyasamy, Senthilkumar (UMKC-Student)" <[email-masked]>
Date: Mon, 22 Jul 2002 16:19:04 -0500

---

From: "Ayyasamy, Senthilkumar (UMKC-Student)" <[email-masked]>
Date: Mon, 22 Jul 2002 16:19:04 -0500

---

From: Hummel Heinrich <[email-masked]>
Date: Tue, 23 Jul 2002 15:19:09 +0200

Hi all debaters,
Thanks for this echo on my initial email yesterday evening, European time.
May I conclude that there is indeed a lot of interest in DiffRout  (if nsis exists as a WG, but
depends on Differentiated Routing (DiffRout), then we should have a diffrout WG, too:-)

Certainly, the basic idea of DiffRout is to use the DSCP-Bits, or even all 8 TOS-bits, for addressing different
Routing Tables for looking up the next hop link (you can as well have one common Routing Table but search for the right entry while using destination address AND DSCP as search keys - this is up to the programmer).
 
The big question however is, what shall the Routing Tables, inside of multiple routers and accessed by the same DSCP, represent?
My thinking is, they should implement a particular (logical) road system - next to other road systems on top of a given
physical network infrastructure.

Some of these road systems may have overlapping links. Some of them
must not have overlapping links. Some may serve different users or different services. Let me indulge in  analogies:

A road system for pedestrians comprises side-walks, sky-walks, streets, country roads, state roads, but not highways and express ways.
A road systems for cars comprises streets, country roads, state roads, highways, express ways, conditionally toll roads, but definitively no side walks and no sky walks (only in Hollywood movies).
A road system towards downtown might also have an associated overflow road system, which is a generalized form of a detour.
And even the overflow road system may have its overflow road system...
You see, some road system may even be defined based on/dependent on the existence of other road systems.

Traffic towards downtown using DSCP X may, at the rim of downtown, be redirected, by also changing DSCP X to DSCP X-overflow, if momentarily and locally available traffic load measurement data do advise so.  

We may consider a couple of  overflow road systems whereby, e.g. the forth one, is determined by disregarding the roads of the first three road systems. These four road systems may be used alternatively so that traffic is well balanced, i.e. so that overflow situations will not occur in the first place.And yet all packets of any given micro flow would use one of these four DSCPs, so that they would all take the same route.

Or consider a road system (=detour route)which is  just a single route tunnel from one road system to the other. And if a detour route between San Francisco and L.A. is associated with DSCP=5, no one would bother if another detour route road system between N.Y. and Baltimore were associated with the same DSCP=5.

We may even allocate bandwidth to some road system (and/or to its center )and may determine its links based on 
sufficiently available bandwidth (road system admission control !).

Also: If we LOCK e.g.the pedestrian traffic onto/into one road system we keep this traffic off the other road system
(and vice versa).

In summary: this is the way I look at it. And the goal should be  to develop solutions which implements such road systems:-)
What is your opinion?

Heinrich

---

From: [email-masked]
Date: Tue, 23 Jul 2002 16:11:38 +0200

Heinrich, 

you have touch a subject that I have been thinking on for awhile. It is definately of interest to explore such a system - I see directly some benefits of doing what you are talking about. However, I also see costs for implementing this, which demands very careful considerations before implementation/standardisation takes place. 

To answer Fred's question on why somebody would like to do such a thing: 
1) it allows for an ISP to have different downstream operators for different services (read quality). The current routing system does not (if I understand routing correctly) allow for this. 

I do not see the need for that short term. It is very interesting to read Clarks design philosophy paper though, and think about section 8, where he talks about service flexibility and that IP allow us to build network with vast different properties/services. Despite this understanding, I see no method by which we as ISPs can technically express the different goals that we have when building networks (be it cost or quality). This may lead to the conclusion that something is missing in the control infrastructure of IP, I don't know if this is the case.

Anyway, if all ISPs optimise for the same thing we clearly have no problem here. But if this is not the case then we may need something new in awhile. And, if Diffserv is to be the way by which we technically express different goals (quality) then it may be wise to re-explore the area of TOS/DSCP routing. But once again, I don't see this as a short term need.

2) it allows for dividing a physical network into logical parts as Heinrich pointed out. This can be used for example for load balancing and it also gives me possibilities to construct some new services that have attractive properties for me. More information on that may be given outside this list. 

I would not necessarily couple "Diffrouting" tightly with DSCP though, since DSCP (at least in my mind) controls queuing and you want to control the logical seperation of topology (ie to control routing). Some may want to do both, which leads to the conclusion that you would need an AND operation between the control of WHERE to send the packets and HOW to forward them. At least I think you would want to allow for that.

Anders

---

From: [email-masked]
Date: Tue, 23 Jul 2002 16:11:38 +0200

Heinrich, 

Anders

---

From: Hummel Heinrich <[email-masked]>
Date: Tue, 23 Jul 2002 16:55:56 +0200

Anders,
One more analogy from our daily road traffic:
DiffServ is what motor-cyclists enjoy at a red traffic light: they can jump the queue of waiting cars.
And this is really not too fancy compared with  all the other mechanisms for managing the road traffic.
DiffServ and DiffRout : How to share the codepoint ? 
DSCP for Gold service = DRCP for using all roads (i.e. incl. express ways, toll roads)
DSCP for Silver service = DRCP for using all roads except...
DSCP for Bronze service = DRCP for using country roads only unless some better road is needed for reaching the destination.

The lesser service traffic is kept off from the best roads of the better services' road systems.
I.e. service differentiation is stressed, both for the better and for the worse.  

Of course life would be easier if we wouldn't have to double the interpretation of the DSCP-bits. But
a) no ISP supports 64 different SLAs
b) see above, some of the road systems may be in compliance/in support of service differentiation.

E.g. a particular bunch of DSCPs may share some DiffServ meaning, although they addresses different road systems.

Maybe the flow label in IPv6 could be used, too. But I think these are second-degree details.

Heinrich

-----Ursprüngliche Nachricht-----
Von: [email-masked] [mailto:[email-masked]]
Gesendet: Dienstag, 23. Juli 2002 16:12
An: [email-masked]; [email-masked];
[email-masked]; [email-masked]
Cc: [email-masked]
Betreff: RE: Differentiated Routing, not only plain rambo-SPF

Heinrich, 

Anders

---

From: Hummel Heinrich <[email-masked]>
Date: Tue, 23 Jul 2002 16:55:56 +0200

Anders,

Heinrich

-----Ursprüngliche Nachricht-----
Von: [email-masked] [mailto:[email-masked]]
Gesendet: Dienstag, 23. Juli 2002 16:12
An: [email-masked]; [email-masked];

Heinrich, 

Anders

---

From: Hummel Heinrich <[email-masked]>
Date: Wed, 24 Jul 2002 10:48:48 +0200

Fred,
Don't over-esteem my phrasing. Maybe I should have written:
The next question ... instead of The big question.... 

I started this thread with the following two sentences:
In normal, state-less IP routing we cannot do QoS-Routing, nor sneak-around the congestion-area routing, nor traffic balanced routing. Instead, all of this is left to MPLS, where multiple states and multiple LSPs and multiple signalling is required.
With other words:
I try to enable QoS-Routing, "sneak-around the congestion-area" -Routing, traffic balanced -Routing. 
Without MPLS and without RSVP.Without circuits and without channels. I also pointed out that you may get for free
multicast delivery channels with voice/video quality. 

From the response I learnt that others have already tried the same, see:
http://www.ieee-infocom.org/2002/papers/675.pdf
and have even chosen the same name = Differentiated Routing. For some reasons no one knows or can remember study on
Differentiated Routing was discontinued  and different prioritization became the seul topic of DiffServ.

Furthermore, it was not me who really started this discussion. Instead it was the IESG, in Salt Lake City (I think),
that encouraged discussion on Equal-Cost Multipath and I guess, as a consequence, this routing-discussion mailing list
has been installed. But from a former admiror of ECMP I turned to opposing it. Hashing traffic according to source/destination is not the best thing. I can hardly imagine that a traffic policeman who has to balance the oncoming
traffic by sending a third to the left, a third to the middle, and a third to the right would ever get the idea 
to check the license plates of the cars, and e.g. would send those from Florida,Georgia,Nevada,.. to the left, 
those from California,Wyoming, Kansas,... to the middle, those from New York,Texas,... to the right.
What would garantee him that the chosen hashing would yield the right proportioning ? 
What if he fails ? Rearranging the three sets of US-states ? But who knows which cars may arrive later on?
I think he will never find out what are the right three sets of US-states.
Believe me, this is the poorest solution ever.

Heinrich

At 03:19 PM 7/23/2002 +0200, Hummel Heinrich wrote:
>The big question however is, what shall the Routing Tables, inside of 
>multiple routers and accessed by the same DSCP, represent?

no. The big question is "what problem are you trying to solve?" If it is a 
lack of roads/circuits/channels in IP routing, I'm not convinced that is a 
problem.

---

From: Hummel Heinrich <[email-masked]>
Date: Wed, 24 Jul 2002 10:48:48 +0200

Fred,

Heinrich

---

From: "J. Noel Chiappa" <[email-masked]>
Date: Wed, 24 Jul 2002 12:35:03 -0400

> From: Hummel Heinrich <[email-masked]>

    > In normal, state-less IP routing

You just hit one of my hot buttons.

Normal IP routing is not stateless. It has lots of state in the network.
Moreover, that state is state such that if it is not properly maintained will
cause packets not to flow. In other words, it is also critical (in the sense
of "it's right, or the communication doesn't work") state. RIP, OSPF, IS-IS,
BGP - they all maintain state, and often include extremely complex and
powerful mechanisms to ensure that that state is perfectly synchronized -
because if it isn't synchronized perfectly, and up-to-date, things will go to
hell in a handbasket. 

The way I look at routing/forwarding, information is split between two places:
the packet header, and the switches (akak routers). A combination of the two
is necessary to determine what path the packet is going to take. The
information in the header allows the switch/router to look into the
information (state) is has, and figure out what to do next.

In this high-level model, it's completely irrelevant whether the information
in the header is:

- just a destination address (in which case the paths selected are independent
	of any kind of service)
- a destination address plus some sort of service selection (be it ToS, or
	DiffServ, or whatever)
- a path selector (think ATM or MPLS)
- a loose source route
- a complete source route

although I admit that in the last one, the information in the switches is
vestigial (simply a binding between the interfaces identifiers in the packet,
and the actual interfaces).

In any routing system, the designer has to answer the following questions:

i) what kind of services do you want the user to be able to ask for;
ii) how do they ask for it (e.g. simply with bits in each packet header, or
	what);
iii) what information does this mean you have to have in the switches, and how
	does it get there.

"Classic" IP routing has a particular set of answers to these questions - and
it does involve state in the routers.

We now return you to the previous discussion...

	Noel

---

From: "J. Noel Chiappa" <[email-masked]>
Date: Wed, 24 Jul 2002 12:35:03 -0400

Noel

---

From: "Naidu, Venkata" <[email-masked]>
Date: Wed, 24 Jul 2002 14:38:05 -0400

Noel,

-> From: J. Noel Chiappa [mailto:[email-masked]]
->     > From: Hummel Heinrich <[email-masked]>
-> 
->     > In normal, state-less IP routing
-> 
-> You just hit one of my hot buttons.
-> 
-> Normal IP routing is not stateless. It has lots of state in 
-> the network.
  
  Hummel is not talking about *state* in the network.
  The information (in your words: a Header) required to 
  route packets is state-less. Routing is purely based on
  *destination* address. Isn't it?
  
-> - just a destination address (in which case the paths 
-> selected are independent of any kind of service)

This is what Hummel meant by *Classical state-less IP-Routing*

  All the below *routing schemes* are considered as
  extra states (in addition to destination address)

-> - a destination address plus some sort of service selection 
-> (be it ToS, or	DiffServ, or whatever)
-> - a path selector (think ATM or MPLS)
-> - a loose source route
-> - a complete source route

  IMO, most of the confusions in the lists are because of 
  our terminology. I have been trying to convince Fred
  about the difference and what we need to achieve based
  on *Traffic Management* and *Traffic Engineering*.
  But I failed to express in the right way.

  I know...I know that Traffic "Engineering" is for
  efficient use of network resources in SPs. Where as
  Traffic "Management" is a local decision on how a
  router must forward/queue/schedule packets to achieve
  a desired CoS QoS.

  IMHO, just using DSCP bits on per-hop won't achieve 
  QoS "Globally". You have to combine TE also.
  That "QoS using TE" has been neglected by us.
  That is what I am trying to convince Fred. 
  
  If you consider IP is a superset, MPLS, QoS and TE are
  some overlapping subsets (pictorially):

       IP Superset
       +-----------------------------------+
       |     __________    __________      |
       |    /          \  /           \    |
       |   /   MPLS     \/    QoS      \   | 
       |  /             /\              \  | 
       | |             |  |             |  | 
       | |             |  |             |  |
       | |             |  |             |  |
       | |          ___|__|___          |  |
       |  \        /    \/    \        /   |
       |   \      /     /\     \      /    |
       |    \____/_____/  \_____\____/     |
       |        |                |         |    
       |        |                |         |
       |        |                |         |
       |         \      TE      /          |
       |          \            /           |
       |           \__________/            |
       |                                   |
       +-----------------------------------+

   You can just do MPLS (for fast label look-up etc).
   You can achieve QoS using MPLS (without TE)
   You can achieve better QoS using TE (with or 
   without MPLS) etc etc...

   IMHO, the intersection of all the subsets (ie., 
   (QoS using MPLS-(DiffServ-Aware-TE) will make a 
   *real-good* impact on end-to-end performance in the 
   global Internet.
   
   I am not alleging these points here. There has been
   some research & simulation in this area. Please 
   look at an old neglected paper by Raj Jain's group: 
ftp://ftp.netlab.ohio-state.edu/pub/jain/ietf/draft-bhani-mpls-te-anal-00.tx
t
   
  Simulation & analysis in a simple topology shows:
  "..in order to benefit from traffic engineering, MPLS 
   trunks should be implemented end-to-end (first router
   to last router). If some part of the network is 
   MPLS-unaware, the benefits are reduced or eliminated."

  So, are we doing MPLS-TE end-to-end to achieve desired QoS?
  If not (I am sure we are not - we are still doing MPLS-TE
  in small areas), then what are the alternatives?

--
Venkata.

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Wed, 24 Jul 2002 15:06:25 -0400

> -----Original Message-----
> From: Naidu, Venkata [mailto:[email-masked]]

>   *destination* address. Isn't it?

But the routers must maintain state information, such as network topology (OSPF) or spanning tree (RIP). True, under default IP best-effort routing, routers do not need to maintain state information *per flow*. But in case of RSVP, they do. MPLS, per labeled path. Diffserv, per flow aggregate rather than per flow.

>   That is what I am trying to convince Fred.

In my opinion, you need TE and you need _access control_ to achieve any credible QoS, no matter what scheme you use.

>   some overlapping subsets (pictorially):

I agree with the words you say above, but not the picture. Seems to me that QoS is a hoped-for result if you implement TE, MPLS, perhaps RSVP, perhaps Diffserv, and so on. QoS is not a technique, as MPLS and TE are. It is the result of using one or possibly several techniques.

>    *real-good* impact on end-to-end performance in the 

"Real good" would have to include access control (otherwise your QoS will go to hell anytime too many flows happen at an edge node, which can easily happen without controls on access) and also constraint-based routing (otherwise, the network will be apt to block new QoS service requests just because one possible route out of many might be temporarily congested). If the network core is assumed to be so fast that none of this is a concern, then the hope is that contraint-based routing is not so essential. I think that's where many of these QoS solutions seem to go. It gets "too hard" to do a complete solution. And a complete solution starts looking oh so similar to ATM.

Bert

---

From: Hummel Heinrich <[email-masked]>
Date: Fri, 26 Jul 2002 11:47:19 +0200

Jing,
Yes, Differentiated Routing should be beneficial to both: a) service differentiation     A N D    b)  traffic balancing
(and later on, by learning from it, many other fancy services).

With ECMP however I have a lot of problems:
a) I don't like "equal-cost". Why is a little bit more costly route not suitable for becoming the 2nd or 3rd best route?
   This equal-cost goal only looks like a valuable goal, but in reality it just hides that the entire internet society is the 
   prisoner of this plain rambo-SPF routing paradigma.
b) It does not accomplish the wanted traffic load proportioning. See my email from last Wednesday. 
   No  policeman, who should balance the arriving car traffic, whould signal them which way to go based on 
   the U.S.-federal state on their car license plates.
c) Some flow/car which deserves best treatment may fall into the bad-luck hash category. So ECMP destroys DiffServ 
   intentions.

Jing wrote:
1. What's the target?
    I think the answer may be :  Differentiated service between flows + Load
balancing over networks + routing stability

HH=> Yes + Yes + Yes.
Yes to DiffServ effects: 
Better than a junction with traffic light (so that motor-cyclist can jump the queue of waiting cars)
is a ramp-based junction where the other traffic is kept out of the way. Remember I am proposing road systems
whereby you can pretty good ban some traffic onto some road system as to keep it off from others.
Yes to load balancing: 
Remember the road systems I proposed which are determined while taking into consideration the existence of previously determined road systems.
Yes to routing stability:
All the  packets of some flow come with some DSCP x and will therefore follow the same path (even if this DSCP x were
modified at some router to x-overflow for being forwarded on the x-overflow road system).  

Jing wrote:

2.  The basic method ?
   It may be :  multipath routing + DSCP based path selection  ( We do not
consider too much of CAC or the like here because we want to walk around
congestied  part of network by routing with multipath path )

HH=> to determine distinct road systems,  indexed by DSCP , implemented by the affected routers.

Jing wrote:
3. How could the overlaid network be built?
    I think this may be most difficult, as :  connection-oriented or
connectionless,  how could the path be computed, how could the path be
establised over network?
    MPLS may be a useful tool, but what about the scalability?

HH=> by deriving DSCP-x associated Routing Tables inside the affected routers.

Jing wrote:
4. Is there any confliction between  routing and  congestion control mechanism
in TCP ?
HH=> I cannot think of any at all.

Heinrich

---

From: Hummel Heinrich <[email-masked]>
Date: Fri, 26 Jul 2002 11:47:19 +0200

Jing,

Jing wrote:
1. What's the target?

HH=> Yes + Yes + Yes.
Yes to DiffServ effects: 

Jing wrote:

2.  The basic method ?

Jing wrote:

Jing wrote:

Heinrich

---

From: Hummel Heinrich <[email-masked]>
Date: Tue, 30 Jul 2002 18:43:26 +0200

Let's be concentrated again. And let me get to the heart of the matter.

Obviously I am not the only one who thought about using the DSCP also for doing Differentiated Routing.
Will say: not the only one who thought about indexing different Routing Tables by different DSCPs.

IMO, these routing tables should represent different and very distinct and differentiated road systems.
This is only possible, if they are genuine partial structures of the total network. In addition to them we still need
that "default"-road system which is identical to the entire network (e.g. in order to ping any node), i.e. today's routing tables.

As a first approach which already highlights all important aspects, let`'s consider just those "edge" nodes with attached
LANs, hosts,external interfaces. The task is to build a minimal road system between them, which suffices some well-determined
QoS/BW/Policy constraints, and which is able to lock the entire traffic between these edge nodes onto/into this road system
associated to a specific DSCP.

The graph of this minimal road system is certainly a "minimal size tree" (and not any shortest path tree with a very specific
root node). A couple of IETF meetings ago,I showed how such a tree can be constructed. At that time I was focussed on
determining a minimal partial mesh between n sites of a VPN. And the "big" gain: 10 % or 15 % less links than any shortest path tree between these n sites. In the meantime however, I realized a much bigger gain: It should be possible that 
each network node may compute the identical graph of some shortest size tree. All it takes is to apply some tie breaker rules
so that each node will compute the identical graph, even if there were several trees of smallest size.
Next:
As soon as the router has determined this graph, it checks, where is its own position relative to this graph.
If it is not touched, it won't have to derive a respective routing table. Otherwise however, it should derive one.
For deriving this routing table, the router runs the Dijkstra while taking into consideration only the links of this
smallest size tree.By doing so, it will get for each destination (prefix) what is its proper next hop link.

There will certainly be alternative road system graphs in addition to the minimal size tree graph. 
E.g. minimal rings, or even any kind of some meshy graph. Important is, that a particular road system turns out to be a "routable" road system, i.e. a road system where the edge nodes may reach each other without leaving this road system. 

A short and rough description on how to determine the shortest size tree between n edge nodes:
make n-1 iteration steps. At each step combine two partitions (of the tree). Start with n partitions of the tree whereby each
partion contains just a different edge node (not one single link). 
At each step combine those two partions which can be combined by the shortest path between any two nodes, 
whereby the one node is in this partition and the other node is in the other partition.
More iteration details later.
Before you start this iteration, you should have computed the shortest-path from any edge/core node to any edge/core node
while obeying the particular QoS/BW/Policy constraints and may store them in a kind of bin  from where you can take them
during the iteration.

I hope this explains why I look at SPF as a rambo routing protocol. Yes, SPF has its advantage. It get's you everywhere.
And also: for constructing the Smallest Size Tree, you even have to compute n Disjktra trees for filling the bin.
However, in the end, each router should determine the identical graph and look for its position rather than behave as the
center(=root) of the network.

Currently I can only see or feel how Differentiated Routing would work in an OSPF-network, and would need help and would appreciate any help to place this concept into a BGP environment, so that the road system may go somehow end-to-end.

Maybe the following is a nice comparison: there are airlines, which form alliances as to extend their flight road systems,
eventually such that you can fly end-to-end with one airline alliance. But note, you may as well travel with a different
airline alliance! Couldn't this be a business model also for ISPs ?

I hope, this get's the discussion back on its track. And away from the "what means state-less" debate - although I am grateful for any comment :-)

Heinrich

-----Ursprüngliche Nachricht-----
Von: Hummel Heinrich [mailto:[email-masked]]
Gesendet: Dienstag, 23. Juli 2002 15:19
An: 'Naidu, Venkata'; 'Fred Baker'; [email-masked]'
Cc: [email-masked]
Betreff: AW: Differentiated Routing, not only plain rambo-SPF

Hi all debaters,

Heinrich

---

From: Hummel Heinrich <[email-masked]>
Date: Tue, 30 Jul 2002 18:43:26 +0200

Heinrich

-----Ursprüngliche Nachricht-----
Von: Hummel Heinrich [mailto:[email-masked]]
Gesendet: Dienstag, 23. Juli 2002 15:19
An: 'Naidu, Venkata'; 'Fred Baker'; [email-masked]'
Cc: [email-masked]
Betreff: AW: Differentiated Routing, not only plain rambo-SPF

Hi all debaters,

Heinrich