Let me resend this email and correct a stupid tiny error w.r.t. the "smallest size tunnel tree" algorithm.
However, the error highlights an important aspect: For building this tunnel tree, you have to combine two partitions
by means of an entire tunnel between some two VPN-sites which are tunnel endpoints.
No split in the middle of a tunnel will occur.
Where as:
For building a "smallest size tree" - road system
you have to combine two partitions by means of ANY route between these partitions.
Eventually, one or two completely new branch nodes may be generated at this, at that, or at both partitions.
I will mark the change with CHANGE***CHANGE and END OF CHANGE*** END OF CHANGE in the text.
Heinrich
-----Ursprščngliche Nachricht-----
Von: Hummel Heinrich [mailto:Heinrich.Hummel@icn.siemens.de]
Gesendet: Freitag, 2. August 2002 13:53
An: 'jshen@cad.zju.edu.cn'
Cc: Venkata.Naidu@Marconi.com; jnc@ginger.lcs.mit.edu; fred@cisco.com; saq66@umkc.edu; irtf-rr@puck.nether.net; routing-discussion@ietf.org
Betreff: AW: Differentiated Routing, not only plain rambo-SPF
Hi Jing,
Find my comments inserted.
Regards
Heinrich
1) if we want to route with DSCP it should be desired that logical views of network based on each possible
DSCP is computed ?
HH=>
Yes, this is feasable. IMO, the alternative, that each link advertises all the DSCPs i.e. all the road systems
it wants to be a part of, is not good eenough for two reasons:
1) Only by computation we can make sure that each road system is "routable", i.e. enables road system
internal transport between a particular set of edge routers.
2) Some road systems are just the overflow-/2nd-best-route, 3rd-best-route road systems w.r.t. another
road system. This cannot be assured without computation.
2.) Each router builds up a seperate routing table for each possible DSCP , and there exist a default routing table
for packets whose DSCP are not set ?
HH=>
Differentiated road systems only make sense, when each of them uses only a part of the network links. A smallest
size tree between a confined set of edge routers would yield such a "slim" road system.
If all your nodes are leaf nodes, then there is no difference between a shortest path tree and a smallest size tree.
But on the other side, it still must be possible to send a packet from any edge or core router to any edge or core
router. I.e. we still need the exisiting best-effort road system. As long as you have only one road system you
won't have to mark it. But as soon as there is a second one, you have to mark not only the second one
but also the first one. Will say you need one DSCP for traffic which shall be forwarded according to the current
routing tables.
3.) When a new packet arrives, the dispatching logic may look like :
Procedure DSCP_BASED_DISPATCH ( incoming_packet )
if DSCP then
if ( DSCP-related-table-exist )
running-table = DSCP-related-table;
if running-table==NULL
running-table = default-table;
out_port= find_routing_item( incoming_packet);
enqueue(out_port, incoming_packet);
END PROCEDURE
HH=>
Yes. I see, you already addresses the case where a packet is forwarded NOT as it should, i.e. not within the respective
road system. Of course, this needs to be covered, too. And yes, as you describe, by using the default (best effort) road system.
But, How could the logical view be computed? DSCP is just for queueing mechanism, should that be included in LSA?
HH=> Life would be easier, if we had more available bits (we still have 2 CU currently unused Bits). But we don't have
64 Service Level Agreements either. It should be possible to satisfy DiffServ as well as DiffRout :-)
And, I think there may other problem as extensiblility and stability.
HH=> Sure. But compare it with DiffServ. DiffServ wasn't done either by one single draft and by one single IETF meeting session.
And,the last , I'm not so clear about the method computing shortest size tree, and I'm very interested in your work of
minimal partial mesh between n sites of a VPN. Would you please give a little more word or some reference sites ?
HH=>
The idea was to interconnect n sites (PEs or CEs) by a minimal partial mesh of tunnels.It could only be a tree of
n-1 tunnels. And well, a tree of those "shortest" tunnels, which nevertheless interconnect all n sites. In principle,
it is a selection process as to sort out n-1 tunnels from n(n-1)/2 candidate tunnels.Thereafter, add those n-1
tunnels which are inverse to the selected n-1 tunnels.
Preparation: Compute n Dijkstra-trees whereby each time another site-node becomes the root.As a result you have the best route from any
CHANGE***CHANGE
site node to any site node. Here we can ignore those routes which do not start or end at a site node.
END OF CHANGE *** END OF CHANGE
You may sort all of these n(n-1) routes according to their
weight sums in ascending order.And you may associate a REGARD/DISREGARD-Bit to each of these routes (for speeding up the algorithm). Initially set all these Bits to REGARD=1.
Iteration:
As I told already, start out with n (separated) partitions, whereby initially each partition
just contains one site-node (no links yet). Also the initial set of tunnels, which finally shall become the
VPN PARTIAL MESH,is empty.
Make n-1 iteration steps.
At each iteration step, determine those two partitions, which can be combined by the shortest route(=tunnel)
among all those routes which are marked REGARD.
Combine the two partitions (logically), but in reality do this:
Add this determined shortest route/tunnel to VPN PARTIAL MESH. Set the REGARD/DISREGARD-Bit to DISREGARD=0 for all
those routes, which are "internal" to this combined partition. Note: this includes this shortest route/tunnel.
Precisely set the bit to DISREGARD for all those routes, wherebe the route started at a node from the one partition
and ended at a node from the other partition.
Do this n-1 times.
So far this was all about forming a "minimal size tunnel tree".
Only slightly different would be the algorithm for building what I used to call a "minimal size multicast tree",
which extends between the sender node and the receiver nodes.
Preparation:
Compute Dijkstra-trees as many as you have nodes in your network (edge as well as core nodes).
(So you also know the shortest route between any two core nodes as well).Hereby, each time another
node is the root node.
Like above, sort all these routes according to the ascending order of their weight sums, assign a REGARD/DISREGARD-Bit
to each of them, and initialize all these bits to REGARD=1.
Iteration:
Start with an empty set of routes, called MULTICAST TREE, and with N partitions whereby each partition would only contain one
sender resp. receiver node initially ( for building a road system it would be any edge router
with attached LAN, Host, ext.interface).
At each iteration step, determine those two partitions, which can be combined by the shortest route between any
node in one partition and any node in another partition. Hereby consider only those routes which are still marked REGARD.
Combine the two partitions (logically), but in reality do this:
Add this determined shortest route to MULTICAST TREE. Set the REGARD/DISREGARD-Bit to DISREGARD=0 for all
those routes, which are "internal" to this combined partition. Note: this includes the determined shortest route.
Precisely, set the bit to DISREGARD for all those routes, wherebe the route started at a node from the one partition
and ended at a node from the other partition.
Do this n-1 times.
As a result MULTICAST TREE will contain a list of routes (which are lists of links/nodes).
Or you may look at it in this way: MULTICAST TREE contains a list of links/nodes (which, by chance form a tree graph with
no special (root) node at all).
Take this list of links/nodes as your "basis network topology". And which ever node is part of it may run the most primitive
Dijkstra, i.e. whereby each link-weight is equal to 1, as to compute a tree which spans this tree-topology :-).
By doing so, that node will find out the right adjacent next-hop link with respect to each
LAN/Host/ext.interface reachability prefix, i.e. can build a respective routing table.
Let's rename MULTICAST TREE to ROAD SYSTEM-for-DSCP "xyz".
It is very important that each node which is part of ROAD SYSTEM-for-DSCP "xyz", has computed the identical set of
links. This means, when, during the iteration, a particular shortest route between some separate partitions is computed,
it must be done in an unambiguous way - yes, even if there were several equally shortest routes.Tie breaker rules
will be needed.
> 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.
>
[snip]
-- Jing ShenState Key Lab of CAD&CG ZheJiang University(YuQuan) HangZhou, Z.J. 310027 P.R.China
Tel: +86-571-87932423
Email: jshen@cad.zju.edu.cn
********************************************************************** * The SunShine of life is made up of very little beams which is * * bright all the time * **********************************************************************
_______________________________________________ routing-discussion mailing list routing-discussion@ietf.org https://www1.ietf.org/mailman/listinfo/routing-discussion
This archive was generated by hypermail 2b29 : Mon Aug 04 2003 - 04:10:04 EDT