AW: Differentiated Routing, not only plain rambo-SPF

Find my lines inserted
Heinrich

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


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

Ok. Understood. Let us discuss without taking problem space 
and applicability statement factors ( as you dont have one.)

1. The diffserv architecture does not assume anything about
routing stability. I am not sure, but the original designers
should have assumed that *routing system should be stable for 
a predictable functioning of diffserv components*. So, in a 
*EXTREMELY* congested network, all queuing and scheduling 
mechanisms may show some anomalous behaviour ( I am not sure 
again.)

How will diffrout help in such a situation. I dont think
you can do some sort of routing based on DSCP at that point.

HH=> a) With respect to a particular road system X , you may determine a respective overflow road system X-overflow.
        E.g. you may determine by computation the cernel of a smallest size tree being that set of links
        which are used by at least y  s/d-traffic combinations, whereby n < y < n*(n-1); y be a fixed assigned number.
        You may recompute the smallest size tree, but before, you want to mark all the cernel links to DISREGARD.
        Traffic which is about to enter the cernel of X, may be forwarded via X-overflow while changing the
        receive DSCP-x to DSCP-x-overflow. The decission to do so may be based on a currently available traffic load/
        traffic metering information.

      b) Or you generate road systems X0, X1, X2, X3 such that the links of Xi, avoid overlaps with links of Xj, j<i.
         One micro flow uses DSCP x0, the next one DSCP x1,... as to balance the traffic and as to avoid congestion
         in the first place.    
 


2. DSCP is actually for classification (queueing mechanism.)
Can you just explain the gap between *DSCP as used for 
classification* and *DSCP as used for routing*? Remember, 
you are using DSCP both for data plane and control plane 
work here.

HH=> I am sure that DSCP codepoints can be selected such that the DiffServ and DiffRout aspects can be supported.
     After all, DiffRout will help DiffServ to avoid anomalous behaviour in the first place. 


I am also sceptical of the following issues:

- scalability: Since you are maintaining multiple Routing
tables, doing at line rate is pretty difficult and hence
doesnt scale well.

- complexity: This work increases the complexity at per 
router level. Some people complain of increase in complexity 
for just adding three more lines in the original forwaring algo
(to include RED features.) I dont know  how much complex
the router becomes because of diffrout.

HH:> There is never a free lunch. But what are a view routing tables compared to the probably much bigger number
of p2p LSPs?

- end to end: Diffserv is defined only for edge to edge. How will 
diffrout behave when considering end to end is still open.

HH=> Help me. I am open:-)


> The algorithm I showed last week is very fast and doesn't 
> constitute any performance problem.

How are you justifying that it doesn't consitute any performance
problems. Do you have any mathematically tractable model or 
simulation work?

HH=> All I have is this C++-program, written by some students, which I have used already several times
     as to show once this aspect, once that aspect, especially w.r.t. tunneling.

Let me suggest you a method for going about your analysis:

1. Formulate  diffrout as a *diffserv routing problem* with 
all possible constraints. prove them to be NP-hard and if possible
find some heuristic results ( genetic algo based or local search
one). 
Refer *http://www.research.att.com/~jrex/papers/ieeecomm02.long.pdf*

I did explain how to determine that set of links, which forms a tree between some edge nodes.
I mentioned that you have to run Dijkstra n times as to make some preparation. If you hereby apply all
the constraints as well as the specific weights you like to be considered, then the resulting
smallest size tree will suffice them, too.
 
2. Define QoS compuatation algebra for your work. 
Refer *http://citeseer.nj.nec.com/sobrinho01algebra.html*

HH=> Do I have to ? Remember, it is August and time to go on vacation :-)

3. If heuritic method is not feasible, go for some approximation
methods and prove using some theoretical results. Then support your 
performance claims with some simulation results.

HH=> If there is enough interest, I would be happy to show this C++-program on work. 
     As I said, it is not yet enhanced with tie breaker rules. But that would be very important as to
     determine the same identical smallest size tree determined b whichever node. If this failed we would
     have to continue with rambo-SPF:-)

If you do all this, I will accept that your algorithm doesn't 
consititute any performance problem.

HH=> No problem. Be sure, it doesn't run 10**80 years :-)