source routing
Gene Tsudik <gts@zurich.ibm.com> Tue, 07 April 1992 15:14 UTC
Received: from nri.nri.reston.va.us by ietf.NRI.Reston.VA.US id aa00947;
7 Apr 92 11:14 EDT
Received: from nri.reston.va.us by NRI.Reston.VA.US id aa13680;
7 Apr 92 11:17 EDT
Received: from PARK-STREET.BBN.COM by NRI.Reston.VA.US id aa13676;
7 Apr 92 11:17 EDT
Received: from park-street by PARK-STREET.bbn.COM id aa03809;
7 Apr 92 10:55 EDT
Received: from BBN.COM by PARK-STREET.BBN.COM id aa03803; 7 Apr 92 10:54 EDT
Received: from [129.34.139.11] by BBN.COM id aa10480; 7 Apr 92 10:56 EDT
Received: from ZURLVM1 by zurich.ibm.com (IBM VM SMTP V2R2) with BSMTP id 1324;
Tue, 07 Apr 92 10:56:21 EDT
Date: Tue, 7 Apr 92 16:56:04 SET
From: Gene Tsudik <gts@zurich.ibm.com>
To: YACOV%YKTVMZ%zurlvm1.zurich.ibm.com@bbn.com, idpr-wg@bbn.com
Subject: source routing
Message-ID: <9204071117.aa13676@NRI.Reston.VA.US>
Yacov,
I'll try to address some of the issues you raise. Let
me first offer a disclaimer, though. I am not an
active member of the IDPR group; I haven't been one for
over a year. Draw your own conclusions...
First of all, you still did not answer my question about
source-specified forwarding. I'd like to point out that
source-specified forwarding may be implemented in a variety
of ways, including, BUT NOT LIMITED TO, source route in every
packet, or source setup (like in IDPR).
Apologies, I misinterpreted your message thinking that you referred
only to the existing IP source routing mechanism.
The ability "to switch to a parallel border
router when one of the routers specified in an LSR goes down"
assumes that there is such "parallel border router". Would
you consider to take a look at the existing Internet and
count the percentage of domain pairs that have more than
one link connecting the pair. That may give us much better
understanding of the importance of this feature.
I believe Milo Medin's message sheds some light on this subject.
Also, I think that with increasing commercialization, transit service
providers will be more likely to install "parallel" border routers.
The reason being that since the end-users (stub ADs) will be paying for
transit service, they will demand better quality of service, i.e.,
transparent re-routing of PRs to parallel paths whenever a border
router failure occurs.
With respect to only 5 AD hops restriction, I think you
are incorrect. I can certainly show you a scheme that would
let you have 9 AD hops.
I insist that my calculation was correct. Recall that I was referring to
the existing IP source routing. Sure, if you modify IP code in
border routers, you can get 9 AD hops. (I believe this can be done
if every entry border router doesn't skip over its own address in the
LSR, but, instead, overwrites it with the address of the exit border
in the same AD).
As was indicated to Tony Li, I was not presuming only the
available source routing facilities, though I was not
ruling them out either. Moreover, as Tony indicated
"there are other ways of doing source routing" that
apparently were discussed between some of the IDPR WG members.
It would be really helpful to get information on why the WG
rejected "other ways".
Do you have any data that would substantiate your assumption
that "there are many more non-border than border routers in an
average PR" ?
No. It was a conjecture on my part.
But, your question got me curious and I ran a few ad hoc tests.
The results appear at the end of this message.
Do you have any data on how much extra processing (how many
instructions) it would take to process source-route option ?
I don't have the source handy at the moment. I'll have to get back to
you on this.
-----------------------------------------------------------------------
I've run some route traces on a number of hosts around the US. The hosts
were selected more-or-less randomly (if you believe that, I got a bridge for
sale). All traces below were collected with traceroute from excalibur.usc.edu.
Hops marked with * are presumed to be non-border routers.
Each trace ends with the ratio of intra-AD (non-border) routers to border
routers. DESTINATION is not counted as a separate hop.
BITSY.MIT.EDU
-------------
traceroute to bitsy.mit.edu (18.72.0.3), 30 hops max, 40 byte packets
* 1 visa1-gw (128.125.51.254) 3 ms 3 ms 3 ms
2 losnettos-gw (128.125.1.33) 43 ms 6 ms 6 ms
3 cit-usc-gw.ln.net (130.152.128.2) 11 ms 8 ms 7 ms
4 cerfnet-cit-gw.ln.net (130.152.104.1) 122 ms 8 ms 7 ms
5 sdsc-cit.cerf.net (134.24.102.100) 12 ms 22 ms 13 ms
6 lboard-cerf.cerf.net (134.24.99.254) 13 ms 20 ms 23 ms
7 enss.sdsc.edu (132.249.32.22) 17 ms 18 ms 16 ms
8 t3-3.cnss16.t3.nsf.net (140.222.16.4) 20 ms 22 ms 22 ms
* 9 t3-0.cnss64.t3.nsf.net (140.222.64.1) 57 ms 83 ms 91 ms
* 10 t3-0.cnss72.t3.nsf.net (140.222.72.1) 243 ms 88 ms 95 ms
* 11 t3-1.cnss48.t3.nsf.net (140.222.48.2) 111 ms 189 ms 157 ms
* 12 t3-0.cnss49.t3.nsf.net (140.222.49.1) 166 ms 103 ms 102 ms
13 t3-0.enss134.t3.nsf.net (140.222.134.1) 126 ms 104 ms 105 ms
14 w91-cisco-external-ether.mit.edu (192.54.222.1) 111 ms 119 ms 107 ms
15 E40-CISCO-FDDI.MIT.EDU (18.168.0.2) 126 ms 112 ms 109 ms
16 BITSY.MIT.EDU (18.72.0.3) 116 ms 110 ms 112 ms
-------------
Ratio: 5/10
CASPER.ACA.MCC.COM
------------------
traceroute to mcc.com (128.62.1.200), 30 hops max, 40 byte packets
* 1 visa1-gw (128.125.51.254) 4 ms 3 ms 3 ms
2 losnettos-gw (128.125.1.33) 58 ms 6 ms 6 ms
3 cit-usc-gw.ln.net (130.152.128.2) 66 ms 9 ms 8 ms
4 cerfnet-cit-gw.ln.net (130.152.104.1) 20 ms 9 ms 9 ms
5 sdsc-cit.cerf.net (134.24.102.100) 24 ms 29 ms 13 ms
6 lboard-cerf.cerf.net (134.24.99.254) 14 ms 17 ms 13 ms
7 enss.sdsc.edu (132.249.32.22) 17 ms 18 ms 18 ms
8 t3-3.cnss16.t3.nsf.net (140.222.16.4) 24 ms 20 ms 21 ms
* 9 t3-0.cnss64.t3.nsf.net (140.222.64.1) 54 ms 52 ms 58 ms
* 10 t3-0.cnss65.t3.nsf.net (140.222.65.1) 53 ms 50 ms 55 ms
11 t3-0.enss139.t3.nsf.net (140.222.139.1) 51 ms 51 ms 54 ms
12 rice2-ut1.sesqui.net (128.241.3.130) 61 ms 63 ms 80 ms
* 13 UT2.sesqui.net (128.241.0.242) 68 ms 66 ms 63 ms
14 ut2-mcc.sesqui.net (128.241.0.162) 85 ms 87 ms 85 ms
15 CASPER.ACA.MCC.COM (128.62.1.200) 108 ms 83 ms 86 ms
-------------
Ratio: 4/10
MAUI.CS.UCLA.EDU
----------------
traceroute to maui.cs.ucla.edu (131.179.128.11), 30 hops max, 40 byte packets
* 1 visa1-gw (128.125.51.254) 3 ms 3 ms 3 ms
2 losnettos-gw (128.125.1.33) 55 ms 33 ms 30 ms
3 isi-usc-gw.ln.net (130.152.32.1) 47 ms 7 ms 7 ms
4 ucla-isi-gw.ln.net (130.152.64.2) 11 ms 11 ms 8 ms
5 Maui.CS.UCLA.EDU (131.179.128.11) 45 ms 9 ms 8 ms
-------------
Ratio: 1/3
IBM.COM
-------
traceroute to ibm.com (129.33.102.1), 30 hops max, 40 byte packets
* 1 visa1-gw (128.125.51.254) 3 ms 3 ms 3 ms
2 losnettos-gw (128.125.1.33) 49 ms 7 ms 5 ms
3 cit-usc-gw.ln.net (130.152.128.2) 80 ms 8 ms 12 ms
4 cerfnet-cit-gw.ln.net (130.152.104.1) 42 ms 7 ms 13 ms
5 sdsc-cit.cerf.net (134.24.102.100) 15 ms 26 ms 13 ms
6 ucop-sdsc.cerf.net (134.24.52.112) 37 ms 58 ms 38 ms
7 cerfnet.west.cix.net (149.20.2.1) 40 ms 40 ms 42 ms
8 santa-clara-cix.psi.net (149.20.3.2) 45 ms 40 ms 40 ms
9 sc.dc.pop.psi.net (38.145.48.1) 102 ms 102 ms 103 ms
* 10 dc.nyc1.pop.psi.net (38.145.32.1) 110 ms 108 ms 134 ms
* 11 nyc1.nyc2.pop.psi.net (38.145.42.1) 113 ms 107 ms 107 ms
* 12 nyc.wp.pop.psi.net (38.145.84.2) 117 ms 110 ms 112 ms
* 13 white-plains_P.lan.white-plains.pop.psi.net (38.145.216.2) 113 ms
108 ms 119 ms
14 ibm.rockefeller.pop.psi.net (38.145.151.2) 131 ms 124 ms 362 ms
15 129.34.139.254 (129.34.139.254) 122 ms 114 ms 114 ms
* 16 * * *
17 ibm.com (129.33.102.1) 241 ms 248 ms 241 ms
-------------
Ratio: 6/10
traceroute to gatech.edu (128.61.1.1), 30 hops max, 40 byte packets
* 1 visa1-gw (128.125.51.254) 3 ms 3 ms 3 ms
2 losnettos-gw (128.125.1.33) 37 ms 6 ms 7 ms
3 cit-usc-gw.ln.net (130.152.128.2) 10 ms 8 ms 16 ms
4 cerfnet-cit-gw.ln.net (130.152.104.1) 11 ms 8 ms 8 ms
5 sdsc-cit.cerf.net (134.24.102.100) 12 ms 19 ms 12 ms
6 lboard-cerf.cerf.net (134.24.99.254) 14 ms 66 ms 25 ms
7 enss.sdsc.edu (132.249.32.22) 25 ms 19 ms
8 t3-3.cnss16.t3.nsf.net (140.222.16.4) 23 ms 22 ms 20 ms
* 9 t3-0.cnss64.t3.nsf.net (140.222.64.1) 88 ms 55 ms 53 ms
* 10 t3-0.cnss72.t3.nsf.net (140.222.72.1) 83 ms 82 ms 83 ms
* 11 t3-0.cnss73.t3.nsf.net (140.222.73.1) 85 ms 86 ms 85 ms
12 t3-0.enss138.t3.nsf.net (140.222.138.1) 91 ms 105 ms 93 ms
13 rich-cisco.gatech.edu (130.207.244.1) 112 ms 97 ms 107 ms
* 14 ni-cisco.gatech.edu (130.207.252.1) 114 ms 95 ms 97 ms
15 gatech.edu (128.61.1.1) 140 ms 107 ms 107 ms
-------------
Ratio: 5/9
traceroute to berkeley.edu (128.32.133.1), 30 hops max, 40 byte packets
* 1 visa1-gw (128.125.51.254) 3 ms 3 ms 3 ms
2 losnettos-gw (128.125.1.33) 47 ms 5 ms 6 ms
3 cit-usc-gw.ln.net (130.152.128.2) 8 ms 157 ms 7 ms
4 cerfnet-cit-gw.ln.net (130.152.104.1) 8 ms 7 ms 7 ms
5 sdsc-cit.cerf.net (134.24.102.100) 22 ms 13 ms 13 ms
6 lboard-cerf.cerf.net (134.24.99.254) 14 ms 16 ms 14 ms
7 enss.sdsc.edu (132.249.32.22) 16 ms 19 ms 16 ms
8 t3-3.cnss16.t3.nsf.net (140.222.16.4) 34 ms 22 ms 37 ms
* 9 t3-2.cnss8.t3.nsf.net (140.222.8.3) 31 ms 35 ms 32 ms
* 10 t3-0.cnss9.t3.nsf.net (140.222.9.1) 33 ms 255 ms 32 ms
11 t3-0.enss128.t3.nsf.net (140.222.128.1) 37 ms 35 ms 34 ms
12 SU1.BARRNET.NET (131.119.254.5) 42 ms 36 ms 39 ms
13 UCB2.BARRNET.NET (131.119.2.4) 55 ms 54 ms 41 ms
14 inr-22-dmz.Berkeley.EDU (192.31.161.22) 75 ms 53 ms 46 ms
* 15 inr-35.Berkeley.EDU (128.32.168.35) 50 ms 55 ms 61 ms
16 ucbvax.Berkeley.EDU (128.32.133.1) 53 ms 51 ms 48 ms
-------------
Ratio: 4/11
The results show that my conjecture was incorrect. Border routers
outnumber non-border routers approx. 2 to 1 (on the avg).
- source routing Gene Tsudik