AW: Differentiated Routing, not only plain rambo-SPF

Let me repeat:
With SPF each node computes its individual tree towards all the other nodes. The sum of all these (n) trees
will most likely cover the entire network. Some may see this advantageous (traffic is distributed all over the network).
However by "DiffRout" as I like to advocat some traffic can be locked into ONE particular slim tree of links (e.g. the smallest size tree), and having several such slim trees (= road systems), which are constructed in awareness of
each other, and which may even have assigned bandwidth, much better control of the traffic/network can be executed.

Because you mention NP-hardness:
The algorithm I showed last week is very fast and doesn't constitute any performance problem.
BTW: I can likewise provide an (yes, heuristic) algorithm (no, four of them)as to build a list of links which form a ring 
(instead of the smallest size tree) and would interconnect n edge nodes by n links. 
Even for n= 200 (as I did for draft-hummel-n-square-investigations-00.txt) it only takes one or two seconds 
computation time.
Note, it is this notorious traveling salesman problem.To find the absolute best link sequence of the ring
it would take 10**80 years computation time, given that one particular link arrangement can be 
checked within 1 micro-second. 

Heinrich

-----Ursprüngliche Nachricht-----
Von: Ayyasamy, Senthilkumar (UMKC-Student) [mailto:[email protected]]
Gesendet: Montag, 5. August 2002 12:03
An: Hummel Heinrich
Cc: [email protected]; [email protected]; [email protected];
[email protected]; [email protected]
Betreff: RE: Differentiated Routing, not only plain rambo-SPF


-- Hummel Heinrich <[email protected]> 
wrote: > From  [MPLS-OPS]: MPLS Debacle back to
> [routing-discussion]:Differentiated Routing, not
> only plain rambo-SPF
>  
> 
> Senthil,
> This email of yours as well as your previous one
> only confirms my statement, that
> the entire Internet community  (or at least you and
> some others) is the prisoner of this rambo-SPF
> routing algorithm.
> All the protocols you have enlisted (...,BW
> inversion SP,...PNNI,..) and let me also add
> the reverse SPF in some multicast models, share this
> egocentric  SPF view.

> I am    N O T     talking just another brand of
> rambo-SPF.

My .02$:

1. The diffserv architecture, as of now, defines only 
the data plane work.  control plane activities( routing,
signaling etc)  are still open questions. 
 My argument is contradictory to what you suggest:
An effective load balancing in diffserv can be done 
by taking SPF algo into consideration. The NP-hardness 
in the existing *routing problem* formulations can be 
be approximated to polynomial time effectively by taking
both diffserv and SPF into consideration(as paths are 
predictable in a diffserv domain. )
 Most of the current routing problems formulations 
are solved by means of heuristic methods. But one can 
approximate to polynomial time by taking both SPF and 
diffserv into consideration.

Note: I am just tossing an idea. I will update you 
all once i get some good results.

2.[ some diffrout def from the discussion]

*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).*

*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.*

*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*   

Do me a favor. Replace the term  *DSCP* with 
*CoS* and *Diffserv* with *MPLS * in the above 
definition, you can call your new routing
scheme as *multi-protocol routing*. 
( humorous aside: Tips from a networking insider 
http://www.cs.ucsd.edu/~savage/papers/OO01.pdf :-) )

Thus said, coming with a new scheme is not a big task,
problem space and applicability statement is very 
important.

Read *An Overview of the New Routing Algorithm for 
the ARPANET, J. M. McQuillan, I. Richter, E. C. Rosen 
(Proc. Sixth Data Comm.Symposium, November 1979)*
http://www.acm.org/sigcomm/ccr/archive/1995/jan95/ccr-9501-mcquilln.pdf 

The above work marked the begining of transition from 
the old ARPANET distributed routing algorithms to 
SPF. The authors start with the *problems with the 
original algorithm*, then *need for SPF* and convinces 
the network floks that *SPF is just an increment to 
the original algorithm*. 

I am not asking you to formulate diffrout as an increment 
to SPF but just enlighten us *problem* and *need* of 
diffrout.

- Senthil.


> 
> Also, it wouldn't be helpful to follow your advice
> (come up with requirements, application
> statements,...)
> because if I did you would read all of it with your
> SPF-centric view in mind. You even do so now, after
> I have explained how each router may aquire the
> identical view of some road system.
> 
> Another analogy: 
> When you fly to some meeting place, you may get a
> flyer-map at the hotel concierge. The flyer-maps may
> be the same
> no matter at which hotel you stay. But, eventually,
> they have a different "You are Here" markation
> depending on
> the specific hotel. I am looking at the propagated
> road systems by a commonly shared view first, then I
> respect the
> different "you are here" markation. Rambo-SPF
> however means:"I am here.I see the world only from
> my point of view."
> Taking into consideration any kind of constraints
> and whichever weights doesn't change anything of
> this egocentric
> view + behavior with all its disadvantages.
> 
> 
> Heinrich
> 
> -----Ursprüngliche Nachricht-----
> Von: senthil ayyasamy [mailto:[email protected]]
> Gesendet: Samstag, 3. August 2002 09:40
> An: venumadhav josyula; Hummel Heinrich;
> '[email protected]';
> [email protected]
> Cc: Andrew Walding; [email protected];
> [email protected]
> Betreff: Re: AW: [MPLS-OPS]: MPLS Debacle
> 
> 
> 
> > See how many
> > QoS
> > > routing schemes were proposed, researched and
> not
> > > deployed. See what is the problem with those
> > routing
> > > Variants and then suggest differential routing
> > > Scheme.
> > >
> > Ok tell me why would not such a scheme work?
> Where I mentioned  *differential routing* wont
> work. Proposing new ideas are always easy. Let me 
> illustrate with an example.
> 
> SPF+ variants of SP algo (widest SP, shortest widest
> bandwidth path, bw inversion SP, ...)+ optimal
> multipath+source routing+ loose source routing+
> explicit paths (MPLS)+ k-shortest path and its
> variants+QoS routing( load sensitive,delay
> sensitive,
> single metric based,multi-metric based) +OSPF
> extensions+ all dynamic routing schemes as mentioned
> 
> in Ash book+PNNI + all frame relay and other type of
> routing+ MPLS based (constrianed or whatever)+
> overlay
> based routing+ onion routing+hot potato+ cold potato
> routing+...
> 
> I have listed a *few* unicast routing schemes. I can
> list more routing Schemes taking multicast, any cast
> into picture... leave alone ad-hoc, host mobility,
> network mobility, topology independent ...so on..
> 
> Most of the above routing schemes are subsets of
> some
> of the listed schemes. So suggesting a new routing
> scheme is not a big work. Using a simple combination
> and taking  some new technologies into picture, one
> can come up with a new routing scheme. But frankly
> that's not a correct approach for any protocol
> developed in IETF.
> 
> You should exactly come up with:
> - Requirements
> - Applicability statement
> - What problems the current schemes did not solve
> which lead you to suggest the present routing
> scheme.
> - What is the over-head when compared to the other
> existing technologies??? Usegood simulation to prove
> them.
> - A theoretical model to prove its use by means of
> routing problem formulations
> - Some case studies.
> - Study their properties (scalability, flexibility
> and
> extendibility.)
> - What all places it is most useful or waste
> (inter-domain or intra-domain)
> - Does it conform with the architectural principle
> (this is important: e.g.. Scalability alone is not
> the
> reason for intserv non-usage. It did not work within
> boundaries (AS.) alone.It can transcend an
> autonomous
> system boundary and so policy cannot be maintained.
> Hence, it did not support the business models well.)
> 
> 
> Now come to IETF. Give an engineering perspective to
> your routing scheme. Convince vendors to implement
> your routing scheme.
> 
> It is sometimes unfortunate that people just come up
> with some X routing scheme and try to convince
> engineering folks. Some of the IETF works was just
> proposals and hence did not succeed or gave problems
> at the later stage. So do all the above work for
> your
> new scheme and then everyone will accept your
> proposal.
> 
> Read the below book on how well the author approach
> such new schemes. 
>  *G. R. Ash. Dynamic Routing in Telecommunications
> Networks. McGraw Hill, New York, 1998*
> This is the book, which introduced dynamic routing
> schemes. It is not just bunch of ideas but has a
> in-depth analysis of requirements and theory.
> 
> 
> > CSPF (Constraint based shortest path) which is a
> > kind
> > of differential routing. I have some discussion in
> > this thread itself on that respect. 
> > Constraint based routing is modification of
> shortest
> > path alo to account for contraints such as (BW ,
> > QOS,
> > policy). 
> 
> I accept this scheme. There are simulation and
> mathematical work to see its behavior. But what it
> lacks is *deployment* which we cannot help.
> There might be lot of operational and business
> policy
> factors associated.
> 
> > CSPF solution is quite popular many are
> implementing
> > it , but I am not sure deployment and
> > interoperatablity concerns......... CSPF answers
> QOS
> > routing concerns (correct if i am wrong). It is
> not
> > the all of the mechanims proposed are
> failure.......
> 
> Note: I could not resist and hence replied. But if
> your care to respond to this mail, reply to general
> routing discussion than MPLS list.
>